【正文】 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6.當(dāng)結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____________________。 當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。 設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_(dá)____＿個字節(jié)。試：（1） （1） int x=(int) sqrt(n)。 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q。 圖8如圖8所示。 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為 A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）9. 9.2. 2.4. 4. 若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。2. 2. else return Find(_______________,item)。 （1）查詢鏈表的尾結(jié)點（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 2. LNode* p=HL。 運算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進行快速排序的每一次劃分結(jié)果。 閱讀算法，回答問題（每小題8分，共16分）1 1 當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用———————表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_______________表示。 閱讀算法（每題7分，共14分）1. 1. 單選題（每題2分，共20分） 二、 二、 item){ if (BST==NULL) return false。 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}。12. 2. 若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38. 8. 算法填空（8 分） (low+high)/2 high=mid1 low=mid+1 六、 六、ElemType DeleFront(LNode * amp。 QInsert(Q,j)。 該算法的時間復(fù)雜度是多少？2. 2. 已知一個6180。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的__________________。 HLnext=p。 j=i。 while(p!=0) if (pkey==key) return(p)。 else {snext=hb。 (10，13，27，76，65，97，38)12. 12. O(n2)， O(n+e)9. 9. qnext7. 7. 1，25. 5. O(nlog2n)，O(n2)3. 3.二、填空題1. 1.}} }typedef struct node{int data。 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。5. 5. (A) 單向鏈表 (B) 單向循環(huán)鏈表(C) 雙向鏈表 (D) 雙向循環(huán)鏈表3．設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為（ ）。amp。數(shù)據(jù)結(jié)構(gòu)試卷（13）參考答案 順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。 希爾排序算法的時間復(fù)雜度為O(n2)。 有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)5．設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為（ ）。i=n1。typedef struct {int vertex[m]。 1，167. 7. 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。（ ）9. 9. 如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。 設(shè)計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。 s=q。四、算法設(shè)計題1. 1.二、判斷題1．對 2．對 3．對 4．對 5．對6．對 7．對 8．錯 9．錯 10．錯} } _________________。 下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。（ ）8．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ ）。 (A) head==0 (B) headnext==0 (C) headnext==head (D) head!=08．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（ ）。（ ）9．線性表中的所有元素都有一個前驅(qū)元素和后繼元素。struct record {int key。}三、填空題1. 1. n(n1)，n(n1)/23. 3. 開放定址法，鏈地址法5. 5. 2h1，2h17. 7. (12，18，24，27，35，26)9. 9. for(p=qnext。void substring(char s[ ], long start, long count, char t[ ]){ long i,j,length=strlen(s)。 設(shè)計求結(jié)點在二叉排序樹中層次的算法。 兩個字符串相等的充要條件是（ ）。 在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（ ）。 設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（ ）。 設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（ ）。（ ）2. 2. 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：snext=pnext。 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。 int edge[m][m]。i++) for(j=0。 (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)是（ ）。 設(shè)指針p指向單鏈表中結(jié)點A，指針s指向被插入的結(jié)點X，則在結(jié)點A的前面插入結(jié)點X時的操作序列為：1) snext=___________；2) pnext=s；3) t=pdata；4) pdata=___________；5) sdata=t；2． 2． 設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為13210，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為________________。( )2． 2．( )6． 6．（ ）10． 10．堆是完全二叉樹，完全二叉樹不一定是堆。一、選擇題1．A 2．A 3．A 4．C 5．D6．D 7．C 8．B 9．C 10．A11．C 12．C 13．D 14．A 15．A 設(shè)計計算二叉樹中所有結(jié)點值之和的算法。 r[i]%2==1) i=i+1。(A) snext=pnext；pnext=s； (B) qnext=s； snext=p；(C) pnext=snext；snext=p； (D) pnext=s；snext=q；4．設(shè)輸入序列為6，則通過棧的作用后可以得到的輸出序列為（ ）。 設(shè)指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為：q=pnext；pdata=qdata；pnext=___________；feee(q)；7. 7.11. 11.struct node *lchild。三、算法設(shè)計題(22分)1． 1． s=hb。else if (pkeykey)p=plchild。 i=i/2。 B. pnext=HL。9. 9. 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。5稀疏矩陣如下所示， } p=pnext。 HL) 單選題（每題 2 分，共20分）1. 1. 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 LinkList mynote(LinkList L) {//L是不帶頭結(jié)點的單鏈表的頭指針 if(Lamp。 //查找失敗 else { if (item==BSTdata){ item=BSTdata。 9 3 34. 4. 有向無回路8. 8. 運算題（每題6分，共24分）1. 1. 見圖124444422255285283452843 一棵高度為5的二叉樹中最少含有_________個結(jié)點，最多含有________個結(jié)點；一棵高度為5的理想平衡樹中，最少含有_________個結(jié)點，最多含有_________個結(jié)點。 假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 –1，請寫出輸出結(jié)果。 在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的_________和___________兩項數(shù)據(jù)。 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。} else if(itemBSTdata) return Find(______________,item)。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } retu