【文章內(nèi)容簡介】 中的________。 6．當(dāng)從一個小根堆中刪除一個元素時，需要把________元素填補到________位置，然后再按條件把它逐層________調(diào)整。三、應(yīng)用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。
2. 空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。 3. 已知一個堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個元素，請給出每刪除一個元素后堆的狀態(tài)。4. 有七個帶權(quán)結(jié)點，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹，并計算出帶權(quán)路徑長度WPL。
四、算法設(shè)計1．編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結(jié)點的非遞歸算法，若查找成功則由item帶回整個結(jié)點的值并返回true，否則返回false。 bool Find( BTreeNode * BST , ElemType amp。 item )2．下面的算法功能是向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。void AH(Heap amp。 HBT , const ElemType item) // 形參HBT為一個小根堆{ []=item。 ++。 ElemType x=item int i=。 while ( i != 0 ){ int j= 。 if ( x=[j]) break。 。 。 } [i]=x。 }第七章 圖 一、填空題 1．在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的________倍。 2．在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。 3. 在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要________條邊。 4．表示圖的三種存儲結(jié)構(gòu)為________、________和________。 5. 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為________。 6．對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別為________和________條。 7. 在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有________和________結(jié)點。 8．對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為________和________條。 9．對于一個具有n個頂點和e條邊的無向圖，當(dāng)分別采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，求任一頂點度數(shù)的時間復(fù)雜度依次為________、________和________。 10. 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，其相應(yīng)的空間復(fù)雜度分別為________、________和________。 11. 對用鄰接矩陣表示的圖進行任一種遍歷時，其時間復(fù)雜度為________，對用鄰接表表示的圖進行任一種遍歷時，其時間復(fù)雜度為________。12．對于下面的無向圖G1，假定用鄰接矩陣表示，則從頂點v0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。13. 對于下面的有向圖G2，假定用鄰接矩陣表示，則從頂點v0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為____________，從頂點v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為____________。 14. 對于下面的帶權(quán)圖G3，其最小生成樹的權(quán)為________。 15．對于下面的帶權(quán)圖G3，若從頂點v0出發(fā)，則按照普里姆算法生成的最小生成樹中，依次得到的各條邊為_______________。 16. 對于下面的帶權(quán)圖G3，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，則得到的各條邊依次為_______________。 17．假定用一維數(shù)組d[n]存儲一個AOV網(wǎng)中用于拓撲排序的頂點入度，則值為0的元素被鏈接成為一個________。 18. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為________和________。 二、應(yīng)用題 1. 對于下圖G4和G5，按下列條件試分別寫出從頂點v0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。 (1) 假定它們均采用鄰接矩陣表示。 (2) 假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。 2. 對于下圖G6，試給出一種拓撲序列，若在它的鄰接表存儲結(jié)構(gòu)中，每個頂點鄰接表中的邊結(jié)點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓撲序列。第八章 查找 一、填空題 1．以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為________，時間復(fù)雜度為________。 2．以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于________，時間復(fù)雜度為________。 3．以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為________。 4．以二分查找方法查找一個線性表時，此線性表必須是________存儲的________表。 5．從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度分別為________和________。 6．對于二分查找所對應(yīng)的判定樹，它既是一棵_______，又是一棵________。 7．假定對長度n=50的有序表進行二分查找，則對應(yīng)的判定樹高度為________，判定樹中前5層的結(jié)點數(shù)為________，最后一層的結(jié)點數(shù)為________。 8．在索引表中，每個索引項至少包含有________域和________域這兩項。 9．假定一個線性表為(12,23,74,55,63,40,82,36)，若按Key % 3條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為________、________和________。10. 假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為________、________和________。 11．在線性表的________存儲中，無法查找到一個元素的前驅(qū)或后繼元素。 12．在線性表的________存儲中，對每一個元素只能采用順序查找。 13．假定對線性表(38,25,74,52,48)進行散列存儲，采用H(K)=K % 7作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對各自散列表進行查找的平均查找長度分別為_______和________。 14．假定要對長度n=100的線性表進行散列存儲，并采用鏈接法處理沖突，則對于長度m=20的散列表，每個散列地址的單鏈表的長度平均為________。 15. 在線性表的散列存儲中，處理沖突有________和________兩種方法。 16．對于線性表(18,25,63,50,42,32,90)進行散列存儲時，若選用H(K)=K % 9作為散列函數(shù)，則散列地址為0的元素有________個，散列地址為5的元素有________個。 二、應(yīng)用題 1. 假定查找有序表A[25]中每一元素的概率相等，試分別求出進行順序、二分查找每一元素時的平均查找長度。 2. 假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。 3. 假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[11]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設(shè)計 設(shè)計在有序表A[n]中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。第九章 排序 一、填空題 1．每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做________排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做________排序。 2．每次直接或通過基準元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做________排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做________排序。 3．在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜度為________，記錄移動次數(shù)的時間復(fù)雜度為________。 4. 在堆排序的過程中，對n個記錄建立初始堆需要進行________次篩運算，由初始堆到堆排序結(jié)束，需要對樹根結(jié)點進行_______次篩運算。 5．在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。 6．假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為________________。 7. 快速排序在平均情況下的時間復(fù)雜度為________，在最壞情況下的時間復(fù)雜度為________。 8．快速排序在平均情況下的空間復(fù)雜度為________，在最壞情況下的空間復(fù)雜度為________。 9．在快速排序方法中，進行每次劃分時，是從當(dāng)前待排序區(qū)間的________向________依次查找出處于逆序的元素并交換之，最后將基準元素交換到一個確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后兩個子區(qū)間。 10. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的一次劃分的結(jié)果為________________。 11. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的過程中，對應(yīng)二叉搜索樹的深度為________，分支結(jié)點數(shù)為________。 12．在二路歸并排序中，對n個記錄進行歸并的趟數(shù)為________。 13. 在歸并排序中，進行每趟歸并的時間復(fù)雜度為________，整個排序過程的時間復(fù)雜度為________，空間復(fù)雜度為________。 14．對20個記錄進行歸并排序時，共需要進行________趟歸并，在第三趟歸并時是把長度為________的有序表兩兩歸并為長度為________的有序表。 15．假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行歸并排序的過程中，第二趟歸并后的結(jié)果為________________。 二、應(yīng)用題 已知一組元素的排序碼為 (46，74，16，53，14，26，40，38，86，65，27，34) (1) 利用直接插入排序的方法寫出每次向前面有序表插入一個元素后的排列結(jié)果。 (2) 利用直接選擇排序方法寫出每次選擇和交換后的排列結(jié)果。 (3) 利用堆排序的方法寫出在構(gòu)成初始堆和利用堆排序的過程中，每次篩運算后的排列結(jié)果，并畫出初始堆所對應(yīng)的完全二叉樹。 (4) 利用快速排序的方法寫出每一層劃分后的排列結(jié)果，并畫出由此快速排序得到的二叉搜索樹。 (5) 利用歸并排序的方法寫出每一趟二路歸并排序后的結(jié)果。 三、算法設(shè)計完成從一維數(shù)組A[n]上進行快速排序的遞歸算法。void QuickSort( ElemType A[] , int s , int t ){ int i = s, j = t+1。 ElemType x = A[s]。 do { do i++。 while ( ) 。 // 填寫一個循環(huán)條件do j。 while ( A[j].stn )。if ( ij ){ ElemType temp = A[i] 。 A[i] = A[j] 。 A[j] = temp。 } } while ( ij )。 A[s] = A[j]。 A[j] = x。 if ( sj1 ) 。 if