【正文】 p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）。else {____________________。 (A) n1 (B) n (C) n+1 (D) 2n18．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進行一趟快速排序的結(jié)果為（ ）。 }//if}六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。 coutBTdata39。 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}。8. 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。2. 一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。 A．688 B．678 C．692 D．6965. 樹最適合用來表示( )。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。三、計算題（每題 6 分，共24分）1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。//查找成功 return ___________。 (A) BADC (B) BCDA (C) CDAB (D) CBDA5．設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。} sqstack。6. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。四、算法設(shè)計題(16分) 1． 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。 (A) n，e (B) e，n (C) 2n，e (D) n，2e8. 設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。6. 設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為_________。struct record{int key。 if (i==j) return(1)。bitree *bstsearch(bitree *t, int k){ if (t==0 ) return(0)。2． 設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。 (A) 必須判別棧是否為滿 (B) 必須判別棧是否為空 (C) 判別棧元素的類型 (D) 對棧不作任何判別8．下列四種排序中（ ）的空間復(fù)雜度最大。6． 設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_________個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。14． 設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。im。_______________________。 (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)鍵字序列進行一趟歸并后的結(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. 設(shè)有一個順序共享棧S[0：n1]，其中第一個棧項指針top1的初值為1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。9. 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。exchange=1。 else if(____________) high=mid1。2． 設(shè)計兩個有序單鏈表的合并排序算法。 (A) 3 (B) 4 (C) 5 (D) 68．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（ ）。 (A) 第i行非0元素的個數(shù)之和 (B) 第i列非0元素的個數(shù)之和 (C) 第i行0元素的個數(shù)之和 (D) 第i列0元素的個數(shù)之和二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（ ）9．中序遍歷二叉排序樹可以得到一個有序的序列。7．設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_____________________________________________。 (A) n (B) n1 (C) 2n (D) 2n13．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ ）。 (A) top=top+1。（ ）5．哈夫曼樹中沒有度數(shù)為1的結(jié)點。3. 設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。struct record {int key。amp。}四、算法設(shè)計題(20分)1. 設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。 (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]7. 設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（ ）。（ ）5. 向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹的高度。typedef struct node{int data。}else if (tdatak) bstinsert(tlchild,k)。8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 (A) N11 (B) N21 (C) N2+N3 (D) N1+N34．利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為（ ）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/2(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（ ）次比較。6． 設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_______________________________。( )4． 若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。2． 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。 (A) (B) (C) (D) 7. 二叉排序樹中左子樹上所有結(jié)點的值均（ ）根結(jié)點的值。3. 設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。12. 設(shè)有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個拓撲序列為_________________________。ch)。}}14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。scanf(“%d”,amp。3． 設(shè)關(guān)鍵字序列(k1，k2，…，kn1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。 qrlink=prlink。 if (ij) {r[i]=r[j]。}2. 設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。p=pnext){ for(q=hb。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。q=qnext) if (qdata==pdata) break。 struct node *next。} while (ij amp。 prlink=q。五、 法填空（每空2分，共8 分）true BSTleft BSTright 六、 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。pnext=0。 struct node *next。39。typedef struct node{int data。5. 設(shè)一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_________個空指針域。 (A) 129 (B) 219 (C) 189 (D) 2299. 設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（ ）次線性探測。數(shù)據(jù)結(jié)構(gòu)試卷（十）一、選擇題(24分)1．下列程序段的時間復(fù)雜度為（ ）。( )6． 用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。8． 設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為13210，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為________________。 (A) 6 (B) 11 (C) 5 (D) ={1，2，2，3，3，4，1，4}，則下列屬于該有向圖G的一種拓撲排序序列的是（ ）。 (A) pright=s； sleft=p； prightleft=s； sright=pright； (B) sleft=p；sright=pright；pright=s； prightleft=s； (C) pright=s； prightleft=s； sleft=p； sright=pright； (D) sleft=p；sright=pright；prightleft=s； pright=s；6．下列各種排序算法中平均時間復(fù)雜度為O(n2)是（ ）。10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。}3． 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：snext=pnext。struct node *rchild。（ ）7. 非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。 (A) 5 (B) 6 (C) 7 (D) 89. 設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（ ）。3. 設(shè)計求結(jié)點在二叉排序樹中層次的算法。 if (ij) {r[i]=r[j]。}。5. 設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有______個。（ ）7．先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。 (C) topnext=top。 (A) 先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（ ）。9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。（ ）三、填空題(30分)1．for(i=1，t=1，s=0；i=n；i++) {t=t*i；s=s+t；}的時間復(fù)雜度為_________。（ ）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)10. 深度為k的完全二叉樹中最少有（ ）個結(jié)點。 (A) 20 (B) 30 (C) 40 (D) 452．執(zhí)行一趟快速排序能夠得到的序列是（ ）。 } return(0)。struct record{int key。i=n1。3. 設(shè)有