電子科技大學期末數(shù)據(jù)結(jié)構(gòu)試題及答案

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

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

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

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

5、條邊，在一個具有n個頂點的有向完全圖中，包含有 n（n-1） 條邊。9. 假定一個線性表為（12,23,74,55,63,40），若按Key % 4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為、和。10. 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度11. 在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為 ，整個堆排序過程的時間復雜度為。12. 在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。三、計算題(每題 6分，共24分)1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A 0.next，試寫出該線性表。2.請畫出下圖的鄰接矩

6、陣和鄰接表。60507890344035720413 4567data n ext3. 已知一個圖的頂點集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;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 畫出向小根堆中加入數(shù)據(jù) 4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法(每題 7分，共14分)1. LinkList mynote(LinkList L)/L是

7、不帶頭結(jié)點的單鏈表的頭指針if(L&L- next) q=L ； L=L next; p=L ;S1:while(p n ext) p=p next;S2：p next=q ; q next=NULL ;return L;請回答下列問題：(1 )說明語句S1的功能；(2) 說明語句組S2的功能；(3) 設鏈表表示的線性表為(a1,a2,an),寫出算法執(zhí)行后的返回值所表示的線性 表。2. void ABC(BTNode * BT)if BT ABC (BT-left);ABC (BT-right);coutdatadata)item=BST-data;/ 查找成功 return ;else i

8、f(itemdata)return Find(,item);else return Find(,item);/if六、編寫算法(共 8 分)統(tǒng)計出單鏈表 HL 中結(jié)點的值等于給定值 X 的結(jié)點數(shù)。 int CountX(LNode* HL,ElemType x)數(shù)據(jù)結(jié)構(gòu)試卷(二)、選擇題 (24 分 )1下面關(guān)于線性表的敘述錯誤的是()。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C) 線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2 設哈夫曼樹中的葉子結(jié)點總數(shù)為m若用二叉鏈表作為存儲結(jié)

9、構(gòu)，則該哈夫曼樹中總共有( )個空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3. 設順序循環(huán)隊列 Q0 : M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置，尾指針 R 總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為 ( )。(A) R-F(B) F-R4 設某棵二叉樹的中序遍歷序列為得到序列為( )。(C) (R-F+M) M (D) (F-R+M) MABCD ，前序遍歷序列為 CABD ，則后序遍歷該二叉樹(A) BADC(B) BCDA (C) CDAB (D) CBDA5. 設某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。2

10、2(A) n(n-1)/2(B) n(n-1)(C) n 下面程序段的功能實現(xiàn)數(shù)據(jù) x 進棧，要求在下劃線處填上正確的語句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,int x)if (stack.top=m- 1) printf( “overflow ”);else ; 中序遍歷二叉排序樹所得到的序列是 序列(填有序或無序) 。 快速排序的最壞時間復雜度為 ，平均時間復雜度為 。 設某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為Nd,度數(shù)為1的結(jié)點數(shù)為N,則該二叉樹中度數(shù)為2 的結(jié)點數(shù)為 ；若采用二叉鏈表作為該二叉樹

11、的存儲結(jié)構(gòu)，則該二叉樹中共有個空指針域。(D) n 2-16 .設某棵二叉樹中有 2000個結(jié)點，則該二叉樹的最小高度為()。(A) 9(B) 10(C) 11(D) 127. 設某有向圖中有 n 個頂點，則該有向圖對應的鄰接表中有()個表頭結(jié)點。(A) n-1(B) n(C) n+1(D) 2n-18. 設一組初始記錄關(guān)鍵字序列(5， 2， 6， 3， 8)，以第一個記錄關(guān)鍵字 5為基準進行一趟快 速排序的結(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. 為了能有效地應用HASH查找技術(shù)

12、，必須解決的兩個問題是 和6. 設某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=。7. 設一組初始記錄關(guān)鍵字序列為（55，63，44，38, 75，80，31，56），則利用篩選法建立的初始堆為。& 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點 1出發(fā)，DFS遍歷的輸出序列是 ，BFS遍歷的輸出序列是團的鄰撞轟存儲結(jié)構(gòu)三、應用題（36分）1. 設一組初始記錄關(guān)鍵字序列為（45，80，48，40，22，78），則分別給出第4趟簡單選擇 排序和第4趟直接插入排序后的結(jié)果。2. 設指針變量p指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點 B,要求給出在結(jié)點 A的后面插入結(jié)點 B的操作

13、序列（設雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink ）。3. 設一組有序的記錄關(guān)鍵字序列為（13，18，24，35，47，50，62，83，90），查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4. 設一棵樹 T 中邊的集合為（A，B），（A，C），（A，D），（B，E），（C，F(xiàn)），（C，G），要求 用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應的二叉樹。5. 設有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6. 設有一組初始記錄關(guān)鍵字為（45，80，48, 40，22，78），要求構(gòu)造一棵二叉排序

14、樹并給出構(gòu)造過程。四、算法設計題（16分）1. 設有一組初始記錄關(guān)鍵字序列（K1，K2，K,），要求設計一個算法能夠在0（n）的時間復雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于K，右半部分的每個關(guān)鍵字均大于等于 K。2. 設有兩個集合 A和集合B,要求設計生成集合 C=AH B的算法，其中集合 A B和C用鏈 式存儲結(jié)構(gòu)表示。12345678.910.二、1.2.3.4.數(shù)據(jù)結(jié)構(gòu)試卷(三)A=(D ，R)，D=01 ，02，03， 04，05，06，07，08，09 ， R=r ，r=， ， ，則數(shù)據(jù)結(jié)構(gòu)(A) 線性結(jié)構(gòu) (B) 下面程序的時間復雜為( for ( i=1 ，

15、s=0； i=n ；(A) O( n)，樹型結(jié)構(gòu))i+)2(B) O(n 2)t=1A 是( )。 (C) 物理結(jié)構(gòu)(D) 圖型結(jié)構(gòu)設指針變量 p 指向單鏈表中結(jié)點 列為(A) q=p-next(B) q=p-next(C) q=p-next(D) q=p-next)。p-data=q-data q-data=p-data p-next=q-next p-data=q-dataA，；for(j=1 ； jnext=q-next p-next=q-next free(q) ； free(q) ；(A) 1(B) n(C) nlog 2n設一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，錄的一

16、趟快速排序結(jié)束后的結(jié)果為() 。(A) 10 ，15，14，18，20，36，40，21(B) 10 ，15，14，18，20，40，36，21(C) 10 ，15，14，20，18，40，36，2l(D) 15 ，10，14，18，20，36，40，21設有 n 個待排序的記錄關(guān)鍵字，則在堆排序中需要(設二叉排序樹中有(A) O(1) 設無向圖 G 中有 nj+) t=t*j ； s=s+t；4(D) O(n 4)A ，則需要修改指針的操作序free(q) ；free(q) ；)個輔助記錄單元。(D) n 221，36，40，10) ，則以 20 為基準記)。n 個結(jié)點，則在二叉排序樹的平均

17、平均查找長度為(2(B) O(log 2n)(C) (D) O(n 2)個頂點 e 條邊，則其對應的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為( )。(A) n， e(B) e ，n(C) 2n ，e (D) n ，2e設某強連通圖中有n 個頂點，則該強連通圖中至少有()條邊。(A) n(n-1) (B) n+1(C) n(D) n(n+1)選擇題 (每題 1 分，共 20分)設某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為設有 5000 個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的 10 個記錄關(guān) 鍵字，則用下列( )方法可以達到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序下

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

19、中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d,則e和d的關(guān)系為7. 遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。8. 設查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較次就可以斷定數(shù)據(jù)元素 X是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復雜度均為10. 設有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為 ，右孩子結(jié)點的編號為 。11. 設一組初始記錄關(guān)鍵字為(72，73，71，23，94，16, 5)，則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)

20、果為。12. 設有向圖G中有向邊的集合 E=1，2，2，3，1，4，4，2，4，3，則該圖的一種拓扌卜序歹y為。13. 下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。struct recordi nt key; int others;int hashsqsearch(struct record hashtable ,i nt k)int i,j; j=i=k % p;while (hashtablej.key!=k&hashtablej.flag!=0)j=() %m; if (i=j) return(-1);if () return(j); else return

21、(-1);14. 下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。typedef struct no dei nt key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k)if (t=0 ) return(0);else while (t!=0)if (t-key=k); else if (t-keyk) t=t-lchild; else;三、計算題(每題10分，共30分)1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ ，中序遍歷序列是EFAGBC

22、HKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2. 已知待散列的線性表為(36，15，40，63，22)，散列用的一維地址空間為0.6，假定 選用的散列函數(shù)是 H ( K) = K mod 7，若發(fā)生沖突采用線性探查法處理，試：(1 )計算出每一個元素的散列地址并在下圖中填寫出散列表：0123456(2)求出在查找每一個元素概率相等情況下的平均查找長度。3. 已知序列(10，18，4，3，6，12，1，9，18，8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。 四、算法設計題(每題15分，共30分)1. 設計在單鏈表中刪除值相同的多余結(jié)點的算法。2. 設計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。數(shù)據(jù)

23、結(jié)構(gòu)試卷(四)一、選擇題 (每題 1 分共 20 分)1設一維數(shù)組中有 n 個數(shù)組元素，則讀取第 i 個數(shù)組元素的平均時間復雜度為( )。2(A) O(n) (B) O(nlog 2n)(C) O(1) (D) O(n 2)2 設一棵二叉樹的深度為k，則該二叉樹中最多有()個結(jié)點。(A) 2k-1(B) 2 k(C) 2 k-1(D) 2 k-13設某無向圖中有 n個頂點e條邊，則該無向圖中所有頂點的入度之和為()。(A) n(B) e(C) 2n(D) 2e4. 在二叉排序樹中插入一個結(jié)點的時間復雜度為()。2(A) O(1)(B) O(n)(C) O(log 2n)(D) O(n 2)5.

24、 設某有向圖的鄰接表中有n個表頭結(jié)點和 m個表結(jié)點，則該圖中有()條有向邊。(A) n(B) n-1(C) m(D) m-16. 設一組初始記錄關(guān)鍵字序列為(345 , 253, 674, 924, 627),則用基數(shù)排序需要進行()趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A) 3(B) 4(C) 5(D) 87. 設用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作()。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別8. 下列四種排序中()的空間復雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆9.設某二叉樹中度數(shù)為0 的結(jié)

25、點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N ,度數(shù)為 2 的結(jié)點數(shù)為 N則下列等式成立的是( )。(A) N 0=N1 +1(B) N 0=Nl +N2(C) N 0=N2+1(D) N 0=2N1+l10. 設有序順序表中有n 個數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過( )。(A) log 2n+1(B) log 2n-1(C) log 2n(D) log2(n+1)二、填空題 ( 每空 1 分共 20 分 )1. 設有 n 個無序的記錄關(guān)鍵字, 則直接插入排序的時間復雜度為 ,快速排序的平均時間復雜度為 。2. 設指針變量 p指向雙向循環(huán)鏈表中的結(jié)點X,則刪除結(jié)點 X需要執(zhí)行的

26、語句序列為 (設結(jié)點中的兩個指 針域分別為 llink 和 rlink )。3. 根據(jù)初始關(guān)鍵字序列 (19, 22, 01, 38, 10)建立的二叉排序樹的高度為 。4. 深度為 k 的完全二叉樹中最少有 個結(jié)點。5. 設初始記錄關(guān)鍵字序列為 (Ki, K2,，K)，則用篩選法思想建堆必須從第 個元 素開始進行篩選。6. 設哈夫曼樹中共有 99 個結(jié)點, 則該樹中有 個葉子結(jié)點； 若采用二叉鏈表作為存儲結(jié)構(gòu),則該樹中有 個空指針域。7. 設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲 個隊列元素； 當前實際存儲 個隊列元素 (設頭指針 F 指向當前隊頭元素的前一個位置,尾

27、指針指向當前隊尾元素的位置) 。& 設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中 個元素。9. 設一組初始記錄關(guān)鍵字序列為(20, 18, 22 , 16, 30, 19)，則以20為中軸的一趟快速排序結(jié)果為。10. 設一組初始記錄關(guān)鍵字序列為(20, 18, 22, 16, 30, 19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為。11設某無向圖 G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是。12 設無向圖對應的鄰接矩陣為 A，則A中第i上非0元素的個數(shù) 第i列上非0元素的個數(shù)(

28、填等于，大于或小于)。13設前序遍歷某二叉樹的序列為ABCD ,中序遍歷該二叉樹的序列為BADC ,則后序遍歷該二叉樹的序列為。14.設散列函數(shù) H(k)=kmodp ,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志0。typedef struct node int key; struct node *n ext; lklist;void createlkhash(lklist *hashtable)int i,k; lklist *s;for(i=0;im;i+);for(i=

29、0;ikey=ai;k=ai % p; s-next=hashtablek;三、計算題(每題10分，共30分)的頭尾鏈表存儲結(jié)構(gòu)。1、畫出廣義表 LS=( ) , (e) , (a , (b , c , d )2、下圖所示的森林：(1) 求樹(a)的先根序列和后根序列；(2) 求森林先序序列和中序序列；(3) 將此森林轉(zhuǎn)換為相應的二叉樹；3、設散列表的地址范圍是0.9 ，散列函數(shù)為 H( key) = ( key 2 +2) MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設計題(每題10分，共30分)1 設單鏈表中有僅三類字符的數(shù)據(jù)元

30、素 （大寫字母、 數(shù)字和其它字符 ） ，要求利用原單鏈表 中結(jié)點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2. 設計在鏈式存儲結(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。3. 在鏈式存儲結(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題 (20 分 ) 1數(shù)據(jù)的最小單位是()。(A) 數(shù)據(jù)項 (B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量2設一組初始記錄關(guān)鍵字序列為 (50，40，95，20，15，70，60，45)，則以增量 d=4 的一 趟希爾排序結(jié)束后前 4 條記錄關(guān)鍵字為( )。(A) 40 ， 50，20，95(C) 15 ， 20，40，45(B) 15 ，

31、40，60，20(D) 45 ， 40，15，20(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,85函數(shù) substr(“DATASTRUCTU”RE,5, 9) 的返回值為果為( )。4(B) “ DATA”)。(A) “ STRUCTUR”E(C) “ ASTRUCTU”R 5設一個有序的單鏈表中有 n 個結(jié)點， 則該操作的時間復雜度為( )。(A) O(log 2n)(B)

32、O(1)6.設一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N),度數(shù)為1的結(jié)點數(shù)為N,，度數(shù)為 m的結(jié)3設一組初始記錄關(guān)鍵字序列為(25，50，15，35，80， 85，20，40，36，70)，其中含有 5個長度為 2 的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)(D) “ DATASTRUCTU”RE現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，2(C) O(n 2)(D) O(n)點數(shù)為Nm則N0= () (A) N i+N2+Nm(B) l+N 2+22+32+(m-1)Nm(C) N 2+2N3+3N4+(m-1)Nm(D) 2N i +3N2+(m+1)Nm7 .設有序表中

33、有1000個元素，則用二分查找查找元素X最多需要比較()次。(A) 25(B) 10(C) 7(D) 1&設連通圖 G 中的邊集 E=(a, b)，(a, e), (a, c)，(b，e), (e, d)，(d，f)，(f，c)，則從 頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為()。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9設輸入序列是1、2、3、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第 i 個輸出元素是( )。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10 設一組初始記錄關(guān)鍵字序列為 (45, 80, 55

34、, 40, 42, 85),則以第一個記錄關(guān)鍵字 45 為基準而得到一趟快速排序的結(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 分)1. 設有一個順序共享棧 S0：n-1 ,其中第一個棧項指針 top1 的初值為 -1 ,第二個棧頂 指針top2的初值為n,則判斷共享棧滿的條件是 。2. 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是3. 設有一個n階的下三角矩陣 A,如果按照行的順序

35、將下三角矩陣中的元素(包括對角線上元素)存放在 n(n+1)個連續(xù)的存儲單元中，則Aij 與A00之間有個數(shù)據(jù)元素。4. 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先 出隊列，所以又把隊列稱為 表。5. 設一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF則該二叉樹的前序遍歷序列為，中序遍歷序列為，后序遍歷序列為。6. 設一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為 ，有個葉子結(jié)點。7. 設有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的，第i列中所有

36、非零元素個數(shù)之和等于頂點i的。8. 設一組初始記錄關(guān)鍵字序列(ki, k2,kn)是堆，則對i=1 , 2,，n/2而言滿足的條件為。9. 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(i ntrn)for(i=1;i=n _1; i+)for(excha nge=O,j=O; jrj+1)temp=rj+1;rj=temp;excha nge=1;if (exchange=0) return ;10. 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordi nt key; int others;int bisea

37、rch(struct record r , i nt k)int low=0,mid,high=n-1;while(lownext=0(D) head!=045設一條單鏈表的頭指針變量為(A) head=0(C) head-next=head 時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog 2n) 的是( )。(A) 堆排序(B) 冒泡排序 (C) 希爾排序 (D) 快速排序設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是(A) 空或只有一個結(jié)點(B) 高度等于其結(jié)點數(shù)(C) 任一結(jié)點無左孩子(D) 任一結(jié)點無右孩子)。)。(B)(D)6一趟排序結(jié)束后不一定能夠選出一個元

38、素放在其最終位置上的是()。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希爾排序7設某棵三叉樹中有40 個結(jié)點，則該三叉樹的最小高度為()。(A) 3(B) 4(C) 5(D) 68順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為()。(A) O(n)2(B) O(n 2)1/2(C) O(n 1/2)(D) O(1og 2n)9二路歸并排序的時間復雜度為()。(A) O(n)2(B) O(n 2)(C) O(nlog 2n)(D) O(1og 2n)10.深度為 k 的完全二叉樹中最少有()個結(jié)點。(A) 2 k-1-1(B) 2 k-1(C) 2 k-1 +1k(D)

39、2 k-111.設指針變量 front表示鏈式隊列的隊頭指針，指針變量rear 表示鏈式隊列的隊尾指針,指針變量 s 指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作序列為()。(A) front-next=s； front=s ；(B) s-next=rear； rear=s ；(C) rear-next=s； rear=s ；(D) s-next=front； front=s ；12.設某無向圖中有 n個頂點 e 條邊，則建立該圖鄰接表的時間復雜度為()。(A) O(n+e)(B) O(n 2)(C) O(ne)(D) O(n 3)13.設某哈夫曼樹中有199 個結(jié)點，則該哈夫曼樹中有()個葉子結(jié)點

40、。(A) 99(B) 100(C) 101(D) 10214. 設二叉排序樹上有n 個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復雜度為()(A) O(n)2(B) O(n 2)(C) O(nlog 2n)(D) O(1og 2n)。o則有向圖 G 中頂點 i 的入度為( 第 i 列非 0元素的個數(shù)之和 第 i 列 0元素的個數(shù)之和15.設用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),(A) 第 i 行非 0 元素的個數(shù)之和(C) 第 i 行 0 元素的個數(shù)之和、判斷題 (20 分 )1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（ ）2分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。

41、（ ）3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）5設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）6層次遍歷初始堆可以得到一個有序的序列。（ ）7 .設一棵樹T可以轉(zhuǎn)化成二叉樹 BT,則二叉樹BT中一定沒有右子樹。（）8線性表的順序存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更好。（ ）9. 中序遍歷二叉排序樹可以得到一個有序的序列。（ ）10. 快速排序是排序算法中平均性能最好的一種排序。 （） 三、填空題 （30 分 ）1. for（i=1 ， t=1 ， s=0 ； i=n ；i+） t=t*i；s=

42、s+t ； 的時間復雜度為 。2. 設指針變量p指向單鏈表中結(jié)點 A,指針變量s指向被插入的新結(jié)點 X,則進行插入操作 的語句序列為 （設結(jié)點的指針域為 next ）。3. 設有向圖 G的二元組形式表示為 G =（ D，R），D=1，2，3，4，5，R=r，r=， 則給出該圖的一種拓撲排序序列 。4設無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是 。5. 設二叉樹中度數(shù)為 0 的結(jié)點數(shù)為 50，度數(shù)為 1 的結(jié)點數(shù)為 30，則該二叉樹中總共有 個結(jié)點數(shù)。6. 設 F 和 R 分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為7. 設二叉樹中結(jié)點的兩個指針域分別為lchi

43、ld 和 rchild ，則判斷指針變量 p 所指向的結(jié)點為葉子結(jié)點的條件是 。8. 簡單選擇排序和直接插入排序算法的平均時間復雜度為 。9. 快速排序算法的空間復雜度平均情況下為 ，最壞的情況下為 。10. 散列表中解決沖突的兩種方法是 和 。四、算法設計題 （20 分 ）1 .設計在順序有序表中實現(xiàn)二分查找的算法。 2設計判斷二叉樹是否為二叉排序樹的算法。3 .在鏈式存儲結(jié)構(gòu)上設計直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷(七)一、選擇題 (30 分 )1設某無向圖有 n 個頂點，則該無向圖的鄰接表中有( )個表頭結(jié)點。(A) 2n (B) n(C) n/2(D) n(n-1)2設無向圖 G 中有 n

44、個頂點，則該無向圖的最小生成樹上有()條邊。(A) n (B) n-1(C) 2n(D) 2n-13設一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字 45 為基準而得到的一趟快速排序結(jié)果是( )。4567(A) 40 ， 42， 60， 55， 80，(C) 42 ， 40， 55， 60， 80， )二叉排序樹可以得到一個從小到大的有序序列。(A) 先序遍歷 (B) 中序遍歷 設按照從上到下、從左到右的順序從 點的左孩子結(jié)點的編號為( )。(A) 2i+1(B) 2i程序段 s=i=0； do i=i+1 ； s=s+i；(A) O(n)(B) O(nlog

45、 2n)8585(B) 42 ，45，(D) 42 ，40，(C) 后序遍歷55，60，60，85，85，8055，80層次遍歷1 開始對完全二叉樹進行順序編號，則編號為i 結(jié)(D)設帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為(A) head=0(C) i/2(D) 2i-1while(inext=0)。)。(C) head-next=head(D) head!=08設某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有()。(A) 20 (B) 256 (C) 512 (D) 1024 9設一組初始記錄關(guān)鍵字序列為(13 ， 18， 24， 35， 47， 50， 62， 83， 90， 115，

46、 134), 則利用二分法查找關(guān)鍵字 90 需要比較的關(guān)鍵字個數(shù)為( )。(A) 1 (B) 2 (C) 3 (D) 410. 設指針變量 top 指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為()。(B) top=top-1;(A) top=top+1;(C) top-next=top;(D) top=top-next;、判斷題 (20 分 )1不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。()2當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。()O(log 2n) 。()3設某堆中有 n 個結(jié)點，則在該堆中插入一個新結(jié)點的時間復雜度為4完全二叉樹中的葉子結(jié)

47、點只可能在最后兩層中出現(xiàn)。 ( ) 5哈夫曼樹中沒有度數(shù)為 1 的結(jié)點。( ) 6對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。 ( ) 7先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。()8由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。( )9線性表中的所有元素都有一個前驅(qū)元素和后繼元素。( )10. 帶權(quán)無向圖的最小生成樹是唯一的。 () 三、填空題 (30 分)1. 設指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點 X 的操作序列為 =p ；s-right=p-right ； =s ；p-right-left=s ；(設結(jié)點中的兩

48、個指針域分別為 left 和 right )。2. 設完全有向圖中有n個頂點，則該完全有向圖中共有 條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有 條無向邊。3. 設關(guān)鍵字序列為(Ki, &, Kn)，則用篩選法建初始堆必須從第 個元素開始進行篩選。4. 解決散列表沖突的兩種方法是 和 。5. 設一棵三叉樹中有 50 個度數(shù)為 0 的結(jié)點, 21 個度數(shù)為 2 的結(jié)點,則該二叉樹中度數(shù)為3 的結(jié)點數(shù)有 個。6. 高度為 h 的完全二叉樹中最少有 個結(jié)點,最多有 個結(jié)點。7. 設有一組初始關(guān)鍵字序列為(24,35, 12,27,18, 26) ,則第 3趟直接插入排序結(jié)束后的結(jié)果的是 。8. 設有一組初始關(guān)鍵字序列為(24,35, 12,27,18, 26) ,則第 3趟簡單選擇排序結(jié)束后的結(jié)果的是 。9. 設一棵二叉樹