國開電大數(shù)據(jù)結(jié)構(gòu)(本)形考作業(yè)4參考答案

國開電大數(shù)據(jù)結(jié)構(gòu)(本)形考作業(yè)4參考答案

1.對于二分查找，要求線性表必須以順序存儲方式，并且數(shù)據(jù)元素有序。2.在采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為(n+1)/2。3.對于一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為29/10。4.已知一個有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較5次。5.對于數(shù)據(jù){53,30,37,12,45,24,96}，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是37,24,12,30,53,45,96。6.對于順序存儲的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，則查找元素26的比較次數(shù)是4次。7.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是直接選擇排序。8.插入排序是一種將未排序序列中的元素依次取出與已經(jīng)排好序的序列中的元素作比較，將其放入已排序序列的正確位置上的排序方法。9.歸并排序是一種依次將每兩個相鄰的有序表合并成一個有序表的排序方法。10.交換排序是一種當(dāng)兩個元素出現(xiàn)逆序的時候就交換位置的排序方法。{if(k<p->key)p=p->left;elseif(k>p->key)p=p->right;elsereturn(p);}return(NULL);}【答案】：(NULL)，(p->key)題目26.(1)對關(guān)鍵字序列(36,69,46,28,30,74)采用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果序列為正確答案：C.28，30，46，36，69，74改寫后：對關(guān)鍵字序列(36,69,46,28,30,74)進(jìn)行快速排序，以第一個關(guān)鍵字36為分割元素，經(jīng)過一次劃分后的結(jié)果序列為28，30，46，36，69，74。(2)用冒泡法對上述序列排序，經(jīng)兩趟冒泡的結(jié)果序列為正確答案：A.36,28,30,46,69,74改寫后：用冒泡法對關(guān)鍵字序列(36,69,46,28,30,74)進(jìn)行排序，經(jīng)過兩趟冒泡的結(jié)果序列為36,28,30,46,69,74。題目27.(1)一組記錄的關(guān)鍵字序列為{45，40，65，43，35，95}，寫出利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為正確答案：C.354043456595改寫后：對關(guān)鍵字序列{45，40，65，43，35，95}進(jìn)行快速排序，以第一個記錄45為基準(zhǔn)得到的一趟劃分的結(jié)果為354043456595。(2)對上述序列利用直接插入排序，逐次插入過程中，共進(jìn)行了次元素間的比較。正確答案：B.11