第六章復(fù)習(xí)題.pdf

第六章復(fù)習(xí)題第六章復(fù)習(xí)題 1 列出圖所示二叉樹的葉結(jié)點 分支結(jié)點和每個結(jié)點的層次 解答 二叉樹的葉結(jié)點有 分支結(jié)點 度不為 0 的結(jié)點 有 結(jié)點 的層次為 1 結(jié)點 的層次為 2 結(jié)點 的層次為 3 結(jié)點 的層次為 4 結(jié)點 的層次 為 5 2 使用 1 順序表示和 2 二叉鏈表表示法 分別畫出上圖所示二叉 樹的存儲表示 解答 1 2 3 4 0 5 6 0 7 0 0 0 8 0 0 0 0 9 3 如果一棵樹有 n1個度為 1 的結(jié)點 有 n2個度為 2 的結(jié)點 nm個 度為 m 的結(jié)點 試問有多少個度為 0 的結(jié)點 試推導(dǎo)之 順序表示 二叉鏈表表示 解答 總結(jié)點數(shù) n n0 n1 n2 nm 總分支數(shù) e n 1 n0 n1 n2 nm 1 m nm m 1 nm 1 2 n2 n1 則有 1 1 2 0 m i i nin 4 試分別找出滿足以下條件的所有二叉樹 1 二叉樹的前序序列與中序序列相同 2 二叉樹的中序序列與后序序列相同 3 二叉樹的前序序列與后序序列相同 解答 1 二叉樹的前序序列與中序序列相同 空樹或缺左子樹的單支樹 2 二叉樹的中序序列與后序序列相同 空樹或缺右子樹的單支樹 3 二叉樹的前序序列與后序序列相同 空樹或只有根結(jié)點的二叉樹 5 請畫出右圖所示的樹所對應(yīng)的二叉樹 解答 6 已知一棵二叉樹的先序遍歷的結(jié)果是 ABECDFGHIJ 中序遍歷的 結(jié)果是 EBCDAFHIGJ 試畫出這棵二叉樹 解答 1 對應(yīng)二叉樹 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 當(dāng)前序序列為 ABECDFGHIJ 中序序列為 EBCDAFHIGJ 時 逐 步形成二叉樹的過程如下圖所示 7 已知一棵樹的先根次序遍歷的結(jié)果與其對應(yīng)二叉樹表示 孩子 兄 弟表示 的前序遍歷結(jié)果相同 樹的后根次序遍歷結(jié)果與其對應(yīng)二 叉樹表示的中序遍歷結(jié)果相同 試問利用樹的先根次序遍歷結(jié)果 和后根次序遍歷結(jié)果能否唯一確定一棵樹 舉例說明 解答 因為給出二叉樹的前序遍歷序列和中序遍歷序列能夠唯一地確定 這棵二叉樹 因此 根據(jù)題目給出的條件 利用樹的先根次序遍歷結(jié) 果和后根次序遍歷結(jié)果能夠唯一地確定一棵樹 例如 對應(yīng)二叉樹的先序序列為 1 2 3 4 5 6 8 7 中序序列為 3 4 8 6 7 5 2 1 樹的先根遍歷序列為 1 2 3 4 5 6 8 7 后根遍歷序列為 3 4 8 6 7 5 2 1 8 給定權(quán)值集合 15 03 14 02 06 09 16 17 構(gòu)造相應(yīng)的赫夫曼樹 EBCD FHIGJ A A B E F CD HIGJ A B E F C D G J HI A B E F C D G J H I 1 2 3 4 5 6 7 8 對應(yīng)二叉樹 1 2 3 4 5 6 7 8 并計算它的帶權(quán)外部路徑長度 解答 此樹的帶權(quán)路徑長度 WPL 229 9 假定用于通信的電文僅由8個字母c1 c2 c3 c4 c5 c6 c7 c8組成 各字母在電文中出現(xiàn)的頻率分別為 5 25 3 6 10 11 36 4 試為這 8 個字母設(shè)計不等長 Huffman 編碼 并給出該電文的總碼數(shù) 解答 已知字母集 c1 c2 c3 c4 c5 c6 c7 c8 頻率 5 25 3 6 10 11 36 4 則 Huffman 編碼為 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 15 03 14 02 06 09 1617 02 03 151406091617 05 02 03 15 14 06 09 16 17 05 11 02 03 1514 09 1617 05 11 06 20 02 03 14 15 09 16 17 05 11 06 20 29 0203 1415091617 05 11 06 202933 02 03 14 1509 05 11 06 20 29 16 17 33 49 0203 15 09 05 11 06 2029 1617 33 49 14 82 電文總碼數(shù)為 4 3 4 4 3 10 3 11 4 5 4 6 2 25 2 36 257 10 填空題 1 對于一棵具有 n 個結(jié)點的樹 該樹中所有結(jié)點的度數(shù)之和為 n 1 度數(shù)和就是樹的分支數(shù) 因此為 n 1 2 假定一棵三叉樹的結(jié)點個數(shù)為 50 則它的最小高度為 5 最大高度為 50 最小高度是滿三叉樹 最大高度為單支樹 3 在一棵二叉樹中 假定度為 2 的結(jié)點有 5 個 度為 1 的結(jié)點 有 6 個 則葉子結(jié)點數(shù)有 6 個 n0 n2 1 4 對于一棵具有 n 個結(jié)點的二叉樹 對應(yīng)二叉鏈表中指針總數(shù) 為 2n 個 其中 n 1 個用于指向子女結(jié)點 n 1 個指針空閑著 見教材 p126 5 在一個小頂堆中 堆頂結(jié)點的值是所有結(jié)點中的 最小者 在一個大頂堆中 堆頂結(jié)點的值是所有結(jié)點中的 最大者 6 當(dāng)從一個小頂堆中刪除一個元素時 需要把 最后 元素填補 到 堆頂 位置 然后再按條件把它逐層調(diào)整 7 在赫夫曼編碼中 若編碼長度只允許小于等于 4 則除了已 100 61 39 36 25 22 17 7 10 11 11 4 3 6 5 C3C8 C5 C6 C1C4 C2 C7 0 0 0 0 0 0 0 1 1 1 1 1 1 1 對兩個字符編碼為 0 和 10 外 還可以最多對 4 個字符編碼 8 設(shè)二叉樹有 n 個結(jié)點且根結(jié)點處于第 1 層 則其高度為 不 確定 9 設(shè)高度為 h 二叉樹只有度為 2 和度為 0 的結(jié)點 則該二叉樹 中所含結(jié)點至少有 2h 1 個 除第一層之外 每層都有 2 個結(jié)點 10 設(shè)森林 F 中有 4 棵樹 第 1 2 3 4 棵樹的結(jié)點個數(shù)分別 為 n1 n2 n3 n4 當(dāng)把森林 F 轉(zhuǎn)換成一棵二叉樹后 其根結(jié)點的右 子樹中有 n2 n3 n4 個結(jié)點 11 設(shè)森林 F 中有 4 棵樹 第 1 2 3 4 棵樹的結(jié)點個數(shù)分別 為 n1 n2 n3 n4 當(dāng)把森林 F 轉(zhuǎn)換成一棵二叉樹后 其根結(jié)點的左 子樹中有 n1 1 個結(jié)點 12 將含有 82 個結(jié)點的完全二叉樹從根結(jié)點開始順序編號 根結(jié) 點為第 0 號 其他結(jié)點自上向下 同一層自左向右連續(xù)編號 則 第 40 號結(jié)點的雙親結(jié)點的編號為 19 編號為 i 的結(jié)點 左孩 子編號 2i 1 右孩子 2i 2 13 高度為 h 的完全二叉樹最少有 2h 1 個結(jié)點 第 h 層只有一 個結(jié)點 14 某二叉樹結(jié)點的中序序列為 A B C D E F G 后序 序列為 B D C A F G E 則其左子樹中結(jié)點數(shù)目為 C A 3 B 2 C 4 D 5 11 n 個結(jié)點可構(gòu)造出多少種不同形態(tài)的二叉樹 解答 見教材 p155 有 種 12 判斷下列敘述的對錯 如果正確 在題前打 否則打 1 若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最 后一個結(jié)點 則它一定是該子樹的先序遍歷結(jié)果序列的最后一個結(jié) 點 最右下結(jié)點有左孩子無右孩子 2 若有一個結(jié)點是二叉樹中某個子樹的先序遍歷結(jié)果序列的最 后一個結(jié)點 則它一定是該子樹的中序遍歷結(jié)果序列的最后一個結(jié) 點 最右下結(jié)點有左孩子無右孩子 3 若有一個葉子結(jié)點葉子結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列 的最后一個結(jié)點 則它一定是該子樹的先序遍歷結(jié)果序列的最后一個 結(jié)點 4 在哈夫曼樹中 權(quán)值最小的結(jié)點離根結(jié)點最近 5 將一棵樹轉(zhuǎn)換為二叉樹表示后 該二叉樹的根結(jié)點一定沒有右 子樹 13 閱讀理解題 說明下列遞歸過程的功能 void unknown BinTreeNode T int a int i 指針 T 是完全二叉樹的根指針 if T NULL a i T data unknown T leftChild a 2 i 1 unknown T rightChild a 2 i 2 1 n C n 2n 主程序調(diào)用方式 unknown BT root a 0 將完全二叉樹所有結(jié)點從根開始 自頂向下 同一層自左向 右連續(xù)編號 根結(jié)點的編號為 0 答案 將用二叉鏈表表示的完全二叉樹轉(zhuǎn)換為二叉樹的順序 數(shù)組 表 示 14 下面是一個使用棧stack實現(xiàn)對二叉樹進行非遞歸先根遍歷的函數(shù) 請在標(biāo)號處填寫合適的語句 程序 Void preorder bitree T bitree stac