1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案

1、中南大學(xué)現(xiàn)代遠(yuǎn)程教育課程考試（?？疲?fù)習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)一、判斷題： 1 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。（ ）2 鏈?zhǔn)酱鎯?chǔ)在插人和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序。 （ ）3 在只有度為0和度為k的結(jié)點(diǎn)的k叉樹中，設(shè)度為0的結(jié)點(diǎn)有n0個(gè)，度為k的結(jié)點(diǎn)有nk個(gè)，則有n0=nk+1。 ( )4 折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。( )5 如果兩個(gè)串含有相同的字符，則這兩個(gè)串相等。（）6 數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對(duì)它進(jìn)行插入、刪除等運(yùn)算。（）7 在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不

2、設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。（ ）8 通常遞歸的算法簡(jiǎn)單、易懂、容易編寫，而且執(zhí)行的效率也高。 （ ）9 一個(gè)廣義表的表尾總是一個(gè)廣義表。 （ ）10 當(dāng)從一個(gè)小根堆（最小堆）中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。 （ ）11 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O（h）。 （ ）12 存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。 （ ）13 直接選擇排序是一種穩(wěn)定的排序方法。 （ ）14 閉散列法通常比開散列法時(shí)間效率更高。 （ ）15 有n個(gè)結(jié)點(diǎn)的

3、不同的二叉樹有n!棵。 ( )16 直接選擇排序是一種不穩(wěn)定的排序方法 。( )17 在2048個(gè)互不相同的關(guān)鍵碼中選擇最小的5個(gè)關(guān)鍵碼，用堆排序比用錦標(biāo)賽排序更快。 ( )18 當(dāng)3階B_樹中有255個(gè)關(guān)鍵碼時(shí),其最大高度(包括失敗結(jié)點(diǎn)層)不超過8。( )19 一棵3階B_樹是平衡的3路搜索樹,反之,一棵平衡的3路搜索樹是3階非B_樹。( ) 20 在用散列表存儲(chǔ)關(guān)鍵碼集合時(shí)，可以用雙散列法尋找下一個(gè)空桶。 在設(shè)計(jì)再散列函數(shù)時(shí)，要求計(jì)算出的值與表的大小m互質(zhì)。 ( )21 在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長(zhǎng)度不僅與表中元素個(gè)數(shù)有關(guān)，而且與每一塊中元素個(gè)數(shù)有關(guān)。（）2

4、2 在順序表中取出第i個(gè)元素所花費(fèi)的時(shí)間與i成正比。（）23 在棧滿情況下不能作進(jìn)棧運(yùn)算，否則產(chǎn)生“上溢”。()24 二路歸并排序的核心操作是將兩個(gè)有序序列歸并為一個(gè)有序序列。（）25 對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個(gè)頂點(diǎn).（）26 二叉排序樹或者是一棵空二叉樹，或者不是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值;若它的右子樹非空，則根結(jié)點(diǎn)的值小于其右孩子的值。（）27 在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。（）28 一個(gè)有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)一定相

5、等。（）二、選擇題：1 在一個(gè)長(zhǎng)度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為( )。 A. O(n) B. O(n2)C. O(1) D. O(n2)2 帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是：( ) A. first=NULL B. first一1inkNULL C. first一link=firstD. first!NUlL3 當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為( )。A. n-2 B. n-l C. n D. n+14 在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時(shí)需利用遞歸工作記錄保存實(shí)際參數(shù)的值。在傳值參數(shù)情形，需為對(duì)應(yīng)形式參數(shù)分配空間，以存放實(shí)際參數(shù)的副本；在引用參數(shù)

6、情形，需保存實(shí)際參數(shù)的( )，在被調(diào)用程序中可直接操縱實(shí)際參數(shù)。A. 空間 B. 副本 C. 返回地址 D. 地址5 在一棵樹中，( )沒有前驅(qū)結(jié)點(diǎn)。 A. 分支結(jié)點(diǎn) D. 葉結(jié)點(diǎn)C. 樹根結(jié)點(diǎn) D. 空結(jié)點(diǎn)6 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加( )。A. 2 B. 1C. 0 D. -17 對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為( )的值除以9。 A. 20 B. 18C. 25 D. 228 在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的( )。 A. 入度 B. 出度 C. 入度與出度之和 D. 入度與出度之差9 在基于排序碼比較的排序

7、算法中，( )算法的最壞情況下的時(shí)間復(fù)雜度不高于O(n10g2n)。 A. 起泡排序 B. 希爾排序C. 歸并排序 D. 快速排序10 當(dāng)?shù)闹递^小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有( )的查找速度。A. 較慢 B. 較快 C. 相同 D. 不清楚11 設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過1.5，則散列表項(xiàng)應(yīng)能夠至少容納( )個(gè)表項(xiàng)。 (設(shè)搜索成功的平均搜索長(zhǎng)度為Snl1+l(1一)2，其中為裝填因子)A. 400 B. 526 C. 624 D. 676 12 堆是一個(gè)鍵值序列k1,k2,.kn,對(duì)I=1,2,.|_n/2_|,滿

8、足( )A. kik2ik2i+1 B. kik2i+1next=NULLC. head!=NULL D. head-next=head16 引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是( )A. 出隊(duì) B. 入隊(duì)C. 取隊(duì)頭元素 D. 取隊(duì)尾元素17 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是( )A. 2，4，3，1，5，6 B. 3，2，4，1，6，5C. 4，3，2，1，5，6 D. 2，3，5，1，6，418 字符串通常采用的兩種存儲(chǔ)方式是( )A. 散列存儲(chǔ)和索引存儲(chǔ) B. 索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)C. 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) D. 散列存儲(chǔ)和順序存儲(chǔ)19

9、 設(shè)主串長(zhǎng)為n，模式串長(zhǎng)為m(mn)，則在匹配失敗情況下，樸素匹配算法進(jìn)行的無(wú)效位移次數(shù)為( )A. m B. n-mC. n-m+1 D. n20 二維數(shù)組A1218采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)元素的地址為150，則元素A97的地址為( )A. 429 B. 432C. 435 D. 43821 對(duì)廣義表L=(a,b),(c,d),(e,f)執(zhí)行操作tail(tail(L)的結(jié)果是( )A. (e,f) B. (e,f)C. (f) D. ( )22 下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹是( )23 n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( ) A. n-1條有向邊 B.

10、n條有向邊C. n(n-1)/2條有向邊D. n(n-1)條有向邊24 對(duì)關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為( )A. (19，23，56，34，78，67，88，92) B. 23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92) D. (19，23，67，56，34，78，92，88)25 若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為( ) A. 4 B. 5C. 8 D. 926 由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹( )A. 其形態(tài)不一定相同，但平

11、均查找長(zhǎng)度相同B. 其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C. 其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同D. 其形態(tài)均相同，平均查找長(zhǎng)度也都相同27 ISAM文件和VSAM文件的區(qū)別之一是( )A. 前者是索引順序文件，后者是索引非順序文件B. 前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取C. 前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)D. 前者的存儲(chǔ)介質(zhì)是磁盤，后者的存儲(chǔ)介質(zhì)不是磁盤28 下列描述中正確的是（ ）A 線性表的邏輯順序與存儲(chǔ)順序總是一致的B 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找C 數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的內(nèi)容D 選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的

12、關(guān)鍵步驟29 下面程序段的時(shí)間復(fù)雜度是（ ）i=s=0while(srear=Q-front B.(Q-rear+1)%maxsize=Q-frontC.Q-rear=0 D.Q-front=035 設(shè)s3=I AM,s4=A TERCHER.則strcmp(s3,s4)=( )A.0 B.小于0 C.大于0 D.不確定36 一維數(shù)組的元素起始地址loc6=1000，元素長(zhǎng)度為4，則loc8為（）A1000 B.1004 C.1008 D.837 廣義表（a,b）,c,d）的表尾是（）Aa B.b C.(a,b) D.(c,d)38 對(duì)于二叉樹來說，第I層上至多有_個(gè)節(jié)點(diǎn)（）A2i B. 2i

13、 -1 C.2i-1 D.2i-1-139 某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為（）ABDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA40 M叉樹中，度為0的節(jié)點(diǎn)數(shù)稱為（）A根 B.葉 C.祖先 D.子孫41 已知一個(gè)圖如下所示，若從頂點(diǎn)a出發(fā)按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂 點(diǎn)序列為（）42 堆的形狀是一棵（）A二叉排序樹 B.滿二叉樹 C.完全二義樹 D.平衡二叉樹43 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（）A希爾排序 B.歸并排序 C.

14、插入排序 D.選擇排序44 采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（）An B.n/2 C.(n+1)/2 D.(n-1)/245 散列查找是由鍵值_確定散列表中的位置，進(jìn)行存儲(chǔ)或查找（）A散列函數(shù)值 B.本身 C.平方 D.相反數(shù)46 順序文件的缺點(diǎn)是（）A不利于修改 B.讀取速度慢 C.只能寫不能讀 D.寫文件慢47 索引文件的檢索方式是直接存取或按_存?。ǎ〢隨機(jī)存取 B.關(guān)鍵字 C.間接 D.散列48 堆是一個(gè)鍵值序列k1,k2,.kn,對(duì)i=1,2,.|_n/2_|,滿足( )A. kik2ik2i+1 B. kik2i+1k2iC. kik2i且kik2i

15、+1(2i+1n) D. kik2i 或kik2i+1(2i+1n)三、 計(jì)算與算法應(yīng)用題（本大題每小題9分）1. 給定表（119，14，22，1，66，21，83，27，56，13，10）請(qǐng)按表中元素的順序構(gòu)造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長(zhǎng)度。（9分）2. 已知一個(gè)有向圖的頂點(diǎn)集V和邊集G分別為：V=a,b,c,d,e,f,g,hE=,;假定該圖采用鄰接矩陣表示，則分別寫出從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。（9分）3. 設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H（h）= k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。

16、試畫出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。（8分） 0 1 2 3 4 5 6 7 8 9 10 11 12 4. 對(duì)7個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為1,2,3,4,5,6,7，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列；(2)對(duì)所舉序列進(jìn)行快速排序，寫出排序過程。（分）5. 如圖所示二叉樹，回答下列問題。（9分）6. 畫出在一個(gè)初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時(shí)每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結(jié)點(diǎn)后的結(jié)果。7.已知一組記錄的排序碼為（ 46 ，

17、79 ， 56 ， 38 ， 40 ， 80, 95 ， 24 ），寫出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。 8. 一個(gè)線性表為 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36 ），設(shè)散列表為 HT0.12 ，散列函數(shù)為 H （ key ） = key % 13 并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。 9. 已知一棵二叉樹的前序遍歷的結(jié)果序列是 ABECKFGHIJ ，中序遍歷的結(jié)果是 EBCDAFHIGJ ，試寫出這棵二叉樹的后序遍歷結(jié)果。10. 假定對(duì)線性表(38，25，74，52，48，65

18、，36)進(jìn)行散列存儲(chǔ)，采用H(K)=K9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對(duì)應(yīng)的平均查找長(zhǎng)度分別為和 。11假定一組記錄的排序碼為(46，79，56，38，40，80，25，34，57，21)，則對(duì)其進(jìn)行快速排序的第一次劃分后又對(duì)左、右兩個(gè)子區(qū)間分別進(jìn)行一次劃分，得到的結(jié)果為： 。12. 下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點(diǎn)V1出發(fā)，深度遍歷圖G所得結(jié)點(diǎn)序列為（ A ），廣度遍歷圖G所得結(jié)點(diǎn)序列為（ B ）；G的一個(gè)拓?fù)湫蛄惺牵?C ）；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的最短路徑為（ D ）；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的關(guān)鍵路徑為（ E ）。其中A、B、C的選擇有：V1,V2,V3,V

19、4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6V1,V2,V3,V8,V5,V7,V4,V6D、E的選擇有： V1,V2,V4,V5,V3,V8 V1,V6,V5,V3,V8 V1,V6,V7,V8 V1,V2,V5,V7,V813.畫出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。14. 已知如圖所示的有向網(wǎng)，試?yán)肈ijkstra算法求頂點(diǎn)1到其余頂

20、點(diǎn)的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。15. 假定用于通信的電文由個(gè)字母a,b,c,d,e,f,g,h組成，各字母在電文中出現(xiàn)的頻率分別為，。試為這個(gè)字母設(shè)計(jì)不等長(zhǎng)Huffman編碼，并給出該電文的總碼數(shù)。16. 已知一棵二叉樹的中序和前序序列如下，試畫出該二叉樹并求該二叉樹的后序序列。（9分）中序序列：c，b，d，e，a，g，i，h，j，f前序序列：a，b，c，d，e，f，g，h，i，j17. 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表

21、示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。四、算法設(shè)計(jì)題1. 已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲(chǔ)結(jié)構(gòu)。請(qǐng)寫一算法，求該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。2. 編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找item帶回整個(gè)結(jié)點(diǎn)的值并返回ture，否則返回false。 bool Find（BtreeNode*BST，ElemType&item）3. 編寫算法，將一個(gè)結(jié)點(diǎn)類型為 Lnode 的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素的次序?yàn)?a 1 ， a n-1 ， a n ，則逆序鏈接后變?yōu)?, a n ， a n-1 ， a

22、 1 。 4.根據(jù)下面函數(shù)原型，編寫一個(gè)遞歸算法，統(tǒng)計(jì)并返回以BT為樹根指針的二叉樹中所有葉子結(jié)點(diǎn)的個(gè)數(shù)。 int Count(BTreeNode * BT)；5. 設(shè)A=(a1,.,am)和B=(b1,.,bn)均為順序表，A和B分別為A和B中除去最大共同前綴后的子表。若A=B=空表，則A=B；若A=空表，而B空表，或者兩者均不為空表，且A的首元小于B的首元，則AB。試寫一個(gè)比較A，B大小的算法。6.已知單鏈表a和b的元素按值遞增有序排列, 編寫算法歸并a和b得到新的單鏈表c，c的元素按值遞減有序。7. 編寫遞歸算法，對(duì)于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。

23、8. 編寫算法判別T是否為二叉排序樹.9. 試寫一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑（ij）。注意：算法中涉及的圖的基本操作必須在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。參考答案一、 判斷題 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 二、單項(xiàng)選擇題1A 2B 3B 4D 5C 6A 7C 8C 9C 10B 11A 12 C 13. B 14. D 15. A16. A 17. D18. C 19. C 20. A 21. B 22. A23. B 24.

24、D 25. C 26. B 27 C28.D 29.B 30.A 31.A 32.B 33.D 34.A 35. C 36.C37.D 38.C 39.D 40.A 41.B 42.C 43.D 44.C 45.A 46.A 47.B 48. C三 計(jì)算與算法應(yīng)用題解答平均長(zhǎng)度為4.2、解：畫圖（略） 深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e 廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g 3、解：計(jì)算機(jī)關(guān)鍵碼得到的散列地址關(guān)鍵碼1914230168208427散列地址611013761在散列表中散列結(jié)果 0 1 2 3 4 5 6 7 8 9 10 11 1214016827192

25、084234. 對(duì)n個(gè)關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個(gè)關(guān)鍵字比較。這里要求10次，而7 - 1 + 2 * ( 3 - 1 ) = 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時(shí)候，正好將序列平分 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7 . (2)按自己序列完成012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2)(1)(1)(1)(1)(2)(4)(

26、5)(2)(5)(6) (2)搜索成功的平均搜索長(zhǎng)度為l12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l12 5答案：(1)djbaechif (2)abdjcefhi (3)jdbeihfca 6. 在這個(gè)AVL樹中刪除根結(jié)點(diǎn)時(shí)有兩種方案:【方案1】在根的左子樹中沿右鏈走到底,用5遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除5所在的結(jié)點(diǎn). 【方案2】在根的右子樹中沿左鏈走到底,用7遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除7所在的結(jié)點(diǎn).7.劃分次序 劃分結(jié)果 第一次 38 24 40 46 56 80 95 79 第二次 24 38 40 46 56 80 95 79 第三次 24 38 40 46 56

27、80 95 79 第四次 24 38 40 46 56 80 95 79 第五次 24 38 40 46 56 79 80 95 第六次 24 38 40 46 56 79 80 95 8 、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找長(zhǎng)度： ASL SUCC =14/10= 1.4 9 、此二叉樹的后序遍歷結(jié)果是： EDCBIHJGFA 10. 137 1l7 112l 25 34 38 404679 56 5780 12. 12. (A) 深度遍歷：1，2，3，8，4，5，7，6或1，2，3，8，

28、5，7，4， （B） 廣度遍歷：1，2，4，6，3，5，7，8（C） 拓?fù)湫蛄校?，2，4，6，5，3，7，8（D） 最短路徑：1，2，5，7，8（E） 關(guān)鍵路徑：1，6，5，3，813.ASLsucc=（1+2X2+3X4+4X3）/10=2.9 14. 源點(diǎn) 終點(diǎn) 最短路徑 路徑長(zhǎng)度 1 2 1，3，2 19 3 1，3 15 4 1，3，2，4 29 5 1，3，5 29 6 1，3，2，4，6 44 15. 已知字母集a, b, c, d, e, f, g, h 次數(shù)，,，則Huffman 編碼為（5分）a b c d e f g h電文總碼數(shù)為（2分）*圖（2分）1111111000

29、00006612510017392236537410111116. 樹（略）后序序列：c，e，d，b，i，j，h，g，f，a （5+4分）17. 方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.0

30、2411100.065100.326111110.037010.21811010.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼四、算法設(shè)計(jì)題： 1 二叉樹采取順序結(jié)構(gòu)存儲(chǔ)，是按完全二叉樹格式存儲(chǔ)的。對(duì)非

31、完全二叉樹要補(bǔ)上“虛結(jié)點(diǎn)”。由于不是完全二叉樹，在順序結(jié)構(gòu)存儲(chǔ)中對(duì)葉子結(jié)點(diǎn)的判定是根據(jù)其左右子女為0。葉子和雙親結(jié)點(diǎn)下標(biāo)間的關(guān)系滿足完全二叉樹的性質(zhì)。int Leaves(int h) /求深度為h以順序結(jié)構(gòu)存儲(chǔ)的二叉樹的葉子結(jié)點(diǎn)數(shù)int BT; int len=2h-1, count=0; /BT是二叉樹結(jié)點(diǎn)值一維數(shù)組，容量為2h for (i=1;ilen) count+; /第i個(gè)結(jié)點(diǎn)沒子女，肯定是葉子else if(BT2*i=0 & 2*i+1data）item=BST一data； return true; else if（itemBST一dataBSTBST一left;else B

32、ST=BST一right； return false; 3. Lnode *P=HL; HL=NULL; While (p!=null) Lnode*q=p; P=p next; q next=HL; HL=q; 4. int Count(BTreeNode* BT) 統(tǒng)計(jì)出二叉樹中所有葉子結(jié)點(diǎn)數(shù) if(BT=NULL)return O； else if(BT-left=NULL&BT-right=NULL)return 1； else return Count(BT-left)+Count(BT-right)； 5. int Compare-List(SqList a, SqList b)

33、/a,b為順序表，若ab時(shí)，返回1 i=0; while (i=a.length-1) & (i=b.length-1) & (a.elemi=b.elemi) +i; switch case i=a.length & i=b.length : return 0; break; case (i=a.length & i=b.length-1) |(i=a.length-1 & i=b.length-1 & a.eleminext; q=b-next; c-next=NULL; while (p & q) if (p-datadata) pn=p-next; p-next=c-next; c-next=p; p=pn; else qn=q-next; q-next=c-next; c-next=q; q=qn; while (p) pn=p-next; p-next=c-next; c-next=p; p=pn; while (q) qn=q-next; q-next=c-next; c-next=q; q=qn; free(b);/MergeList7. Status Del-subtree(Bitree bt) /刪除bt所指二叉樹，并釋放相應(yīng)的空間 if (bt) Del-subtree(bt-lchild);Del-