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