數(shù)據(jù)結(jié)構(gòu)試題與答案

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

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

3、則查找 A 3的比較序列的下標(biāo)依次為8.A. O(1)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ù)，則散列地址為A 1B10. 保是一個連通圖。A.5 B.6 C.7 、填空題(每空 1分，共 26 分) 通常從四個方面評價算法的質(zhì)量： 、 、_一個算法的時間復(fù)雜度為 (n 3+n2log 2n+14n)/n 2，其數(shù)量級表示為 。假定一棵樹的廣義表表示為A ( C, D(E, F, G) , H( I , J),則樹中所含的結(jié)點數(shù)為個，樹的深度為 ，樹的度為

4、。 后綴算式 9 2 3 +- 10 2 / - 的值為 。中綴算式( 3+4X) -2Y/3 對應(yīng)的后綴算式為 。若用鏈表存儲一棵二叉樹時,每個結(jié)點除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個 指針。在這種存儲結(jié)構(gòu)中, 個指針域是存放了地址,有 對于一個具有 n 個頂點和 點分別有 _AOV網(wǎng)是一種的圖。在一個具有 n 個頂點的無向完全圖中,包含有 有向完全圖中,包含有 條邊。假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù) 的元素成為一個子表,則得到的四個子表分別為1 的元素有( )個，2 C 3D 4設(shè)有 6 個結(jié)點的無向圖，該圖至少應(yīng)有(

5、 ) 條邊才能確D.8個和n 個結(jié)點的二叉樹共有 個指針域，其中有 _ 個指針是空指針。e 條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié) 個。條邊，在一個具有 n 個頂點的10.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度11. 在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運(yùn)算的時間復(fù)雜度為，整個堆排序過程的時間復(fù)雜度為 。12. 在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。三、計算題(每題 6分，共24分)1.在如下數(shù)組A中存儲了一個線性表，表頭指針為A 0. next，試寫出該線性表。60507890344035720413 4567data n ext2

6、.請畫出下圖的鄰接矩陣和鄰接表。3. 已知一個圖的頂點集 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&L- next

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

8、tem);else return Find(,item);/if六、編寫算法(共 8 分) 統(tǒng)計出單鏈表 HL 中結(jié)點的值等于給定值 X 的結(jié)點數(shù)。 int CountX(LNode* HL,ElemType x)、選擇題 (24 分 )1下面關(guān)于線性表的敘述錯誤的是()。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2 設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有( )個空指針域。(A) 2m-1(B)

9、2m(C) 2m+1(D) 4m3 設(shè)順序循環(huán)隊列Q0 : M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為)。(A) R-F(B) F-R4 設(shè)某棵二叉樹的中序遍歷序列為到序列為( )。(C) (R-F+M) MABCD前序遍歷序列為(D) (F-R+M) MCABD則后序遍歷該二叉樹得(A) BADC5.設(shè)某完全無向圖中有(A) n(n-1)/2(D) CBDA)條邊。2(D) n 2-1(B) BCDA(C) CDABn 個頂點，則該完全無向圖中有(2(B) n(n-1)(C) n 26 .設(shè)某棵二叉樹

10、中有2000個結(jié)點，則該二叉樹的最小高度為()。(A) 9(B) 10(C) 11(D) 127. 設(shè)某有向圖中有 n個頂點，則該有向圖對應(yīng)的鄰接表中有()個表頭結(jié)點。(A) n-1(B) n(C) n+1(D) 2n-1&設(shè)一組初始記錄關(guān)鍵字序列(5 ， 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ù)，必須解決的兩個問題是 和2. 下面程序段的功能實現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的

11、語句。typedef struct int s100; int top; sqstack;void push（sqstack &stack,i nt x）if （stack.top=m-1）printf（“overflow ” ）;else ;3. 中序遍歷二叉排序樹所得到的序列是 序列（填有序或無序）。4. 快速排序的最壞時間復(fù)雜度為 ，平均時間復(fù)雜度為。5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N）,度數(shù)為1的結(jié)點數(shù)為Ni,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為;若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有個空指針域。6. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=

12、7. 設(shè)一組初始記錄關(guān)鍵字序列為（55，63，44，38，75，80，31，56），則利用篩選法建立的初始堆為。&已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點 1出發(fā)，DFS遍歷的輸出序列是，BFS遍歷的輸出序列是國的鄰接轟存舊結(jié)枸三、應(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)鍵字序列為（1

13、3，18，24，35，47，50，62，83，90），查找方法用二分查找，要求計算出查找關(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)鍵字序列（K , K2，Kn）,

14、要求設(shè)計一個算法能夠在0（n）的時間復(fù)雜度將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki ，右半部分的每個關(guān)鍵字均大于等于 Ki 。2. 設(shè)有兩個集合 A和集合B,要求設(shè)計生成集合 C=AA B的算法，其中集合 A B和C用鏈 式存儲結(jié)構(gòu)表示。12345678.910.二、1.2.3.4.、選擇題 (每題 1 分，共 20分)設(shè)某數(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 是()。(A) 線性結(jié)構(gòu) 下面程序的時間復(fù)雜為( for ( i=1 ， s=0 ；(A

15、) O(n) 設(shè)指針變量 p 列為( )。(A) q=p-next(B) q=p-next(C) q=p-next(D) q=p-next(B) 樹型結(jié)構(gòu)) idata=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) ；設(shè)有 n 個待排序的記錄關(guān)鍵字，則在堆排序中需要(A) 1(B) n(C) nlog 2n設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為 (20 ， 15， 14， 18， 記錄的一趟快速排序結(jié)束后的結(jié)果為(A) 10 ，(B) 1

16、0 ，(C) 10 ，(D) 15 ，15，15，15，10，14，14，14，14，18，18，20，18，20，20，18，20，36，40，40，36，40，36，36，40，( ) 。21212l21； j+) t=t*j；s=s+t ； 4(D) O(n 4)A,則需要修改指針的操作序free(q) ； free(q) ；)個輔助記錄單元。(D) n 221， 36， 40， 10) ，則以 20 為基準(zhǔn)設(shè)二叉排序樹中有(A) O(1) 設(shè)無向圖 G 中有 nn 個結(jié)點，則在二叉排序樹的平均平均查找長度為(2(B) O(log 2n)(C) (D) O(n 2)個頂點 e 條邊，則其

17、對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別)。為( )。(A) n ， e(B) e ， n (C) 2n ， e (D) n ， 2e設(shè)某強(qiáng)連通圖中有n 個頂點，則該強(qiáng)連通圖中至少有()條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)設(shè)有 5000 個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10 個記錄關(guān)鍵字，則用下列()方法可以達(dá)到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序下列四種排序中()的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序填空殖 (每空 1分 共20分)數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和

18、兩種情況。設(shè)一棵完全二叉樹中有 500 個結(jié)點，則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個空指針域。設(shè)輸入序列為 1、2、3，則經(jīng)過棧的作用后可以得到 種不同的輸出序列。設(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個元

19、素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較次就可以斷定數(shù)據(jù)元素X是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為。10. 設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為 ，右孩子結(jié)點的編號為 。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，則該圖的一種拓扌卜序歹y為。13. 下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃

20、線處填上正確的語句。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!=O)j=() %m; if (i=j)return(-1);if () return(j); else return(-1);14. 下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。typedef structnodeintkey; struct node *lchild

21、; 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中序遍歷序列是EFAGBCHKIJD畫出此二叉樹，并畫出它的后序線索二叉樹。2 .已知待散列的線性表為(36，15，40，63，22)，散列用的一維地址空間為0.6，假定選用的散列函數(shù)是 H ( K) = K mod

22、 7，若發(fā)生沖突采用線性探查法處理，試：(1 )計算出每一個元素的散列地址并在下圖中填寫出散列表：0123456(2)求出在查找每一個元素概率相等情況下的平均查找長度。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é)點算法。一、選擇題 (每題 1 分共 20 分)1設(shè)一維數(shù)組中有 n 個數(shù)組元素，則讀取第 i 個數(shù)組元素的平均時間復(fù)雜度為( )。2(A) O(n) (B) O(nlog 2n)(C) O(1) (D) O

23、(n . 設(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，Kn)，則用篩選法思想建堆必須從第 個元 素開始進(jìn)行篩選。6. 設(shè)哈夫曼樹中共有 99 個結(jié)點,則該樹中有 個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu),則該樹中有 個

24、空指針域。 7. 設(shè)有一個順序循環(huán)隊列中有 M 個存儲單元,則該循環(huán)隊列中最多能夠存儲 個隊列元素；當(dāng)前實際存儲 個隊列元素(設(shè)頭指針 F 指向當(dāng)前隊頭元素的前一個位置,尾指針指向當(dāng)前隊尾元素的位置) 。)2 設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有()個結(jié)點。(A) 2k-1(B) 2 k(C) 2 k-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è)某有向圖的鄰接

25、表中有n個表頭結(jié)點和 m個表結(jié)點，則該圖中有()條有向邊。(A) n(B) n-1(C) m(D) m-16. 設(shè)一組初始記錄關(guān)鍵字序列為(345 , 253, 674, 924, 627),則用基數(shù)排序需要進(jìn)行()趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(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é)點數(shù)為N0,

26、度數(shù)為1的結(jié)點數(shù)為N ,度數(shù)為2的結(jié)點數(shù)為N2, 則下列等式成立的是( )。(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) log2n+1(B) log 2n-1(C) log 2n(D) log2(n+1)二、填空題( 每空 1 分共 20 分 )& 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中 個元素。9. 設(shè)一組初始記錄關(guān)鍵字序列為(20, 18, 22,

27、 16, 30, 19)，則以20為中軸的一趟快速排序結(jié)果為。10. 設(shè)一組初始記錄關(guān)鍵字序列為(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，解決沖突的方法為鏈地址法。要求在下列算法劃線處填

28、上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志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=0;ikey=ai; k=ai % p; s-next=hashtablek;三、計算題(每題10分，共30分)的頭尾鏈表存儲結(jié)構(gòu)。1、畫出廣義表 LS=( ) , (e) , (a , (b , c , d )2、

29、下圖所示的森林：(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、& 9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計題(每題10分，共30分)1 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素 （ 大寫字母、數(shù)字和其它字符 ） ，要求利用原單鏈 表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。一

30、、選擇題 (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(B) 15 ，40，60，20(C) 15 ，20，40，45(D) 45 ，40，15，203設(shè)一組初始記錄關(guān)鍵字序列為 (25，50，15，35，80，85，20，40，36，70) ，其中含有5 個長度為 2 的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果

31、為()(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(“DATASTRUCTU”RE, 5, 9) 的返回值為()(A) “STRUCTUR”E(B) “ DATA”(C) “ASTRUCTU”R(D) “ DATASTRUCTU”RE5. 設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序， 則該操作的時間復(fù)雜度為( )。

32、2(A) O(log 2n)(B) O(1)(C) O(n 2)(D) O(n)6. 設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N),度數(shù)為1的結(jié)點數(shù)為N ,，度數(shù)為 m的結(jié)點數(shù)為Nm則N0= () (A) N 1+N2+Nm(C) N 2+2N3+3N4+(m-1)Nm(B) l+N 2+22+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 , e) , (e , d) ,

33、(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 為基準(zhǔn)而得到一趟快速排序的結(jié)果是( )。(A) 40 , 42, 45, 55, 80, 83(B) 42 , 40, 45, 8

34、0, 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. 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，

35、所以又把棧稱為表；隊列的插入和刪除運(yùn)算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定 先出隊列，所以又把隊列稱為 表。5. 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDE，F(xiàn) 則該二叉樹的前序遍歷序列為 ，中序遍歷序列為 ，后序遍歷序列為 。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. 下面程序段的

36、功能是實現(xiàn)冒泡排序算法,請在下劃線處填上正確的語句。 void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;rj=temp;exchange=1;if (exchange=0) return ；10. 下面程序段的功能是實現(xiàn)二分查找算法,請在下劃線處填上正確的語句。 struct recordint key; int others;int bisearch(struct record r , int k)int low=0,mid,high=n-1; while(lownext=0(D) head!=0

37、設(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é)點無右孩子一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是(A) 堆排序(B) 冒泡排序(C) 快速排序(D)設(shè)某棵三叉樹中有 40個結(jié)點,則該三叉樹的最小高度為(A) 3(B) 4(C) 5(D) 6順序查找不論在順序

38、線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為(D) O(1og希爾排序 )。)。)。)。2(A) O(n)(B) O(n 2)二路歸并排序的時間復(fù)雜度為(2(A) O(n)(B) O(n 2)深度為 k 的完全二叉樹中最少有(A) 2 k-1-1(B) 2 k-11/2(C) O(n 1/2)。2n)。(C) O(nlog 2n) )個結(jié)點。(C) 2 k-1+1(D) O(1og2n)設(shè)指針變量 front 表示鏈?zhǔn)疥犃械年狀^指針,指針變量 指針變量 s 指向?qū)⒁腙犃械慕Y(jié)點； front=s ； rear=s ；n 個頂點 e 條邊,(B) O(n 2)(A) front-next=s(C)

39、rear-next=s 設(shè)某無向圖中有(A) O(n+e) 設(shè)某哈夫曼樹中有(A) 99 設(shè)二叉排序樹上有(A) O(n)k(D) 2 k-1 rear 表示鏈?zhǔn)疥犃械年犖仓羔?，X,則入隊列的操作序列為(B) s-next=rear ； rear=s ；)。(D) s-next=front； front=s ；則建立該圖鄰接表的時間復(fù)雜度為(C) O(ne)(D) O(n 3)個葉子結(jié)點。(D) 102)。199 個結(jié)點,則該哈夫曼樹中有( (B) 100 (C) 101 n 個結(jié)點,則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為( 2(B) O(n 2)(C) O(nlog 2n)(D) O(1

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

41、后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）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é)點A,指針變量s指向被插入的新結(jié)點X,則進(jìn)行插入操作的語句序列為 （設(shè)結(jié)點的指針域為 next ）

42、 。3 .設(shè)有向圖 G 的二元組形式表示為G =（ D, R），D=1，2，3，4，5，R=r，r=， ， ， ， ，則給出該圖的一種拓?fù)渑判蛐蛄?。4設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是 。5. 設(shè)二叉樹中度數(shù)為 0 的結(jié)點數(shù)為 50，度數(shù)為 1 的結(jié)點數(shù)為 30，則該二叉樹中總共有 個結(jié)點數(shù)。6. 設(shè) F 和 R 分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為7. 設(shè)二叉樹中結(jié)點的兩個指針域分別為Ichild 和rchild ，則判斷指針變量 p所指向的結(jié)點為葉子結(jié)點的條件是 。8. 簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為 。9. 快速排序

43、算法的空間復(fù)雜度平均情況下為 ，最壞的情況下為 。10. 散列表中解決沖突的兩種方法是 和 。四、算法設(shè)計題 （20 分）1. 設(shè)計在順序有序表中實現(xiàn)二分查找的算法。2. 設(shè)計判斷二叉樹是否為二叉排序樹的算法。3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法、選擇題 (30 分 )設(shè)某無向圖有 n 個頂點，則該無向圖的鄰接表中有( (A) 2n(B) n(C) n/2設(shè)無向圖 G 中有 n 個頂點，則該無向圖的最小生成樹上有(A) n(B) n-1(C) 2n設(shè)一組初始記錄關(guān)鍵字序列為(60 ，80，55，準(zhǔn)而得到的一趟快速排序結(jié)果是( )。(A) 40 ，42，60，55，80，85(B) 42(

44、C) 42 ，40，55，60，80，85(D) 42)個表頭結(jié)點。(D) n(n-1)條邊。(D) 2n-140，42，85) ，則以第一個關(guān)鍵字45 為基，45，40，55，60，60，85，85，8055，80)二叉排序樹可以得到一個從小到大的有序序列。(A) 先序遍歷 (B) 中序遍歷 設(shè)按照從上到下、從左到右的順序從 點的左孩子結(jié)點的編號為( )。(A) 2i+1(B) 2i程序段 s=i=0 ； do i=i+1 ； s=s+i(A) O(n)(B) O(nlog 2n)設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head ，(A) head=0(B) head-next=0(C) h

45、ead-next=head(D) head!=0設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有(A) 20 (B) 256 (C) 512 設(shè)一組初始記錄關(guān)鍵字序列為(13 ， 18，24，35，利用二分法查找關(guān)鍵字 90 需要比較的關(guān)鍵字個數(shù)為(A) 1 (B) 2 (C) 3設(shè)指針變量 top 指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為( (A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;(C) 后序遍歷層次遍歷1 開始對完全二叉樹進(jìn)行順序編號，則編號為(D)(C) i/2 while(iright=p-right ； =s ；p-right-left=s ；(設(shè)結(jié)點中的兩個指針域分別為 left 和 right )。2. 設(shè)完全有向圖中有 n 個頂點,則該完全有向圖中共有 條有向條；設(shè)完全無向圖中有 n 個頂點,則該完全無向圖中共有 條無向邊。3. 設(shè)關(guān)鍵字序列為(Ki, K2,，冋，則用篩選法建初始堆必須從第 個元素開始進(jìn)行篩選。4. 解決散列表沖突的兩種方法是 和 。5. 設(shè)一棵三叉樹中有 50個度數(shù)為 0 的結(jié)點, 2