學號 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)一棵二叉樹的度可以小於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開始進行編號，要求每個結點的編號大於其左右孩子的編號，同一結點的左右孩子中，其左孩子的編號小於其右孩子的編號，可採用 a 遍歷實現編號。
(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子孫
13．實現對任意二叉樹的後序遍歷的非遞迴演算法而不使用棧結構，最佳方案是二叉樹採用 c 儲存結構。
(a) 二叉鍊錶 (b) 廣義表 (c)三叉鍊錶 (d)順序
14. 一棵樹可轉換成為與其對應的二叉樹，則下面敘述正確的是 a 。
(a) 樹的先根遍歷序列與其對應的二叉樹的先序遍歷相同
(b) 樹的後根遍歷序列與其對應的二叉樹的後序遍歷相同
(c) 樹的先根遍歷序列與其對應的二叉樹的中序遍歷相同
(d) 以上都不對
二、填空題
1．對一棵具有n個結點的二叉樹，當它為一棵完全二叉樹時具有最小高度；當它為單分支二叉樹時，具有最大高度。
2．在二叉樹的第i（i≥1）層上至多有 2^(i-1) 個結點，深度為k（k≥1）的完全二叉樹至多 2^(k)-1 個結點，最少 2^(k-1) 個結點；
3．如果二叉樹的終端結點數為n0，度為2的結點數為n2，則n0 = n2+1
4．已知一棵二叉樹的中序序列是cbedahgijf，後序序列是cedbhjigfa，則該二叉樹的先序序列是 abcdefghij ，該二叉樹的深度為 5 。
5．若一棵二叉樹的中序遍歷結果為abc，則該二叉樹有 3 中不同的形態。
6．在順序儲存的二叉樹中，下標為i和j的兩個結點處在同一層的條件是 log(2)i=log(2)j 。
7．已知完全二叉樹的第7層有8個結點，則其葉子結點數為 36 個。總結點數為 71 個。
8．在對二叉樹進行非遞迴中序遍歷過程中，需要用棧來暫存所訪問結點的位址；進行層序遍歷過程中，需要用佇列來暫存所訪問結點的位址；
9．高度為h，度為k的樹中至少有 h+k-1 個結點，至多有 k^(h)-1 個結點。
10．一維陣列存放完全二叉樹：abcdefghi，則後序遍歷該二叉樹的序列為 hidebfgca
三、應用題
1. 應用題：說明分別滿足下列條件的二叉樹各是什麼？
⑴先序遍歷和中序遍歷相同； 空樹，只有乙個跟節點或右單分支二叉樹。
⑵中序遍歷和後序遍歷相同； 空樹，只有乙個根節點或左單分支二叉樹。
⑶先序遍歷和後序遍歷相同； 空樹，只有乙個根節點的二叉樹。
2. 已知一棵二叉樹的中序序列是cbedahgijf，後序序列是cedbhjigfa，畫出這棵二叉樹的邏輯結構圖。
af bg
c dh i
ej3.一棵二叉樹的先序、中序、後序序列如下，其中一部分未標出，試構造出該二叉樹。
先序序列： a b c d e f g h i j k
中序序列：c b e d f a h j k i g
後序序列： c e f d b k j i h g a
4.有n個結點的二叉樹，已知葉子結點個數為n0,回答下列問題：
(1)寫出求度為1的結點的個數n1的計算公式；
(2)若此樹是深度為k的完全二叉樹，寫出n為最小的公式；
(3)若二叉樹中僅有度為0和度為2的結點，寫出求該二叉樹結點個數n的公式；
（1） n1=n+1-2n0
（2） n（min）=2^(k-1)
(3) n=2n0-1
四、演算法設計題
1．編寫求二叉樹bt中結點總數的演算法。
int btreecount(btreenode *bt) //二叉樹中結點的總數
2．編寫求二叉樹bt中葉子結點數的演算法。
int btreecount(btreenode *bt) //二叉樹中結點的總數
3．若已知兩棵二叉樹bt1和bt2皆為空，或者皆不為空且bt1的左、右子樹和bt2的左、右子樹分別相似，則稱二叉樹bt1和bt2相似。編寫演算法，判別給定的兩棵二叉樹是否相似。
int btreesim(btreenode *bt1,btreenode *bt1)
4．編寫演算法，求二叉樹中以元素值為x的結點為根的子樹的深度。
int btreesim(btreenode *bt , elemtype x)
int depthbtree(btreenode *bt) //求二叉樹bt的深度
}5．編寫演算法，計算二叉樹中度為1的結點數和度為2的結點數。
int s1=0,s2=0;
void btreebranch(btreenode *bt)
{if(bt!=null){
if(bt->lchild!=null){
if(bt->rchild!=null) s2++;
else s1 ++;
btreebranch(bt->lchild);
資料結構試驗 二叉樹
實驗報告名稱 姓名學號專業班級 日期實驗6 二叉樹的建立及遍歷 一 實驗目的 1 學會實現二叉樹結點結構和對二叉樹的基本操作。2 掌握對二叉樹每種操作的具體實現，學會利用遞迴方法編寫對二叉樹這種遞迴資料結構進行處理的演算法。二 實驗要求 1 認真閱讀和掌握和本實驗相關的教材內容。2 編寫完整程式完成...
資料結構二叉樹基本演算法
資料結構實驗報告 實驗四二叉樹儲存結構的應用 實驗內容 二叉樹各種演算法的實現 專業班級 網路工程專業 1002班 組長 賈鑫 2010100234 組員 賈鵬飛 2010100237 鄧桐桐 2010100229 2012年 4月 27日 實驗報告 實驗型別 綜合實驗室 軟體實驗室二一 實驗名稱 ...
資料結構基礎練習第5章二叉樹
學號姓名班級 一 選擇題 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 至少有乙個...