學號姓名班級
一、選擇題
1．按照二叉樹定義，具有3個結點的二叉樹共有 c 種形態。
(a) 3 (b) 4 (c) 5d) 6
2．具有五層結點的完全二叉樹至少有 d 個結點。
(a) 9 (b) 15 (c) 31 (d) 16
3．以下有關二叉樹的說法正確的是 b 。
(a) 二叉樹的度為2b)一棵二叉樹的度可以小於2
(c) 至少有乙個結點的度為2 (d)任一結點的度均為2
4．已知二叉樹的後序遍歷是dabec，中序遍歷是debac，則其前序遍歷是 d
（a）acbed （b）decab (c) deabc (d) cedba
5．將一棵有1000個結點的完全二叉樹從上到下，從左到右依次進行編號，根結點的編號為1，則編號為49的結點的右孩子編號為 b 。
(a) 98b) 99 (c) 50 (d) 沒有右孩子
6．對具有100個結點的二叉樹，若有二叉鍊錶儲存，則其指標域共有 d 為空。
(a) 50b) 99 (c) 100 (d) 101
7．設二叉樹的深度為h，且只有度為1和0的結點，則此二叉樹的結點總數為 c 。
(a) 2hb) 2h-1 (c) h (d) h+1
8．對一棵滿二叉樹，m個樹葉，n個結點，深度為h，則 d 。
(a) n=h+m (b) h+m=2n (c)m=h-1 (d)n=2h-1
9．某二叉樹的先序序列和後序序列正好相反，則下列說法錯誤的是 a 。
(a) 二叉樹不存在
(b) 若二叉樹不為空，則二叉樹的深度等於結點數
(c) 若二叉樹不為空，則任一結點不能同時擁有左孩子和右孩子
(d) 若二叉樹不為空，則任一結點的度均為1
10．對二叉樹的結點從1開始進行編號，要求每個結點的編號大於其左右孩子的編號，同一結點的左右孩子中，其左孩子的編號小於其右孩子的編號，可採用 c 遍歷實現編號。
(a) 先序 (b)中序 (c)後序 (d)層序
11．乙個具有1025個結點的二叉樹的高h為 c 。
(a) 10 (b)11 (c)11~1025 (d)10~1024
12．設n,m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是 c 。
( a) n在m右方b)n是m祖先
(c) n在m左方d) n是m子孫
二、填空題
1．對一棵具有n個結點的二叉樹，當它為一棵完全二叉樹時具有最小高度；當它為
單分支二叉樹時，具有最大高度。
2．在二叉樹的第i（i≥1）層上至多有 2i-1 個結點，深度為k（k≥1）的完全二叉樹至多 2k-1 個結點，最少 2k-1 個結點；
3．如果二叉樹的終端結點數為n0，度為2的結點數為n2，則n0 = n2-1 。
4．已知一棵二叉樹的中序序列是cbedahgijf，後序序列是cedbhjigfa，則該二叉樹的先序序列是 abcdefghij ，該二叉樹的深度為 5 。
5．若一棵二叉樹的中序遍歷結果為abc，則該二叉樹有 3 中不同的形態。
6．在順序儲存的二叉樹中，下標為i和j的兩個結點處在同一層的條件是 log2i==log2j 。
7．已知完全二叉樹的第7層有8個結點，則其葉子結點數為 36 個。總結點數為 71 個。
8．在對二叉樹進行非遞迴中序遍歷過程中，需要用棧來暫存所訪問結點的位址；進行層序遍歷過程中，需要用佇列來暫存所訪問結點的位址。
三、應用題
1.有n個結點的二叉樹，已知葉子結點個數為n0,回答下列問題：
(1)寫出求度為1的結點的個數n1的計算公式；
n1=n+1-2n0
(2)若此樹是深度為k的完全二叉樹，寫出n為最小的公式；
nmin=2k-1
(3)若二叉樹中僅有度為0和度為2的結點，寫出求該二叉樹結點個數n的公式；
n=2n0-1
四、演算法分析題
教材p208 習題5-2 中：1、2、4、5四題
1.返回二叉樹bt中值為x的結點所在的層號。
int nodelevel(btreenode*bt,elemtype x)
}2.指出下面函式的功能。
btreenode* btreeswopx(btreenode* bt)
}函式的功能：交換二叉樹的左右子樹，生成新的二叉樹。
4.指出下面函式的功能。
void btc(btreenode*bt)
}函式的功能：調整二叉樹，使樹中左子樹結點的值小於等於右子樹結點的值。
5.設bt指向一顆二叉樹，該二叉樹的廣義表表示為a(b(a,d(f)),c(e(,a(k)),b))，則依次使用btc1(bt』a』,c)、btc1(bt』b』,c)、btc1(bt』c』,c)和btc1(bt』g』,c)呼叫下面演算法時，假定每次呼叫時c的初值為0，引用變數c的帶回值依次為 3 、 2 、 1 和 0 。
void btc1(btreenode*bt, char x, int&k)
}五、演算法設計題（參照上題，並總結有關二叉樹操作實現的常用方法）
1．編寫求二叉樹bt中結點總數的演算法。
int btreecount(btreenode *bt)
2．編寫求二叉樹bt中葉子結點數的演算法。
int btreeleafcount(btreenode *bt)
3．若已知兩棵二叉樹bt1和bt2皆為空，或者皆不為空且bt1的左、右子樹和bt2的左、右子樹分別相似，則稱二叉樹bt1和bt2相似。編寫演算法，判別給定的兩棵二叉樹是否相似。
int similartrees(btreenode *bt1,btreenode *bt2)
資料結構練習二叉樹
學號 31301374 姓名張一博班級軟體工程1301 一 選擇題 1 按照二叉樹定義，具有3個結點的二叉樹共有 c 種形態。a 3 b 4 c 5d 6 2 具有五層結點的完全二叉樹至少有 d 個結點。a 9 b 15 c 31 d 16 3 以下有關二叉樹的說法正確的是 b a 二叉樹的度為2b...
資料結構試驗 二叉樹
實驗報告名稱 姓名學號專業班級 日期實驗6 二叉樹的建立及遍歷 一 實驗目的 1 學會實現二叉樹結點結構和對二叉樹的基本操作。2 掌握對二叉樹每種操作的具體實現，學會利用遞迴方法編寫對二叉樹這種遞迴資料結構進行處理的演算法。二 實驗要求 1 認真閱讀和掌握和本實驗相關的教材內容。2 編寫完整程式完成...
資料結構二叉樹基本演算法
資料結構實驗報告 實驗四二叉樹儲存結構的應用 實驗內容 二叉樹各種演算法的實現 專業班級 網路工程專業 1002班 組長 賈鑫 2010100234 組員 賈鵬飛 2010100237 鄧桐桐 2010100229 2012年 4月 27日 實驗報告 實驗型別 綜合實驗室 軟體實驗室二一 實驗名稱 ...