2019電大數(shù)據(jù)結(jié)構(gòu)形考作業(yè)4

1、1.對線性表進(jìn)行二分查找時(shí)，要求線性表必須（ ）。選擇一項(xiàng)：B. 以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序2.采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（ ）。選擇一項(xiàng)：D. (n+1)/23.有一個(gè)長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。選擇一項(xiàng)：C. 29/104.已知一個(gè)有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55需要比較（ ）次。選擇一項(xiàng)：C. 55.有數(shù)據(jù)53,30,37,12,45,24,96，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（ ）。選擇一

2、項(xiàng)：B. 37,24,12,30,53,45,966.對于順序存儲(chǔ)的有序表5,12,20,26,37,42,46,50,64，若采用折半查找，則查找元素26的比較次數(shù)是（ ）。選擇一項(xiàng)：A. 47.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（ ）。選擇一項(xiàng)：C. 直接選擇排序8.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（ ）。選擇一項(xiàng)：C. 插入排序9.依次將每兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（ ）。選擇一項(xiàng)：C. 歸并排序10.當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（ ）。選擇一項(xiàng)

3、：A. 交換排序11.每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（ ）。選擇一項(xiàng)：C. 快速排序12.一組記錄的關(guān)鍵字序列為（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。選擇一項(xiàng)：B.40，20,30,38，46，56，79，84,90,11013.在有序表10,14，34，43，47，64，75，80，90中，用折半查找法查找值80時(shí)，經(jīng)（ ）次比較后查找成功。選擇一項(xiàng)：C. 314.對序列（4

4、9，38，65，97，76，13，47，50）采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47插入到已排序中，為尋找插入的合適位置需要進(jìn)行（ ）次元素間的比較。選擇一項(xiàng)：C. 515.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。選擇一項(xiàng)：A. 選擇16.一組記錄的關(guān)鍵字序列為（26，59，36，18，20，25），利用堆排序的方法建立的初始小根堆為（ ）。選擇一項(xiàng)：C. 18，20，25，59，26，3617.一組記錄的關(guān)鍵字序列為（25，48，16，35，79，82，23，40，36，72），其中，含有5個(gè)長度為2的有序表，按歸并排序的

5、方法對該序列進(jìn)行一趟歸并后的結(jié)果為（ ）。選擇一項(xiàng)：A. 16，25，35，48，23，40，79，82，36，7218.已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（ ）。選擇一項(xiàng)：D. 28，16，34，54，62，73，60，26，43，9519.一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。選擇一項(xiàng)：C. 40，38，46，56，79，8420.一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序

6、（堆頂元素是最小元素）的方法建立的初始堆為（ ）。選擇一項(xiàng)：A. 39，46，41，57，80，472、 程序填空題（每題10分，2題，共20分。請點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上） 以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格typedef struct Bnode int key;struct Bnode *left;struct Bnode *right; Bnode;Bnode*BSearch(Bnode *bt, int k)/* bt用于接收二叉排序樹

7、的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/ Bnode *p;if(bt=空白)return (bt);p=bt;while(p-key!=空白) if(kkey) 空白;else空白; if(p=NULL) break; return(空白;1）NULL（2）k（3）p=p-left（4）p=p-right（5）p22.以下程序是折半插入排序的算法 設(shè)待排序的記錄序列存放在a1,an中，以a0作為輔助工作單元，程序是要把a(bǔ)i 插入到已經(jīng)有序的序列a1,ai-1中。void binsort (NODE a ,int n) int x,i,j,s,k,m;for （i=2；i=空白;i+） a

8、0=ai;x= ai.key;s=1;j=i-1;while (s=j) m=空白if( x=j+1;k- -) 空白=ak;aj+1=a0;(1)n(2)(s+j)/2;(3)j=m-1;(4)s=m+1;(5)ak+1（1）設(shè)查找表為(1,10,11,14,23,27,29,55,68) ，畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹，為了成功查找到元素14,需要依次與元素回答進(jìn)行比較。 C. 23,10,11,14 （2）在等概率條件下，成功查找的平均比較次數(shù)為回答。 B. 25 /9 （1）一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），利用堆排序的方法建立的初始堆為回答（

9、堆頂元素是最小元素,采用樹的形式建堆）。 B.39,41,46,80,47,57 （2）輸出堆頂元素后,調(diào)整后的堆為回答。 A.41,47,46,80,57 （1）對關(guān)鍵字序列(56,51,71,54,46,106),利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為回答；C.46,51,54,56,71,106 （2）一組記錄的關(guān)鍵字序列為（ 60,47，80，57， 39，41，46,30），利用歸并排序的方法,經(jīng)過(2,2)歸并的結(jié)果序列為回答。.D. (47, 57, 60, 80, 30,39,41,46 ) （1）對關(guān)鍵字序列(36,69,46,28,30,74)采用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果序列為回答 D.30，28，36，46，69，74 （2）用冒泡法對上述序列排序,經(jīng)兩趟冒泡的結(jié)果序列為回答。 A. 36,2