數(shù)據(jù)結(jié)構(gòu)(第二版)模擬測(cè)試題4套及答案

1、試卷B一、選擇題（本題共20分,每題2分）1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ） 。 A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) C. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2. 下列程序段的時(shí)間復(fù)雜度是（ ）count=0; for(k=1;k=n;k*=2) for(j=1;j=n;j+) count+; A.O(nlog2n) B.O(n) C.O(log2n) D.O(n2) 3. 以下描述錯(cuò)誤的是：（ ）A. 線(xiàn)性表是n個(gè)數(shù)據(jù)元素的有限非空集合。B. 棧和隊(duì)列都是操作受限的線(xiàn)性表。C. 串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列。D. 非空棧中的棧頂指針

2、top始終指向棧頂元素的下一個(gè)位置。4. 若采用少用一個(gè)隊(duì)列空間的方法來(lái)區(qū)分隊(duì)滿(mǎn)隊(duì)空兩種狀態(tài)，則判定一個(gè)順序循環(huán)隊(duì)列 Q（最大隊(duì)列長(zhǎng)度MAXSIZE）為滿(mǎn)隊(duì)列的條件是( )。A. Q.front=Q.rear B. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZE D. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉樹(shù)的定義，具有 3 個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ ）種。 A. 3 B. 4 C. 5 D. 6 6. 設(shè)矩陣A（如下圖所示）是一個(gè)對(duì)稱(chēng)矩陣，為了節(jié)省存儲(chǔ)，將其下三角（包括對(duì)角線(xiàn)）部分按行序存放在一維數(shù)組 Bn(n+1)

3、/2中，對(duì)下三角部分中任一元素 ai,j(ij)，在一維數(shù)組 B 的下標(biāo)位置k的值是（ ）。A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 7. 有一個(gè)有序表為5, 18，23, 33, 42, 54,56,78，當(dāng)折半查找56時(shí)，經(jīng)過(guò)（ ）次比較后查找成功。A. 1 B. 2 C. 3 D. 88. 一組記錄的排序關(guān)鍵字為（39，19，36，68，35，84），則利用快速排序方法進(jìn)行正序排列時(shí)，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。A. 35，36，19，39，68，84 B. 19，35，36，39，68，84

4、C. 35，19，36，39，84，68 D. 35，19，36，39，68，849.若對(duì)下圖a中的二叉樹(shù)進(jìn)行先序線(xiàn)索化，則結(jié)點(diǎn)x的左、右線(xiàn)索指向的結(jié)點(diǎn)分別是（ ）A. e,c B. e,a C. d,c D. b,abdxeac (a) (b)10. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如上圖b所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn) v1 出發(fā)，所得到的頂點(diǎn)序列是（ ）。 A. v1，v2，v3，v5，v4 B. v1，v3，v2，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2二、填空題（本題共 20 分，每題2分）1. 設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n，則圖G最多有_

5、條邊2. 在一個(gè)長(zhǎng)度為n（n1）的順序表中的第i個(gè)元素（1in）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。3. 在一個(gè)雙向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)，應(yīng)執(zhí)行的操作序列為_(kāi)。4. 有一棵樹(shù)如右圖所示，回答下面問(wèn)題： 樹(shù)的度：_；樹(shù)的深度：_； 結(jié)點(diǎn)C的孩子結(jié)點(diǎn)：_；結(jié)點(diǎn)F的祖先結(jié)點(diǎn)：_。5. 一棵完全二叉樹(shù)的第5層有5個(gè)結(jié)點(diǎn)，則這棵完全二叉樹(shù)共有_個(gè)結(jié)點(diǎn)。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0ABCDE6. 已知無(wú)向圖G的鄰接矩陣如下圖所示，則圖G是_圖(連通/非連通)，頂點(diǎn)A的度為_(kāi)。7. 在一棵平衡二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的左子樹(shù)深度與右子樹(shù)深度之差

6、可以是 。8若一組記錄的關(guān)鍵字序列為（50，40，95，20，15，70，60，45，80），要對(duì)其按關(guān)鍵字從小到大進(jìn)行堆排序時(shí)，則創(chuàng)建的初始堆序列為_(kāi)。9.對(duì)n個(gè)不同的關(guān)鍵字從小到大進(jìn)行冒泡排序，最好情況下，需要經(jīng)過(guò)比較_次將其排好；最壞情況下，需要經(jīng)過(guò)比較_次排好。10. 已知一個(gè)有向圖的邊集為,，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨開(kāi) 。 三、應(yīng)用題（本題共40分，1-4每小題5分，5-6題每小題10分）1. 利用普里姆算法，對(duì)于下面所示的連通圖，從結(jié)點(diǎn)a出發(fā)，構(gòu)造最小生成樹(shù)。 2. 設(shè)給定權(quán)集 w=2，4，3，7，8，9，試構(gòu)造關(guān)于 w 的一棵Huffman樹(shù)，并計(jì)算所構(gòu)造Huffman

7、樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL。3. 已知一棵二叉樹(shù)的中序序列為CBEDAHGIJF，后序序列為CEDBHJIGFA，畫(huà)出該二叉樹(shù)。 4. 設(shè)數(shù)據(jù)集合D=24，13，53，37，90，48，依次取D中各數(shù)據(jù)，構(gòu)造一棵平衡二叉樹(shù)，畫(huà)出構(gòu)造過(guò)程（說(shuō)明平衡旋轉(zhuǎn)的類(lèi)型）及結(jié)果。5. 假設(shè)有一組關(guān)鍵字32，01，23，14，55，20，84，27，68，要求：（1）散列函數(shù)為 H(key) = key % 13，計(jì)算這組關(guān)鍵字的散列地址并填入下表：Key320123145520842768H（key）沖突次數(shù)（2）采用線(xiàn)性探測(cè)法解決沖突，在0-12的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表，將各關(guān)鍵字填入下表：

8、 地址0123456789101112關(guān)鍵字（3）計(jì)算成功查找時(shí)的平均查找長(zhǎng)度ASLS ，要求寫(xiě)出計(jì)算過(guò)程和結(jié)果：ASLS =6. 下圖是一個(gè)有7個(gè)頂點(diǎn)的網(wǎng)圖，邊上的權(quán)值為相鄰兩頂點(diǎn)的距離。使用Dijkstra算法，計(jì)算頂點(diǎn)a到所有其余頂點(diǎn)的最短路徑。計(jì)算過(guò)程和結(jié)果填入下表，要求：(1)從第1步至第6步，每步選擇的頂點(diǎn)填入表格倒數(shù)第二行；（4分）(2)表格中D值在填寫(xiě)時(shí)，請(qǐng)注意存儲(chǔ)兩部分信息：頂點(diǎn)a至其余頂點(diǎn)的“當(dāng)前最短距離”，以及相應(yīng)的路徑頂點(diǎn)信息。將每一步的計(jì)算過(guò)程填入相應(yīng)的位置。（6分）終點(diǎn)從a到各個(gè)終點(diǎn)的D值和最短路徑的求解過(guò)程步驟1步驟2步驟3步驟4步驟5步驟6b距離值頂點(diǎn)序列c距離

9、值頂點(diǎn)序列d距離值頂點(diǎn)序列e距離值頂點(diǎn)序列f距離值頂點(diǎn)序列g(shù)距離值頂點(diǎn)序列篩選頂點(diǎn)終點(diǎn)集S四、算法設(shè)計(jì)題（本題共20分）1. 編寫(xiě)算法，實(shí)現(xiàn)將值為e的元素插入到單鏈表L的第i個(gè)結(jié)點(diǎn)的位置上。(本題10分)單鏈表結(jié)構(gòu)定義如下：typedef struct LNode ElemType data; Struct Lnode *next; Lnode,*LinkList; 2. 試寫(xiě)一個(gè)判別給定二叉樹(shù)是否為二叉排序樹(shù)的算法，設(shè)此二叉樹(shù)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，且樹(shù)中結(jié)點(diǎn)的關(guān)鍵字均不同。（本題10分）參考答案一、選擇題 答案 （本題共20分，每小題2分）1.B 2. A 3.A 4.C 5. C6.D

10、7. C 8.D 9.A 10.B二、填空題 答案 （本體共20分，每小題2分）n(n-1)/2。n-i+1 。p-prior-next=p-next; p -next-prior =p-prior; free(p);3_;4 ，G; A,B20連通圖; 20,1,-1 15,20,60,45,40,70,95,50,80(小頂堆)/ 95,80,70,45,15,50,60,40,20（大頂堆）n-1;n(n-1)/2 a,c,b,d,e 三、應(yīng)用題 答案要點(diǎn)（本題共40分，1-4每小題5分，5-6題每小題10分）1. 最小生成樹(shù)2.解：哈夫曼樹(shù)如圖其帶權(quán)路徑長(zhǎng)度 WPL=72+82+43+

11、24+34+92=80 3. 二叉樹(shù)的結(jié)構(gòu)為：4. 平衡二叉樹(shù)的構(gòu)造過(guò)程及結(jié)果：RL243753904813 132453903748 5.（1）關(guān)鍵字的散列地址并填入下表：（4分）key320123145520842768H(Key)6110137613沖突次數(shù)000100232（2）采用線(xiàn)性探測(cè)法解決沖突，在0-12的散列地址空間列構(gòu)造散列表，（3分） 地址0123456789101112關(guān)鍵字011455276832208423（3）計(jì)算成功查找時(shí)的平均查找長(zhǎng)度ASLS ，要求寫(xiě)出計(jì)算過(guò)程和結(jié)果：（3分）ASLS =(15+21+32+41)/9=17/96.最短路徑： （10分）終點(diǎn)從

12、a到各個(gè)終點(diǎn)的D值和最短路徑的求解過(guò)程步驟1步驟2步驟3步驟4步驟5步驟6b距離值151515151515頂點(diǎn)序列（a,b）（a,b）（a,b）（a,b）（a,b）（a,b）c距離值2頂點(diǎn)序列(a,c)d距離值12121111頂點(diǎn)序列(a,d)(a,d)(a,c,f,d)(a,c,f,d)e距離值1010頂點(diǎn)序列(a,c,e)(a,c,e)f距離值6頂點(diǎn)序列(a,c,f)g距離值161614頂點(diǎn)序列(a,c,f,g)(a,c,f,g)(a,c,f,d,g)篩選頂點(diǎn)cfedgb終點(diǎn)集Sa,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,fe,d,g,b算法設(shè)計(jì)題 （只列

13、出答案要點(diǎn)，可以有不同的答案，酌情給分）1、參考代碼如下：（10分） status ListInsert(LinkList &L,int i,ElemType e)/在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)p=L; j=0;while(p&jnext; +j;if(!p|ji-1) return ERROR;s=(LinkList) malloc (sizeof(LNode);s-data=e;p-next=s;s-next=p-next;2. 主要代碼如下：（10分）算法思路：對(duì)二叉排序樹(shù)來(lái)說(shuō)，其中序遍歷序列為一個(gè)遞增有序序列，因此，對(duì)給定的二叉樹(shù)進(jìn)行中序遍歷，如果始終能保持前一個(gè)

14、值比后一個(gè)值小，則說(shuō)明該二叉樹(shù)是一棵二叉排序樹(shù)。中序遍歷整棵二叉樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)時(shí)將根結(jié)點(diǎn)信息存入一個(gè)數(shù)組中，以用來(lái)比較中序遍歷后序列是否為空。比較數(shù)組元素時(shí)，從下標(biāo)為0的數(shù)組元素開(kāi)始比較，先將下標(biāo)為i=0的ai與下標(biāo)為1的ai+1比較，如果aiai+1，則結(jié)束比較，即該二叉樹(shù)不是二叉排序樹(shù)，否則繼續(xù)比較，直至比較完整個(gè)數(shù)組元素。intIsSearchTree(structBitree*root) if (!root)return1; elseif(!(root-lChild)&!(root-rChild) /左,右子樹(shù)都沒(méi)有 return1; elseif(root-lChild)&!(roo

15、t-rChild) /只有左子樹(shù) if(root-lChild-dataroot-data) return0; /0:不是二叉排序樹(shù) elsereturnIsSearchTree (root-lChild);elseif (root-rChild)&!(root-lChild)/只有右子樹(shù) if(root-rChild-datadata) return0; /0:不是二叉排序樹(shù)elsereturnIsSearchTree(root-rChild);else /左,右子樹(shù)都有 if(root-lChild-dataroot-data)|(root-rChild-datadata) return0

16、; /0:不是二叉排序樹(shù)else return(IsSearchTree(root-lChild)&IsSearchTree(root-rChild);試卷一一、選擇題（本題共30分,每題2分）1. 計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱(chēng)為_(kāi)。A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)結(jié)構(gòu) D. 數(shù)據(jù)類(lèi)型2. 已知一棧的進(jìn)棧序列為：1234，則下列哪個(gè)序列為不可能的出棧序列_。A1234B4321 C2143D41233. 鏈表不具有的特點(diǎn)是_。A. 隨機(jī)訪(fǎng)問(wèn) B. 不必事先估計(jì)所需存儲(chǔ)空間大小C. 插入與刪除時(shí)不必移動(dòng)元素 D. 所需空間與線(xiàn)性表長(zhǎng)度成正比4. 設(shè)InitQueue(Q)、EnQ

17、ueue(Q,e)、DeQueue(Q,e)分別表示隊(duì)列初始化、入隊(duì)和出隊(duì)的操作。經(jīng)過(guò)以下隊(duì)列操作后，隊(duì)頭的值是_InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x)A. a B. b C.NULL D.x5.在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行_。Ap=q-next; p-next=q-next;free(p);Bp=q-next; q-next=p; free(p);Cp=q-next; q-next=p-next; free(p);Dq-next=q-next-next; q-

18、next=q; free(p);6. 一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的地址是_。A110 B108 C100 D1207. 在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線(xiàn)性表中，在其第i個(gè)位置插入一個(gè)新元素時(shí)，需要移動(dòng)元素的次數(shù)是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面關(guān)于線(xiàn)性表的敘述錯(cuò)誤的是_。A. 線(xiàn)性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D. 線(xiàn)性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)9. Push(e)表示e進(jìn)棧，Pop(e)表示退

19、棧并將棧頂元素存入e。下面的程序段可以將A,B的值交換的操作序列是_。A.Push(A) Push(B) Pop(A) Pop(B)B.Push(A) Push(B) Pop(B) Pop(A)C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B)10.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)_。A順序查找 B分塊查找 C二分查找 D散列查找11. 下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的算法是_?？焖倥判?B.希爾排序 C.堆排序 D.冒泡排序12. 設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最

20、多有_個(gè)結(jié)點(diǎn)。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四個(gè)選項(xiàng)中，能構(gòu)成堆的是_。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20, 15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要多少條邊_。An(n-1)/2 Bn-1 Cn Dn+115.棧和隊(duì)列的共同特點(diǎn)是_。A. 都是操作受限的線(xiàn)性表 B.都是先進(jìn)后出 C. 都是后進(jìn)先出 D.無(wú)共同點(diǎn)二、填空題（本題共 10分，每空1分）若經(jīng)常需要對(duì)線(xiàn)性表進(jìn)行查找操作

21、，則最好采用_存儲(chǔ)結(jié)構(gòu)。某帶頭結(jié)點(diǎn)單鏈表的頭指針為L(zhǎng)，判定該單鏈表非空的條件_。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、_、_和圖狀結(jié)構(gòu)四種類(lèi)型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_。線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含_域和_域。向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_上。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線(xiàn)處填上正確的語(yǔ)句。typedef struct int stack100; int top; seqstack;void push(seqstack *s,int x)if (s-top=99) printf(“overflow”);else _(1)_;

22、_(2)_;三、應(yīng)用題（本題共40分） 1 設(shè)散列表長(zhǎng)度為11，散列函數(shù)h(key)=key % 11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫(huà)出用線(xiàn)性探查法解決沖突時(shí)所構(gòu)造的散列表。并計(jì)算在查找成功時(shí)候的平均查找長(zhǎng)度。（6分）2有一組權(quán)值14、21、32、15、28，畫(huà)出哈夫曼樹(shù)，并計(jì)算其WPL。（6分）3已知圖G=(V,E)，其中V=1,2,3,4,5, E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)。要求完成如下操作：（6分）（1）寫(xiě)出圖的鄰接矩陣（2）寫(xiě)出采用鄰接矩陣存儲(chǔ)時(shí)，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列。4已知序列50

23、3，87，512，61，908，170，897，275，653，462，分別寫(xiě)出執(zhí)行下列排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5對(duì)于下面所示的連通圖，寫(xiě)出由Prim算法生成的最小生成樹(shù)。（5分） 6. 將下面的樹(shù)轉(zhuǎn)化為一棵二叉樹(shù),并寫(xiě)出對(duì)二叉樹(shù)進(jìn)行層序遍歷的序列。（7分）ABCDEFGH四、算法題（本題共20 分）1完成中序遍歷二叉樹(shù)。Typedef struct node Char data; Struct node *lchild;Struct node *rchild;BTreeNode,*LinkBtree; Void InOrder(L

24、inkBtree Bt_pointer) If(Bt_pointer!=NULL) _(1)_; _(2)_; _(3)_; 2.完成二分查找算法：#Define n 10typedef int KeyType;typedef struct KeyType key; NodeType;Typedef NodeType SeqListn+1;int BinSearch (SeqList R,KeyType k)int low=1,high=n,mid;while(_（4）_) mid=(low+high)/2; if(Rmid.key=k) return mid; if(Rmid.keyk) _

25、（5）_; else _（6）_;return 0;3.編寫(xiě)算法實(shí)現(xiàn)直接插入排序。（8分） 參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1） 順序 2）L-next!=NULL3） 線(xiàn)性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 4） 深度優(yōu)先遍歷5） 數(shù)據(jù) 指針 6）左子樹(shù)7） s-top+ s-stacks-top=x 三、應(yīng)用題（本題共40分）1、（6分）H(1)=1 H(13)=2 H(12)=1 沖突 ， H1=2 沖突， H2=3 H(34)=1 沖突 ， H1=2 沖突， H2=3 沖突， H3=4

26、H(38)=5 H(33)=0 H(2)=2 沖突 ， H1=3 沖突， H2=4 沖突， H3=5 沖突， H4=6 H(22)=0 沖突 ， H1=1 沖突， H2=2 沖突， H3=3 沖突， H4=4 沖突，H5=5 沖突， H6=6 沖突， H7=7 ASL=(1+1+3+4+1+1+5+8)/8=24/8=3 2、（6分）1104961212829321415Wpl=2493、圖的鄰接矩陣：（3分） 廣度優(yōu)先序列： 1 2 3 4 5（3分）0 1 1 1 01 0 1 0 11 1 0 1 01 0 1 0 10 1 0 1 0 4、 1）（503）87 512 61 908 1

27、70 897 275 653 462（5分） （87 503）512 61 908 170 897 275 653 462 （87 503 512）61 908 170 897 275 653 462（61 87 503 512）908 170 897 275 653 462（61 87 503 512 908）170 897 275 653 462（61 87 170 503 512 908）897 275 653 462（61 87 170 503 512 897 908）275 653 462（61 87 170 275 503 512 897 908）653 462（61 87 170

28、 275 503 512 653 897 908）462（61 87 170 275 462 503 512 653 897 908） 2）第一趟： 170 61 512 462 503 653 275 87 897 908（5分） 第二趟： 503 908 512 653 61 462 170 275 87 897 第三趟： 61 87 170 275 462 503 512 653 897 9085、（5分） ABDEFGHC6. （7分）層序遍歷序列:ABECFDGH四、算法題（本題共20分）1、 （1）InOrder (Bt_pointer -lchild); （2分） (2) pri

29、ntf(“%c”, Bt_pointer -data);（2分） (3) InOrder (Bt_pointer -rchild); （2分）2、 （4） low=high （5）high=mid-1; （6） low= mid+1; （6分）3、 void InsertSort(int a,int n) （8分） int i,j; for(i=2;i=n;i+) a0=ai; j=i-1; while(a0next; p-next=q-next;free(p);Bp=q-next; q-next=p; free(p);Cp=q-next; q-next=p-next; free(p);Dq-

30、next=q-next-next; q-next=q; free(p);6. 一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的地址是_。A110 B108 C100 D1207. 在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線(xiàn)性表中，在其第i個(gè)位置插入一個(gè)新元素時(shí)，需要移動(dòng)元素的次數(shù)是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面關(guān)于線(xiàn)性表的敘述錯(cuò)誤的是_。A. 線(xiàn)性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D. 線(xiàn)性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)9. Pu

31、sh(e)表示e進(jìn)棧，Pop(e)表示退棧并將棧頂元素存入e。下面的程序段可以將A,B的值交換的操作序列是_。A.Push(A) Push(B) Pop(A) Pop(B)B.Push(A) Push(B) Pop(B) Pop(A)C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B)10.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)_。A順序查找 B分塊查找 C二分查找 D散列查找11. 下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的算法是_。快速排序 B.希爾排序 C.堆排序 D.冒泡排序12.

32、 設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有_個(gè)結(jié)點(diǎn)。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四個(gè)選項(xiàng)中，能構(gòu)成堆的是_。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20, 15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要多少條邊_。An(n-1)/2 Bn-1 Cn Dn+115.棧和隊(duì)列的共同特點(diǎn)是_。A. 都是操作受限的線(xiàn)性表 B.都是先進(jìn)后出 C. 都是后進(jìn)先出 D.無(wú)共同點(diǎn)二、填空題（本題共 10分，

33、每空1分）若經(jīng)常需要對(duì)線(xiàn)性表進(jìn)行查找操作，則最好采用_存儲(chǔ)結(jié)構(gòu)。某帶頭結(jié)點(diǎn)單鏈表的頭指針為L(zhǎng)，判定該單鏈表非空的條件_。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、_、_和圖狀結(jié)構(gòu)四種類(lèi)型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_。線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含_域和_域。向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_上。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線(xiàn)處填上正確的語(yǔ)句。typedef struct int stack100; int top; seqstack;void push(seqstack *s,int x)if (s-top=99) printf(“ov

34、erflow”);else _(1)_;_(2)_;三、應(yīng)用題（本題共40分） 1 設(shè)散列表長(zhǎng)度為11，散列函數(shù)h(key)=key % 11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫(huà)出用線(xiàn)性探查法解決沖突時(shí)所構(gòu)造的散列表。并計(jì)算在查找成功時(shí)候的平均查找長(zhǎng)度。（6分）2有一組權(quán)值14、21、32、15、28，畫(huà)出哈夫曼樹(shù)，并計(jì)算其WPL。（6分）3已知圖G=(V,E)，其中V=1,2,3,4,5, E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)。要求完成如下操作：（6分）（1）寫(xiě)出圖的鄰接矩陣（2）寫(xiě)出采用鄰接矩陣存儲(chǔ)時(shí)，從頂點(diǎn)1出

35、發(fā)的廣度優(yōu)先搜索遍歷序列。4已知序列503，87，512，61，908，170，897，275，653，462，分別寫(xiě)出執(zhí)行下列排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5對(duì)于下面所示的連通圖，寫(xiě)出由Prim算法生成的最小生成樹(shù)。（5分） 6. 將下面的樹(shù)轉(zhuǎn)化為一棵二叉樹(shù),并寫(xiě)出對(duì)二叉樹(shù)進(jìn)行層序遍歷的序列。（7分）ABCDEFGH四、算法題（本題共20 分）1完成中序遍歷二叉樹(shù)。Typedef struct node Char data; Struct node *lchild;Struct node *rchild;BTreeNode,*LinkB

36、tree; Void InOrder(LinkBtree Bt_pointer) If(Bt_pointer!=NULL) _(1)_; _(2)_; _(3)_; 2.完成二分查找算法：#Define n 10typedef int KeyType;typedef struct KeyType key; NodeType;Typedef NodeType SeqListn+1;int BinSearch (SeqList R,KeyType k)int low=1,high=n,mid;while(_（4）_) mid=(low+high)/2; if(Rmid.key=k) return

37、mid; if(Rmid.keyk) _（5）_; else _（6）_;return 0;3.編寫(xiě)算法實(shí)現(xiàn)直接插入排序。（8分） 參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1） 順序 2）L-next!=NULL3） 線(xiàn)性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 4） 深度優(yōu)先遍歷5） 數(shù)據(jù) 指針 6）左子樹(shù)7） s-top+ s-stacks-top=x 三、應(yīng)用題（本題共40分）1、（6分）H(1)=1 H(13)=2 H(12)=1 沖突 ， H1=2 沖突， H2=3 H(34)=1 沖突 ， H1=

38、2 沖突， H2=3 沖突， H3=4 H(38)=5 H(33)=0 H(2)=2 沖突 ， H1=3 沖突， H2=4 沖突， H3=5 沖突， H4=6 H(22)=0 沖突 ， H1=1 沖突， H2=2 沖突， H3=3 沖突， H4=4 沖突，H5=5 沖突， H6=6 沖突， H7=7 ASL=(1+1+3+4+1+1+5+8)/8=24/8=3 2、（6分）1104961212829321415Wpl=2493、圖的鄰接矩陣：（3分） 廣度優(yōu)先序列： 1 2 3 4 5（3分）0 1 1 1 01 0 1 0 11 1 0 1 01 0 1 0 10 1 0 1 0 4、 1）

39、（503）87 512 61 908 170 897 275 653 462（5分） （87 503）512 61 908 170 897 275 653 462 （87 503 512）61 908 170 897 275 653 462（61 87 503 512）908 170 897 275 653 462（61 87 503 512 908）170 897 275 653 462（61 87 170 503 512 908）897 275 653 462（61 87 170 503 512 897 908）275 653 462（61 87 170 275 503 512 897 9

40、08）653 462（61 87 170 275 503 512 653 897 908）462（61 87 170 275 462 503 512 653 897 908） 2）第一趟： 170 61 512 462 503 653 275 87 897 908（5分） 第二趟： 503 908 512 653 61 462 170 275 87 897 第三趟： 61 87 170 275 462 503 512 653 897 9085、（5分） ABDEFGHC6. （7分）層序遍歷序列:ABECFDGH四、算法題（本題共20分）1、 （1）InOrder (Bt_pointer -l

41、child); （2分） (2) printf(“%c”, Bt_pointer -data);（2分） (3) InOrder (Bt_pointer -rchild); （2分）2、 （4） low=high （5）high=mid-1; （6） low= mid+1; （6分）3、 void InsertSort(int a,int n) （8分） int i,j; for(i=2;i=n;i+) a0=ai; j=i-1; while(a0aj) aj+1=aj; j-; aj+1=a0;試卷二一、選擇題（本題共20分,每題2分）1.下面程序段的時(shí)間復(fù)雜度為（ ）。for(i=1;i=

42、n;i+) for(j=1;j=n;j+) s+;A. O(n) B. O(n2) C. O(2*n) D. O（i*j）2. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ）。A必須是不連續(xù)的 B部分地址必須是連續(xù)的C連續(xù)與否均可 D和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3.若讓元素1，2，3依次進(jìn)棧，則出棧時(shí)的序列不可能出現(xiàn)的是（ ）。 A3，2，1 B1，2，3 C3，1，2 D2，1，34.下面說(shuō)法不正確的是()A串S1=“this_is_a_string”的長(zhǎng)度是16。 B串S2=“this”是串S1的子串。C串S3=“thisis”在串S1中的位置是1。D串S4=“a”在串S1中的位置是9。 5. 一

43、個(gè)非空廣義表的表頭（ ）。A不可能是子表 B只能是子表C只能是原子 D可以是子表或原子6.完全二叉樹(shù)()滿(mǎn)二叉樹(shù)A 不一定是 B一定不是 C一定是 D不能確定關(guān)系7. 用鏈表表示線(xiàn)性表的優(yōu)點(diǎn)是（ ）便于隨機(jī)存取便于插入和刪除操作花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少元素的物理順序與邏輯順序相同8.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要多少條邊()。An(n-1)/2 Bn-1 Cn Dn+19.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)()A順序查找 B分塊查找 C二分查找 D散列查找10.下面哪種排序方法穩(wěn)定性最好()。 A希爾排序 B冒泡排序 C快速排序 D堆排序二、填空題（本題共 20分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為兩大類(lèi)：_和_。2. 在二叉樹(shù)的第i層上最多有_個(gè)結(jié)點(diǎn)。3. 無(wú)向圖中恰好有_條邊，才稱(chēng)為無(wú)向完全圖。4. 用單鏈表方式存儲(chǔ)的線(xiàn)性表，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是_，另一個(gè)是_。