十套數(shù)據(jù)結(jié)構(gòu)試題

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

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

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

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

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

6、 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是不帶頭結(jié)點的單鏈表的頭指針if(L&&

7、;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) 設(shè)鏈表表示的線性表為(a1,a2,an),寫出算法執(zhí)行后的返回值所表示的線性 表。2. void ABC(BTNode * BT)if BT ABC (BT->left);ABC (BT->right);cout<<BT->data<<&#

8、39;'該算法的功能是：五、算法填空(共 8分)二叉搜索樹的查找 一讒歸算法：bool Fi nd(BTreeNode* BST,ElemType & item) if (BST=NULL) return false; / 查找失敗 else if (item=BST->data) item=BST->data;/ 查找成功 return ;else if(item<BST->data) return Find(,item);else return Find(,item);/if六、編寫算法(共 8 分) 統(tǒng)計出單鏈表 HL 中結(jié)點的值等于給定值 X 的

9、結(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 設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有( )個空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3. 設(shè)順序循環(huán)隊列 Q0 : M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元

10、素的前一位置，尾指針 R 總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為 ( )。(A) R-F(B) F-R4 設(shè)某棵二叉樹的中序遍歷序列為得到序列為( )。(C) (R-F+M) M (D) (F-R+M) MABCD ，前序遍歷序列為 CABD ，則后序遍歷該二叉樹(A) BADC(B) BCDA (C) CDAB (D) CBDA5. 設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。22(A) n(n-1)/2(B) n(n-1)(C) n 下面程序段的功能實現(xiàn)數(shù)據(jù) x 進棧，要求在下劃線處填上正確的語句。typedef struct int s100; int top

11、; sqstack;void push(sqstack &stack,int x)if (stack.top=m- 1) printf( “overflow ”);else ; 中序遍歷二叉排序樹所得到的序列是 序列(填有序或無序) 。 快速排序的最壞時間復(fù)雜度為 ，平均時間復(fù)雜度為 。 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為Nd,度數(shù)為1的結(jié)點數(shù)為N,則該二叉樹中度數(shù)為2 的結(jié)點數(shù)為 ；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有個空指針域。(D) n 2-16 .設(shè)某棵二叉樹中有 2000個結(jié)點，則該二叉樹的最小高度為()。(A) 9(B) 10(C) 11(D) 127. 設(shè)

12、某有向圖中有 n 個頂點，則該有向圖對應(yīng)的鄰接表中有()個表頭結(jié)點。(A) n-1(B) n(C) n+1(D) 2n-18. 設(shè)一組初始記錄關(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. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是 和6. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=。7. 設(shè)一組初始記錄關(guān)鍵字序列為（55，63，44，38, 75，80，31，

13、56），則利用篩選法建立的初始堆為。& 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點 1出發(fā)，DFS遍歷的輸出序列是 ，BFS遍歷的輸出序列是團的鄰撞轟存儲結(jié)構(gòu)三、應(yīng)用題（36分）1. 設(shè)一組初始記錄關(guān)鍵字序列為（45，80，48，40，22，78），則分別給出第4趟簡單選擇 排序和第4趟直接插入排序后的結(jié)果。2. 設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點 B,要求給出在結(jié)點 A的后面插入結(jié)點 B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink ）。3. 設(shè)一組有序的記錄關(guān)鍵字序列為（13，18，24，35，47，50，62，83，90），查找方法用二

14、分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4. 設(shè)一棵樹 T 中邊的集合為（A，B），（A，C），（A，D），（B，E），（C，F(xiàn)），（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è)計題（16分）1. 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，K,），要求設(shè)計一個算法能夠在0（n）的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部

15、分的每個關(guān)鍵字均小于K，右半部分的每個關(guān)鍵字均大于等于 K。2. 設(shè)有兩個集合 A和集合B,要求設(shè)計生成集合 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=<01 ，02>，<01，03>，<01，04>， <03，08>，<03，09> ，則數(shù)據(jù)結(jié)構(gòu)(A) 線性結(jié)構(gòu) (B) 下面程序的時間復(fù)雜為( for ( i=1 ， s=0； i<=n ；(A)

16、O( n)<02，05>，<02，06>，<03，07>，樹型結(jié)構(gòu))i+)2(B) O(n 2)t=1A 是( )。 (C) 物理結(jié)構(gòu)(D) 圖型結(jié)構(gòu)設(shè)指針變量 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 ； j<=i ；3(C) O(n 3) 若

17、刪除單鏈表中結(jié)點p->next=q->next p->next=q->next free(q) ； free(q) ；(A) 1(B) n(C) nlog 2n設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，錄的一趟快速排序結(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設(shè)有 n 個待排序的記錄關(guān)鍵字，則在堆排序中需要(設(shè)二叉排序樹中有(A) O(1) 設(shè)無向圖 G 中

18、有 n為( )。(A) n， e設(shè)某強連通圖中有j+) 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é)點，則在二叉排序樹的平均平均查找長度為(2(B) O(log 2n)(C) (D) O(n 2)個頂點 e 條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別(B) e ，n(C) 2n ，e (D) n ，2en 個頂點，則該強連通圖中至少有()條邊。)。(A) n(n-1) (B) n+1(C) n(D) n(n+1)選擇題 (每題

19、1 分，共 20分)設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為設(shè)有 5000 個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的 10 個記錄關(guān) 鍵字，則用下列( )方法可以達到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序下列四種排序中( )的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序填空殖 (每空 1分 共20 分)數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和兩種情況。設(shè)一棵完全二叉樹中有 500 個結(jié)點， 則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個空指針域。設(shè)輸入序列為 1、2、 3，則經(jīng)過棧的作用后可以得到 種不同的輸出

20、序列。設(shè)有向圖 G 用鄰接矩陣 Ann 作為存儲結(jié)構(gòu)， 則該鄰接矩陣中第 i 行上所有元素之和 等于頂點 i 的 ，第 i 列上所有元素之和等于頂點 i 的。5. 設(shè)哈夫曼樹中共有 n個結(jié)點，則該哈夫曼樹中有 個度數(shù)為1的結(jié)點。6. 設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d,則e和d的關(guān)系為7. 遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。8. 設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較次就可以斷定數(shù)據(jù)元素 X是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為10.

21、 設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為 ，右孩子結(jié)點的編號為 。11. 設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16, 5)，則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)果為。12. 設(shè)有向圖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

22、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(-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 ) ret

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

24、元素概率相等情況下的平均查找長度。3. 已知序列(10，18，4，3，6，12，1，9，18，8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。 四、算法設(shè)計題(每題15分，共30分)1. 設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。2. 設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。數(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é)點。(A) 2k-1(B) 2 k(C) 2 k-

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

26、 設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作()。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別8. 下列四種排序中()的空間復(fù)雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆9.設(shè)某二叉樹中度數(shù)為0 的結(jié)點數(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. 設(shè)有序順序表中有n 個數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過( )。(A) log 2n+1(B) log

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

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

29、(20, 18, 22, 16, 30, 19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為。11設(shè)某無向圖 G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是。12 設(shè)無向圖對應(yīng)的鄰接矩陣為 A，則A中第i上非0元素的個數(shù) 第i列上非0元素的個數(shù)(填等于，大于或小于)。13設(shè)前序遍歷某二叉樹的序列為ABCD ,中序遍歷該二叉樹的序列為BADC ,則后序遍歷該二叉樹的序列為。14.設(shè)散列函數(shù) H(k)=kmodp ,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功

30、時返回標志0。typedef struct node int key; struct node *n ext; 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;三、計算題(每題10分，共30分)的頭尾鏈表存儲結(jié)構(gòu)。1、畫出廣義表 LS=( ) , (e) , (a , (b , c ,

31、 d )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è)計題(每題10分，共30分)1 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素 （大寫字母、 數(shù)字和其它字符 ） ，要求利用原單鏈表 中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2. 設(shè)計在鏈式存儲結(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。3. 在鏈式存儲結(jié)構(gòu)

32、上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題 (20 分 ) 1數(shù)據(jù)的最小單位是()。(A) 數(shù)據(jù)項 (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(C) 15 ， 20，40，45(B) 15 ， 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

33、,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設(shè)一個有序的單鏈表中有 n 個結(jié)點， 則該操作的時間復(fù)雜度為( )。(A) O(log 2n)(B) O(1)6.設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N),度數(shù)為1的結(jié)點數(shù)為N,，度數(shù)為 m的結(jié)3設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80， 85，20，40，36，70)，其中含有 5個長度為

34、 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 .設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較()次。(A) 25(B) 10(C) 7(D) 1&設(shè)連通圖 G 中的邊集 E=(a, b)，(a, e), (a, c)，(b

35、，e), (e, d)，(d，f)，(f，c)，則從 頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為()。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9設(shè)輸入序列是1、2、3、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第 i 個輸出元素是( )。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為 (45, 80, 55, 40, 42, 85),則以第一個記錄關(guān)鍵字 45 為基準而得到一趟快速排序的結(jié)果是( )。(A) 40 , 42, 45, 55, 80, 83(B) 42 , 40, 45,

36、 80, 85, 88(C) 42 , 40, 45, 55, 80, 85(D) 42 , 40, 45, 85, 55, 80二、填空題 ( 共 20 分)1. 設(shè)有一個順序共享棧 S0：n-1 ,其中第一個棧項指針 top1 的初值為 -1 ,第二個棧頂 指針top2的初值為n,則判斷共享棧滿的條件是 。2. 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是3. 設(shè)有一個n階的下三角矩陣 A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素)存放在 n(n+1)個連續(xù)的存儲單元中，則Aij 與A00之間有個數(shù)據(jù)元素。4. 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所

37、以又把棧稱為表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先 出隊列，所以又把隊列稱為 表。5. 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF則該二叉樹的前序遍歷序列為，中序遍歷序列為，后序遍歷序列為。6. 設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為 ，有個葉子結(jié)點。7. 設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的，第i列中所有非零元素個數(shù)之和等于頂點i的。8. 設(shè)一組初始記錄關(guān)鍵字序列(ki, k2,kn)是堆，則對i=1 , 2,，n/2而言滿足的條件為。9. 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下

38、劃線處填上正確的語句。void bubble(i ntrn)for(i=1;i<=n _1; i+)for(excha nge=O,j=O; j<j+)if (rj>rj+1)temp=rj+1;rj=temp;excha nge=1;if (exchange=0) return ;10. 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordi nt key; int others;int bisearch(struct record r , i nt k)int low=0,mid,high=n-1;while(low<=high

39、)if(rmid.key=k) return(mid+1); else if() high=mid-1;else low=mid+1; return(O);三、應(yīng)用題(32分)1. 設(shè)某棵二叉樹的中序遍歷序列為DBEAC前序遍歷序列為 ABDEC要求給出該二叉樹的的后序遍歷序列。2. 設(shè)無向圖G (如右圖所示)，給出該圖的最小生成樹上邊的集合并 計算最小生成樹各邊上的權(quán)值之和。3. 設(shè)一組初始記錄關(guān)鍵字序列為(15 , 17, 18, 22, 35, 51, 60),要求計算出成功查找時的平均查找長度。4. 設(shè)散列表的長度為 8,散列函數(shù)H(k)=k mod7，初始記錄關(guān)鍵字序列為(25, 3

40、1, 8, 27,13, 68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。四、算法設(shè)計題 （28 分 ）1 設(shè)計判斷兩個二叉樹是否相同的算法。2 設(shè)計兩個有序單鏈表的合并排序算法。數(shù)據(jù)結(jié)構(gòu)試卷(六)1、選擇題 (30 分 )設(shè)一組權(quán)值集合 W=2， 3， 4， 5， 6 ，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度 之和為(A) 20(B) 30)。2執(zhí)行一趟快速排序能夠得到的序列是(A) 41(B) 45(C) 63(D) 12，12，34，12，27，34，12，34，45，(C) 40)。63277272(D) 45345， 27 55 72，41 55 72

41、 ， 63，45， 27 55 41，41 55 34 ， 63，head 且該鏈表沒有頭結(jié)點，則其判空條件是(B) head->next=0(D) head!=045設(shè)一條單鏈表的頭指針變量為(A) head=0(C) head->next=head 時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog 2n) 的是( )。(A) 堆排序(B) 冒泡排序 (C) 希爾排序 (D) 快速排序設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是(A) 空或只有一個結(jié)點(B) 高度等于其結(jié)點數(shù)(C) 任一結(jié)點無左孩子(D) 任一結(jié)點無右孩子)。)。(B)(D)6一趟排序結(jié)束

42、后不一定能夠選出一個元素放在其最終位置上的是()。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希爾排序7設(shè)某棵三叉樹中有40 個結(jié)點，則該三叉樹的最小高度為()。(A) 3(B) 4(C) 5(D) 68順序查找不論在順序線性表中還是在鏈式線性表中的時間復(fù)雜度為()。(A) O(n)2(B) O(n 2)1/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(1og 2n)10.深度為 k 的完全二叉樹中最少有()個結(jié)點。(A) 2 k-1-1(B) 2 k-1(C) 2

43、k-1 +1k(D) 2 k-111.設(shè)指針變量 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.設(shè)某無向圖中有 n個頂點 e 條邊，則建立該圖鄰接表的時間復(fù)雜度為()。(A) O(n+e)(B) O(n 2)(C) O(ne)(D) O(n 3)13.設(shè)某哈夫

44、曼樹中有199 個結(jié)點，則該哈夫曼樹中有()個葉子結(jié)點。(A) 99(B) 100(C) 101(D) 10214. 設(shè)二叉排序樹上有n 個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為()(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.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu), (A) 第 i 行非 0 元素的個數(shù)之和 (C) 第 i 行 0 元素的個數(shù)之和、判斷題 (20 分 )1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（ ）2分塊查找的平均查

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

46、， s=0 ； i<=n ；i+） t=t*i；s=s+t ； 的時間復(fù)雜度為 。2. 設(shè)指針變量p指向單鏈表中結(jié)點 A,指針變量s指向被插入的新結(jié)點 X,則進行插入操作 的語句序列為 （設(shè)結(jié)點的指針域為 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> 則給出該圖的一種拓撲排序序列 。4設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是 。5. 設(shè)二叉樹中度數(shù)為 0 的結(jié)點數(shù)為 50，度數(shù)

47、為 1 的結(jié)點數(shù)為 30，則該二叉樹中總共有 個結(jié)點數(shù)。6. 設(shè) F 和 R 分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為7. 設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild 和 rchild ，則判斷指針變量 p 所指向的結(jié)點為葉子結(jié)點的條件是 。8. 簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為 。9. 快速排序算法的空間復(fù)雜度平均情況下為 ，最壞的情況下為 。10. 散列表中解決沖突的兩種方法是 和 。四、算法設(shè)計題 （20 分 ）1 .設(shè)計在順序有序表中實現(xiàn)二分查找的算法。 2設(shè)計判斷二叉樹是否為二叉排序樹的算法。3 .在鏈式存儲結(jié)構(gòu)上設(shè)計直接插入排序算法數(shù)據(jù)結(jié)

48、構(gòu)試卷(七)一、選擇題 (30 分 )1設(shè)某無向圖有 n 個頂點，則該無向圖的鄰接表中有( )個表頭結(jié)點。(A) 2n (B) n(C) n/2(D) n(n-1)2設(shè)無向圖 G 中有 n 個頂點，則該無向圖的最小生成樹上有()條邊。(A) n (B) n-1(C) 2n(D) 2n-13設(shè)一組初始記錄關(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) 中序

49、遍歷 設(shè)按照從上到下、從左到右的順序從 點的左孩子結(jié)點的編號為( )。(A) 2i+1(B) 2i程序段 s=i=0； do i=i+1 ； s=s+i；(A) O(n)(B) O(nlog 2n)8585(B) 42 ，45，(D) 42 ，40，(C) 后序遍歷55，60，60，85，85，8055，80層次遍歷1 開始對完全二叉樹進行順序編號，則編號為i 結(jié)(D)設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為(A) head=0(C) i/2(D) 2i-1while(i<=n) ；的時間復(fù)雜度為(C) O(n 2)(D) O(n 3/2)head，則其判空條件是(B) head->

50、;next=0)。)。(C) head->next=head(D) head!=08設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有()。(A) 20 (B) 256 (C) 512 (D) 1024 9設(shè)一組初始記錄關(guān)鍵字序列為(13 ， 18， 24， 35， 47， 50， 62， 83， 90， 115， 134), 則利用二分法查找關(guān)鍵字 90 需要比較的關(guān)鍵字個數(shù)為( )。(A) 1 (B) 2 (C) 3 (D) 410. 設(shè)指針變量 top 指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為()。(B) top=top-1;(A) top=top+1;(C) top-&

51、gt;next=top;(D) top=top->next;、判斷題 (20 分 )1不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。()2當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。()O(log 2n) 。()3設(shè)某堆中有 n 個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為4完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。 ( ) 5哈夫曼樹中沒有度數(shù)為 1 的結(jié)點。( ) 6對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。 ( ) 7先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。()8由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。( )

52、9線性表中的所有元素都有一個前驅(qū)元素和后繼元素。( )10. 帶權(quán)無向圖的最小生成樹是唯一的。 () 三、填空題 (30 分)1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點 X 的操作序列為 =p ；s->right=p->right ； =s ；p->right->left=s ；(設(shè)結(jié)點中的兩個指針域分別為 left 和 right )。2. 設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有 條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有 條無向邊。3. 設(shè)關(guān)鍵字序列為(Ki, &, Kn)，則用篩選法建初始堆必須從第 個元素開始進行篩選。4. 解決散列表沖突的兩種方法是 和 。5. 設(shè)一棵三叉樹中有 50 個度數(shù)為 0 的結(jié)點, 21 個度數(shù)為 2 的結(jié)點,則該二叉樹中度數(shù)為3 的結(jié)點數(shù)有 個。6. 高度為 h 的完全二叉樹中最少有 個結(jié)點,最多有 個結(jié)點。7. 設(shè)有一組初始關(guān)鍵字序列為(24,35, 12,27,18, 26),則第 3趟直接插入