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

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

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