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

1、試卷B一、選擇題（本題共20分,每題2分）1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ） 。 A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) C. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2. 下列程序段的時間復(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. 以下描述錯誤的是：（ ）A. 線性表是n個數(shù)據(jù)元素的有限非空集合。B. 棧和隊列都是操作受限的線性表。C. 串（或字符串）是由零個或多個字符組成的有限序列。D. 非空棧中的棧頂指針

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

3、/2中，對下三角部分中任一元素 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. 有一個有序表為5, 18，23, 33, 42, 54,56,78，當(dāng)折半查找56時，經(jīng)過（ ）次比較后查找成功。A. 1 B. 2 C. 3 D. 88. 一組記錄的排序關(guān)鍵字為（39，19，36，68，35，84），則利用快速排序方法進行正序排列時，以第一個記錄為基準(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.若對下圖a中的二叉樹進行先序線索化，則結(jié)點x的左、右線索指向的結(jié)點分別是（ ）A. e,c B. e,a C. d,c D. b,abdxeac (a) (b)10. 已知一有向圖的鄰接表存儲結(jié)構(gòu)如上圖b所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點 v1 出發(fā)，所得到的頂點序列是（ ）。 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è)無向圖G中頂點數(shù)為n，則圖G最多有_

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

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

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

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

9、值頂點序列d距離值頂點序列e距離值頂點序列f距離值頂點序列g(shù)距離值頂點序列篩選頂點終點集S四、算法設(shè)計題（本題共20分）1. 編寫算法，實現(xiàn)將值為e的元素插入到單鏈表L的第i個結(jié)點的位置上。(本題10分)單鏈表結(jié)構(gòu)定義如下：typedef struct LNode ElemType data; Struct Lnode *next; Lnode,*LinkList; 2. 試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，且樹中結(jié)點的關(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)用題 答案要點（本題共40分，1-4每小題5分，5-6題每小題10分）1. 最小生成樹2.解：哈夫曼樹如圖其帶權(quán)路徑長度 WPL=72+82+43+

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

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

13、出答案要點，可以有不同的答案，酌情給分）1、參考代碼如下：（10分） status ListInsert(LinkList &L,int i,ElemType e)/在帶頭結(jié)點的單鏈表L中第i個位置插入值為e的新結(jié)點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分）算法思路：對二叉排序樹來說，其中序遍歷序列為一個遞增有序序列，因此，對給定的二叉樹進行中序遍歷，如果始終能保持前一個

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

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

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

17、ueue(Q,e)、DeQueue(Q,e)分別表示隊列初始化、入隊和出隊的操作。經(jīng)過以下隊列操作后，隊頭的值是_InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x)A. a B. b C.NULL D.x5.在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(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. 一個順序表第一個元素的存儲地址是100,每個元素占2個存儲單元，則第5個元素的地址是_。A110 B108 C100 D1207. 在一個長度為n的順序存儲的線性表中，在其第i個位置插入一個新元素時，需要移動元素的次數(shù)是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面關(guān)于線性表的敘述錯誤的是_。A. 線性表采用順序存儲必須占用一片連續(xù)的存儲空間B. 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C. 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)D. 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)9. Push(e)表示e進棧，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)酱鎯Y(jié)構(gòu)_。A順序查找 B分塊查找 C二分查找 D散列查找11. 下列排序算法中，不能保證每趟排序至少能將一個元素放到其最終的位置上的算法是_?？焖倥判?B.希爾排序 C.堆排序 D.冒泡排序12. 設(shè)一棵二叉樹的深度為k，則該二叉樹中最

20、多有_個結(jié)點。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四個選項中，能構(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. 在一個具有n個頂點的無向圖中，要連通全部頂點至少需要多少條邊_。An(n-1)/2 Bn-1 Cn Dn+115.棧和隊列的共同特點是_。A. 都是操作受限的線性表 B.都是先進后出 C. 都是后進先出 D.無共同點二、填空題（本題共 10分，每空1分）若經(jīng)常需要對線性表進行查找操作

21、，則最好采用_存儲結(jié)構(gòu)。某帶頭結(jié)點單鏈表的頭指針為L，判定該單鏈表非空的條件_。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、_、_和圖狀結(jié)構(gòu)四種類型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中的結(jié)點包含_域和_域。向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的_上。下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。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è)散列表長度為11，散列函數(shù)h(key)=key % 11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫出用線性探查法解決沖突時所構(gòu)造的散列表。并計算在查找成功時候的平均查找長度。（6分）2有一組權(quán)值14、21、32、15、28，畫出哈夫曼樹，并計算其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）寫出圖的鄰接矩陣（2）寫出采用鄰接矩陣存儲時，從頂點1出發(fā)的廣度優(yōu)先搜索遍歷序列。4已知序列50

23、3，87，512，61，908，170，897，275，653，462，分別寫出執(zhí)行下列排序算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5對于下面所示的連通圖，寫出由Prim算法生成的最小生成樹。（5分） 6. 將下面的樹轉(zhuǎn)化為一棵二叉樹,并寫出對二叉樹進行層序遍歷的序列。（7分）ABCDEFGH四、算法題（本題共20 分）1完成中序遍歷二叉樹。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àn)直接插入排序。（8分） 參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1） 順序 2）L-next!=NULL3） 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 4） 深度優(yōu)先遍歷5） 數(shù)據(jù) 指針 6）左子樹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. 一個順序表第一個元素的存儲地址是100,每個元素占2個存儲單元，則第5個元素的地址是_。A110 B108 C100 D1207. 在一個長度為n的順序存儲的線性表中，在其第i個位置插入一個新元素時，需要移動元素的次數(shù)是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面關(guān)于線性表的敘述錯誤的是_。A. 線性表采用順序存儲必須占用一片連續(xù)的存儲空間B. 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C. 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)D. 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)9. Pu

31、sh(e)表示e進棧，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)酱鎯Y(jié)構(gòu)_。A順序查找 B分塊查找 C二分查找 D散列查找11. 下列排序算法中，不能保證每趟排序至少能將一個元素放到其最終的位置上的算法是_?？焖倥判?B.希爾排序 C.堆排序 D.冒泡排序12.

32、 設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有_個結(jié)點。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四個選項中，能構(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. 在一個具有n個頂點的無向圖中，要連通全部頂點至少需要多少條邊_。An(n-1)/2 Bn-1 Cn Dn+115.棧和隊列的共同特點是_。A. 都是操作受限的線性表 B.都是先進后出 C. 都是后進先出 D.無共同點二、填空題（本題共 10分，

33、每空1分）若經(jīng)常需要對線性表進行查找操作，則最好采用_存儲結(jié)構(gòu)。某帶頭結(jié)點單鏈表的頭指針為L，判定該單鏈表非空的條件_。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、_、_和圖狀結(jié)構(gòu)四種類型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中的結(jié)點包含_域和_域。向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的_上。下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。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è)散列表長度為11，散列函數(shù)h(key)=key % 11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫出用線性探查法解決沖突時所構(gòu)造的散列表。并計算在查找成功時候的平均查找長度。（6分）2有一組權(quán)值14、21、32、15、28，畫出哈夫曼樹，并計算其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）寫出圖的鄰接矩陣（2）寫出采用鄰接矩陣存儲時，從頂點1出

35、發(fā)的廣度優(yōu)先搜索遍歷序列。4已知序列503，87，512，61，908，170，897，275，653，462，分別寫出執(zhí)行下列排序算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5對于下面所示的連通圖，寫出由Prim算法生成的最小生成樹。（5分） 6. 將下面的樹轉(zhuǎn)化為一棵二叉樹,并寫出對二叉樹進行層序遍歷的序列。（7分）ABCDEFGH四、算法題（本題共20 分）1完成中序遍歷二叉樹。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àn)直接插入排序。（8分） 參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1） 順序 2）L-next!=NULL3） 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 4） 深度優(yōu)先遍歷5） 數(shù)據(jù) 指針 6）左子樹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.下面程序段的時間復(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. 線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（ ）。A必須是不連續(xù)的 B部分地址必須是連續(xù)的C連續(xù)與否均可 D和頭結(jié)點的存儲地址相連續(xù)3.若讓元素1，2，3依次進棧，則出棧時的序列不可能出現(xiàn)的是（ ）。 A3，2，1 B1，2，3 C3，1，2 D2，1，34.下面說法不正確的是()A串S1=“this_is_a_string”的長度是16。 B串S2=“this”是串S1的子串。C串S3=“thisis”在串S1中的位置是1。D串S4=“a”在串S1中的位置是9。 5. 一

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