【正文】 。查找成功的平均查找長度：ASL SUCC=14/10= 此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9鄰接表表示時0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，5四、閱讀算法，回答問題（每小題8分，共16分） 5745203178 0 1 2 3 4 5 6 7 8 9 10 11 12Void contrary (Lnode * amp。 編寫算法（10分） else if ( K A[mid].key) return 2 else return 3}else return 4對順序存儲的有序表進(jìn)行二分查找的遞歸算法 。五、 五、 undnown(p→rightchild)。 p→rightchild = temp。 if (p!=NULL) { temp = p→leftchild。}該算法的輸出結(jié)果為：__________________________________________________________. 閱讀以下二叉樹操作算法，指出該算法的功能。}while (!stackempty (a)) cout pop (a) ”” 。 while (x! = 1) { push (a, x )。 int x。 include “”Void main ( ){ stack a。 int top。typedef int elemtype。假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 –1，請寫出輸出結(jié)果。四、 四、 鄰接表表示時圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時 已知一個圖的頂點集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)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。三、 三、7： 5 318： 邊結(jié)點、鄰接點域、權(quán)域、鏈域；9： 索引值域、開始位置域；10： B、I和J；11： O（log2n）、O(nlog2n)。二、填空題（每空1分，共32分）1： 集合、線性、樹、圖；2： 數(shù)據(jù)描述、操作聲名；3： （38，56，25，60，42，74）；4： HL→next =NULL； HL=HL→next；5： 前一個位置； n1；6： []。1 11 1 在圖的鄰接表中，每個結(jié)點被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用———————表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_______________表示。 在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 4 3 7 6 2 0 1 60 56 42 38 在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 填空題（每空1分，共32分） 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為__________、 ___________ 、________和________四種。A 棧頂 B 棧底 C 任意位置 D 指定位置 D q →link=s。 C p→link=s→link。 B p→link=s。 A s→link=p→link。 單選題（每小題2分，共8分） 在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( C)。 }//CountX p=pnext。 LNode* p=HL。 算法填空（每空2分，共8 分）true BSTleft BSTright 四、 六、 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹?（1）查詢鏈表的尾結(jié)點（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 2. 閱讀算法（每題7分，共14分）1. 1.參考答案三、 int CountX(LNode* HL,ElemType x) }//if}} else if(itemBSTdata) return Find(______________,item)。 //查找失敗 else { if (item==BSTdata){ item=BSTdata。 算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。五、 五、 39。 ABC (BTright)。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í)行后的返回值所表示的線性表。 LinkList mynote(LinkList L) {//L是不帶頭結(jié)點的單鏈表的頭指針 if(Lamp。 閱讀算法（每題7分，共14分）1. 1.四、 四、 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 已知一個圖的頂點集V和邊集E分別為： V={1,2,3,4,5,6,7}。 圖10請畫出圖10的鄰接矩陣和鄰接表。40next357204 A 0 1 2 3 4 5 6 7 data 運算題（每題 6 分，共24分）1. 1.三、 三、 O(log2n) O(nlog2n)12. 12. （12，40） （ ） （74） （23,55，63）10. 10. n(n1)/2 n(n1)9. 9. 有向無回路8. 8. e 2e7. 7. 2n n1 n+16. 6. 1 3 4 X * + 2 Y * 3 / 5. 5. 9 3 34. 4. O(n)3. 3. 正確性 易讀性 強壯性 高效率2. 2. 填空題（每空1分，共26分）1. 1.12. 12.11. 11.10. 10.9. 9.8. 8.7. 7.6. 6. 若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。中綴算式（3+4X）2Y/3對應(yīng)的后綴算式為_______________________________。4. 4.3. 3.2. 2. 填空題（每空1分，共26分）1. 1.二、 二、 對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ D ）個， A．1 B．2 C．3 D．410. 10. 設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有( A )條邊才能確保是一個連通圖。 對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為C A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）9. 9. 若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38. 8. 二叉樹的第k層的結(jié)點數(shù)最多為( D ). A．2k1 +1 　　　D. 2k17. 7. 6. 6. 設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( C ) A. 隊列 　　 B. 棧 C. 線性表 　　 D. 二叉樹4. 4. 用鏈接方式存儲的隊列，在進(jìn)行插入運算時( D ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 、尾指針可能都要修改3. 3. 2. 2.（二）return temp。ElemType temp=pdata。}LNode* p=HL。 HL){if (HL==NULL){ cerr空表endl。 算法填空（8 分） (low+high)/2 high=mid1 low=mid+1 六、 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 (1) 判斷n是否是素數(shù)（或質(zhì)數(shù)） （2）O（）2. 2. 閱讀算法（每題7分，共14分）1. 1.ElemType DeleFront(LNode * amp。 //查找失敗，返回1} //在左子表上繼續(xù)查找 else __________________________________。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。 } }} QInsert(Q,j)。 39。 while(p!=NULL) { int j=padjvex。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。 visited[i]=true。 couti39。 寫出下述算法的功能： void AJ(adjlist GL, int i, int n)