【正文】 12 HL) int Binsch( ElemType A[ ],int low ,int high,KeyType K ) {if (low = high){ int mid = 1 if ( K= = A[ mid ].key ) return mid。 unknown(p→leftchild)。Template calss type void BinTree Type ：：unknown (BinTreeNodeType*t) { BinTreeNode Type *p =t, *temp。 cin x。 initstack(a)。struct stack {elemtype stack [stackmaxsize]。 閱讀算法，回答問題（每小題8分，共16分） 假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。 運(yùn)算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。12： m 、 m 1 在對m階的B_樹插入元素的過程中，每向一個結(jié)點插入一個索引項（葉子結(jié)點中的索引項為關(guān)鍵字和空指針）后，若該結(jié)點的索引項數(shù)等于______個，則必須把它分裂為_______個結(jié)點。 在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運(yùn)算的時間復(fù)雜度為_________,整個堆排序過程的時間復(fù)雜度為________________。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點數(shù)為_________個，樹的深度為_________,樹的度為________, 結(jié)點H的雙親結(jié)點為________,孩子結(jié)點為_______________ 。 在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的_________和___________兩項數(shù)據(jù)。 用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的___________，該循環(huán)隊列的最大長度為__________。 74 25 一種抽象數(shù)據(jù)類型包括______________和_____________兩個部分。 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ B） A 24 B 71 C 48 D 53二、 二、 s→link =p。 s→link=q。A n B n/2 C (n+1)/2 D (n1)/2 在一個單鏈表中,若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若在q與p之間插入一個s所指的結(jié)點,則執(zhí)行( D )。 （三）一、 }//while, 出循環(huán)時i中的值即為x結(jié)點個數(shù) return i。 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。圖12二、 四、六、 六、//查找成功 return ___________。 coutBTdata39。amp。4. 4.6050789034 歸并 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。 在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運(yùn)算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度___________。 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。 AOV網(wǎng)是一種___________________的圖。 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有_______個和________個。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。5. 5. 棧和隊列的共同特點是( A )。 單選題（每題 2 分，共20分）1. 1.} HL=HLnext。 編寫算法（8分）ElemType DeleFront(LNode * amp。參考答案四、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。 //在右子表上繼續(xù)查找}return 1。int high=n1。五、 五、 visited[j]=true。 edgenode* p=GL[k]。 39。 else return 0。 int Prime(int n){ int i=1。 閱讀算法（每題7分，共14分）1. 1. 圖8如圖8所示。2. 2.試：（1） （1） 已知一個6180。 若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A[0]中。 對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的__________________。8. 8. 設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_(dá)____＿個字節(jié)。 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_________，在表尾插入元素的時間復(fù)雜度為____________。 當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示棧空，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。 隊列的插入操作是在隊列的___尾______進(jìn)行，刪除操作是在隊列的____首______進(jìn)行。當(dāng)結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____________________。 運(yùn)算題（每題 6 分，共24分）1. 1.A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( C )。 采用開放定址法處理散列表的沖突時，其平均查找長度（ S ）。 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6. p=HL。 HLnext=p。 單選題（每題 2 分，共20分）1. 1. 對一個算法的評價，不包括如下（B ）方面的內(nèi)容。 B. pnext=HL。 D. HL=p。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. 若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（ D ）參數(shù)。 A. O(n) B. O(1) C. O(log2n) D. O(n2)2. 2.3. 3.4. 4.5. 5.W中第6 行的元素和第4 列的元素共占用＿_(dá)______＿個字節(jié)。9. 9.10. 10.其余類推，則A[ i ]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。 運(yùn)算題（每題6分，共24分）1. 1.5稀疏矩陣如下所示， 已知一個圖的頂點集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。3. 3. DFS：????… BFS：???…? 4. 拓樸排序為： 4 3 6 5 7 2 1 int x=(int) sqrt(n)。 } (1) (1) 指出該算法的功能；(2) (2) 該算法的時間復(fù)雜度是多少？2. 2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q。 visited[i]=true。 while(p!=NULL) { int j=padjvex。 QInsert(Q,j)。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。 //查找失敗，返回1}ElemType DeleFront(LNode * amp。 閱讀算法（每題7分，共14分）1. 1. (1) 判斷n是否是素數(shù)（或質(zhì)數(shù)） （2）O（）2. 2. 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 HL){if (HL==NULL){ cerr空表endl。ElemType temp=pdata。（二） 2. 2. 用鏈接方式存儲的隊列，在進(jìn)行插入運(yùn)算時( D ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 、尾指針可能都要修改3. 3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( C ) A. 隊列 　　 B. 棧 C. 線性表 　　 D. 二叉樹4. 4. 設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。二、 二、6. 6.7. 7.8. 8.9. 9.10. 10.11. 11.12. 12. 填空題（每空1分，共26分）1. 1. 正確性 易讀性 強(qiáng)壯性 高效率2. 2. O(n)3. 3. 9 3 34. 4. 1 3 4 X * + 2 Y * 3 / 5. 5. 2n n1 n+16. 6. e 2e7. 7. 有向無回路8. 8. n(n1)/2 n(n1)9. 9. （12，40） （ ） （74） （23,55，63）10. 10.三、 三、40next357204 圖10請畫出圖10的鄰接矩陣和鄰接表。 已知一個圖的頂點集V和邊集E分別為： V={1,2,3,4,5,6,7}。四、 四、Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－ne