中南大學(xué)十套數(shù)據(jù)結(jié)構(gòu)試題與答案

1、數(shù)據(jù)結(jié)構(gòu)試卷（一） 1數(shù)據(jù)結(jié)構(gòu)試卷（二） 5數(shù)據(jù)結(jié)構(gòu)試卷（三） 9數(shù)據(jù)結(jié)構(gòu)試卷（四） 14數(shù)據(jù)結(jié)構(gòu)試卷（五） 19數(shù)據(jù)結(jié)構(gòu)試卷（六） 24數(shù)據(jù)結(jié)構(gòu)試卷（七） 28數(shù)據(jù)結(jié)構(gòu)試卷（八） 32數(shù)據(jù)結(jié)構(gòu)試卷（九） 36數(shù)據(jù)結(jié)構(gòu)試卷（十） 41數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案 47數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案 48數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案 51數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案 54數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案 58數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案 60數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案 64數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案 66數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案 69數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案 71、/幾/、單選題（每題 2 分，共 20 分）

2、1. 棧和隊(duì)列的共同特點(diǎn)是 （）。A. 只允許在端點(diǎn)處插入和刪除元素B. 都是先進(jìn)后出C. 都是先進(jìn)先出D. 沒有共同點(diǎn)2. 用方式存儲的隊(duì)列，在進(jìn)行插入運(yùn)算時（ ）.A. 僅修改頭指針B. 頭、尾指針都要修改C. 僅修改尾指針D. 頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（ ）A. 隊(duì)列B. 棧C. 線性表D. 二叉樹4. 設(shè)有一個二維數(shù)組 Am n ，假設(shè) A00 存放位置在 644 （10） ，A22 存放位置在 676（io）,每個元素占一個空間， 問A33（10）存放在什么位置？腳注（io）表示用10進(jìn) 制表示。C 692D 696B. 無序數(shù)據(jù)元素D. 元素之

3、間無聯(lián)系的數(shù)據(jù)A 688B6785. 樹最適合用來表示 （）。A. 有序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 2k-16. 二叉樹的第 k 層的結(jié)點(diǎn)數(shù)最多為 （ ）. A2k-1B.2K+1C.2K-17. 若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放 A1中，現(xiàn)進(jìn)行二分查找，則查找 A :3的比較序列的下標(biāo)依次為 （）A. 1 ， 2 ， 3B. 9 ， 5， 2 ， 31.2.3.4.5.6.7.8.9.10.11.12.三、1.2.C. 9 , 5, 3D. 9 , 4 , 2 , 38. 對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為A. O （ 1

4、）B. O （n ）C. O （ 1og2n）D. O （n2）9. 對于線性表（7，34 ,55，25，64 ,46，20，10）進(jìn)行散列存儲時，若選用H（ K）=K %9作為散列函數(shù)，則散列地址為1的元素有（）個，A. 1B . 2C . 3D . 410. 設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（）條邊才能確保是一個連通圖。A.5B.6C.7D.8填空題（每空1分，共26分）通常從四個方面評價(jià)算法的質(zhì)量： 、和。一個算法的時間復(fù)雜度為（n3 + n2log2n+14 n）/n2,其數(shù)量級表示為 。假定一棵樹的廣義表表示為A （ C, D （ E, F , G）, H （I, J）,則樹中所含

5、的結(jié)點(diǎn)數(shù)為個，樹的深度為 ，樹的度為 。后綴算式9 2 3 +- 10 2 / - 的值為 。中綴算式（3+4X ） -2Y/3 對應(yīng)的后綴算式為。若用鏈表存儲一棵二叉樹時，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有 個指針域，其中有 個指針域是存放了地址，有 個指針是空指針。對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié) 點(diǎn)分別有個和個。AOV網(wǎng)是一種的圖。在一個具有n個頂點(diǎn)的無向完全圖中，包含有 條邊，在一個具有 n個頂點(diǎn)的有向完全圖中，包含有 條邊。假定一個線性表為（12,23,74,55,63,40） ，若按

6、Key % 4條件進(jìn)行劃分，使得同一余數(shù) 的元素成為一個子表，則得到的四個子表分別為、和。 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為 ,整個堆排序過程的時間復(fù)雜度為。6050789034403572041排序是穩(wěn)定的。datan ext表頭指針為 A 0 .n ext ，試寫出該線性表。234567在快速排序、堆排序、歸并排序中， 計(jì)算題（每題 6分，共24分） 在如下數(shù)組A中存儲了一個線性表,0 1請畫出下圖的鄰接矩陣和鄰接表。3. 已知一個圖的頂點(diǎn)集 V 和邊集 E 分別為： V=1,2,3,4,5,

7、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;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 畫出向小根堆中加入數(shù)據(jù) 4, 2, 5, 8, 3 時，每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法(每題 7 分，共 14 分)1. LinkList mynote(LinkList L)/L 是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(L&&L->next) q=L ；L=L >next ； p=L ；S1

8、：while(p >next) p=p >next ；S2 ：p >next=q ； q >next=NULL ；returnL ； 請回答下列問題：(1 )說明語句 S1 的功能；(2 )說明語句組 S2 的功能；(3)設(shè)鏈表表示的線性表為(ai,a2,an),寫出算法執(zhí)行后的返回值所表示的線 性表。2. void ABC(BTNode * BT) if BT ABC (BT->left); ABC (BT->right); cout<<BT->data<<' ' 該算法的功能是：五、算法填空(共 8 分) 二

9、叉搜索樹的查找 遞歸算法 : bool Find(BTreeNode* BST,ElemType& item)if (BST=NULL)return false; / 查找失敗 else if (item=BST->data) item=BST->data;/查找成功return ;else if(item<BST->data)else return Find(,item);/if六、編寫算法(共 8 分) 統(tǒng)計(jì)出單鏈表 HL 中結(jié)點(diǎn)的值等于給定值 X 的結(jié)點(diǎn)數(shù)。int CountX(LNode* HL,ElemType x)數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題 (24

10、 分 )1 下面關(guān)于線性表的敘述錯誤的是( )。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為 m ，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有( )個空指針域。(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m3 .設(shè)順序循環(huán)隊(duì)列 Q0 : M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素的前一位置，尾指針 R 總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個數(shù)為)。(A)

11、R-F(B) F-R(C) (R-F+M) M (D) (F-R+M) M4設(shè)某棵二叉樹的中序遍歷序列為ABCD ，前序遍歷序列為 CABD ，則后序遍歷該二叉樹得到序列為( )。(A) BADC(B) BCDA (C) CDAB (D) CBDA5 設(shè)某完全無向圖中有 n 個頂點(diǎn)，則該完全無向圖中有( )條邊。(A) n(n-1)/2(B) n(n-1)(C) n2(D) n 2-1(A) 9(B) 10(C) 11(D) 127 設(shè)某有向圖中有 n 個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有( )個表頭結(jié)點(diǎn)。(A) n-1(B) n(C) n+1(D) 2n-18 設(shè)一組初始記錄關(guān)鍵字序列 (5，

12、2 ， 6 ，3 ， 8) ，以第一個記錄關(guān)鍵字 5 為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為( )。(A) 2，3，5，8，6(B) 3 ，2，5，8，6(C) 3 ，2，5，6，8(D) 2 ，3，6，5，8二、填空題 (24 分 )1. 為了能有效地應(yīng)用 HASH 查找技術(shù)，必須解決的兩個問題是 和6. 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e=<7. 設(shè)一組初始記錄關(guān)鍵字序列為（55，63，44，38，75，80，31，56），則利用篩選法建立的初始堆為。8 .已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點(diǎn) 1出發(fā)，DFS遍歷的輸出序列是, BFS遍歷的輸出序列是團(tuán)的鄰

13、撞麥存儲結(jié)枸三、應(yīng)用題（36分）1 .設(shè)一組初始記錄關(guān)鍵字序列為（45 , 80 , 48 , 40 , 22 , 78），則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2 .設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn) A ,指針變量q指向被插入結(jié)點(diǎn) B ,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink 和rlink ）。3 .設(shè)一組有序的記錄關(guān)鍵字序列為（13 , 18 , 24 , 35 , 47 , 50 , 62 , 83 , 90），查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字 62時的比較次數(shù)并計(jì)算出查找成功時的平均查找長度。4 .設(shè)一棵樹 T

14、 中邊的集合為(A, B) , (A, C), (A , D), (B , E) , (C, F), (C , G)，要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5 .設(shè)有無向圖G ,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6設(shè)有一組初始記錄關(guān)鍵字為 (45 , 80 , 48 , 40 , 22 , 78) ,要求構(gòu)造一棵二叉排序樹并 給出構(gòu)造過程。四、算法設(shè)計(jì)題 (16 分 )1. 設(shè)有一組初始記錄關(guān)鍵字序列(Ki , K2，Kn),要求設(shè)計(jì)一個算法能夠在0(n)的時間復(fù)雜度將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的

15、每個關(guān)鍵字均大于等于Ki。2 .設(shè)有兩個集合 A和集合B,要求設(shè)計(jì)生成集合 C=A A B的算法，其中集合 A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題 （每題 1 分，共 20 分 ）1 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D ， R)，D=01 ，02 ，03 ，04 ，05 ， 06 ，07 ，08 ， 09 ， R=r ， r=<01 ，02>，<01，03>，<01，04>，<02，05>，<02，06> ，<03 , 07> , <03 , 08> , <03 , 09>，

16、則數(shù)據(jù)結(jié)構(gòu) A 是(）。（A） 線性結(jié)構(gòu)（B） 樹型結(jié)構(gòu) （C） 物理結(jié)構(gòu) （D） 圖型結(jié)構(gòu)for ( i=1 ， s=0 ； i<=n ； i+ )t=1 ； for(j=1 ； j<=i ；j+) t=t*j ；s=s+t ；(A) O(n)(B) O(n 2)(C) O(n 3)(D) O(n 4)設(shè)指針變量 p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（ ）。(A) q=p->next；p->data=q->data；p->next=q->next； free(q) ；(B) q=p->next；q->da

17、ta=p->data；p->next=q->next； free(q) ；(C) q=p->next；p->next=q->next； free(q) ；(D) q=p->next；p->data=q->data； free(q) ；2 下面程序的時間復(fù)雜為（ ）34 設(shè)有 n 個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。(A) 1(B) n(C) nlog 2n(D) n(C) 10 ，15 ，14 ， 20 ，18 ，40，36，2l(D) 15 ，10，14，18，20 ，36，40，216 設(shè)二叉排序樹中有 n 個結(jié)點(diǎn)

18、，則在二叉排序樹的平均平均查找長度為( )。2(A) O(1)(B) O(log 2n)(C)(D) O(n 2)7 設(shè)無向圖 G 中有 n 個頂點(diǎn) e 條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為( )。(A) n ，e(B) e ，n(C) 2n ， e(D) n ， 2e8. 設(shè)某強(qiáng)連通圖中有 n 個頂點(diǎn)，則該強(qiáng)連通圖中至少有( )條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9 設(shè)有 5000 個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的 10 個記錄關(guān)鍵字，則用下列( )方法可以達(dá)到此目的。(A) 快速排序 (B) 堆排序 (C) 歸并排

19、序 (D) 插入排序10. 下列四種排序中()的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序 (C) 堆排序(D) 歸并排序二、填空殖 (每空 1 分 共 20 分 )1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和兩種情況。2. 設(shè)一棵完全二叉樹中有 500 個結(jié)點(diǎn)，則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個空指針域。3. 設(shè)輸入序列為 1、 2 、3 ，則經(jīng)過棧的作用后可以得到 種不同的輸出序列。4. 設(shè)有向圖 G 用鄰接矩陣 Ann 作為存儲結(jié)構(gòu)，則該鄰接矩陣中第 i 行上所有元素之和等于頂點(diǎn) i 的，第 i 列上所有元素之和等于頂點(diǎn) i 的 5. 設(shè)哈夫曼樹中共有 n

20、 個結(jié)點(diǎn)，則該哈夫曼樹中有 個度數(shù)為 1 的結(jié)點(diǎn)。6. 設(shè)有向圖 G 中有 n 個頂點(diǎn) e 條有向邊，所有的頂點(diǎn)入度數(shù)之和為d ，則 e 和 d 的關(guān)系為。7. 遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列 (填先序、 中序或后序)。8. 設(shè)查找表中有 100 個元素，如果用二分法查找方法查找數(shù)據(jù)元素X ，則最多需要比較次就可以斷定數(shù)據(jù)元素 X 是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧， 其入棧和出棧操作的時間復(fù)雜度均為10. 設(shè)有 n 個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從 1 開始順序編號，則 第 i 個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為 ，右孩子結(jié)點(diǎn)的編號為

21、。11. 設(shè)一組初始記錄關(guān)鍵字為 (72，73，71，23，94，16 ，5)，則以記錄關(guān)鍵字 72 為基 準(zhǔn)的一趟快速排序結(jié)果為 。12. 設(shè)有向圖 G 中有向邊的集合 E=<1 ， 2> ， <2 ， 3> ， <1 ，4> ，<4 ，2> ，<4 ， 3> ，則 該圖的一種拓?fù)湫蛄袨?。13. 下列算法實(shí)現(xiàn)在順序散列表中查找值為 x 的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。 struct recordint key; int others;int hashsqsearch(struct record hashtable ,int

22、k)int i,j; j=i=k % p;while (hashtablej.key!=k&&hashtablej.flag!=0)j=() %m; if (i=j)return(-1);14. 下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請?jiān)谙聞澗€處填上正確的語句。typedef struct no dei nt key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, intk)if (t=0 ) return(0);else while (t!=0)if (t->k

23、ey=k); else if (t->key>k) t=t->lchild;else;三、計(jì)算題(每題10分，共30分)1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD ，畫出此二叉樹，并畫出它的后序線索二叉樹。2 .已知待散列的線性表為(36 ,15 , 40, 63 , 22 ),散列用的一維地址空間為0.6，假定選用的散列函數(shù)是 H (K) = K mod 7 ，若發(fā)生沖突采用線性探查法處理，試：(1)計(jì)算出每一個元素的散列地址并在下圖中填寫出散列表：'0123456(2 )求出在查找每一個元素概率相等情況下的平均查找

24、長度。3 .已知序列(10 , 18 , 4 , 3 , 6 , 12 , 1 , 9 , 18, 8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計(jì)題 （每題 15 分，共 30 分 ）1 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。2 設(shè)計(jì)一個求結(jié)點(diǎn) x 在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)結(jié)構(gòu)試卷(四)一、選擇題 (每題 1 分共 20 分 )1 設(shè)一維數(shù)組中有 n 個數(shù)組元素，則讀取第 i 個數(shù)組元素的平均時間復(fù)雜度為( )。2(A) O(n)(B) O(nlog 2n) (C) O(1)(D) O(n 2)2 設(shè)一棵二叉樹的深度為 k ，則該二叉樹中最多有( )個結(jié)點(diǎn)。(A) 2k-1(B)

25、 2 k(C) 2 k-1(D) 2 k-13 設(shè)某無向圖中有 n 個頂點(diǎn) e 條邊，則該無向圖中所有頂點(diǎn)的入度之和為()。(A) n(B) e(C) 2n(D) 2e4 在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為( )。2(A) O(1)(B) O(n)(C) O(log 2n)(D) O(n 2)5 設(shè)某有向圖的鄰接表中有 n 個表頭結(jié)點(diǎn)和 m 個表結(jié)點(diǎn)，則該圖中有( )條有向邊。(A) n(B) n-1(C) m(D) m-16 設(shè)一組初始記錄關(guān)鍵字序列為 (345 ，253 ，674 ，924 ，627) ，則用基數(shù)排序需要進(jìn)行 ( )趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(

26、A) 3(B) 4(C) 5(D) 87 設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作( )。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別8 下列四種排序中( )的空間復(fù)雜度最大。(A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆9 .設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No，度數(shù)為1的結(jié)點(diǎn)數(shù)為Ni,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（）。(A) N o=Ni+1(B) N 0=Nl+N2(C) N 0=N 2+1(D) N 0=2N 1+l10. 設(shè)有序順序表中有n 個數(shù)據(jù)元素, 則利用二分查找法查找數(shù)據(jù)元素X 的最多比較次數(shù)不超

27、過（ ）。(A) log 2n+1(B) log 2n-1(C) log 2n(D) log 2(n+1)二、填空題 （每空 1 分共 20 分 ）1 . 設(shè)有 n 個無序的記錄關(guān)鍵字,則直接插入排序的時間復(fù)雜度為 ,快速排序的平均時間復(fù)雜度為 。2 .設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn) X需要執(zhí)行的語句序列為 （設(shè)結(jié)點(diǎn)中的兩個指 針域分別為 llink 和 rlink ）。3 根據(jù)初始關(guān)鍵字序列 （19 , 22 , 01 , 38 , 10） 建立的二叉排序樹的高度為 。4 深度為 k 的完全二叉樹中最少有 個結(jié)點(diǎn)。5 .設(shè)初始記錄關(guān)鍵字序列為（Ki , K2，Kn），則用

28、篩選法思想建堆必須從第 個元素開始進(jìn)行篩選。6. 設(shè)哈夫曼樹中共有 99 個結(jié)點(diǎn),則該樹中有 個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu),則該樹中有 個空指針域。7. 設(shè)有一個順序循環(huán)隊(duì)列中有 M 個存儲單元,則該循環(huán)隊(duì)列中最多能夠存儲 個隊(duì)列元素；當(dāng)前實(shí)際存儲 個隊(duì)列元素（設(shè)頭指針 F 指向當(dāng)前隊(duì)頭元素的前一個位置,尾指針指向當(dāng)前隊(duì)尾元素的位置） 。8 設(shè)順序線性表中有 n 個數(shù)據(jù)元素，則第 i 個位置上插入一個數(shù)據(jù)元素需要移動表中個數(shù)據(jù)元素；刪除第 i 個位置上的數(shù)據(jù)元素需要移動表中 個元素。9 設(shè)一組初始記錄關(guān)鍵字序列為 (20，18，22，16，30，19) ，則以 20 為中軸的一趟快

29、速排序結(jié)果為 。10 設(shè)一組初始記錄關(guān)鍵字序列為 (20 ，18 ，22 ，16 ，30 ，19) ，則根據(jù)這些初始關(guān)鍵 字序列建成的初始堆為 。11 設(shè)某無向圖 G 中有 n 個頂點(diǎn)，用鄰接矩陣 A 作為該圖的存儲結(jié)構(gòu)，則頂點(diǎn) i 和頂 點(diǎn) j 互為鄰接點(diǎn)的條件是 。12 設(shè)無向圖對應(yīng)的鄰接矩陣為 A ，則 A 中第 i 上非 0 元素的個數(shù) 第 i 列上非 0 元素的個數(shù)(填等于，大于或小于) 。13 設(shè)前序遍歷某二叉樹的序列為 ABCD ，中序遍歷該二叉樹的序列為 BADC ，則后 序遍歷該二叉樹的序列為 。14 設(shè)散列函數(shù) H(k)=k mod p ，解決沖突的方法為鏈地址法。要求在下

30、列算法劃線處 填上正確的語句完成在散列表 hashtalbe 中查找關(guān)鍵字值等于 k 的結(jié)點(diǎn)，成功時返回 指向關(guān)鍵字的指針，不成功時返回標(biāo)志0 。typedef struct node int key; struct node *next; lklist;void createlkhash(lklist *hashtable )int i,k; lklist *s;for(i=0;i<m;i+);for(i=0;i<n;i+)s=(lklist *)malloc(sizeof(lklist); s->key=ai;k=ai % p; s->next=hashtablek

31、;三、計(jì)算題(每題10分，共30分)1、 畫出廣義表 LS=( ) , (e) , (a , (b , c , d )的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林：(1) 求樹(a)的先根序列和后根序列；(2) 求森林先序序列和中序序列；(3) 將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；3、設(shè)散列表的地址圍是0.9 ，散列函數(shù)為H ( key)=( key 2 +2)MOD 9,并采用鏈表處理沖突，請畫出元素 7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計(jì)題(每題10分，共30分)1 .設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的

32、算法，使每個單鏈表只包含同類字符。2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷(五)、選擇題 (20 分 )1 數(shù)據(jù)的最小單位是( )。(A) 數(shù)據(jù)項(xiàng) (B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量2 設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20 ，15，70 ，60 ，45) ，則以增量d=4的一趟希爾排序結(jié)束后前 4條記錄關(guān)鍵字為( )。(A) 40 ，50 ，20 ，95(B) 15 ，40 ，60 ，20(C) 15 ，20 ，40 ，45(D) 45 ，40 ，15 ，203 設(shè)一組初始記錄關(guān)鍵字序列

33、為(25 ， 50 ， 15 ， 35 ，80，85 ，20 ，40 ，36 ，70) ，其中含有 5 個長度為 2 的有序子表， 則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并 后的結(jié)果為( )。(A) 15 ，25 ，35，50 ，20 ，40，80 ，85 ，36 ，70(B) 15 ，25 ，35，50 ，80 ，20，85 ，40，70 ，36(C) 15 ，25 ，35，50 ，80 ，85，20 ，36 ，40 ，70(D) 15 ，25，35 ，50 ，80 ，20，36 ，40，70 ，854函數(shù) substr( “ DATASTRUCTURE ”， 5 ， 9)的返回值為

34、( )。(A) “ STRUCTURE ” (B) “ DATA ”(C) “ ASTRUCTUR ” (D) “ DATASTRUCTURE5 設(shè)一個有序的單鏈表中有 n 個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序， 則該操作的時間復(fù)雜度為( )。2(A) O(log 2n)(B) O(1) (C) O(n 2) (D) O(n)6 .設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No，度數(shù)為1的結(jié)點(diǎn)數(shù)為Ni, ，度數(shù)為 m的結(jié)點(diǎn)數(shù)為 Nm ，則 N0=（）。(B) l+N 2+2N 3+3N 4+(A) N 1+N2+ +Nm+(m-1)Nm(C) N 2+2N 3+3N 4 + +(m-1)

35、Nm(D) 2N 葉3N 2+ +(m+1)Nm7.設(shè)有序表中有 1000 個元素，則用二分查找查找元素 X 最多需要比較（ ）次。8.(A) 25(B) 10(C) 7(D) 1設(shè)連通圖 G 中的邊集 E=（a ， b）， （a， e）， （a， c）， （b，e)， (e， d)， (d， f)，(f, c)，則從頂點(diǎn) a 出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9.設(shè)輸入序列是 1 、2、3 、n，經(jīng)過棧的作用后輸出序列的第一個元素是n ，則輸10出序列中第 i 個輸出元素是（(A) n-i(B) n-

36、1-i設(shè)一組初始記錄關(guān)鍵字序列為）。(C) n+1-i（D） 不能確定(45， 80 ， 55， 40，42 ，85） ，則以第一個記錄關(guān)鍵字45 為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。(A) 40 ， 42， 45， 55， 80， 83(B) 42 ， 40 ，45，80 ，85 ， 88(C) 42 ， 40 ， 45 ， 55 ， 80 ， 85(D) 42 ， 40 ，45，85 ，55 ， 80、填空題 （共 20 分 ）top1 的初值為 -1 ，第二個棧頂1. 設(shè)有一個順序共享?xiàng)?S0 ：n-1 ，其中第一個棧項(xiàng)指針指針top2的初值為n ,則判斷共享?xiàng)M的條件是 2. 在圖的

37、鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是3. 設(shè)有一個 n 階的下三角矩陣A ，如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素) 存放在 n(n+1) 個連續(xù)的存儲單元中， 則 Aij 與 A00 之間有 個數(shù)據(jù)元素。4. 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為 表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行， 先進(jìn)隊(duì)列的元素必定先 出隊(duì)列，所以又把隊(duì)列稱為 表。5. 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為 ABCDEF ，則該二叉樹的前序遍 歷序列為 ，中序遍歷序列為 ，后序遍歷序列為 。6. 設(shè)一棵完全二叉樹有 128 個結(jié)點(diǎn)，則該完全二叉

38、樹的深度為 ，有 個葉子結(jié)點(diǎn)。7. 設(shè)有向圖 G 的存儲結(jié)構(gòu)用鄰接矩陣 A 來表示，則 A 中第 i 行中所有非零元素個數(shù)之和 等于頂點(diǎn) i 的，第 i 列中所有非零元素個數(shù)之和等于頂點(diǎn) i 的 。8. 設(shè)一組初始記錄關(guān)鍵字序列(ki, k2,kn)是堆，則對i=1 , 2，n/2 而言滿足的條件為 。9. 下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請?jiān)谙聞澗€處填上正確的語句。void bubble(int rn)for(i=1;i<=n-1; i+)for(exchange=0,j=0; j<j+)if (rj>rj+1)temp=rj+1;rj=temp;exchange=1;

39、10. 下面程序段的功能是實(shí)現(xiàn)二分查找算法，請?jiān)谙聞澗€處填上正確的語句。struct recordint key; int others;int bisearch(struct record r , int k)int low=0,mid,high=n-1;while(low<=high)if(rmid.key=k) return(mid+1); else if() high=mid-1;elselow=mid+1;return(0);三、應(yīng)用題 (32 分 )1. 設(shè)某棵二叉樹的中序遍歷序列為 DBEAC ，前序遍歷序列為 ABDEC ，要求給出該二叉 樹的的后序遍歷序列。2. 設(shè)無向

40、圖 G (如右圖所示)，給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。3. 設(shè)一組初始記錄關(guān)鍵字序列為 (15 ， 17 ， 18， 22， 35 ， 51 ， 60) ，要求計(jì)算出成功查找時的平均查找長度。4. 設(shè)散列表的長度為 8，散列函數(shù) H(k)=k mod 7 ，初始記錄關(guān)鍵字序列為 (25 ，31 ，8，27 ，13，68) ，要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找 長度。四、算法設(shè)計(jì)題 (28 分 )1 設(shè)計(jì)判斷兩個二叉樹是否相同的算法。2 設(shè)計(jì)兩個有序單鏈表的合并排序算法。數(shù)據(jù)結(jié)構(gòu)試卷(六)一、選擇題 (30 分 )1 設(shè)一組權(quán)值集合

41、W=2 ，3，4，5， 6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長 度之和為( )。(A) 20 (B) 30 (C) 40 (D) 452 執(zhí)行一趟快速排序能夠得到的序列是()。(A) 41 ，12，34，45 ， 27 55 72 ，63(B) 45 ，34，12 ，41 55 72 ，63 ，27(C) 63 ，12，34 ，45 ， 27 55 41 ，72(D) 12 ，27，45 ，41 55 34 ，63 ，723 設(shè)一條單鏈表的頭指針變量為 head 且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是( )。(A) head=0(B) head->next=0(C) head->

42、next=head(D) head!=04 時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog 2n) 的是( )。(A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序5 設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是( )。(A) 空或只有一個結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無左孩子(D) 任一結(jié)點(diǎn)無右孩子6 一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是( )。(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序)。7 設(shè)某棵三叉樹中有 40 個結(jié)點(diǎn)，則該三叉樹的最小高度為(A) 3(B) 4(C) 5(D) 6(A

43、) O(n)(B) O(n 2)(C) O(n 1/2 )(D) O(1og 2n)9 二路歸并排序的時間復(fù)雜度為（）。(A) O(n)2(B) O(n 2)(C) O(nlog 2n)(D) O(1og2n)10. 深度為 k 的完全二叉樹中最少有（）個結(jié)點(diǎn)。(A) 2 k-1 -1(B) 2 k-1(C) 2 k-1 +1(D) 2 k-18 順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（ ）。11. 設(shè)指針變量 front 表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear 表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，12.13.14.15.指針變量 s 指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）

44、。(A) front->next=s(C) rear->next=s設(shè)某無向圖中有(A) O(n+e)設(shè)某哈夫曼樹中有(A) 99設(shè)二叉排序樹上有(A) O(n)； front=s ； rear=s ；n 個頂點(diǎn) e 條邊，(B) O(n 2)(B) s->next=rear ； rear=s ；(D) s->next=front； front=s ；則建立該圖鄰接表的時間復(fù)雜度為（(C) O(ne)(D) O(n 3)）。199 個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。(B) 100(C) 101(D) 102n 個結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時間復(fù)雜度為（(

45、B) O(n 2)(C) O(nlog 2n) (D) O(1og 2n)設(shè)用鄰接矩陣 A 表示有向圖 G 的存儲結(jié)構(gòu)，則有向圖 G 中頂點(diǎn) i 的入度為（）。）。（A） 第 i 行非 0 元素的個數(shù)之和（C） 第 i 行 0 元素的個數(shù)之和（B）第 i 列非 0 元素的個數(shù)之和（D）第 i 列 0 元素的個數(shù)之和、判斷題 （20 分 ）1 調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。2 分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。 （ ）3 冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。 （ ）4 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。 （

46、 ）5 設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。 （ ）6 層次遍歷初始堆可以得到一個有序的序列。 （ ）7 設(shè)一棵樹 T 可以轉(zhuǎn)化成二叉樹 BT ，則二叉樹 BT 中一定沒有右子樹。 （ ）8 線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。 （ ）9 中序遍歷二叉排序樹可以得到一個有序的序列。 （ ）10. 快速排序是排序算法中平均性能最好的一種排序。 （ ）三、填空題 （30 分 ）1 for（i=1 ，t=1 ， s=0 ；i<=n ； i+） t=t*i ； s=s+t ； 的時間復(fù)雜度為 。2 .設(shè)指針變量p指向單鏈表中結(jié)點(diǎn) A，指針變量s指向被插入的新結(jié)點(diǎn)

47、X，則進(jìn)行插入操作的語句序列為 （設(shè)結(jié)點(diǎn)的指針域?yàn)?next ）。3 .設(shè)有向圖 G 的二元組形式表示為G =（ D，R）, D=1，2，3，4 ,5，R=r , r=<1,2> ，<2,4> ， <4,5> ， <1,3> ， <3,2> ， <3,5> ，則給出該圖的一種拓?fù)渑判蛐蛄?。4. 設(shè)無向圖 G 中有 n 個頂點(diǎn),則該無向圖中每個頂點(diǎn)的度數(shù)最多是 。5. 設(shè)二叉樹中度數(shù)為0 的結(jié)點(diǎn)數(shù)為 50 ,度數(shù)為 1 的結(jié)點(diǎn)數(shù)為 30 ,則該二叉樹中總共有個結(jié)點(diǎn)數(shù)。6. 設(shè) F 和 R 分別表示順序循環(huán)隊(duì)列的頭指針和尾指

48、針,則判斷該循環(huán)隊(duì)列為空的條件為7 設(shè)二叉樹中結(jié)點(diǎn)的兩個指針域分別為 lchild 和 rchild ，則判斷指針變量 p 所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是 。8 簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為 。9 快速排序算法的空間復(fù)雜度平均情況下為 ，最壞的情況下為 10. 散列表中解決沖突的兩種方法是 和 。四、算法設(shè)計(jì)題 （20 分 ）1. 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。2 設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。3 .在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法、選擇題 （30 分 ）數(shù)據(jù)結(jié)構(gòu)試卷（七）1 設(shè)某無向圖有 n 個頂點(diǎn)，則該無向圖的鄰接表中有（）個表頭結(jié)點(diǎn)。(A) 2n(

49、B) n(C) n/2(D) n(n-1)2 設(shè)無向圖 G 中有 n 個頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。(A) n(B) n-1(C) 2n(D) 2n-13 設(shè)一組初始記錄關(guān)鍵字序列為 （60 ，80 ， 55 ，40 ，42，85） ，則以第一個關(guān)鍵字 45基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。(A) 40 ，42 ，60 ， 55 ，80 ，85(B) 42 ，45 ，55，60，85 ，80(C) 42 ，40 ，55 ， 60 ，80 ，85(D) 42 ，40 ，60，85 ，55 ， 804 （ ）二叉排序樹可以得到一個從小到大的有序序列。（A） 先序遍歷（B） 中序遍歷

50、（C） 后序遍歷（D） 層次遍歷5 設(shè)按照從上到下、從左到右的順序從1 開始對完全二叉樹進(jìn)行順序編號，則編號為 i點(diǎn)的左孩子結(jié)點(diǎn)的編號為（）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16 程序段 s=i=0 ； do i=i+1 ； s=s+iwhile(i<=n)的時間復(fù)雜度為（）。(A) O(n)(B) O(nlog 2n)2(C) O(n 2)3(D) O(n 3/2)7 設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。(A) head=0(B) head->next=0(C) head->next=head(D) head!=08

51、 設(shè)某棵二叉樹的高度為 10 ，則該二叉樹上葉子結(jié)點(diǎn)最多有（）。(A) 20(B) 256(C) 512(D) 1024134),9 設(shè)一組初始記錄關(guān)鍵字序列為 （13 ，18 ，24 ，35，47，50，62，83，90，115 則利用二分法查找關(guān)鍵字 90 需要比較的關(guān)鍵字個數(shù)為（ ）。（A） 1 （B） 2 （C） 3（D） 410. 設(shè)指針變量 top 指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（ ）。（A） top=top+1;（B） top=top-1;（C）top->next=top;（D） top=top->next;二、判斷題 （20 分 ）1 不論是入隊(duì)列

52、操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。2 當(dāng)向二叉排序樹中插入一個結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。 （ ）3 設(shè)某堆中有 n 個結(jié)點(diǎn)，則在該堆中插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O（log 2n） 。（4 完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。 （ ）5 哈夫曼樹中沒有度數(shù)為 1 的結(jié)點(diǎn)。（ ）6 對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。 （ ）7 先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。 （ ）8 由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）9 線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（ ）10. 帶權(quán)無向圖的最小生成樹是唯一的。 （ ）三、填空題 （30 分 ）1. 設(shè)指針變量 p 指向雙向鏈表中的結(jié)點(diǎn) A ，指針變量 s 指向被插入的結(jié)點(diǎn) X ，則在結(jié)點(diǎn) A 的后面插入結(jié)點(diǎn) X 的操作序列為 =p ； s->right=p->right； =s ；p->right->left=s ；(設(shè)結(jié)點(diǎn)中的兩個指針域分別為 left 和 right )。2. 設(shè)完全有向圖中有 n 個頂點(diǎn)，則該完全有向圖中共有