數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)

1、練 習(xí)1. 內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。2. 敘述前序和中序遍歷二叉樹的步驟；一棵前序序列為1,2,3,4的二叉樹,其中序序列可能是4,1,2,3嗎?設(shè)一棵二叉樹的前序序列為1,2,3,4,5,6,7,8,9,其中序序列為2,3,1,5,4,7,8,6,9,試畫出該二叉樹。3. 設(shè)有一個(gè)關(guān)鍵碼的輸入序列 55, 31, 11, 37, 46, 73, 63 , (1) 從空樹開始構(gòu)造平衡二叉搜索樹, 畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。若發(fā)生不平衡, 指明需做的平衡旋轉(zhuǎn)的類型及平

2、衡旋轉(zhuǎn)的結(jié)果。(2) 計(jì)算該平衡二叉搜索樹在等概率下的查找成功的平均查找長(zhǎng)度。4. 設(shè)散列表為HT0.12,即表的大小為m=13?，F(xiàn)采用雙散列法解決沖突。散列函數(shù)和再散列函數(shù)分別為： H0(key)=key%13;    注：是求余數(shù)運(yùn)算（mod） Hi=(Hi-1+REV(key+1)%11+1)%13;    i=1,2,3,，m-1其中，函數(shù)REV（x）表示顛倒10進(jìn)制數(shù)x的各位，如REV(37)=73,REV(7)=7等。若插 入的關(guān)鍵碼序列為2,8,31,20,19,18,53,27。 (1)試畫出插入這8個(gè)關(guān)鍵碼后的散列表

3、。 (2)計(jì)算搜索成功的平均搜索長(zhǎng)度ASL。5. 下圖表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費(fèi)的代價(jià)，如何選擇能溝通每個(gè)城市且總代價(jià)最省的n-1條線路，畫出所有可能的選擇。6. 給出一組關(guān)鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進(jìn)行排序時(shí)的變化過(guò)程：  （1）歸并排序   每歸并一次書寫一個(gè)次序。  （2）快速排序   每劃分一次書寫一個(gè)次序。  （3）堆排序   先建成一個(gè)最大堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次。7

4、. 假設(shè)用于通訊的電文由 5個(gè)字母組成，A B C D E F ，字母在電文中的出現(xiàn)頻率分別為 0.09，0.12，0.07，0.22，0.23，0.27，畫出哈夫曼樹，并寫出各個(gè)字符的哈夫曼編碼。（左子樹根節(jié)點(diǎn)值不大于右子樹根節(jié)點(diǎn)值）8. 已知序列（50，72，43，85，75，20，35，45，65，30），請(qǐng)以順序插入方式構(gòu)造二叉排序樹，并畫出刪除結(jié)點(diǎn)72之后的二叉排序樹。9. 已知帶權(quán)無(wú)向圖G的鄰接矩陣是A。A=6 0 5 0 0 40 5 0 6 0 00 0 6 0 0 76 0 0 0 0 23 4 0 7 2 00 6 0 0 6 3V1 V2 V3 V4 V5 V6(1) 畫

5、出圖G；(2) 分別畫出一顆從V1出發(fā)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹；(3) 畫出一棵最小生成樹。10. 假定一組記錄的排序碼為(46，79，56，38，40，84，50，42)，利用堆排序方法畫出初始大頂堆（以樹狀表示）。11. 圖的深度優(yōu)先搜索類似于BFS,不同之處在于使用棧代替BFS中的隊(duì)列，進(jìn)出隊(duì)列的操作改為入出棧的操作。即當(dāng)一個(gè)頂點(diǎn)的一個(gè)鄰接點(diǎn)被搜索后，下一個(gè)搜索的出發(fā)點(diǎn)應(yīng)該是最近入棧(棧頂)的頂點(diǎn)。用 深度優(yōu)先搜索方法搜索下圖,設(shè)初始出發(fā)點(diǎn)為1。(1) 畫出搜索過(guò)程中棧的變化。15678423(2) 寫出頂點(diǎn)的訪問(wèn)次序（當(dāng)從某頂點(diǎn)出發(fā)搜索他的鄰接點(diǎn)時(shí)，請(qǐng)按鄰接點(diǎn)序號(hào)遞增序搜索,以使答案唯一）。 12.按照次序輸入關(guān)鍵字的值建立2-3樹(3階B-樹):(68,54,82,35,75,90，103，22)。(1)請(qǐng)畫出所建的2-3樹。(2)如果此后依次刪除22,75，畫出每一步執(zhí)行后的2-3樹的狀態(tài)。13已知如下樹林，畫出對(duì)應(yīng)的二叉樹。14. 已知二