帶答案的數(shù)據(jù)結(jié)構(gòu)補(bǔ)充習(xí)題

1、補(bǔ)充習(xí)題第一章第五章一、 單選或填空題1. 下列程序段中S語(yǔ)句的執(zhí)行頻度為 n(n-1)/2 。for(i0；in；i+ ）for(j0；ji；j+ ） S；2. 下列算法的時(shí)間復(fù)雜度是（O(n)）。for(i0；in；i+ ）cii；3. 算法的時(shí)間復(fù)雜度可表示為 常數(shù)階 O(1)、線性階 O(n) 、平方階O(n2)、對(duì)數(shù)階O(logn)和指數(shù)階O(2n)等。4 以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的基本概念中，敘述正確的是 C A) 數(shù)據(jù)元素是數(shù)據(jù)不可分割的最小單位。B) 數(shù)據(jù)是數(shù)據(jù)對(duì)象的子集。C) 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中可用順序映像和非順序映像兩種不同的方法表示。D) 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示又稱為

2、邏輯結(jié)構(gòu)。5. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)包括（A）。 A) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) B) 邏輯結(jié)構(gòu)和物理結(jié)構(gòu) C) 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) D) 虛擬結(jié)構(gòu)和抽象結(jié)構(gòu) 6. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括 C 。§ A) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) B) 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)§ C) 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) D) 虛擬結(jié)構(gòu)和抽象結(jié)構(gòu) 7. 線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在一種( D )。A一對(duì)多關(guān)系B多對(duì)多關(guān)系C多對(duì)一關(guān)系D一對(duì)一關(guān)系8. 在長(zhǎng)度為n的順序表中插入一個(gè)元素，需要平均移動(dòng) A 個(gè)元素。A) n/2 B)nC) n(n-1) D) n(n+1)9. 在有n個(gè)元素的順序表中做插入、刪

3、除運(yùn)算，平均時(shí)間復(fù)雜度為 O(n) 。10. 順序表中邏輯上相鄰的元素物理位置 B 相鄰，單鏈表中邏輯上相鄰的元素的物理位置 相鄰。A)必然、必然 B)必然、不一定C)不一定、必然 D)不一定、不一定11相對(duì)于順序存儲(chǔ)而言，鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是（C）。A隨機(jī)存取B節(jié)約空間C增、刪操作方便D節(jié)點(diǎn)間關(guān)系簡(jiǎn)單12 以下關(guān)于頭結(jié)點(diǎn)的描述中，敘述錯(cuò)誤的是 A A) 頭結(jié)點(diǎn)是對(duì)鏈表首元結(jié)點(diǎn)的別稱B) 若鏈表中附設(shè)頭結(jié)點(diǎn)，則頭指針一定不為空C) 頭結(jié)點(diǎn)中不存儲(chǔ)鏈表的數(shù)據(jù)元素，而是一些諸如表長(zhǎng)之類的輔助信息D) 在單鏈表中附設(shè)頭結(jié)點(diǎn)，插入或刪除首元素時(shí)不必進(jìn)行特殊處理13已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P所指結(jié)點(diǎn)既

4、不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，則在P之后插入S所指結(jié)點(diǎn)，則執(zhí)行（A）。A) S->next=P->next； P->next=S；B) P->next=S->next； S->next=P；C) S->next=P； P->nextS；D) P->next=S； S->next=P；14. 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)是S結(jié)點(diǎn)的直接前驅(qū)。則刪除S結(jié)點(diǎn)的語(yǔ)句序列為 B 。I. P->next = S ;free(P)II. P->next = P->next->next; free(S)III. P-

5、>next = S->next; free(S) IV. P = P->next ;free(S)A) I和II正確 B) II和 III正確C) III和IV正確 D) 全部正確15. 已知L是帶表頭結(jié)點(diǎn)的單鏈表，則刪除首元結(jié)點(diǎn)的語(yǔ)句序列是（ C）。A) L->next =L->next->next; free(L)B) P = L ;L= P->next ;free(P)C) P = L->next ; L->next= P->next ;free(P)D) P = L ;L= P->next ;free(P)16. 已知L

6、是一帶有頭結(jié)點(diǎn)的單鏈表的頭指針，則該單鏈表為空的條件是 L->next=NULL 。17. 已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，則刪除P結(jié)點(diǎn)的語(yǔ)句序列是 P->prior->next=p->next ， P->next->prior=P->prior ，free(P);18. 設(shè)將整數(shù)1，2，3，4，5依次進(jìn)棧，最后都出棧，出?？梢栽谌魏螘r(shí)刻(只要棧不空)進(jìn)行，則出棧序列不可能的是（B ）。A) 32415 B) 45231 C) 32145 D) 4532119. 在棧中由頂向下已存放元素c, b, a 在第4個(gè)元素d入棧前，棧中元素可以出棧，則不可能

7、的出棧序列是 ( D )A) dcba B) cbda C) cdba D) cadb21. 設(shè)有棧S和隊(duì)列Q，其初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a6依次入棧，出棧的元素進(jìn)入隊(duì)列Q。若元素出隊(duì)列的順序是a2,a4,a3,a6,a5,a1，則棧的容量至少是 3 。22. 某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則abcde順序入隊(duì)，不可能的到的順序是（C）。AbacdeBdbaceCdbcaeDecbad23. 設(shè)用一維數(shù)組An存儲(chǔ)一個(gè)棧，令A(yù)n為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。當(dāng)從棧中彈出一個(gè)元素時(shí)，變量T的變化為（A）。A) T=T+1

8、 B) T=T-1 C) T不變 D) T=n-124. 循環(huán)隊(duì)列是滿隊(duì)列的條件是 B 。A）Q.rearQ.front B）(Q.rear+1) % maxsizeQ.frontC）Q.rear0 D）Q.front025. 在具有m個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是（A）A. front= (rear1) % m B. front1= rearC. front= rear D. rear= m26. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是（C）A)front=

9、 (rear1) % n B)front1=rearC)front=rear D)front=027. 循環(huán)隊(duì)列用數(shù)組A0m-1存放其數(shù)據(jù)元素。設(shè)front指向其實(shí)際的隊(duì)頭，rear指向其實(shí)際隊(duì)尾的下一個(gè)位置，則當(dāng)前隊(duì)列中的數(shù)據(jù)元素有 (rear-front+m)%m 個(gè)。28 在串的運(yùn)算中，StrLength(Concat (aa，bb)的返回值為 D A) 0B) 8C) 6D) 429設(shè)s1”I have_”，s2”a dream”，則strcat(s1, s2)的值是 I have_ a dream ，SubString(s1,4,3)的值是 ave 。 30. 設(shè)s1”I am a

10、student”，s2”a student”，則Index(s1,s2)的值是 6 。31. 假設(shè)有二維數(shù)組A5×6，每個(gè)元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的基地址為1000，則數(shù)組A的最后一個(gè)元素a45的第一個(gè)字節(jié)的地址是 1116 ；按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址是 1040 。32. 已知二維數(shù)組A1.7，1.7按列存放，其起始存儲(chǔ)位置為100，每個(gè)元素占用4個(gè)字節(jié)，則元素A4,6的第一個(gè)字節(jié)的地址為 B 。A）204 B）252 C）208 D）25633. 一個(gè)非空廣義表的表頭（D）。A一定是子表 B一定是原子C不能是子表 D可以是原子，也可以是子

11、表34. 設(shè)廣義表L（(a,b),c,()），則head(L) (a,b) ，tail(L) ( c,() ) 。二、 算法題1. 寫(xiě)出下列程序段的功能。Status A(LinkedList L) /L是無(wú)表頭結(jié)點(diǎn)的單鏈表If(L &&L->next) Q=L; L=L->next; P=L; While (P->next) P=P->next; P->next=Q; Q->next=NULL; Return OK; 2. 寫(xiě)出下列程序段的輸出結(jié)果。void main() Stack S; char x,y; InitStack(S); x

12、=i; y=s; Push(S,x);Push(S,r);Push(S,y); Pop(S,x); Push(S,h);Push(S,x); Pop(S,x); Push(S,c); while (!StackEmpty(S) Pop(S,y);printf(y); printf(x);3. 寫(xiě)出下列程序段的輸出結(jié)果。void main() Queue Q; InitQueue(Q); char x=e, y=c; EnQueue(Q, a);EnQueue(Q, d);EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); En

13、Queue(Q, r); while (!QueueEmpty(Q) DeQueue(Q, y); printf(y); printf(x);4. 已知L是帶頭結(jié)點(diǎn)的單鏈表。試寫(xiě)一算法求該單鏈表的長(zhǎng)度。5. 已知L是帶頭結(jié)點(diǎn)的單鏈表。試寫(xiě)一算法在該鏈表上查找值為x的元素。6. 將帶頭結(jié)點(diǎn)的L中的第i個(gè)數(shù)據(jù)元素刪除。7. 在帶頭結(jié)點(diǎn)的L中第i個(gè)元素之前插入數(shù)據(jù)元素e 。8. 正位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表L。9. 已知線性表中的元素以值遞增有序排列，并以帶有頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫(xiě)一算法刪除表中所有值大于mink且小于maxk的元素，同時(shí)釋放被刪除的結(jié)點(diǎn)空間。10. LA和L

14、B是兩個(gè)數(shù)據(jù)元素按升序排列的單鏈表，將LA和LB合并為有序單鏈表LC。寫(xiě)出這兩個(gè)有序鏈表合并的算法。第六章一、 單選或填空題1. 已知完全二叉樹(shù)的第7層上有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多是 C A) 73 B) 63 C) 235 D) 2452. 300個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉結(jié)點(diǎn)有 150 個(gè)。3一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為_(kāi)C_。A）11 B）10 C）11至1025之間 D）10至1024之間4. m叉樹(shù)的第i層至多有 mi-1 個(gè)結(jié)點(diǎn)5. 將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的節(jié)點(diǎn)的右孩子編號(hào)為（A）。

15、ABCDEFA99B98C50D486把如右圖所示的樹(shù)轉(zhuǎn)換成二叉樹(shù)時(shí)，C是（ D ） A. A的左子女 B. A的右子女 C. B的左子女 D. B的右子女7. 設(shè)森林F中有3棵樹(shù)，其結(jié)點(diǎn)個(gè)數(shù)分別是n1、n2和n3，則與森林對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是 D 。 A) n1-1 B)n1+n2 C) 0 D) n2+n38.在一顆度為4的樹(shù)T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，5個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹(shù)T的葉結(jié)點(diǎn)個(gè)數(shù)有 86 個(gè)。9. 一棵二叉樹(shù)中序遍歷結(jié)果為DCBAEFG，后序遍歷結(jié)果為DCBGFEA。則此二叉樹(shù)先序遍歷的結(jié)果應(yīng)為AA) ABCDEFG

16、B)ABECFDG C)AEBFCGD D)不能確定10. 將一棵樹(shù)t 轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹(shù)h，則t 的后根遍歷是h 的 BA）先序遍歷 B）中序遍歷 C）后序遍歷 C）層序遍歷11.現(xiàn)有一段電文共100個(gè)字符，其中A出現(xiàn)50次，B出現(xiàn)20次，C出現(xiàn)5次，D出現(xiàn)10次，E出現(xiàn)15次?，F(xiàn)對(duì)這5個(gè)字符進(jìn)行哈夫曼編碼，則其平均碼長(zhǎng)為 1.95 。二、 解答題1. 某二叉樹(shù)的中序遍歷結(jié)果為DEFABCG；后序遍歷結(jié)果為FEDCBAG。（1）畫(huà)出此二叉樹(shù)，并給出其先序遍歷的結(jié)果。 GADBEFC（2）畫(huà)出與這棵二叉樹(shù)對(duì)應(yīng)的樹(shù)（森林）。2. 已知一個(gè)二叉樹(shù)的先序遍歷序列為：ABDGIECFH；中

17、序遍歷序列為：DIGBEAFHC。（1）畫(huà)出該二叉樹(shù)（2）畫(huà)出下圖所示森林對(duì)應(yīng)的二叉樹(shù)。AACABADAEAHAIAFAGAJAKLA3. 某二叉樹(shù)層序序列為abcdefghij，中序序列為bgdhjaecif。（1）畫(huà)出該二叉樹(shù)；（2）畫(huà)出該二叉樹(shù)的后序后繼線索樹(shù)；（3）畫(huà)出該二叉樹(shù)對(duì)應(yīng)的樹(shù)或森林。4. 已知某通訊用電文僅有A、B、C、D、E、F六個(gè)字符構(gòu)成，其出現(xiàn)的頻率分別為26，8，17，11，28，10，請(qǐng)首先建立哈夫曼樹(shù)，然后給出六個(gè)字符的哈夫曼編碼（注：建立哈夫曼樹(shù)時(shí)權(quán)值小的為左子樹(shù)，權(quán)值大的為右子樹(shù)）。三、算法題1. 以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法：（1）求先序序列

18、為k的結(jié)點(diǎn)的值（2）求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目（3）交換所有結(jié)點(diǎn)的左右子樹(shù)（4）求二叉樹(shù)的深度第七章一 單選或填空題1. 若某有向圖的鄰接矩陣A只有0和1兩種元素，其中aij1表示有向圖中存在弧<i,j>，則編號(hào)為i頂點(diǎn)的入度可用 B 表示。A) 鄰接矩陣中第i行元素之和 B) 鄰接矩陣中第i列元素之和 C) 鄰接矩陣中對(duì)角線元素之和 D) 以上均不正確2. 使用鄰接表作為某無(wú)向圖的存儲(chǔ)結(jié)構(gòu)，若無(wú)向完全圖中有n個(gè)頂點(diǎn)，則鄰接表中必存在 個(gè)表結(jié)點(diǎn)。 A)n2 B)2n C)n(n-1) D) 2n-13. 一個(gè)含有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中共有（）零元素。AeB2

19、eCn2-eDn2-2e4在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A1/2B1C2D45下列關(guān)于圖的敘述中，正確的是（ ）、 回路是簡(jiǎn)單路徑 、存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間 、若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路 A僅 B僅、 C僅 D僅、 6. 有n個(gè)頂點(diǎn)的無(wú)向圖至少有 條邊才能確保是一個(gè)連通圖。7在有n個(gè)結(jié)點(diǎn)的無(wú)向圖中，其邊數(shù)最多為 。8. 對(duì)于具有n個(gè)結(jié)點(diǎn)的連通圖，它的最小生成樹(shù)中有 條邊。A)n2 B)n-1 C)n(n-1) D) n(n-1)/29. 關(guān)鍵路徑是AOE網(wǎng)中A）從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B）從源點(diǎn)到匯點(diǎn)的最短路徑C）最長(zhǎng)回路D）最

20、短回路10. 以下關(guān)于圖的描述中，正確的是A) n個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。B) 對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)）進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的。C) 若圖G的鄰接矩陣是對(duì)稱的，則G一定是無(wú)向圖cabedD) 有向圖的鄰接矩陣一定是非對(duì)稱矩陣11. 對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是（）A5B3C2D112下圖為用邊表示活動(dòng)的AOE-網(wǎng)。則V8的最早發(fā)生時(shí)間是 。二、解答題1. 已知某無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，求解下列問(wèn)題：（1）畫(huà)出它的無(wú)向圖；（2）畫(huà)出它的的鄰接矩陣存儲(chǔ)結(jié)構(gòu)；（3）從頂點(diǎn)A出發(fā)，畫(huà)出其廣度優(yōu)先生成樹(shù)。0 A 1 41 B 0 2 52 C 1 3

21、43 D 2 54 E 0 2 55 F 1 3 42. 已知無(wú)向帶權(quán)圖G的鄰接矩陣如下所示。（1）從頂點(diǎn)a出發(fā)，求其深度優(yōu)先生成樹(shù)； （2）從頂點(diǎn)a出發(fā)，根據(jù)普里姆算法構(gòu)造最小生成樹(shù)，過(guò)程在下面的圖(1)至(5)中畫(huà)出。（3）給出鄰接表存儲(chǔ)結(jié)構(gòu)；3. 對(duì)于如下圖所示的帶權(quán)有向圖，求解關(guān)鍵路徑, 計(jì)算各事件（頂點(diǎn)）的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，各活動(dòng)（弧）的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間。請(qǐng)?zhí)顚?xiě)在答題紙的表格中。bbdg64521187244acdefhk表1 計(jì)算各事件（頂點(diǎn)）的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，請(qǐng)?zhí)顚?xiě)在表1的空白處。頂點(diǎn)abcdefghkve06457151418vl08101614

22、18表2 計(jì)算各活動(dòng)（弧）的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間，請(qǐng)?zhí)顚?xiě)在表2的空白處?；bacadbecedfegehfhgkhke00064571514l38101614 4.對(duì)于右圖，求解下列問(wèn)題：（1）寫(xiě)出該圖的鄰接矩陣；（2）寫(xiě)出全部拓?fù)渑判蛐蛄?；?）從頂點(diǎn)V1出發(fā)，給出深度優(yōu)先遍歷生成樹(shù)；（4）按照迪杰斯特拉算法，求V1結(jié)點(diǎn)到各點(diǎn)的最短路徑，填寫(xiě)表1的空白處。終點(diǎn)從V1到各終點(diǎn)的距離和最短路徑的求解過(guò)程i=1i=2i=3i=4i=5i=6i=7V22-V333-V4-V51313-V6-V7-V8161616vjv2v3第九章一單選或填空題1已知一個(gè)長(zhǎng)度為11的有序表，使用折半查找的方法

23、，查找第8個(gè)元素時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。2. 已知一個(gè)長(zhǎng)度為16的有序表，使用折半查找的方法，查找一個(gè)不存在的元素，則所需進(jìn)行的關(guān)鍵字比較次數(shù)最多是 。A4B5C6D73. 在二叉排序樹(shù)中，關(guān)鍵字值最大的結(jié)點(diǎn)A）左指針一定為空 B）右指針一定為空C）左右指針均為空 D）左右指針均不為空4 對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹(shù)中一條查找路徑的序列是（ ） A95,22,91,24,94,71 B92,20,91,34,88,35 C21,89,77,29,36,38 D12,25,71,68,33,34 5AVL樹(shù)是一種平衡的二叉排序樹(shù)，樹(shù)中任一結(jié)點(diǎn)的A左、右子樹(shù)的高度均相同 B.

24、 左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1C. 左子樹(shù)的高度均大于右子樹(shù)的高度 D. 左子樹(shù)的高度均小于右子樹(shù)的高度6. 以下關(guān)于查找方法的描述中，錯(cuò)誤的是 A) 平衡二叉樹(shù)一定也是二叉排序樹(shù)。B) 有序表的折半查找判定樹(shù)是二叉排序樹(shù)。C) 中序遍歷一棵二叉排序樹(shù)，可以得到其數(shù)據(jù)元素的升序排列。D) 后序遍歷一棵二叉排序樹(shù)，可以得到其數(shù)據(jù)元素的降序排列。7.下列二叉排序樹(shù)中，滿足平衡二叉樹(shù)定義的是（ ）8、在下列所示的平衡二叉樹(shù)中插入關(guān)鍵字48后得到一棵新平衡二叉樹(shù)，在新平衡二叉樹(shù)中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ ）A、13，48 B、24，48 C、24，53 D、24，9

25、09. 從理論上講，將數(shù)據(jù)以何（）結(jié)構(gòu)存放，則查找一個(gè)數(shù)據(jù)所用時(shí)間不依賴于數(shù)據(jù)個(gè)數(shù)n.A）二叉查找數(shù) B）鏈表 C）二叉樹(shù)D）哈希表10 為提高散列（Hash）表的查找效率，可以采取的正確措施是（ ）、增大裝填（載）因子 、設(shè)計(jì)沖突（碰撞）少的散列函數(shù)、處理沖突（碰撞）時(shí)避免產(chǎn)生聚集（堆積）現(xiàn)象A僅 B僅 C僅、 D僅、二、解答題1. 設(shè)記錄關(guān)鍵字集合key=33,20,53,55,23,38,40,65，選取哈希函數(shù)為H(x)=key mod 11；解決沖突的方法為“線性探測(cè)法”。（1）請(qǐng)按上述條件將key中各值依次填入下表中：（2）求該哈希表查找成功和查找不成功情況下的平均查找長(zhǎng)度。2.

26、設(shè)記錄關(guān)鍵字集合key=32,13,49,55,22,39,20，選取哈希函數(shù)為H(x)=key mod 7；解決沖突的方法為“鏈地址法”。（1）畫(huà)出所構(gòu)造的哈希表；（2）求該哈希表查找成功和查找不成功情況下的平均查找長(zhǎng)度。3. 設(shè)記錄關(guān)鍵字集合key=32,13,49,55,22,39,20，解決沖突的方法為“線性探測(cè)法”，要求裝填因子為：0.7，哈希函數(shù)的形式為H(x)=key mod P，散列表的地址從0開(kāi)始。（1）構(gòu)造哈希函數(shù)；（2）畫(huà)出所構(gòu)造的哈希表；（2）求該哈希表查找成功和查找不成功情況下的平均查找長(zhǎng)度。4. 選取哈希函數(shù)H(key)=(3*key) mod 11。用開(kāi)放定址法處

27、理沖突，di=i(7*key) % 10+1)(i=1,2,3)。試在010的散列地址空間對(duì)關(guān)鍵字序列（22，41，53，46，30，13，01，67）：1） 構(gòu)造該序列對(duì)應(yīng)的哈希表；2） 求等概率情況下查找成功的平均查找長(zhǎng)度。哈希表如下圖所示：5. 從空樹(shù)開(kāi)始，依次插入13，34，51，24，62，43，75，18，畫(huà)出建立2-3樹(shù)后的狀態(tài)，并分別畫(huà)出刪除43、24后的2-3樹(shù)狀態(tài)。6. 畫(huà)出對(duì)長(zhǎng)度為12的有序表進(jìn)行折半查找的判定樹(shù)，并求其等概率查找成功時(shí)的平均查找長(zhǎng)度。第十章一、 單選或填空題1. 數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組用不同排序方法進(jìn)行一趟排序

28、后的結(jié)果。則ABCD四個(gè)選項(xiàng)中，說(shuō)法正確的是 I 12，13，15，18，20，60 II 13，15，18，12，20，60III 13，15，20，18，12，60 IV 12，13，20，18，15，60V 13，15，18，20，12，60A) I快速排序；II簡(jiǎn)單選擇排序；III直接插入排序；IV冒泡排序；V歸并排序B) I冒泡排序；II快速排序；III歸并排序；IV簡(jiǎn)單選擇排序；V直接插入排序C) I快速排序；II冒泡排序；III直接插入排序；IV簡(jiǎn)單選擇排序；V歸并排序D) I直接插入排序；II歸并排序；III快速排序；IV簡(jiǎn)單選擇排序；V冒泡排序 2. 對(duì)一組數(shù)據(jù)(2，12，16，88，5，10)進(jìn)行排序，若前三趟排序結(jié)果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，1