熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

第6章樹(基礎知識)習題練習

2013-11-15 15:44:27  來源: 數據結構 

假設在樹中結點x是結點y的雙親時用(xy)來表示樹邊已知一棵樹邊的集合為{(im)(in)(ei)(be)(bd)(ab)(gj)(gk)(cg)(cf)(hl)(ch)(ac)}用樹形表示法出此樹並回答下列問題

 ()哪個是根結點? ()哪些是葉結點? ()哪個是g的雙親? ()哪些是g的祖先? 
 ()哪些是g的孩子? ()哪些是e的子孫? ()哪些是e的兄弟?哪些是f的兄弟? 
 ()結點b和n的層次各是多少? ()樹的深度是多少? ()以結點c為根的子樹的深度是多少?
 () 樹的度數是多少?

一棵度為的有序樹與一棵二叉樹有何區別?

試分別畫出具有個結點的樹和個結點的二叉樹的所有不同形態

已知一棵度為m的樹中有n個度為的結點n個度為的結點nm個度為m的結點問該樹中有多少片葉子?

一個深度為h的滿k叉樹有如下性質第h層上的結點都是葉子結點其余各層上每個結點都有k棵非空子樹如果按層次順序(同層自左至右)從開始對全部結點編號
 ()各層的結點數目是多少?
 ()編號為i的結點的雙親結點(若存在)的編號是多少?
 ()編號為i的結點的第j個孩子結點(若存在)的編號是多少?
 ()編號為i的結點的有右兄弟的條件是什麼? 其右兄弟的編號是多少?

高度為h的完全二叉樹至少有多少個結點?至多有多少個結點?

在具有n個結點的k叉樹(k>=)的k叉鏈表表示中有多少個空指針?

假設二叉樹包含的結點數據為
 ()畫出兩棵高度最大的二叉樹
 ()畫出兩棵完全二叉樹要求每個雙親結點的值大於其孩子結點的值

試找出分別滿足下面條件的所有二叉樹
 ()前序序列和中序序列相同 ()中序序列和後序序列相同
 ()前序序列和後序序列相同 ()前序中序後序序列均相同

試采用順序存儲方法和鏈接存儲方法分別畫出(下圖)所示各二叉樹的存儲結構

分別寫出圖(下圖)所示各二叉樹的前序中序和後序序列

   

若二叉樹中各結點的值均不相同則由二叉樹的前序序列和中序序列或由其後序序列和中序序列均能唯一地確定一棵二叉樹但由前序序列和後序序列卻不一定能唯一地確定一棵二叉樹
 ()已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF請畫出此二叉樹
 ()已知一棵二叉樹的在序序列和後序序列分別為BDCEAFHG和DECBHGFA請畫出此二叉樹
 ()已知一棵二叉樹的前序序列和後序序列分別為AB和BA請畫出這兩棵不同的二叉樹

對二叉樹中的結點進行按層次順序(每一層自左至右)的訪問操作稱為二叉樹的層次遍歷遍歷所得到的結點序列稱為二叉樹層次序列現已知一棵二叉樹的層次序列為ABCDEFGHIJ中序序列為DBGEHJACIF請畫出此二叉樹

試畫出圖(上圖)所示各二叉樹的前序中序和後序線索樹及相應的線索鏈表 

在何種線索樹中線索對求指定結點在相應次序下的前趨和後繼並無幫助?

對圖(下圖)所示的森林

  

 ()求各樹的前序序列和後序序列
 ()求森林的前序序列和後序序列
 ()將此森林轉換為相應的二叉樹
 ()給出(a)所示樹的以親鏈表表示孩子鏈表表示雙親孩子鏈表表示及孩子兄弟鏈表示等四種存儲結構並指出哪些存儲結構易於求指定結點的祖先哪些易於求指定結點的後代?

畫出圖(下圖)所示的各二叉樹所對應的森林

   

高度為h的嚴格二叉樹至少有多少個結點?至多有多少個結點? 

在什麼樣的情況下等長編碼是最優的前綴碼?

下述編碼哪一組不是前綴碼?
  {}{}{}

假設用於通信的電文由字符集{abcdefgh}中的字母構成個字母在電文中出現的概率分別為{}
 ()為這個字母設計哈夫曼編碼
 ()若用這三位二進制數()對這個字母進行等長編碼則哈夫曼編碼的平均碼長是等長編碼的百分之幾?它使電文總長平均壓縮多少?


From:http://tw.wingwit.com/Article/program/sjjg/201311/23878.html
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.