數(shù)據(jù)結(jié)構(gòu)(C語言版)第補(bǔ)考復(fù)習(xí)題

1、 數(shù)據(jù)結(jié)構(gòu)補(bǔ)考復(fù)習(xí)題數(shù)據(jù)結(jié)構(gòu)補(bǔ)考復(fù)習(xí)題 * * * * *紅色題號的題為基本要求題紅色題號的題為基本要求題* 2004.10 一、選擇題一、選擇題 .在一個長度為在一個長度為n的順序表中，向第的順序表中，向第i個元素個元素(1in+1)之前插入之前插入一個新元素時，需向后移動一個新元素時，需向后移動 B 個元素。個元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一個具有在一個具有n個單元的順序棧中，假定以地址低端作為棧底，個單元的順序棧中，假定以地址低端作為棧底，以以top作為棧頂指針，作為棧頂指針， 則當(dāng)做退棧處理時，則當(dāng)做退棧處理時，top變化為變化為 C 。 A.

2、 top不變不變 . top -n C. toptop-1 D. top=top+1 .若進(jìn)棧序列為若進(jìn)棧序列為1,2,3,4,進(jìn)棧過程中可以出棧，則進(jìn)棧過程中可以出棧，則 C 不可能是不可能是一個出棧序列。一個出棧序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 .在具有在具有n個單元的順序存儲的循環(huán)隊列中，假定個單元的順序存儲的循環(huán)隊列中，假定front和和rear分分別為隊首指針和隊尾指針，則判斷隊滿的條件是別為隊首指針和隊尾指針，則判斷隊滿的條件是 D 。 A. rear % n= =front B. (rear-1) % n= =fron

3、t C. (rear-1) % n= =rear D. (rear+1) % n= =frontP24P46P44P64 9.在一個單鏈表中，已知在一個單鏈表中，已知*q結(jié)點(diǎn)是結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和和*p之間插入之間插入*s結(jié)點(diǎn)，結(jié)點(diǎn)， 則執(zhí)行則執(zhí)行 C 。 A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p; C. q-next=s; s-next=p; D. p-next=s; s-next=q; 10.向一個棧項(xiàng)指針為向一個棧項(xiàng)指針為hs的鏈棧中插入一個的鏈棧中插入一個*s結(jié)點(diǎn)時，則執(zhí)行結(jié)點(diǎn)時，則

4、執(zhí)行 C 。 A. hs-next=s; B. s-next=hs-next; hs-next=s; C. s-next=hs；hs=s; D. s-next=hs; hs=hs-next; 11.在一個鏈隊列中，假定在一個鏈隊列中，假定front和和rear分別為隊首指針和隊尾分別為隊首指針和隊尾指針，則進(jìn)行插入指針，則進(jìn)行插入*s結(jié)點(diǎn)的操作時應(yīng)執(zhí)行結(jié)點(diǎn)的操作時應(yīng)執(zhí)行 B 。 A. front-next=s; front=s; B. rear-next=s; rear=s; C. front=front-next; D. front=rear-next; 14.線性表采用鏈?zhǔn)酱鎯r，其地址線

5、性表采用鏈?zhǔn)酱鎯r，其地址 D 。 A. 必須是連續(xù)的必須是連續(xù)的 B. 部分地址必須是連續(xù)的部分地址必須是連續(xù)的 C. 一定是不連續(xù)的一定是不連續(xù)的 D. 連續(xù)與否均可以連續(xù)與否均可以P29P47P62P27 15.設(shè)單鏈表中指針設(shè)單鏈表中指針p指著結(jié)點(diǎn)指著結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閿?shù)據(jù)域?yàn)閙)，指針，指針f指著將要插指著將要插入的新結(jié)點(diǎn)入的新結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閿?shù)據(jù)域?yàn)閤)，當(dāng)，當(dāng)x插在結(jié)點(diǎn)插在結(jié)點(diǎn)m之后時，只要先修改之后時，只要先修改 B 后修改后修改p-link=f即可。即可。 A. f-link=p; B. f-link=p-link; C. p-link=f-link; D. f=nil; 16.在

6、雙向鏈表存儲結(jié)構(gòu)中，刪除在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時需修改指針?biāo)傅慕Y(jié)點(diǎn)時需修改指針 B 。 A. (p-rlink) -rlink) -link=p; p-rlink=(p-rlink) -rlink; B. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; C. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p; D. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; 17.在雙向鏈表存儲結(jié)構(gòu)中，刪除在雙向鏈表存

7、儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時需修改指針存在）時需修改指針 A 。 A. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; B. (p-rlink) -rlink) -llink=p; p-rlink=(p-rlink) -rlink; C. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; D. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p;P29P36P36 20.二分法查找二分

8、法查找 A 存儲結(jié)構(gòu)。存儲結(jié)構(gòu)。 A. 只適用于順序只適用于順序 B. 只適用于鏈?zhǔn)街贿m用于鏈?zhǔn)?C. 既適用于順序也適用于鏈?zhǔn)郊冗m用于順序也適用于鏈?zhǔn)?D. 既不適合于順序也不適合于鏈?zhǔn)郊炔贿m合于順序也不適合于鏈?zhǔn)?21.在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上置上 B 。 A. 一定相鄰一定相鄰 B. 不一定相鄰不一定相鄰 C. 有時相鄰有時相鄰 22.設(shè)字符串設(shè)字符串s1=abcdefg,s2=pqrst，則運(yùn)算，則運(yùn)算 s=concat(sub(s1,2,len(s2),sub(s1,len(s2),2)后串值為后串值為

9、D 。 A. bcdef B. bcdefg C. bcpqrst D. bcdefef 23.假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個，單分支結(jié)點(diǎn)個，單分支結(jié)點(diǎn)數(shù)為數(shù)為32個，則葉子結(jié)點(diǎn)個，則葉子結(jié)點(diǎn) 數(shù)為數(shù)為 B 。 A. 15 B. 16 C. 17 D. 47 24.假定一棵二叉樹的結(jié)點(diǎn)數(shù)為假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18個，則它的最小高度個，則它的最小高度 B 。 A. 4 B. 5 C. 6 D. 18P221P27P71P124P124 25.在一棵二叉樹中第五層上的結(jié)點(diǎn)數(shù)最多為在一棵二叉樹中第五層上的結(jié)點(diǎn)數(shù)最多為 C 。 A. 8 B. 15 C.

10、 16 D. 32 26.在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為 A 。 A. 31 B. 32 C. 33 D. 16 27.已知已知8個數(shù)據(jù)元素為個數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，最后兩層上的按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為結(jié)點(diǎn)總數(shù)為 B 。 A. 1 B. 2 C. 3 D. 4 28.由分別帶權(quán)為由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為樹，該樹的帶權(quán)路徑長度為 C 。 A. 2

11、3 B. 37 C. 44 D. 46 31.如果結(jié)點(diǎn)如果結(jié)點(diǎn)A有三個兄弟，而且有三個兄弟，而且B是是A的雙親，則的雙親，則B的出度是的出度是 B 。 A. 3 B. 4 C. 5 D. 1 33.在完全二叉樹中，當(dāng)在完全二叉樹中，當(dāng)i為奇數(shù)且不等于時，結(jié)點(diǎn)為奇數(shù)且不等于時，結(jié)點(diǎn)i的左兄弟的左兄弟是結(jié)點(diǎn)是結(jié)點(diǎn) D ，否則沒有左兄弟。，否則沒有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1P123P124P227P144P120P124 34.某二叉樹某二叉樹T有有n個結(jié)點(diǎn)，設(shè)按某種遍歷順序?qū)€結(jié)點(diǎn)，設(shè)按某種遍歷順序?qū)中的每個結(jié)中的每個結(jié)點(diǎn)進(jìn)行編號，編號值為點(diǎn)進(jìn)行編號，編

12、號值為1,2,n且有如下性質(zhì)：且有如下性質(zhì)：T中任一結(jié)點(diǎn)中任一結(jié)點(diǎn)V，其編號等于左子樹上的最小編號減其編號等于左子樹上的最小編號減1，而，而V的右子樹的右子樹 的結(jié)點(diǎn)中，的結(jié)點(diǎn)中，其最小編號等于其最小編號等于V左子樹上結(jié)點(diǎn)的最大編號加左子樹上結(jié)點(diǎn)的最大編號加1。這時按。這時按 B 編編號。號。 A. 中序遍歷序列中序遍歷序列 B. 前序遍歷序列前序遍歷序列 C. 后序遍歷序列后序遍歷序列 D. 層次遍歷序列層次遍歷序列 35.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的度之和的 B 倍。倍。 A. 1/2 B. 1 C. 2 D.

13、 4 36.對于一個具有對于一個具有n個頂點(diǎn)和個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表?xiàng)l邊的無向圖，若采用鄰接表表示，則表頭向量的大小示，則表頭向量的大小 為為 A 。 A. n B. n+1 C. n-1 D. n+e 37.具有具有n個頂點(diǎn)的無向完全圖，邊的總數(shù)為個頂點(diǎn)的無向完全圖，邊的總數(shù)為 D 條。條。 A. n-1 B. n C. n+1 D. n*(n-1)/2 39.最小代價生成樹最小代價生成樹 D 。 A.是唯一的是唯一的 B.不是唯一的不是唯一的 C.唯一性不確定唯一性不確定 D.唯一性與原因的邊的權(quán)數(shù)有關(guān)唯一性與原因的邊的權(quán)數(shù)有關(guān)P129P158P164P158P173 40

14、.在無向圖在無向圖G的鄰接矩陣的鄰接矩陣A中，若中，若Ai,j等于等于1，則，則Aj,i等于等于 C 。 A. i+j B. i-j C. 1 D. 0 42.已知一個有序表為已知一個有序表為(12、18、24、35、47、50、62、83、90、115、134)，當(dāng)二分查找值為，當(dāng)二分查找值為90的元素時，的元素時， B 次比較后查找成次比較后查找成功；當(dāng)二分查找值為功；當(dāng)二分查找值為47的元素時，的元素時， D 次比較后查找成功。次比較后查找成功。 A. 1 B. 2 C. 3 D. 4 43.散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)當(dāng)以散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 D 取其值取其值域

15、的每個值。域的每個值。 A. 最大概率最大概率 B. 最小概率最小概率 C. 平均概率平均概率 D. 同等概率同等概率 44.設(shè)散列地址空間為設(shè)散列地址空間為0m1,k為關(guān)鍵字，用為關(guān)鍵字，用p去除去除k，將所，將所得的余數(shù)作為得的余數(shù)作為k的散列地址，即的散列地址，即H(k)k % p。為了減少發(fā)生沖突。為了減少發(fā)生沖突的頻率，一般取的頻率，一般取p為為 D 。 A. 小于小于m的最大奇數(shù)的最大奇數(shù) B. 小于小于m的最大偶數(shù)的最大偶數(shù) C. m D. 小于小于m的最大素數(shù)的最大素數(shù)P161P220P254P255 48.一組記錄排序碼為一組記錄排序碼為(46、79、56、38、40、84)

16、，則利用堆排，則利用堆排序的方法建立的初始堆為序的方法建立的初始堆為 B 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 49.一組記錄的關(guān)鍵碼為一組記錄的關(guān)鍵碼為(46、79、56、38、40、84)，則利用快，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為 C 。 A. (38、40、46、56、79、84) B. (40、38、46、79、56、84) C. (40、38、46、56、

17、79、84) D. (40、38、46、84、56、79) 50.在平均情況下快速排序的時間復(fù)雜性為在平均情況下快速排序的時間復(fù)雜性為 C ，空間復(fù)雜性，空間復(fù)雜性為為 B ；在最壞情況下（如初始記錄已有序），快速排序的時；在最壞情況下（如初始記錄已有序），快速排序的時間復(fù)雜性為間復(fù)雜性為 D ，空間復(fù)雜性為，空間復(fù)雜性為 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 )P276P273P280 二、填空題二、填空題 3.一個數(shù)據(jù)結(jié)構(gòu)用二元組表示時，它包括一個數(shù)據(jù)結(jié)構(gòu)用二元組表示時，它包括 1 數(shù)據(jù)元數(shù)據(jù)元素素 的集合的集合K和和K上上 2二元關(guān)

18、系二元關(guān)系 的集合的集合R。 5.對于順序存儲的線性表，當(dāng)隨機(jī)插入或刪除一個元對于順序存儲的線性表，當(dāng)隨機(jī)插入或刪除一個元素時，約需平均移動表長素時，約需平均移動表長 1 一半一半 的元素。的元素。 6.對于長度為對于長度為n的順序表，插入或刪除元素的時間復(fù)的順序表，插入或刪除元素的時間復(fù)雜性為雜性為 1 O(n) ；對于順序?；蜿犃?，插入或刪除元；對于順序?；蜿犃?，插入或刪除元素的時間復(fù)雜性為素的時間復(fù)雜性為 2 O(1) 。 7.在具有在具有n個單元、順序存儲的循環(huán)隊列中，隊滿時個單元、順序存儲的循環(huán)隊列中，隊滿時共有共有 1 n-1 個元素。個元素。 9.在線性表的順序存儲中，元素之間的

19、邏輯關(guān)系是通在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過過 1 相鄰位置相鄰位置 決定的；在線性表的鏈接存儲中，元決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過素之間的邏輯關(guān)系是通過 2 鏈接指針鏈接指針 決定的。決定的。P27P63P25,P47P25P5 10.一個單鏈表中刪除一個單鏈表中刪除*p結(jié)點(diǎn)時，應(yīng)執(zhí)行如下操作結(jié)點(diǎn)時，應(yīng)執(zhí)行如下操作: (1)q=p-next; (2)p-data=p-next-data; (3)p-next= 1 q-next或或p-next-next ; (4)free(q); 11.若要在一個單鏈表中的若要在一個單鏈表中的*p結(jié)點(diǎn)之前插入一個結(jié)點(diǎn)之前

20、插入一個*s結(jié)結(jié)點(diǎn)時，可執(zhí)行如下操作點(diǎn)時，可執(zhí)行如下操作: (1)s-next= 1 p-next ; (2)p-next=s; (3)t=p-data; (4)p-data= 2 s-data ; (5)s-data= 3 t ; P29P28ppqs 13.無論對于順序存儲還是鏈接存儲的棧和隊列來說，進(jìn)行插無論對于順序存儲還是鏈接存儲的棧和隊列來說，進(jìn)行插入或刪除運(yùn)算的時間復(fù)入或刪除運(yùn)算的時間復(fù) 雜性均相同，則為雜性均相同，則為 1 O(1) 。 15.對于一棵具有對于一棵具有n個結(jié)點(diǎn)的樹，則該樹中所有結(jié)點(diǎn)的度之和為個結(jié)點(diǎn)的樹，則該樹中所有結(jié)點(diǎn)的度之和為 n-1 。 16.在一棵二叉樹中，

21、度為在一棵二叉樹中，度為0的結(jié)點(diǎn)的個數(shù)為的結(jié)點(diǎn)的個數(shù)為n0 ，度為，度為2的結(jié)點(diǎn)的結(jié)點(diǎn)的個數(shù)為的個數(shù)為n2 ，則：，則：n0 = n2 +1 。 17.在二叉樹的順序存儲中，對于下標(biāo)為在二叉樹的順序存儲中，對于下標(biāo)為5的結(jié)點(diǎn)，它的雙親結(jié)的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)的下標(biāo)為點(diǎn)的下標(biāo)為 1 2 ， 若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為 2 10 ，若它存在右孩子，則右孩子結(jié)點(diǎn)的下標(biāo)為，若它存在右孩子，則右孩子結(jié)點(diǎn)的下標(biāo)為 3 11 。 19.在一棵二叉排序樹中，按在一棵二叉排序樹中，按 中序中序 遍歷得到的結(jié)點(diǎn)序列是一遍歷得到的結(jié)點(diǎn)序列是一個有序序列。個有序序列。 20

22、.由分別帶權(quán)為由分別帶權(quán)為3,9,6,2,5的共五個葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，的共五個葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為則帶權(quán)路徑長度為 55 。P47,P62P120P124P124P227P144 2121. .假定在二叉樹的鏈接存儲中，每個結(jié)點(diǎn)的結(jié)構(gòu)為假定在二叉樹的鏈接存儲中，每個結(jié)點(diǎn)的結(jié)構(gòu)為 left data right left data right ，其中，其中 datadata為值域，為值域，leftleft和和rightright分別為鏈接左、右孩子結(jié)點(diǎn)的指針域，分別為鏈接左、右孩子結(jié)點(diǎn)的指針域，請在下面中序遍歷算法請在下面中序遍歷算法 中畫中畫有橫線的地方填寫合適的

23、語句。有橫線的地方填寫合適的語句。 void inorder(bt); if bt!=nil (1) 1 inorder(bt-left) ； (2) 2 printf(bt-data) ； (3) 3 inorder(bt-right) ； 23.假定一個圖具有假定一個圖具有n個頂點(diǎn)和個頂點(diǎn)和e條邊，則采用鄰接矩陣表示的條邊，則采用鄰接矩陣表示的空間復(fù)雜性為空間復(fù)雜性為 1 O(n2 ) ， 采用鄰接表表示的空間復(fù)雜性為采用鄰接表表示的空間復(fù)雜性為 2 O(n+e) 。P129P161,P163 25.已知一個圖如下所示，在該圖的最小生成樹中，各邊的權(quán)已知一個圖如下所示，在該圖的最小生成樹中

24、，各邊的權(quán)值之和為值之和為 20 。 10 15 5 2 8 12 3 26.假定在有序表假定在有序表A1.20上進(jìn)行二分查找，則比較一次查找成上進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為功的結(jié)點(diǎn)數(shù)為 11 ， 比較兩次查找成功的結(jié)點(diǎn)數(shù)為比較兩次查找成功的結(jié)點(diǎn)數(shù)為 22 ，比較，比較三次查找成功的結(jié)點(diǎn)數(shù)為三次查找成功的結(jié)點(diǎn)數(shù)為 34 ，比較四次查找成功結(jié)點(diǎn)數(shù)為，比較四次查找成功結(jié)點(diǎn)數(shù)為 48 ，比較五次查找成功的結(jié)點(diǎn)數(shù)為，比較五次查找成功的結(jié)點(diǎn)數(shù)為 55 ，平均查找長度為，平均查找長度為 63.7 。P173P220 28.在散列存儲中，裝填因子在散列存儲中，裝填因子的值越大，存取元素時的值越

25、大，存取元素時發(fā)生沖突的可能性就發(fā)生沖突的可能性就 1 越大越大，當(dāng)，當(dāng)?shù)闹翟叫?，存取元的值越小，存取元素時發(fā)生沖突的可能性就素時發(fā)生沖突的可能性就 2 越小越小 。 29.給定線性表給定線性表(18,25,63,50,42,32,90)，用散列方式存，用散列方式存儲，若選用儲，若選用h(K)=K % 9作為散列函數(shù)，則元素作為散列函數(shù)，則元素18的同的同義詞元素共有義詞元素共有 12 個，元素個，元素25的同義詞元素共有的同義詞元素共有 20 個，元素個，元素50的同義詞元素共有的同義詞元素共有 31 個。個。 30.在對一組記錄在對一組記錄(54,38,96,23,15,72,60,45,

26、83)進(jìn)行直接進(jìn)行直接選擇排序時，第四次選擇和交換后，未排序記錄選擇排序時，第四次選擇和交換后，未排序記錄(即無即無序表序表)為為 (54,72,60,96,83) 。 33.在直接插入和直接選擇排序中，若初始數(shù)據(jù)基本在直接插入和直接選擇排序中，若初始數(shù)據(jù)基本正序，則選用正序，則選用 1 直接插入排序直接插入排序 ，若初始數(shù)據(jù)基本反，若初始數(shù)據(jù)基本反序，則選用序，則選用 2 直接選擇排序直接選擇排序 。P261P257P277P266,P277 34.在堆排序、快速排序和歸并排序中，若只從在堆排序、快速排序和歸并排序中，若只從節(jié)省空間考慮，則應(yīng)首先選取節(jié)省空間考慮，則應(yīng)首先選取 1 堆排序堆排

27、序 方法，方法，其次選取其次選取 2 快速排序快速排序 方法，最后選取方法，最后選取 3 歸歸并排序并排序 方法；若只從排序結(jié)果的穩(wěn)定性考慮，方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取則應(yīng)選取 4 歸并排序歸并排序 ；若只從平均情況下排；若只從平均情況下排序最快考慮，則應(yīng)選取序最快考慮，則應(yīng)選取 5 快速排序快速排序 方法；若方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取則應(yīng)選取 6 堆排序堆排序 方法。方法。P289 三、判斷題三、判斷題 3順序存儲的線性表可以隨機(jī)存?。樞虼鎯Φ木€性表可以隨機(jī)存取（ ）。）。 4線性表中的元素可以是各種

28、各樣的，但同一線性表中的數(shù)線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，據(jù)元素具有相同的特性， 因此，是屬于同一數(shù)據(jù)對象（因此，是屬于同一數(shù)據(jù)對象（ ）。）。 5在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個元素（系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個元素（ ）。）。 7鏈表的每個結(jié)點(diǎn)中，都恰好包含一個指針（鏈表的每個結(jié)點(diǎn)中，都恰好包含一個指針（ ）。）。 11.由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的（由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的（ ）。）。 12.后序遍歷樹和中序遍歷與

29、該樹對應(yīng)的二叉樹，其結(jié)果不同后序遍歷樹和中序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同（ ）。）。 15.已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹，因?yàn)椴恢罉溥@棵樹，因?yàn)椴恢罉?的根結(jié)點(diǎn)是哪一個（的根結(jié)點(diǎn)是哪一個（ ）。）。 17.有回路的圖不能進(jìn)行拓?fù)渑判颍ㄓ谢芈返膱D不能進(jìn)行拓?fù)渑判颍?）。）。 18.連通分量是無向圖中的極小連通子圖（連通分量是無向圖中的極小連通子圖（ ）。）。 /極大極大/P22P27P27P139P128P182 19.散列法存儲的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地散列法存儲的基本思想是由關(guān)鍵碼的值決定數(shù)

30、據(jù)的存儲地址（址（ ）。）。 20.散列表的查找效率取決于散列表造表時選取的散列函數(shù)和散列表的查找效率取決于散列表造表時選取的散列函數(shù)和處理沖突的方法（處理沖突的方法（ ）。）。 22.中序遍歷二叉排序樹的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列中序遍歷二叉排序樹的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列（ ）。）。 23.在二叉排序樹上插入新的結(jié)點(diǎn)時，不必移動其它結(jié)點(diǎn)，僅在二叉排序樹上插入新的結(jié)點(diǎn)時，不必移動其它結(jié)點(diǎn)，僅需改動某個結(jié)點(diǎn)的指針，需改動某個結(jié)點(diǎn)的指針， 由空變?yōu)榉强占纯桑ㄓ煽兆優(yōu)榉强占纯桑?）。）。 24.當(dāng)待排序的元素很多時，為了交換元素的位置，移動元素當(dāng)待排序的元素很多時，為了交換元素的位置，移

31、動元素要占用較多的時間，這是影響時間復(fù)雜性的主要因素（要占用較多的時間，這是影響時間復(fù)雜性的主要因素（ ）。）。 25.對于對于n個記錄的集合進(jìn)行快速排序，所需要的平均時間是個記錄的集合進(jìn)行快速排序，所需要的平均時間是O(nlog2 n)（ ）。）。 27.堆中所有非終端結(jié)點(diǎn)的值均小于或等于（大于或等于）左堆中所有非終端結(jié)點(diǎn)的值均小于或等于（大于或等于）左右子樹的值（右子樹的值（ ）。）。P252P251P227P228P276P280 四、綜合題四、綜合題 1. 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：試問： (1)兩種存儲表示各有哪些主

32、要優(yōu)缺點(diǎn)兩種存儲表示各有哪些主要優(yōu)缺點(diǎn)? 1. 解答解答: (1)順序存儲是按索引（隱含的）直接存取數(shù)據(jù)元素，順序存儲是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時將引起元素移方便靈活，效率高，但插入、刪除操作時將引起元素移動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間有序關(guān)系的指針域，存取率高，但需增設(shè)指示結(jié)點(diǎn)之間有序關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作十分簡單。十分簡單。P27 (2)如果有如果有n個線性表同時并

33、存，并且在處理過程中各表個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性的長度會動態(tài)發(fā)生變化，線性 表的總數(shù)也會自動地改表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)?為什么為什么? (2)解答解答: 應(yīng)選用鏈接表存儲結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯Y(jié)應(yīng)選用鏈接表存儲結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯Y(jié)構(gòu)用一組任意的存儲單元依次存儲線性表里各元構(gòu)用一組任意的存儲單元依次存儲線性表里各元素，這里存儲單元可以是連續(xù)的，也可以是不連素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲結(jié)構(gòu)，在對元素作插入或刪除運(yùn)續(xù)的。這種存儲結(jié)構(gòu)，在對元素作插入或刪除運(yùn)算時

34、，不需要移動元素，僅修改指針即可。所以算時，不需要移動元素，僅修改指針即可。所以很容易實(shí)現(xiàn)表的容量擴(kuò)充。很容易實(shí)現(xiàn)表的容量擴(kuò)充。 P27 (3)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應(yīng)采但要求以最快的速度存取線性表中的元素，那么，應(yīng)采用哪種存儲結(jié)構(gòu)用哪種存儲結(jié)構(gòu)?為什么為什么? (3)解答解答: 應(yīng)選用順序存儲結(jié)構(gòu)。其理由是，每個數(shù)據(jù)元素應(yīng)選用順序存儲結(jié)構(gòu)。其理由是，每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。由

35、此，只元素在線性表中的序號成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲結(jié)構(gòu)是一種隨隨機(jī)存取，所以線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。而鏈表則是一種順序存取的機(jī)存取的存儲結(jié)構(gòu)。而鏈表則是一種順序存取的存儲結(jié)構(gòu)。存儲結(jié)構(gòu)。P27 2. 用線性表的順序結(jié)構(gòu)來描述一個城市用線性表的順序結(jié)構(gòu)來描述一個城市的設(shè)計和規(guī)劃合適嗎的設(shè)計和規(guī)劃合適嗎?為什么為什么? 2.解答解答: 不合適。因?yàn)橐粋€城市的設(shè)計和不合適。因?yàn)橐粋€城市的設(shè)計和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常需要修改

36、、擴(kuò)充和刪除各種信息，才能需要修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合線性表不能很好適應(yīng)其需要，故是不合適的。適的。P27 3. 在單鏈表和雙向表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)在單鏈表和雙向表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任一結(jié)點(diǎn)訪問到任一結(jié)點(diǎn)? 3. 解答解答: 在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問其后的在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問其后的任一結(jié)點(diǎn)，因?yàn)闆]有指向其前驅(qū)結(jié)點(diǎn)的指針。而任一結(jié)點(diǎn)，因?yàn)闆]有指向其前驅(qū)結(jié)點(diǎn)的指針。而在雙向鏈表中，既有指向后繼結(jié)點(diǎn)的指針又有指在雙向鏈表中，既有指向后繼結(jié)點(diǎn)的指針又有指向前驅(qū)結(jié)點(diǎn)的指針

37、，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問鏈向前驅(qū)結(jié)點(diǎn)的指針，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問鏈表中任一結(jié)點(diǎn)。表中任一結(jié)點(diǎn)。 6. 兩個字符串相等的充要條件是什么兩個字符串相等的充要條件是什么? 6. 解答解答: 兩個字符串相等的充要條件是：兩兩個字符串相等的充要條件是：兩個串的長度相等，且對應(yīng)位置的字符相等。個串的長度相等，且對應(yīng)位置的字符相等。P35P71 13.若對大小均為若對大小均為n的有序的順序表和無序的順序表分別的有序的順序表和無序的順序表分別進(jìn)行順序查找，試問在下面三種情況下，分別討論兩者進(jìn)行順序查找，試問在下面三種情況下，分別討論兩者在等概率時，平均查找長度是否相同在等概率時，平均查找長度是否相同? (1

38、)查找不成功，即表中沒有關(guān)鍵字等于給定值查找不成功，即表中沒有關(guān)鍵字等于給定值k的記的記錄；錄； 13.(1) 解答解答:不相同。對于有序的順序表而言，當(dāng)表中無不相同。對于有序的順序表而言，當(dāng)表中無此關(guān)鍵字時，只要在查找過程中發(fā)現(xiàn)順序表中的某個關(guān)此關(guān)鍵字時，只要在查找過程中發(fā)現(xiàn)順序表中的某個關(guān)鍵字大于待查的關(guān)鍵字時，查找過程就可以結(jié)束（假定鍵字大于待查的關(guān)鍵字時，查找過程就可以結(jié)束（假定順序表是由小到大排列的，對于由大到小排列的情況類順序表是由小到大排列的，對于由大到小排列的情況類似），沒有必要查找到表中最后一個關(guān)鍵字才確定查找似），沒有必要查找到表中最后一個關(guān)鍵字才確定查找不成功。而對于非有

39、序的順序表，只有對表中的每一個不成功。而對于非有序的順序表，只有對表中的每一個關(guān)鍵字比較完之后，才能說明查找不成功。顯然在等概關(guān)鍵字比較完之后，才能說明查找不成功。顯然在等概率時兩種順序的平均查找長度是不相同的。有序順序表率時兩種順序的平均查找長度是不相同的。有序順序表的平均長度為的平均長度為(n1)/2，而無序順序表的平均查找長度，而無序順序表的平均查找長度為為n。但從數(shù)量級上兩者是相同的。但從數(shù)量級上兩者是相同的,即即O(n)。 P216 (2)查找成功，且表中只有一個關(guān)鍵字等于給定值查找成功，且表中只有一個關(guān)鍵字等于給定值k的記的記錄；錄； (2) 解答解答:相同的。其分析類似于相同的。

40、其分析類似于(1)。兩者在等概率下的。兩者在等概率下的平均長度為平均長度為(n1)/2，數(shù)量級上為，數(shù)量級上為 O(n)。 (3)查找成功，且表中有若干個關(guān)鍵字等于給定值查找成功，且表中有若干個關(guān)鍵字等于給定值k的記的記錄，一次查找要求找出所有記錄，此時的平均查找長度錄，一次查找要求找出所有記錄，此時的平均查找長度應(yīng)考慮找到所有記錄時所用的比較次數(shù)。應(yīng)考慮找到所有記錄時所用的比較次數(shù)。 (3) 解答解答:不相同。其分析完全與不相同。其分析完全與(1)相同，其結(jié)論也完全相同，其結(jié)論也完全相同。相同。P216P216 15.有一個有一個10000項(xiàng)的表，欲采用等分區(qū)間順序查找方法項(xiàng)的表，欲采用等分

41、區(qū)間順序查找方法進(jìn)行查找，問進(jìn)行查找，問 (1)每塊的理想長度是多少每塊的理想長度是多少? (2)分成多少塊最為理想分成多少塊最為理想? 15.解答：解答： (1)在給定在給定n的前提下，理想的塊長的前提下，理想的塊長d為為 n10000=100 (2)因查找方法為等分區(qū)間順序查找，長度為因查找方法為等分區(qū)間順序查找，長度為n的表被的表被分成分成bn/d塊，塊，d為塊長，故有為塊長，故有 bn/d10000/100100 P226 (3)平均查找長度是多少平均查找長度是多少? (3)解答：解答：平均查找長度為平均查找長度為 ASLbd/21(100100)/21101 (4)若每塊長度為若每塊

42、長度為20，平均查找長度是多少，平均查找長度是多少? (4)解答：解答：因每塊的長度為因每塊的長度為20，所以表被分成，所以表被分成b塊，其平塊，其平均查找均查找ASL長度為長度為 bn/d10000/20500 ASL(bd)/21(50020)/21261P226P226 17.設(shè)有設(shè)有5000個無序的元素，希望用最快速度挑個無序的元素，希望用最快速度挑選出其中前選出其中前10個最大的元素。在以下個最大的元素。在以下 的排序方的排序方法中，采用哪種方法最好法中，采用哪種方法最好?為什么為什么? 快速排序，堆排序，歸并排序，基數(shù)排序，快速排序，堆排序，歸并排序，基數(shù)排序，Shell排序。排序

43、。 17. 解答解答:上面所列的幾種排序方法的速度都很塊，上面所列的幾種排序方法的速度都很塊，但快速排序、歸并排序、基數(shù)排序和希爾排序都但快速排序、歸并排序、基數(shù)排序和希爾排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，而無法知道排序過程中部分元素的有序性。而堆而無法知道排序過程中部分元素的有序性。而堆排序則每次輸入一個最大（或最?。┑脑兀慌判騽t每次輸入一個最大（或最?。┑脑?，然后對堆進(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略睾髮Χ堰M(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲螅ɑ蜃钚。┑摹８鶕?jù)題意，只要選取前中最大（或最?。┑摹８鶕?jù)題意，只要選取前10個

44、最大的元素，故采用堆排序方法是合適的。個最大的元素，故采用堆排序方法是合適的。P273，P279，P283，P284 ，P271 19.判斷下列序列是否是堆。若不是堆，則把它們依判斷下列序列是否是堆。若不是堆，則把它們依次調(diào)整為堆。次調(diào)整為堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)； (2) (100，98，85，82，80，77，66，60，40，20，10) (3) (100，85，40，77，80，60，66，98，82，10，20)； (4) (10，20，40，60，66，77，80，82，85，98，100)； 19. 解答解答:根據(jù)堆的定

45、義可知堆中元素滿足下面中的某一根據(jù)堆的定義可知堆中元素滿足下面中的某一個式子的關(guān)系，個式子的關(guān)系， kik2i kik2i 或或 kik2i1 kik2i1 因此因此(1)、(2)和和(4)序列是堆。序列是堆。(3)不是堆。不是堆。 (3) 調(diào)整為調(diào)整為100,98,66,85,80,60,40,77,82,10,20后成為堆。后成為堆。P280 21.編寫下列算法編寫下列算法 (1)向類型有向類型有l(wèi)ist的線性表的線性表L的第的第i個元素（個元素（0iL.len）之后插入一個新元素之后插入一個新元素x。 (1) 解答解答: status insert(SqList L,int i,Elem

46、Type x) / 向線性表向線性表L中第中第i個元素之后插入值為個元素之后插入值為x的新元素的新元素 (1) if (L.len = =m0) error(overflow); (2) if (iL.len) error (out of range); (3) for (j=L.len ;j= i1;-j ) L.vecj1L.vecj; (4) L.veci1x; (5) L.lenL.len1; (2)從類型為從類型為list的線性表的線性表L中刪除其值等于中刪除其值等于x的所有元的所有元 (2) 解答解答: status delete(L,x) / 從線性表從線性表L中刪除其值等于中刪

47、除其值等于x的所有元素的所有元素 i1; while (iL.len ) if (L.veci= =x ) () for( ji1 ;jm0 ) error(overflow): (2) i=1;j1;k1; / i和和j分別作為掃描數(shù)組分別作為掃描數(shù)組A和和B的指針，的指針，k指示存入數(shù)組指示存入數(shù)組C中元素中元素的下標(biāo)位置的下標(biāo)位置 (3) while (iA.len) & (jB.len) if (A.veciB.vecj) C.veckA.veci; ii1; kk1; else C.veckB.vecj; jj1; kk1; (4) while (iA.len) C.veck

48、A.veci; ii1; kk1; (5) while (jnext; (3) q-nextHL; (4) HLq; (2)刪除單鏈表中第刪除單鏈表中第i個（個（i1）結(jié)點(diǎn)。）結(jié)點(diǎn)。 (2) 解答解答:status delete(HL,i) (1) if (inext; return ; (3) j1; pHL;/p指針?biāo)赶虻慕Y(jié)點(diǎn)，是單鏈表中第指針?biāo)赶虻慕Y(jié)點(diǎn)，是單鏈表中第j個結(jié)點(diǎn)個結(jié)點(diǎn) while (jnext!=nil) jj1; pp-next; / 尋找第尋找第i個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) (4) if (p-next!= =nil) p-nextp-next-next; el

49、se error(out of range); (3)刪除單鏈表中由指針刪除單鏈表中由指針p所指向的結(jié)點(diǎn)。所指向的結(jié)點(diǎn)。 (3) 解答解答: status delete(HL,P,X) / 刪除單鏈表刪除單鏈表HL中由指針中由指針p所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn) if (p-nextnil ) error (not delete); Xp-data; qp-next; p-datap-next-data; p-nextp-next-next; free(q); 或者：或者： status delete(HL,P,X) if ( HLp ) XHL-data ; HLHL-next; free(p);

50、 else (1) qHL; (2) while (q-next!=nil) & (q-next!=p) qq-next; (3) if (q-nextp) Xp-data; q-nextp-next; free(p) else error(*p結(jié)點(diǎn)不存在結(jié)點(diǎn)不存在); (4)從帶有附加表頭結(jié)點(diǎn)的循環(huán)單鏈表中刪除其值等于從帶有附加表頭結(jié)點(diǎn)的循環(huán)單鏈表中刪除其值等于x的第一個結(jié)點(diǎn)。的第一個結(jié)點(diǎn)。 (4) 解答解答: status delete(HL,x) (1) qHL; pHL-next; (2) while (p!=HL) & (p-data!=x) qp; pp-next;

51、 (3) if (p= =HL) error(not found); else q-nextp-next; free(p); (5)在單鏈表中指針在單鏈表中指針p所指結(jié)點(diǎn)之前插入一個值為所指結(jié)點(diǎn)之前插入一個值為x的新結(jié)點(diǎn)。的新結(jié)點(diǎn)。 (5) 解答解答: status insert(HL,p,x) malloc(q); q-datap-data; q-nextp-next; p-nextq; p-datax; (6)從循環(huán)單鏈表中查找出最小值。從循環(huán)單鏈表中查找出最小值。 (6) 解答解答: elemtype min(HL) /從循環(huán)單鏈表從循環(huán)單鏈表HL中查找出最小值中查找出最小值 if (H

52、L= =nil ) printf(HLnil); return; minHL-data; pHL-next; while (p!=HL) (1) if (p-datadata; (2) pp-next; (7)根據(jù)一維數(shù)組根據(jù)一維數(shù)組A(1:n)中順序存儲的具有中順序存儲的具有n個元素的線性表建立個元素的線性表建立一個帶有附加表頭結(jié)一個帶有附加表頭結(jié) 點(diǎn)的單鏈表。點(diǎn)的單鏈表。 (7) 解答解答: status create(HL,A,n) (1) malloc(HL); qHL; / 產(chǎn)生附加表頭結(jié)點(diǎn)產(chǎn)生附加表頭結(jié)點(diǎn) (2) for (i1 ;IdataA(i); q-nextp; qp; (

53、3) q-nextnil ; / 把最后一個結(jié)點(diǎn)的指針域置空把最后一個結(jié)點(diǎn)的指針域置空 23.請指出下面的過程執(zhí)行請指出下面的過程執(zhí)行p(5)和和p(6)時分別輸出的結(jié)果。時分別輸出的結(jié)果。 void P(int n); if n0 p(n-2); printf(“%d”,n); 23. 解答解答:這是一個遞歸過程，這是一個遞歸過程，n執(zhí)行一次就減執(zhí)行一次就減2，當(dāng)，當(dāng)n0時該過程執(zhí)行結(jié)束。因此，當(dāng)時該過程執(zhí)行結(jié)束。因此，當(dāng)n5 時，其輸出結(jié)果為時，其輸出結(jié)果為1、3、5；當(dāng)；當(dāng)n6時，其輸出結(jié)果為時，其輸出結(jié)果為2、4、6。 24.假定用一個循環(huán)單鏈表表示隊列（稱此為循環(huán)鏈隊），該隊假定用一

54、個循環(huán)單鏈表表示隊列（稱此為循環(huán)鏈隊），該隊列只設(shè)一個隊尾指針，列只設(shè)一個隊尾指針， 不設(shè)隊首指針，試編寫下列算法：不設(shè)隊首指針，試編寫下列算法： (1)向循環(huán)鏈隊插入一個元素為向循環(huán)鏈隊插入一個元素為x的結(jié)點(diǎn)；的結(jié)點(diǎn)； (1) 解答解答: status insert(Rear,x) / 假定假定Rear為循環(huán)鏈隊的隊尾指針，為循環(huán)鏈隊的隊尾指針，x為待插入的元素為待插入的元素 (1) malloc(p); p-datax; / 建立值為建立值為x的新結(jié)點(diǎn)的新結(jié)點(diǎn)p (2) if( Rearnil) Rearp; Rear-nextp; else p-nextRear-next; Rear-n

55、extp; Rearp; / 若條件成立則建立循環(huán)鏈隊的第一個結(jié)點(diǎn)，否則在隊若條件成立則建立循環(huán)鏈隊的第一個結(jié)點(diǎn)，否則在隊 尾插入尾插入p結(jié)點(diǎn)結(jié)點(diǎn) (2)從循環(huán)鏈隊中刪除一個結(jié)點(diǎn)（假定不需要保從循環(huán)鏈隊中刪除一個結(jié)點(diǎn)（假定不需要保留被刪除結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)）。留被刪除結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)）。 (2) 解答解答: status delete(Rear) if( Rearnil ) error(underflow); if (Rear-next= =Rear) Rearnil; else Rear-nextRear-next-next; /Rear-next 所指向的結(jié)點(diǎn)為循環(huán)鏈隊的隊首

56、結(jié)所指向的結(jié)點(diǎn)為循環(huán)鏈隊的隊首結(jié)點(diǎn)點(diǎn) 27.設(shè)有一個已排序的整數(shù)數(shù)組設(shè)有一個已排序的整數(shù)數(shù)組a1.n，和一個整，和一個整數(shù)數(shù)x，研究下面用類，研究下面用類C所表示的折半查找的五個所表示的折半查找的五個程序段，指出哪些是正確的。程序段，指出哪些是正確的。 第一個：第一個： i=1; j=n; do k=(i+j)div 2; if xak i=k+1; else j=k-1; while !(ak=x) | (ij); 第一個程序段是正確的折半查找算法的表示。第一個程序段是正確的折半查找算法的表示。 第二個第二個: i=1; j=n; while (iak: i=k+1; case x= =ak

57、: return; case xak i=k; else j=k while !(ak= =x) | (i=j); 第三個程序段不正確。例如，令第三個程序段不正確。例如，令n2,a15,a26,x6,則開始時，則開始時，i1,j2, k(12) div 2，又因，又因akx,所以執(zhí)行所以執(zhí)行i:k,沒沒有改變有改變i的值，循環(huán)將不終止。的值，循環(huán)將不終止。 第四個：第四個： i1; j=n; do k=(i+j) / 2; if xak i=k+1; while !(i=j); 第四個程序段是正確的折半查找算法的表示。第四個程序段是正確的折半查找算法的表示。 第五個：第五個： i=1; j=n; do k=(i+j) / 2; if x=j); 第五個程序段不正確。例如，令第五個程序段不正確。例如，令n2,a15,a26,x6,則開始時，則開始時，i1,j2, k1,又因又因xak不成立不成立,執(zhí)行執(zhí)行i:k1,使循環(huán)終使循環(huán)終止條件止條件ij成立成立,程序結(jié)束，但此時程序結(jié)束，但此時ak 并不等于并不等于x，即求出的，即求出的k是錯誤的。是錯誤的。28.設(shè)設(shè)a、b、c、d都是串名，都是串名，aTHIS IS A BOOK，bESE ARE，CS。 求求dCONCAT(SUB(a,1,2)，b，SUB(a,10,5),c