【正文】 畫出該圖的圖形； （2）根據鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。4832．假設兩個隊列共享一個循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct{ DateType data[MaxSize]； int front[2],rear[2]； }Queue2；對于i=0或1，front[i]和rear[i]分別為第i個隊列的頭指針和尾指針。amp。!s2) ⑤return 031.（1）查詢鏈表的尾結點 （2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點 （3）返回的線性表為（a2,a3,…,an,a1）32. ①(i＋1)%2(或1－i) ②Q－rear[i] ③(Q－rear[i]＋)%Maxsize33.(1)LeafheadF五、算法設計題（本題共10分） 34．（1）該函數的功能是：調整整數數組a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。 (A) 線性表 (B) 棧 (C) 隊列 (D) 樹4．二叉樹中第i(i≥1)層上的結點數最多有（ ）個。二、填空題(30分)1. 1.2. 2.3. 3.4. 4.5. 5.6. 6.7. 7.8. 8.9. 9.int index(char s[ ], char t[ ]){i=j=0。else return (1)。3．設一組初始記錄關鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準的一趟快速排序結果以及第2趟直接選擇排序后的結果。 m=2e7. 7. n1三、應用題1. 1.2. 2. = 1。p=pnext) if (pdata==[]) =。bt){ char ch。 btdata=ch。 if(minnumbtkey)flag=0。 (A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。typedef struct {int s[100]。4. 4. 快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。2． 2．6． 6． 設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結構表示。 有序4. 4. 設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。3. 3. N01，2N0+N16. 6.2． 2．5． 5．三、應用題(36分)1． 1．_________________。 為了能有效地應用HASH查找技術，必須解決的兩個問題是____________________和__________________________。二、填空題(24分)1. 1. (A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B) 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C) 線性表采用鏈式存儲便于插入和刪除操作的實現(D) 線性表采用順序存儲便于插入和刪除操作的實現2．設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（ ）個空指針域。}bitree。 return。} bitree。} for(p=head。} sqstack。 (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 4. 4，169. 9.三、應用題（30分）1．設完全二叉樹的順序存儲結構中存儲數據ABCDE，要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列。 j=______。 (A) 4 (B) 5 (C) 6 (D) 710. 10. 設有以下四種排序方法，則（ ）的空間復雜度最大。 (A) 數據項 (B) 數據類型 (C) 數據元素 (D) 數據變量2．設數據結構A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，則數據結構A是（ ）。D∧ （2）中序遍歷二叉樹，按遍歷序列中葉子結點數據域的值構建一個以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結點數據自右至左鏈接成一個鏈表）。!s1) ④s1(或s1!=NULL或s1amp。 28．該圖的圖形為： （1）畫出執(zhí)行上述算法后所建立的結構； （2）說明該算法的功能。(!T－rchild)){ s=(ListNode*)malloc(sizeof(ListNode))； s－data=T－data； s－next=Leafhead； Leafhead=s； } Inorder(T－rchild)； } } 對于如下所示的二叉樹 amp。 23．在單鏈表上難以實現的排序方法有 和 。17．在一個帶頭結點的單循環(huán)鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head= 。 q→next=HL。五、算法填空，在畫有橫線的地方填寫合適的內容（10分）1是：（low + high）/2。Void contrary (Lnode * amp。對順序存儲的有序表進行二分查找的遞歸算法 。 p→rightchild = temp。 while (x! = 1) { push (a, x )。typedef int elemtype。 已知一個圖的頂點集V各邊集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_________,整個堆排序過程的時間復雜度為________________。 在一個索引文件的索引表中，每個索引項包含對應記錄的_________和___________兩項數據。 74 25 由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 s→link=q。 一、 一、 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。圖12四、 四、 O(log2n) O(nlog2n)12. 12.參考答案一、 一、} else if(itemBSTdata) return Find(______________,item)。 39。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）設鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。四、 四、三、 三、 后綴算式9 2 3 + 10 2 / 的值為__________。 假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結點數為__________個，樹的深度為___________，樹的度為_________。 一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為________。 通常從四個方面評價算法的質量：_________、_________、_________和_________。 A．688 B．678 C．692 D．6965. 5.delete p。五、 五、 （1） ((1,5,1),(3,2,1),(4,5,2),(5,1,5),(6,3,7)) (3分)（2） 三元組線性表的順序存儲表示如圖7示。 運算題（每題6分，共24分）1. 1. 開放定址法 鏈接法12. 12. 2n n1 n+110. 10. 有序序列 后綴表達式（或逆波蘭式）9. 9. 655151321452515637 圖7有序 n18. 8. 3 3 7. 7. 128 44 1086. 6. O（1） O（n）5. 5. top==04. 4. 尾 首3. 3. 聯(lián)系 圖（或圖結構）2. 2. 填空題（每空1分，共26分）1. 1.參考答案一、 一、 //在右子表上繼續(xù)查找}return 1。五、 五、 edgenode* p=GL[k]。 int Prime(int n){ int i=1。若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。3. 3.2. 2. 寫出它的三元組線性表；（2） （2） 數據結構是指數據及其相互之間的______________。A．行號 B．列號 C．元素值 D．非零元素個數9. 9. AOV網是一種（ ）。 對線性表，在下列哪種情況下應當采用鏈表表示？( ) 4. 4. C. pnext=HL。 一、 A．健壯性和可讀性 B．并行性 C．正確性 D．時空復雜度2. 2. HL=p。 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（ ）。二、 二、12. 12. 給出三元組線性表的順序存儲表示。 設有一個輸入數據的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數據而生成的二叉搜索樹。 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 4.E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5}。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。 } }} //在左子表上繼續(xù)查找 else __________________________________。 閱讀算法（每題