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

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

3、則查找 A 3的比較序列的下標依次為8.A. O(1)B. O(n)C. O (1og2n)D. O(n2)9. 對于線性表( 7，34， 55，25，64， 46，20，10)進行散列存儲時，若選用H(K)=K %9 作為散列函數，則散列地址為A 1B10. 保是一個連通圖。A.5 B.6 C.7 、填空題(每空 1分，共 26 分) 通常從四個方面評價算法的質量： 、 、_一個算法的時間復雜度為 (n 3+n2log 2n+14n)/n 2，其數量級表示為 。假定一棵樹的廣義表表示為A ( C, D(E, F, G) , H( I , J),則樹中所含的結點數為個，樹的深度為 ，樹的度為

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

5、 ) 條邊才能確D.8個和n 個結點的二叉樹共有 個指針域，其中有 _ 個指針是空指針。e 條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結 個。條邊，在一個具有 n 個頂點的10.向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度11. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為，整個堆排序過程的時間復雜度為 。12. 在快速排序、堆排序、歸并排序中， 排序是穩定的。三、計算題(每題 6分，共24分)1.在如下數組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. 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。四、 閱讀算法(每題7分，共14分)1. LinkList mynote(LinkList L)/L是不帶頭結點的單鏈表的頭指針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) 設鏈表表示的線性表為(&,a2,an),寫出算法執行后的返回值所表示的線 性表。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 分) 統計出單鏈表 HL 中結點的值等于給定值 X 的結點數。 int CountX(LNode* HL,ElemType x)、選擇題 (24 分 )1下面關于線性表的敘述錯誤的是()。(A) 線性表采用順序存儲必須占用一片連續的存儲空間(B) 線性表采用鏈式存儲不必占用一片連續的存儲空間(C) 線性表采用鏈式存儲便于插入和刪除操作的實現(D) 線性表采用順序存儲便于插入和刪除操作的實現2 設哈夫曼樹中的葉子結點總數為m若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有( )個空指針域。(A) 2m-1(B)

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

10、中有2000個結點，則該二叉樹的最小高度為()。(A) 9(B) 10(C) 11(D) 127. 設某有向圖中有 n個頂點，則該有向圖對應的鄰接表中有()個表頭結點。(A) n-1(B) n(C) n+1(D) 2n-1&設一組初始記錄關鍵字序列(5 ， 2， 6， 3， 8) ，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為()。(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查找技術，必須解決的兩個問題是 和2. 下面程序段的功能實現數據x進棧，要求在下劃線處填上正確的

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. 快速排序的最壞時間復雜度為 ，平均時間復雜度為。5. 設某棵二叉樹中度數為0的結點數為N）,度數為1的結點數為Ni,則該二叉樹中度數為2的結點數為;若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有個空指針域。6. 設某無向圖中頂點數和邊數分別為n和e，所有頂點的度數之和為d，則e=

12、7. 設一組初始記錄關鍵字序列為（55，63，44，38，75，80，31，56），則利用篩選法建立的初始堆為。&已知一有向圖的鄰接表存儲結構如下：從頂點 1出發，DFS遍歷的輸出序列是，BFS遍歷的輸出序列是國的鄰接轟存舊結枸三、應用題（36分）1 .設一組初始記錄關鍵字序列為（45，80, 48，40，22，78），則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結果。2. 設指針變量p指向雙向鏈表中結點 A，指針變量q指向被插入結點 B，要求給出在結點 A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink 和rlink ）。3. 設一組有序的記錄關鍵字序列為（1

13、3，18，24，35，47，50，62，83，90），查找方法用二分查找，要求計算出查找關鍵字62時的比較次數并計算出查找成功時的平均查找長度。4. 設一棵樹 T 中邊的集合為（A，B），（A，C），（A，D），（B，E），（C，F），（C，G），要求 用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5. 設有無向圖G要求給出用普里姆算法構造最小生成樹所走過的邊的集合。6 設有一組初始記錄關鍵字為 （45 ，80，48，40，22，78） ，要求構造一棵二叉排序樹并給 出構造過程。四、算法設計題 （16 分 ）1. 設有一組初始記錄關鍵字序列（K , K2，Kn）,

14、要求設計一個算法能夠在0（n）的時間復雜度將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki ，右半部分的每個關鍵字均大于等于 Ki 。2. 設有兩個集合 A和集合B,要求設計生成集合 C=AA B的算法，其中集合 A B和C用鏈 式存儲結構表示。12345678.910.二、1.2.3.4.、選擇題 (每題 1 分，共 20分)設某數據結構的二元組形式表示為A=(D， R)， D=01， 02，03，04，05，06，07，08，09 ， R=r ， r=， ， ， ， ， ，, ，則數據結構 A 是()。(A) 線性結構 下面程序的時間復雜為( for ( i=1 ， s=0 ；(A

15、) O(n) 設指針變量 p 列為( )。(A) q=p-next(B) q=p-next(C) q=p-next(D) q=p-next(B) 樹型結構) 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) ；設有 n 個待排序的記錄關鍵字，則在堆排序中需要(A) 1(B) n(C) nlog 2n設一組初始關鍵字記錄關鍵字為 (20 ， 15， 14， 18， 記錄的一趟快速排序結束后的結果為(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 為基準設二叉排序樹中有(A) O(1) 設無向圖 G 中有 nn 個結點，則在二叉排序樹的平均平均查找長度為(2(B) O(log 2n)(C) (D) O(n 2)個頂點 e 條邊，則其

17、對應的鄰接表中的表頭結點和表結點的個數分別)。為( )。(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)設有 5000 個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10 個記錄關鍵字，則用下列()方法可以達到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序下列四種排序中()的空間復雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序填空殖 (每空 1分 共20分)數據的物理結構主要包括 和

18、兩種情況。設一棵完全二叉樹中有 500 個結點，則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有 個空指針域。設輸入序列為 1、2、3，則經過棧的作用后可以得到 種不同的輸出序列。設有向圖G用鄰接矩陣Ann作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點 i 的 ，第 i 列上所有元素之和等于頂點 i 的 。5. 設哈夫曼樹中共有 n個結點，則該哈夫曼樹中有 個度數為1的結點。6. 設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為 d,則e和d的關系為7. 遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列(填先序、中序或后序)。8. 設查找表中有100個元

19、素，如果用二分法查找方法查找數據元素X,則最多需要比較次就可以斷定數據元素X是否在查找表中。9. 不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為。10. 設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為 ，右孩子結點的編號為 。11. 設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為。12. 設有向圖 G中有向邊的集合 E=1，2，2，3，1，4，4，2，4，3，則該圖的一種拓扌卜序歹y為。13. 下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃

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. 下列算法實現在二叉排序樹上查找關鍵值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，假定選用的散列函數是 H ( K) = K mod

22、 7，若發生沖突采用線性探查法處理，試：(1 )計算出每一個元素的散列地址并在下圖中填寫出散列表：0123456(2)求出在查找每一個元素概率相等情況下的平均查找長度。3. 已知序列(10，18，4，3，6，12，1，9，18，8)請用快速排序寫出每一趟排序的結果。四、算法設計題(每題15分，共30分)1 設計在單鏈表中刪除值相同的多余結點的算法。2 設計一個求結點 x 在二叉樹中的雙親結點算法。一、選擇題 (每題 1 分共 20 分)1設一維數組中有 n 個數組元素，則讀取第 i 個數組元素的平均時間復雜度為( )。2(A) O(n) (B) O(nlog 2n)(C) O(1) (D) O

23、(n . 設有 n 個無序的記錄關鍵字,則直接插入排序的時間復雜度為 ,快速排序的平均時間復雜度為 。2. 設指針變量 p指向雙向循環鏈表中的結點X,則刪除結點 X需要執行的語句序列為 (設結點中的兩個指 針域分別為 llink 和 rlink )。3. 根據初始關鍵字序列 (19, 22, 01, 38, 10)建立的二叉排序樹的高度為 。4. 深度為 k 的完全二叉樹中最少有 個結點。5. 設初始記錄關鍵字序列為(Ki , K2，Kn)，則用篩選法思想建堆必須從第 個元 素開始進行篩選。6. 設哈夫曼樹中共有 99 個結點,則該樹中有 個葉子結點；若采用二叉鏈表作為存儲結構,則該樹中有 個

24、空指針域。 7. 設有一個順序循環隊列中有 M 個存儲單元,則該循環隊列中最多能夠存儲 個隊列元素；當前實際存儲 個隊列元素(設頭指針 F 指向當前隊頭元素的前一個位置,尾指針指向當前隊尾元素的位置) 。)2 設一棵二叉樹的深度為k，則該二叉樹中最多有()個結點。(A) 2k-1(B) 2 k(C) 2 k-1(D) 2 k-13設某無向圖中有 n個頂點e條邊，則該無向圖中所有頂點的入度之和為()。(A) n(B) e(C) 2n(D) 2e4. 在二叉排序樹中插入一個結點的時間復雜度為()。2(A) O(1)(B) O(n)(C) O(log 2n)(D) O(n 2)5. 設某有向圖的鄰接

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

26、度數為1的結點數為N ,度數為2的結點數為N2, 則下列等式成立的是( )。(A) N 0=N1+1(B) N 0=Nl +N2(C) N 0=N2+1(D) N 0=2N1+l10. 設有序順序表中有n 個數據元素,則利用二分查找法查找數據元素X的最多比較次數不超過()。(A) log2n+1(B) log 2n-1(C) log 2n(D) log2(n+1)二、填空題( 每空 1 分共 20 分 )& 設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中個數據元素；刪除第i個位置上的數據元素需要移動表中 個元素。9. 設一組初始記錄關鍵字序列為(20, 18, 22,

27、 16, 30, 19)，則以20為中軸的一趟快速排序結果為。10. 設一組初始記錄關鍵字序列為(20 , 18, 22, 16, 30, 19)，則根據這些初始關鍵字序列建成的初始堆為 。11. 設某無向圖G中有n個頂點，用鄰接矩陣 A作為該圖的存儲結構，則頂點 i和頂點j互為鄰接點的條件是。12. 設無向圖對應的鄰接矩陣為 A,則A中第i上非0元素的個數 第i列上非0元素的個數(填等于，大于或小于)。13. 設前序遍歷某二叉樹的序列為ABCD中序遍歷該二叉樹的序列為BADC則后序遍歷該二叉樹的序列為 。14. 設散列函數H(k)=kmodp，解決沖突的方法為鏈地址法。要求在下列算法劃線處填

28、上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志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分)的頭尾鏈表存儲結構。1、畫出廣義表 LS=( ) , (e) , (a , (b , c , d )2、

29、下圖所示的森林：(1) 求樹(a)的先根序列和后根序列;(2) 求森林先序序列和中序序列；(3) 將此森林轉換為相應的二叉樹；3、設散列表的地址圍是0.9 ，散列函數為 H (key)(key 2+2) MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、& 9依次插入散列表的存儲結構。四、算法設計題(每題10分，共30分)1 設單鏈表中有僅三類字符的數據元素 （ 大寫字母、數字和其它字符 ） ，要求利用原單鏈 表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。3. 在鏈式存儲結構上建立一棵二叉排序樹。一

30、、選擇題 (20 分 ) 1數據的最小單位是()。(A) 數據項 (B) 數據類型 (C) 數據元素 (D) 數據變量2設一組初始記錄關鍵字序列為 (50 ， 40，95， 20，15， 70，60， 45) ，則以增量 d=4 的一 趟希爾排序結束后前 4 條記錄關鍵字為( )。(A) 40 ，50，20，95(B) 15 ，40，60，20(C) 15 ，20，40，45(D) 45 ，40，15，203設一組初始記錄關鍵字序列為 (25，50，15，35，80，85，20，40，36，70) ，其中含有5 個長度為 2 的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果

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

32、2(A) O(log 2n)(B) O(1)(C) O(n 2)(D) O(n)6. 設一棵m叉樹中度數為0的結點數為N),度數為1的結點數為N ,，度數為 m的結點數為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 .設有序表中有1000個元素，則用二分查找查找元素X最多需要比較()次。(A) 25(B) 10(C) 7(D) 1&設連通圖 G 中的邊集 E=(a , b) , (a , e) , (a , c) , (b , e) , (e , d) ,

33、(d , f) , (f , c), 則從頂點 a 出發可以得到一種深度優先遍歷的頂點序列為()。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9設輸入序列是1、2、3、n,經過棧的作用后輸出序列的第一個元素是n,則輸出序列中第 i 個輸出元素是( )。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10 設一組初始記錄關鍵字序列為 (45 , 80, 55, 40, 42, 85) ,則以第一個記錄關鍵字 45 為基準而得到一趟快速排序的結果是( )。(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. 設有一個順序共享棧 S0：n-1 ,其中第一個棧項指針 top1 的初值為 -1 ,第二個棧頂 指針top2的初值為n,則判斷共享棧滿的條件是 2. 在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是3. 設有一個n階的下三角矩陣A,如果按照行的順序將下三角矩陣中的元素(包括對角線上元素)存放在 n(n+1) 個連續的存儲單元中，則 Aij 與 A00 之間有 個數據元素。4. 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，

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

36、功能是實現冒泡排序算法,請在下劃線處填上正確的語句。 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. 下面程序段的功能是實現二分查找算法,請在下劃線處填上正確的語句。 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、設一條單鏈表的頭指針變量為(A) head=0(C) head-next=head 時間復雜度不受數據初始狀態影響而恒為O(nlog 2n) 的是()。(A) 堆排序(B) 冒泡排序 (C) 希爾排序 (D) 快速排序設二叉樹的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹滿足的條件是(A) 空或只有一個結點(B) 高度等于其結點數(C) 任一結點無左孩子(D) 任一結點無右孩子一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是(A) 堆排序(B) 冒泡排序(C) 快速排序(D)設某棵三叉樹中有 40個結點,則該三叉樹的最小高度為(A) 3(B) 4(C) 5(D) 6順序查找不論在順序

38、線性表中還是在鏈式線性表中的時間復雜度為(D) O(1og希爾排序 )。)。)。)。2(A) O(n)(B) O(n 2)二路歸并排序的時間復雜度為(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) )個結點。(C) 2 k-1+1(D) O(1og2n)設指針變量 front 表示鏈式隊列的隊頭指針,指針變量 指針變量 s 指向將要入隊列的結點； front=s ； rear=s ；n 個頂點 e 條邊,(B) O(n 2)(A) front-next=s(C)

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

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

41、后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）6層次遍歷初始堆可以得到一個有序的序列。（ ）7 .設一棵樹T可以轉化成二叉樹 BT,則二叉樹BT中一定沒有右子樹。（）8線性表的順序存儲結構比鏈式存儲結構更好。（ ）9. 中序遍歷二叉排序樹可以得到一個有序的序列。（ ）10. 快速排序是排序算法中平均性能最好的一種排序。（） 三、填空題 （30 分 ）1. for（i=1 ， t=1 ， s=0 ； i=n ； i+） t=t*i；s=s+t ； 的時間復雜度為 。2. 設指針變量p指向單鏈表中結點A,指針變量s指向被插入的新結點X,則進行插入操作的語句序列為 （設結點的指針域為 next ）

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

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

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

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