書面作業練習題
6.1 單項選擇題
1. 下圖所示的4棵二叉樹，____不是完全二叉樹。
2. 下列編碼中屬字首碼的是( )
（a） （b）
（c）（d）{0,1,00,11
3. 已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是____。
a. acbed b. decab c. deabc d. cedba
4．設a,b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前的條件是 。
a．a在b的右方b．a在b的左方
c．a是b的祖先d．a是b的子孫
5. 假定在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為個。
a．15b．16c．17d．47
6. 按照二叉樹的定義，具有3個結點的二叉樹有____種。
a. 3 b. 4 c. 5 d. 6
7. 樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這裡，我們把由樹轉化得到的二叉樹叫做這棵數對應的二叉樹。
結論____是正確的。
a. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
b. 樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同
c. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
d. 以上都不對
8. 深度為5的二叉樹至多有____個結點。
a. 16 b. 32 c. 31 d. 10
9. 樹最適合用來表示____。
a. 有序資料元素b. 無序資料元素
c. 元素之間具有分支層次關係的資料 d. 元素之間無聯絡的資料
10. 設有13個值，用它們組成一棵赫夫曼樹，則該赫夫曼樹共有( )個結點。
a．13 b. 12 c. 26d. 25
6.2 應用題
1. 有一棵樹如圖8.12所示，回答下面的問題：
⑴ 這棵樹的根結點是____；
⑵ 這棵樹的葉子結點是____；
⑶ 結點k3的度是____；
⑷ 這棵樹的度是____；
⑸ 這棵樹的深度是____；
⑹ 結點k3的子女是____；
⑺ 結點k3的父結點是____；
2. 深度為k的完全二叉樹至少有____個結點。至多有____個結點，若按自上而下，從左到右次序給結點編號（從0開始），則編號最小的葉子結點的編號是____。
3. 結點最少的樹為____，結點最少的二叉樹為____。
4. 由如圖8.17所示的二叉樹， 該二叉樹對應的森林是?。
5. 已知一棵樹如圖8.20所示，畫出其轉換為的一棵二叉樹。
該樹的先根遍歷序列、後根遍歷序列？
6. 有乙份電文中共使用8個字元：a、b、c、d、e、f、g、h，它們出現的頻率是5, 29, 7, 8, 14, 23, 3, 11（9分）
（1）試畫出對應的哈夫曼樹；
（2）每個字元的哈夫曼編碼；
（3）求帶權外部路徑長度(wpl)。
6.3 演算法設計題:
試編寫演算法，統計二叉樹的葉子的個數。
6.4 證明題:
證明：在非空二叉樹的第i層上，至多有2i個結點（i≥0）。
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法，即兩種儲存結構表示時的基本操作實現演算法，特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...
資料結構練習題
a.n b.n 1 2 c.n 1 9 對於乙個具有n個頂點和e條邊的無向圖，若採用鄰接表表示，則表頭向量的大小為 所有鄰接表中的接點總數是 b.n 1 c.n 1 d.n e a.e 2 b.e d.n e 10 已知乙個圖如圖7.1所示，若從頂點a出發按深度搜尋法進行遍歷，則可能得到的一種頂點序...