數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及參考答案

1、中南大學(xué)網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)一、填空:1.設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_次，至多需要比較_次。2.設(shè)二叉排序樹(shù)的高度為h，則在該樹(shù)中查找關(guān)鍵字key最多需要比較_次。3.設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_個(gè)。4.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：_、_和_。5.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。6.向一棵B_樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度_。7.在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的

2、時(shí)間復(fù)雜度為_(kāi)，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)。8.在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。9.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，總結(jié)點(diǎn)數(shù)是_。1. 評(píng)卷人2. 得分3.4.10.一棵樹(shù)T采用二叉鏈表存儲(chǔ)，如果樹(shù)T中某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則在二叉鏈表BT中所對(duì)應(yīng)的結(jié)點(diǎn)一定_。11.3.已知數(shù)組A1010為對(duì)稱矩陣，其中每個(gè)元素占5個(gè)單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5，6對(duì)應(yīng)的地址是_。12.在有n個(gè)結(jié)點(diǎn)的無(wú)向圖中，其邊數(shù)最多為_(kāi)。13.取出廣義表A=(x,(a,b,c,d)中原子x的函數(shù)是_。14.對(duì)矩陣采用壓縮存儲(chǔ)是為了_ _。15.帶頭

3、結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是_。16.設(shè)線性表中元素的類型是實(shí)型，其首地址為1024，則線性表中第6個(gè)元素的存儲(chǔ)位置是 。17.對(duì)于順序存儲(chǔ)的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行 運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行 運(yùn)算時(shí)，可能發(fā)生棧的下溢。18.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 ，另一個(gè)指向 。19.由一棵二叉樹(shù)的前序序列和 可唯一確定這棵二叉樹(shù)。20.折半查找的存儲(chǔ)結(jié)構(gòu)僅限于_ _，且是_ _。21.對(duì)于一個(gè)順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi),在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)。22.在稀疏距陣所對(duì)應(yīng)的三元組線形表中，每個(gè)三元組元素按_為主序，_為輔序的次序排列。23.

4、中綴表達(dá)示3+X*（2.4/5-6）所對(duì)應(yīng)的后綴表達(dá)示為_(kāi)。24.在一棵高度為h的3叉樹(shù)中，最多含有_結(jié)點(diǎn)。25.分析下面算法（程序段），給出最大語(yǔ)句頻度 ，該算法的時(shí)間復(fù)雜度是_ _。for (i=0;i<n;i+) for (j=0;j<n; j+) Aij=0;26.空串是_ _，其長(zhǎng)度等于 。27.一個(gè)圖的 表示法是唯一的，而 表示法是不唯一的。28.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s (值為e)所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=head;while (q->next!=p) q=q->next;s= new Node; s->data=e;q->

5、next= ; /填空s->next= ; /填空29.在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q= p->next;p->next= _ _; /填空delete ; /填空30.兩個(gè)串相等的充分必要條件是_。31.二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A00的存儲(chǔ)地址是200，則A612的地址是_。32.二維數(shù)組A10.205.10采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則A189的地址是_。33.求下列廣義表操作的結(jié)果：(1) GetTailGetHead(a,b),(c,d);(2)

6、 GetTailGetHeadGetTail(a,b),(c,d)34.已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是_。35.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是_。36.在利用快速排序方法對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行快速排序時(shí)，遞歸調(diào)用而使用的棧所能達(dá)到的最大深度為_(kāi)，共需遞歸調(diào)用的次數(shù)為_(kāi)，其中第二次遞歸調(diào)用是對(duì)_一組記錄進(jìn)行快速排序。37.在堆排序，快速排序和歸并排序中，若只從存儲(chǔ)空間考慮，則應(yīng)首先選取_方法，其次選取_方法，最后選取_方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取_方法；若只從平均情況下排序最

7、快考慮，則應(yīng)選取_方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取_方法。二、選擇題：1.隊(duì)列的特點(diǎn)是【 】。A.先進(jìn)后出 B.先進(jìn)先出 C.任意位置進(jìn)出 D.前面都不正確2.有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行【 】遍分配與收集。A.n B.d C.r D.n - d 3.在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序【 】。A.都不相同 B.完全相同C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同4.設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為【 】。A.12 B.13 C.14 D.1

8、55.下面關(guān)于廣義表的敘述中，不正確的是【 】。A.廣義表可以是一個(gè)多層次的結(jié)構(gòu) B.廣義表至少有一個(gè)元素C.廣義表可以被其他廣義表所共享 D.廣義表可以是一個(gè)遞歸表6.設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0，一棵深度（高度）為k的滿二叉樹(shù)和同樣深度完全二叉樹(shù)各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是【 】。A.f>=c B.c>f C.f=2k+1-a D.c>sk-17.從L=(apple,pear),(orange,banana)中，取出banana元素的表達(dá)式為【 】。A.head(tail(L) B.head(head(tail(L)C.tail(head(tail(L) D.

9、head(tail(head(tail(L)8.下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是【 】。A.順序結(jié)構(gòu) B.鏈接結(jié)構(gòu) C.索引結(jié)構(gòu) D.Hash結(jié)構(gòu)9.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由【 】。A.實(shí)體 B.域 C.數(shù)據(jù)項(xiàng) D.字段10.對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德（FloyD）算法求每一對(duì)頂之間的最短路徑的時(shí)間復(fù)雜度是【 】。A.O(1) B.O(n) C.O(n) D.O(n3)11.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為【 】。A.O(1) B.O(log2 n) C.O(n) D.O(n2)12.哈夫曼樹(shù)中一定不存在【 】。A.度為0的結(jié)點(diǎn) B.度

10、為1的結(jié)點(diǎn) C.度為2的結(jié)點(diǎn) D.帶權(quán)的結(jié)點(diǎn)13.下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？【 】A.存儲(chǔ)密度大 B.插入和刪除運(yùn)算方便C.獲取符合某種條件的元素方便 D.查找運(yùn)算速度快14.有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在600(10)，A33存放位置在678(10)，每個(gè)元素占一個(gè)空間，問(wèn)A23(10)存放在什么位置？（腳注(10)表示用10進(jìn)制表示，m>3）【 】。A.658 B.648 C.633 D.65315.列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是【 】。A.若一個(gè)葉子是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B.若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷最后

11、一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)C.若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D.若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)16.層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為【 】。A.2k-1 B.2k+1 C.2K-1 D.2k-117.線性表進(jìn)行二分法查找，其前提條件是【 】。A.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 B.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序18.n個(gè)記錄進(jìn)行堆排序，所需要的輔助

12、存儲(chǔ)空間為【 】。A.O(1og2n) B.O(n) C.O(1) D.O(n2)19.線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%7作為散列函數(shù)，則散列地址為0的元素有【 】個(gè)。A.1 B.2 C.3 D.420.列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是【 】。A.數(shù)組是不同類型值的集合 B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C.樹(shù)是一種線性結(jié)構(gòu)D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法21.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？【 】A.有向圖 B.隊(duì)列 C.線索二叉樹(shù) D.B樹(shù)22.在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入

13、一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下【 】語(yǔ)句序列。A.p=q; p->next=q B.p->next=q; q->next=pC.p->next=q->next; p=q; D.q->next=p->next; p->next=q;23.【 】不是隊(duì)列的基本運(yùn)算。A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素 B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空 D.讀取隊(duì)頭元素的值24.若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為【 】。A. i B. n=i C. n-i+1 D.不確定25.棧的特點(diǎn)是【 】

14、，隊(duì)列的特點(diǎn)是【 】。A.先進(jìn)先出 B.先進(jìn)后出26.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作【 】。A.連接 B.模式匹配 C.求子串 D.求串長(zhǎng)27.二維數(shù)組A中，每個(gè)元素Aij的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為【 】。A.SA+141 B.SA+180 C.SA+222 D.SA+22528.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是【 】。A. bdgcefha B. gdbecfha C. bdgae

15、chf D. gdbehfca29.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊【 】。A.只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的部分結(jié)點(diǎn) D.只有左子樹(shù)上的所有結(jié)點(diǎn)30.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有【 】條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 831.二分查找和二叉排序樹(shù)的時(shí)間性能【 】。A.相同 B.不相同32.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【 】。A.O（n2） B.O(nlog2n) C.O(n) D.O(log2n)33.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 】。A.插入排序

16、B.選擇排序 C.快速排序 D.歸并排序34.下述幾種排序方法中，要求內(nèi)存量最大的是【 】。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序35.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作【 】。A.連接 B.模式匹配 C.求子串 D.求串長(zhǎng)36.二維數(shù)組A中，每個(gè)元素Aij的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為【 】。A. SA+141 B. SA+180 C. SA+222 D. SA+22537.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaec

17、hf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是【 】。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca38.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊【 】。A.只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的部分結(jié)點(diǎn) D.只有左子樹(shù)上的所有結(jié)點(diǎn)39.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有【 】條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 840.二分查找和二叉排序樹(shù)的時(shí)間性能【 】。A.相同 B.不相同 C.可能相同 D.不確定41.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【 】。A.O(n2 ) B.O(

18、nlog2 n) C.O(n) D.O(log2n)42.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 】。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序43.下面的序列中【 】是大頂堆。A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2 C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,144.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下【 】方面的內(nèi)容。A.健壯性和可讀性 B.并行性 C.正確性 D.時(shí)空復(fù)雜度45.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行【 】。A.p->next=HL->next;

19、 HL->next=p B.p->next=HL; HL=pC.p->next=HL; p=HL D.HL=p; p->next=HL46.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？【 】A.經(jīng)常需要隨機(jī)地存取元素 B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 D.表中元素的個(gè)數(shù)不變47.一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是【 】。A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 348.每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是【 】。A.冒泡排序 B.簡(jiǎn)單選擇排序 C.希爾排序 D

20、.直接插入排序49.采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度【 】。A.低于鏈接法處理沖突 B.高于鏈接法處理沖突C.與鏈接法處理沖突相同 D.高于二分查找50.若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為【 】參數(shù)。A.值 B.函數(shù) C.指針 D.引用51.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的【 】。A.行號(hào) B.列號(hào) C.元素值 D.非零元素個(gè)數(shù)52.快速排序在最壞情況下的時(shí)間復(fù)雜度為【 】。A.O(log2n) B.O(nlog2n) C.O(n) D.O(n2)53.從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為【 】。A.O(n) B.O

21、(1) C.O(log2n) D.O(n2)54.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為【 】。A.O(log2n) B.O(1) C.O(n2) D.O(n)55.設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=【 】。A.Nl+N2+Nm B.l+N2+2N3+3N4+(m-1)NmC.N2+2N3+3N4+(m-1)Nm D.2Nl+3N2+(m+1)Nm56.二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按

22、行存放時(shí)，數(shù)組元素A74的起始地址為【 】。A. SA+141 B. SA+144 C. SA+222 D. SA+22557.如果某二叉樹(shù)的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹(shù)的后序?yàn)椤?】。A.uwvts B.vwuts C.wuvts D.wutsv58.深度為5的二叉樹(shù)至多有【 】個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 1059.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的【 】倍。A. 1/2 B. 1 C. 2 D. 4 60.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【 】。A. n B. n/2 C. (n+1)/

23、2 D. (n-1)/261.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【 】。AO（n2） B. O(nlog2n) C. O(n) D. O(log2n)62.下述幾種排序方法中，要求內(nèi)存量最大的是【 】。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序63.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為【 】。A.希爾排序 B.起泡排序 C.插入排序 D.選擇排序64.對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為【 】的值除以9。A. 20 B.

24、18 C. 25 D. 2265.在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的【 】。A.入度 B.出度 C.入度與出度之和 D.入度與出度之差66.在基于排序碼比較的排序算法中，【 】算法的最壞情況下的時(shí)間復(fù)雜度不高于O(n10g2n)。A.起泡排序 B.希爾排序 C.歸并排序 D.快速排序67.當(dāng)?shù)闹递^小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有【 】的查找速度。A.較慢 B.較快 C.相同 D.不清楚68.設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過(guò)1.5，則散列表項(xiàng)應(yīng)能夠至少容納【 】個(gè)表項(xiàng)。 (設(shè)搜索成功的平均搜索長(zhǎng)度為Snl1+l(1一)2，其

25、中為裝填因子)A. 400 B. 526 C. 624 D. 676 69.堆是一個(gè)鍵值序列k1,k2,.kn,對(duì)I=1,2,.|_n/2_|,滿足【 】A. kik2ik2i+1 B. ki<k2i+1<k2iC. kik2i且kik2i+1(2i+1n) D. kik2i 或kik2i+1(2i+1n) 70.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上【 】 A.操作的有限集合 B.映象的有限集合 C.類型的有限集合 D.關(guān)系的有限集合71.下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹(shù)是【 】72.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)【 】A.其形態(tài)不

26、一定相同，但平均查找長(zhǎng)度相同B.其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C.其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同D.其形態(tài)均相同，平均查找長(zhǎng)度也都相同73.ISAM文件和VSAM文件的區(qū)別之一是【 】A.前者是索引順序文件，后者是索引非順序文件B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)D.前者的存儲(chǔ)介質(zhì)是磁盤(pán)，后者的存儲(chǔ)介質(zhì)不是磁盤(pán)74.下列描述中正確的是【 】A.線性表的邏輯順序與存儲(chǔ)順序總是一致的B.每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找C.數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的內(nèi)容D.選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問(wèn)題的

27、關(guān)鍵步驟75.下面程序段的時(shí)間復(fù)雜度是【 】I=s=0While(s<n)I+;s+=I;A.O(1) B.O(n) C.O(log2n) D.O(n2)三、計(jì)算與算法應(yīng)用題：1.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。2.一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有一部分未顯示出來(lái)。試求出空格處

28、的內(nèi)容，并畫(huà)出該二叉樹(shù)。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A3.畫(huà)出下列樹(shù)對(duì)應(yīng)的二叉樹(shù)，并寫(xiě)出其先根遍歷序列：BDFCAEG4.將關(guān)鍵字序列為54，29，37，86，71，91，8，31，44，26進(jìn)行歸并排序，寫(xiě)出各趟詳細(xì)過(guò)程。5.試列出如下圖中全部可能的拓?fù)渑判蛐蛄小?.設(shè)某通信系統(tǒng)使用A，B ，C，D，E，F(xiàn)，G，H八個(gè)字符，他們出現(xiàn)的概率w=5，29，7，8，14，23，3，11，試構(gòu)造對(duì)應(yīng)的哈夫曼樹(shù)（請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于右子樹(shù)樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）。7.給定表（119，14，22，1，66，21，83，27，56，13

29、，10）,請(qǐng)按表中元素的順序構(gòu)造一棵平衡二叉樹(shù)，并求其在等概率情況下查找成功的平均長(zhǎng)度。8.已知一個(gè)有向圖的頂點(diǎn)集V和邊集G分別為：V=a,b,c,d,e,f,g,hE=<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>假定該圖采用鄰接矩陣表示，則分別寫(xiě)出從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。9.設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H（h）= k%13，給定的關(guān)鍵碼序列為19，14，2

30、3，01，68，20，84，27。試畫(huà)出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。0 1 2 3 4 5 6 7 8 9 10 11 1210.對(duì)7個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為1,2,3,4,5,6,7，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列；(2)對(duì)所舉序列進(jìn)行快速排序，寫(xiě)出排序過(guò)程。11.如圖所示二叉樹(shù)，回答下列問(wèn)題。12.畫(huà)出在一個(gè)初始為空的AVL樹(shù)中依次插入3,1,4,6,9,8,5,7時(shí)每一插入后AVL樹(shù)的形態(tài)。若做了某種旋轉(zhuǎn)，說(shuō)明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的AVL樹(shù)中刪去根結(jié)點(diǎn)后的結(jié)果。13.已知一組記錄的排序碼為（

31、46 ， 79 ， 56 ， 38 ， 40 ， 80 ， 95 ， 24 ），寫(xiě)出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。 14.一個(gè)線性表為 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36 ），設(shè)散列表為 HT0.12 ，散列函數(shù)為 H （ key ） = key % 13 并用線性探查法解決沖突，請(qǐng)畫(huà)出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。 15.已知一棵二叉樹(shù)的前序遍歷的結(jié)果序列是 ABECDFGHIJ ，中序遍歷的結(jié)果是 EBCDAFHIGJ ，試寫(xiě)出這棵二叉樹(shù)的后序遍歷結(jié)果。16.假定對(duì)線性表(38，25，74，52，

32、48，65，36)進(jìn)行散列存儲(chǔ)，采用H(K)=K9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則計(jì)算對(duì)應(yīng)的平均查找長(zhǎng)度。四、閱讀下列算法，分析它的作用：1.int AA(LNode *HL , ElemType x) int n=0; LNode *p=HL;while (p!=NULL) if (p->data= =x) n+; p=p->next;return n;對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：2.int AA(LNode *HL , ElemType x) int n=0; LNode *p=HL;while (p!=NULL) if (p-&g

33、t;data= =x) n+; p=p->next;return n;對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：3.假定從鍵盤(pán)上輸入一批整數(shù)，依次為：78 63 45 30 91 34 1，請(qǐng)寫(xiě)出輸出結(jié)果。# include < iostream.h># include < stdlib.h >const int stackmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize; int top;# include “stack.h”void main 【 】

34、stack a; initstack(a); int x; cin >>x; while (x! = -1) push (a, x ); cin >>x;while (!stackempty (a) cout <<pop (a) <<” ;cout <<end1;該算法的輸出結(jié)果為：_.4.讀下述算法，說(shuō)明本算法完成什么功能。template <calss type > void BinTree <Type> ：unknown (BinTreeNode<Type>*t) BinTreeNode<

35、; Type> *p =t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); / 類定義const int MAX=20;typedef char ElemType ;class Sqstack private:ElemType elem MAX;int top ; public:Sqstack()top=0;ElemType pop();void push(ElemType x);

36、/.; ;該算法的功能是：_5.閱讀下列算法，說(shuō)明該算法的作用。void Sqstack:push(ElemType x ) if ( top=MAX-1 )cout<<”n 滿！”；else top+; elemtop=x; / push struct Snode /結(jié)點(diǎn)結(jié)構(gòu) char data; Snode *next ; ;class Link /鏈表類 private:Snode *Head; public:Link ()Head =NULL;void creat();void output();/.;6.有如下圖所示單鏈表，經(jīng)過(guò)output（）算法處理后，單鏈表發(fā)生了什么

37、變化 ？畫(huà)出處理后的單鏈表圖示。void Link :output() p=Head->next; while( p !=NULL) cout<<”n data=”<<p->data ; p=p->next; /output aHeadbced7.閱讀下列算法，說(shuō)明該算法的作用。int LinkList:sum【 】 int x;NodeType *p;p=Head->next; while(p!=NULL) x+; p=p->next;return x; / pop 8.讀下述算法，說(shuō)明本算法完成什么功能。 void Btree :ino

38、rdern( bnode *p, int &n ) if ( p!=NULL) inordern( p->lch, n); if ( p->lch=NULL && p->rch=NULL) n+; inordern( p->rch, n); / inordern9.void AD(Lnode* & HL) Insert(HL,30); Insert(HL,50); Delete(HL,26); Delete(HL,55); 假定調(diào)用該算法時(shí)以HL為表頭指針的單鏈表中的內(nèi)容為（15，26，48，55），則調(diào)用返回后該單鏈表中的內(nèi)容為：_。1

39、0.void AI(adjmatrrix GA,int i,int n) cout<<i<</ 類定義const int MAX=20;typedef char ElemType ;class Sqstack private:ElemType elem MAX;int top ; public:Sqstack()top=0;ElemType pop();void push(ElemType x);/.; ; vistedi=true; for(int j=0;j<n;j+)if(GaIj! =0&& GAij! =MaxValue&&

40、; ! visitedj) AI(GA,j,n);該算法的功能為：_。11.閱讀下列算法，說(shuō)明該算法的作用。ElemTtype Sqstack:pop【 】 ElemType x; if ( top=0 ) x=-999; else x = elemtop; top-;return x; / pop 12.有如下圖所示單鏈表，經(jīng)過(guò)reverse 算法處理后，單鏈表發(fā)生了什么變化 ？畫(huà)出處理后的單鏈表圖示。struct Snode /結(jié)點(diǎn)結(jié)構(gòu) char data; Snode *next ; ;class Link /鏈表類 private:Snode *Head; public:Link ()

41、Head =NULL;void creat();void reverse ();void output();/.;void Link :reverse() Snode *p, *q ; p= Head ->next; Head ->next=NULL; while( p !=NULL) q=p->next ; p->next= Head ->next; Head >next=p; p=q; aHeadbced / reverse 13.下列函數(shù)是二叉排序樹(shù)的什么算法？如果K值為5，針對(duì)下圖所示二叉樹(shù)，運(yùn)行下列算法，輸出是什么？比較幾次得到結(jié)果？Void Bs

42、tree:Search( KeyType K) int flag = 0; BstNode *q=root, *p = NULL; while(q!=NULL)&&(flag=0) if(q->key=K) flag = 1; else if ( K<q->key) p = q; q = q->lch; else p = q; q = q->rch; if(flag = 0) cout<<"n 查找失敗，無(wú)此結(jié)點(diǎn)！n" else cout<<"n 查找成功，找到："<<q-

43、>key<<endl;7852492914.void AA (LNode * HL,const ElemType & item) LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL; while ( p->next!=HL ) p=p->next;newptr->next=HL;p->next=newptr;對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：15.void BB(List &L)int i=0;while (i<L.size)int j=i+1;while (j<L.size)if(L.listj = =L.list)for (int k=j+1;k<L.size;k+)L.listk-1=L.listk;L.size-;else j+;i+;以上算法的功能為：16.void CC(BTreeNode * & BST )ElemType a6 =45，23，78，35，77，25；BST=NULL；for( int i=0,i<6;i+)Insert(BST , ai);調(diào)用該算法后，生成的二叉搜索數(shù)的中序序列為：1