數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題第一章 緒論一、 單選或填空題1. 下列程序段中S語(yǔ)句的執(zhí)行頻度為 。for(i0；in；i+ ）for(j0；ji；j+ ） S；2. 下列算法的時(shí)間復(fù)雜度是（）。for(i0；in；i+ ）cii；3. 算法的時(shí)間復(fù)雜度可表示為 O(1)、線性階 、平方階O(n2)、對(duì)數(shù)階O(logn)和指數(shù)階O(2n)等。4 以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的基本概念中，敘述正確的是 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ī)中的表示又稱為邏輯結(jié)構(gòu)。5. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)

2、包括（）。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)包括 。§ 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) 第二章 線性表1. 線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在一種( )。A一對(duì)多關(guān)系B多對(duì)多關(guān)系C多對(duì)一關(guān)系D一對(duì)一關(guān)系2. 在長(zhǎng)度為n的順序表中插入一個(gè)元素，需要平均移動(dòng) 個(gè)元素。A) n/2 B)nC) n(n-1) D) n(n+1)3. 在有n個(gè)元素的順序表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為 。4. 順序表中邏輯上相

3、鄰的元素物理位置 相鄰，單鏈表中邏輯上相鄰的元素的物理位置 相鄰。A)必然、必然 B)必然、不一定C)不一定、必然 D)不一定、不一定5相對(duì)于順序存儲(chǔ)而言，鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是（）。A隨機(jī)存取B節(jié)約空間C增、刪操作方便D節(jié)點(diǎn)間關(guān)系簡(jiǎn)單6. 以下關(guān)于頭結(jié)點(diǎn)的描述中，敘述錯(cuò)誤的是 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)行特殊處理7已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P所指結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，則在P之后插入S所指結(jié)點(diǎn)，則執(zhí)行（）。A) S

4、->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；8. 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)是S結(jié)點(diǎn)的直接前驅(qū)。則刪除S結(jié)點(diǎn)的語(yǔ)句序列為 。I. P->next = S ;free(P)II. P->next = P->next->next; free(S)III. P->next = S->next; free(S) IV. P = P-&

5、gt;next ;free(S)A) I和II正確 B) II和 III正確C) III和IV正確 D) 全部正確9. 已知L是帶表頭結(jié)點(diǎn)的單鏈表，則刪除首元結(jié)點(diǎn)的語(yǔ)句序列是（ ）。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)10. 已知L是一帶有頭結(jié)點(diǎn)的單鏈表的頭指針，則該單鏈表為空的條件是 。11. 已知P結(jié)點(diǎn)是某雙向鏈表

6、的中間結(jié)點(diǎn)，則刪除P結(jié)點(diǎn)的語(yǔ)句序列是 ， ，free(P);12.試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LOCATE(L,X)13. 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH(L)14. 試寫一算法，在無(wú)頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作INSERT(L,i,b)，并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。15. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素。同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析時(shí)間復(fù)雜度。16. LA和LB是兩個(gè)帶有頭結(jié)點(diǎn)且元素以值遞增有序排列。寫一算法，將LA與

7、LB合并成一個(gè)有序鏈表LC。第三章 棧和隊(duì)列1. 設(shè)將整數(shù)1，2，3，4，5依次進(jìn)棧，最后都出棧，出?？梢栽谌魏螘r(shí)刻(只要棧不空)進(jìn)行，則出棧序列不可能的是（ ）。A) 32415 B) 45231 C) 32145 D) 453212. 在棧中由頂向下已存放元素c, b, a 在第4個(gè)元素d入棧前，棧中元素可以出棧，則不可能的出棧序列是A) dcba B) cbda C) cdba D) cadb3. 若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)3次進(jìn)行退棧操作，則不可能得到的出棧序列是（）。AdcebfaBcbdaefCbdcaefDafedcb4. 設(shè)有

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

9、ont B）(Q.rear+1) % maxsizeQ.frontC）Q.rear0 D）Q.front08. 在具有m個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是（ ）A. front= (rear1) % m B. front1= rearC. front= rear D. rear= m9. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是（ ）A)front= (rear1) % n B)front1=rearC)front=rear D)front=010. 循環(huán)隊(duì)列用數(shù)組

10、A0m-1存放其數(shù)據(jù)元素。設(shè)front指向其實(shí)際的隊(duì)頭，rear指向其實(shí)際隊(duì)尾的下一個(gè)位置，則當(dāng)前隊(duì)列中的數(shù)據(jù)元素有 個(gè)。11.寫出下列程序段的輸出結(jié)果（棧的元素類型SelemType為char）void main() Stack S; char x,y; InitStack(S); x='c'y='k' Push(S,x); Push(S,'a'); Push(S,y); Pop(S,x);Push(S,'t');Push(S,x); Pop(S,x);Push(S,'s'); while(!StackEmpty

11、(S)Pop(S,y);printf(y); printf(x);12.寫出以下程序段的輸出結(jié)果（隊(duì)列中的元素類型QelemType為char）void main() Queue Q; InitQueue(Q); char x='e'y='c' EnQueue(Q,'h'); EnQueue(Q,'r');EnQueue(Q,y); DeQueue(Q,x);EnQueue(Q,x); DeQueue(Q,x);EnQueue(Q,'a'); while(!QueueEmpty(Q) DeQueue(Q,y); p

12、rintf(y); printf(x);第四章 串1.在串的運(yùn)算中，StrLength(Concat (aa，bb)的返回值為 A) 0B) 8C) 6D) 42設(shè)s1”I have_”，s2”a dream”，則strcat(s1, s2)的值是 ，SubString(s1,4,3)的值是 。3. 設(shè)s1”I am a student”，s2”a student”，則Index(s1,s2)的值是 。第五章 數(shù)組和廣義表1. 假設(shè)有二維數(shù)組A5×6，每個(gè)元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的基地址為1000，則數(shù)組A的最后一個(gè)元素a45的第一個(gè)字節(jié)的地址是 ；按行存儲(chǔ)

13、時(shí)，元素a14的第一個(gè)字節(jié)的地址是 。2. 已知二維數(shù)組A1.7，1.7按列存放，其起始存儲(chǔ)位置為100，每個(gè)元素占用4個(gè)字節(jié)，則元素A4,6的第一個(gè)字節(jié)的地址為 。A）204 B）252 C）208 D）2563. 一個(gè)非空廣義表的表頭（）。A一定是子表 B一定是原子C不能是子表 D可以是原子，也可以是子表4. 設(shè)廣義表L（(a,b),c,()），則head(L) ，tail(L) 。5. 求下列廣義表(1)A=(p,h,w) ，對(duì)A求表頭和表尾(2)B=(b,k,p,h)，對(duì)B求表頭和表尾(3)C=(a,b),(c,d)，對(duì)C求表頭(4)C=(a,b),(c,d)，對(duì)C求表尾(5) 對(duì)(3

14、)的結(jié)果求表尾(6) 對(duì)(4)的結(jié)果求表頭(7) 對(duì)(5)的結(jié)果求表尾(8) 對(duì)(6)的結(jié)果求表頭第六章 樹和二叉樹一、 單選或填空題1. 已知完全二叉樹的第7層上有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多是 A) 73 B) 63 C) 235 D) 2452. 300個(gè)結(jié)點(diǎn)的完全二叉樹的葉結(jié)點(diǎn)有 個(gè)。3一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為_。A）11 B）10 C）11至1025之間 D）10至1024之間4. m叉樹的第i層至多有 個(gè)結(jié)點(diǎn)5. 將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的節(jié)點(diǎn)的右孩子編號(hào)為（）。ABCDEFA99

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

16、GD D)不能確定10. 將一棵樹t 轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹h，則t 的后根遍歷是h 的A）先序遍歷 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. 某二叉樹層序序列為abcdefghij，中序序列為bgdhjaecif。（1）畫出該二叉樹；（2）畫出該二叉樹的后序后繼線索樹；（3）畫出該二叉樹對(duì)應(yīng)的樹或森林。2. 一棵二叉樹的先序、中序和后序序列分別如下，其中有部分未給出。 先序：_B_EHI_FG_K 中序：D_HEIA

17、_CJG_ 后序：_H_EBF_KG_A （1）試求出空格處的結(jié)點(diǎn)字符； （2）畫出該二叉樹；（3）畫出與該二叉樹對(duì)應(yīng)的樹或森林。3. 已知某通訊用電文僅有A、B、C、D、E、F六個(gè)字符構(gòu)成，其出現(xiàn)的頻率分別為23，5，14，8，25，7，請(qǐng)首先建立哈夫曼樹，然后給出六個(gè)字符的哈夫曼編碼（注：建立哈夫曼樹時(shí)權(quán)值小的為左子樹，權(quán)值大的為右子樹）。第七章一 單選或填空題1. 若某有向圖的鄰接矩陣A只有0和1兩種元素，其中aij1表示有向圖中存在弧<i,j>，則編號(hào)為i頂點(diǎn)的入度可用 表示。A) 鄰接矩陣中第i行元素之和 B) 鄰接矩陣中第i列元素之和 C) 鄰接矩陣中對(duì)角線元素之和 D

18、) 以上均不正確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)中共有（）零元素。AeB2eCn2-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é)

19、點(diǎn)的無(wú)向圖中，其邊數(shù)最多為 。8. 對(duì)于具有n個(gè)結(jié)點(diǎn)的連通圖，它的最小生成樹中有 條邊。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）最短回路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

20、-網(wǎng)。則V8的最早發(fā)生時(shí)間是 。二、解答題1. 已知某無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示，求解下列問(wèn)題：（1）畫出它的無(wú)向圖；（2）畫出它的的鄰接矩陣存儲(chǔ)結(jié)構(gòu)；（3）從頂點(diǎn)A出發(fā)，畫出其廣度優(yōu)先生成樹。0 A 1 41 B 0 2 52 C 1 3 43 D 2 54 E 0 2 55 F 1 3 42. 已知無(wú)向帶權(quán)圖G的鄰接矩陣如下所示。（1）從頂點(diǎn)a出發(fā)，求其深度優(yōu)先生成樹； （2）從頂點(diǎn)a出發(fā)，根據(jù)普里姆算法構(gòu)造最小生成樹，過(guò)程在下面的圖(1)至(5)中畫出。（3）給出鄰接表存儲(chǔ)結(jié)構(gòu)；3. 對(duì)于如下圖所示的帶權(quán)有向圖，求解關(guān)鍵路徑, 計(jì)算各事件（頂點(diǎn)）的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，各活動(dòng)

21、（弧）的最早開始時(shí)間和最遲開始時(shí)間。請(qǐng)?zhí)顚懺诖痤}紙的表格中。bbdg64521187244acdefhk表1 計(jì)算各事件（頂點(diǎn)）的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，請(qǐng)?zhí)顚懺诒?的空白處。頂點(diǎn)abcdefghkve06457151418vl0810161418表2 計(jì)算各活動(dòng)（?。┑淖钤玳_始時(shí)間和最遲開始時(shí)間，請(qǐng)?zhí)顚懺诒?的空白處?；bacadbecedfegehfhgkhke00064571514l38101614 4.對(duì)于右圖，求解下列問(wèn)題：（1）寫出該圖的鄰接矩陣；（2）寫出全部拓?fù)渑判蛐蛄?；?）從頂點(diǎn)V1出發(fā)，給出深度優(yōu)先遍歷生成樹；（4）按照迪杰斯特拉算法，求V1結(jié)點(diǎn)到各點(diǎn)的最短路徑，填

22、寫表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的有序表，使用折半查找的方法，查找第8個(gè)元素時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。2. 已知一個(gè)長(zhǎng)度為16的有序表，使用折半查找的方法，查找一個(gè)不存在的元素，則所需進(jìn)行的關(guān)鍵字比較次數(shù)最多是 。A4B5C6D73. 在二叉排序樹中，關(guān)鍵字值最大的結(jié)點(diǎn)A）左指針一定為空 B）右指針一定為空C）左右指針均為空 D）左右指針均不為空4 對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路

23、徑的序列是（ ） 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樹是一種平衡的二叉排序樹，樹中任一結(jié)點(diǎn)的A左、右子樹的高度均相同 B. 左、右子樹高度差的絕對(duì)值不超過(guò)1C. 左子樹的高度均大于右子樹的高度 D. 左子樹的高度均小于右子樹的高度6. 以下關(guān)于查找方法的描述中，錯(cuò)誤的是 A) 平衡二叉樹一定也是二叉排序樹。B) 有序表的折半查找判定樹是二叉排序樹。C) 中序遍歷一棵二叉排序樹，可以得到其數(shù)據(jù)元素的升序排列。D) 后序遍歷一棵二叉排序樹，可以得到其數(shù)據(jù)元素的降序排列。7.

24、下列二叉排序樹中，滿足平衡二叉樹定義的是（ ）8、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ ）A、13，48 B、24，48 C、24，53 D、24，909. 從理論上講，將數(shù)據(jù)以何（）結(jié)構(gòu)存放，則查找一個(gè)數(shù)據(jù)所用時(shí)間不依賴于數(shù)據(jù)個(gè)數(shù)n.A）二叉查找數(shù) B）鏈表 C）二叉樹D）哈希表10 為提高散列（Hash）表的查找效率，可以采取的正確措施是（ ）、增大裝填（載）因子 、設(shè)計(jì)沖突（碰撞）少的散列函數(shù)、處理沖突（碰撞）時(shí)避免產(chǎn)生聚集（堆積）現(xiàn)象A僅 B僅 C僅、 D僅、二、解答題1. 設(shè)記錄關(guān)鍵字集

25、合key=33,20,53,55,23,38,40,65，選取哈希函數(shù)為H(x)=key mod 11；解決沖突的方法為“線性探測(cè)法”。（1）請(qǐng)按上述條件將key中各值依次填入下表中：（2） 求該哈希表查找成功和查找不成功情況下的平均查找長(zhǎng)度。2. 設(shè)記錄關(guān)鍵字集合key=32,13,49,55,22,39,20，選取哈希函數(shù)為H(x)=key mod 7；解決沖突的方法為“鏈地址法”。（1）畫出所構(gòu)造的哈希表；（2）求該哈希表查找成功和查找不成功情況下的平均查找長(zhǎng)度。3. 設(shè)記錄關(guān)鍵字集合key=32,13,49,55,22,39,20，解決沖突的方法為“線性探測(cè)法”，要求裝填因子為：0.7

26、，哈希函數(shù)的形式為H(x)=key mod P，散列表的地址從0開始。（1）構(gòu)造哈希函數(shù)；（2）畫出所構(gòu)造的哈希表；（2）求該哈希表查找成功和查找不成功情況下的平均查找長(zhǎng)度。4. 選取哈希函數(shù)H(key)=(3*key) mod 11。用開放定址法處理沖突，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. 從空樹開始，依次插入13，34，51，24，62，43，75，18，畫出建立2-3樹后的狀態(tài)，并分

27、別畫出刪除43、24后的2-3樹狀態(tài)。6. 畫出對(duì)長(zhǎng)度為12的有序表進(jìn)行折半查找的判定樹，并求其等概率查找成功時(shí)的平均查找長(zhǎng)度。第十章一、 單選或填空題1. 數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組用不同排序方法進(jìn)行一趟排序后的結(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

28、快速排序；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，16，88第三趟：2，5，10，12，16，88則采用的排序方法可能是( )A.冒泡排序法 B.希爾排序法 C.歸并排序法 D.基數(shù)排序法3. 若一組記錄的排序碼為(45，78，56，36，40，87)，則初始小根堆的結(jié)果為A36，45，56，78，40，87B87，