第五章樹(答案)
一、選擇題
1、二叉樹的第i層最多有（ ）個結點。
a．2i b. 2ic. 2i-1d.2i-1
2.對於一棵滿二叉樹，高度為h，共有n個結點，其中有m個葉子結點，則（ ）
a．n=h+m b.h+m=2n c.m=h-1d.n=2h -1
3.在一棵二叉樹中，共有16個度為2的結點，則其共有個葉子結點。
a．15 b.16c.17 d.18
4. 一棵完全二叉樹中根結點的編號為1，而且編號為23的結點有左孩子但沒有右孩子，則此樹中共有（ ）個結點。
a．24 b.45 c.46d.47
5.下述編碼那一組不是字首碼
a．00,01,10,11b.0,1,00,11 c.0,10,110,111d.1,01,001,000
6.某二叉樹的中序序列和後序序列相同，則這棵二叉樹必然是（ ）
a．空樹
b．空樹或任一結點均無左孩子的非空二叉樹
c．空樹或任一結點均無右孩子的非空二叉樹
d．空樹或僅有乙個結點的二叉樹
7.設n,m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是（ ）
a．n在m的右邊b.n是m的祖先
c．n在m的左邊d.n是m的子孫
8、假定中根遍歷二叉樹的定義如下：若二叉樹為非空二叉樹，則中根遍歷根的右子樹；訪問根結點；中根遍歷根的左子樹。按此定義遍歷下圖所示的二叉樹，遍歷的結果為：
a、 dbeafhgca
b、 cghfadbebc
c、 ebdafhgce d f
d、 fhgcadbeg
h9、文中出現的字母為a、b、c、d和e，每個字母在電文中出現的次數分別為9、27、3、5和11。按哈夫曼編碼（構造時左小右大），則字母c的編碼應是：
a、10 b、0110 c、1110 d、1100
10、設樹t的度為4，其中度為1，2，3和4的結點個數分別為4，2，1，1 則t中的葉子數為（ ）
a．5b．6c．7d．8
11．算術表示式a+b*（c+d/e）轉為字尾表示式後為（ ）
a．ab+cde/* b．abcdec．abcde/*++ d．abcde*/++
12. 設有一表示算術表示式的二叉樹（見下圖），
它所表示的算術表示式是（ ）
a. a*b+c/(d*e)+(f-g) b. (a*b+c)/(d*e)+(f-g)
c. (a*b+c)/(d*e+（f-g）) d. a*b+c/d*e+f-g
13．已知一算術表示式的中綴形式為 a+b*c-d/e，字尾形式為abc*+de/-，其字首形式為( )
a．-a+b*c/de b. -a+b*cd/e c．-+*abc/ded. -+a*bc/de
14．若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（ ）
a．9b．11 c．15 d．不確定
15．樹的後根遍歷序列等同於該樹對應的二叉樹的( ).
a. 先序序列b. 中序序列c. 後序序列
16．已知一棵二叉樹的前序遍歷結果為abcdef,中序遍歷結果為cbaedf,則後序遍歷的結果為（ ）。
a．cbefda b． fedcba c． cbedfa d．不定
17．引入二叉線索樹的目的是（ ）
a．加快查詢結點的前驅或後繼的速度 b．為了能在二叉樹中方便的進行插入與刪除
c．為了能方便的找到雙親 d．使二叉樹的遍歷結果唯一
18．下面幾個符號串編碼集合中，不是字首編碼的是（ ）。
a．c． d．
二、填空題
1.高度為h的完全二叉樹至少有2h-1個結點，至多有2h -1個結點。
2.對下圖的二叉樹進行遍歷，其先序序列為abdcegf,中序序列為dbaegcf,後序序列為dbgefca
3．已知一棵完全二叉樹的第7層有10個葉子結點，則整個二叉樹的結點最多是235個。
4.一棵完全二叉樹共有1001個結點，其中葉子結點的個數是501 .
5．中綴式a+b*3+4*（c-d）對應的字首式為__++a*b3*4-cd_，若a=1，b=2，c=3，d=4，則字尾式db/cc*a-b*+的運算結果為_18__。
6.假設一棵二叉樹的中序遍歷序列為dcbgeahfijk和後序序列為dcegbfhkjia。請畫出該樹。
7．將下列由三棵樹組成的森林轉換為二叉樹。（只要求給出轉換結果）
8．設一棵二叉樹的先序、中序遍歷序列分別為
先序遍歷序列： a b d f c e g h 中序遍歷序列： b f d a g e h c
（1）畫出這棵二叉樹。
（2）畫出這棵二叉樹的後序線索樹
（3）將這棵二叉樹轉換成對應的樹（或森林）。
9.設通訊中出現5中字元a、b、c、d、e對應的頻率為0.2,0.1,0.5,0.15,0.25構造哈夫曼樹，並給出對應字元的編碼。
10.下列演算法是輸出一棵二叉樹的第i層（根結點為第一層）上的所有結點的值。
tpedef struct nodebitnode;
void level(bitnode *t,int i)
level( t->lchild,i-1);
level(t->rchild,i-1);}
資料結構習題第五章
5.1 選擇題 1 一維陣列和線性表的區別是 a a 前者長度固定，後者長度可變 b 後者長度固定，前者長度可變 c 兩者長度均固定d 兩者長度均可變 2 設w為乙個二維陣列，其每個資料元素wij 占用6個位元組，行下標i從0到8，列下標j從2到5，則二維陣列w的資料元素共占用 c 個位元組。a 4...
資料結構作業系統第五章答案
k n else if a.data k i else if k a.tu while n b.tu else while k a.tu c.mu a.mu c.nu a.nu c.tu p 1 return true 5.23 三元組表的一種變型是，從三元組表中去掉 行下標域得到二元組表，另設乙個...
第五章GIS的資料表達與資料結構
1 地理現象及其認識的抽象過程 無論現實世界如何複雜，人們在對其認識和抽象表達時，總是把它們分成幾種基本的幾何型別，並賦予它們不同的屬性和編碼。然後在根據一定的資料結構和資料庫模型對其進行表達 組織和儲存。2 幾何型別與地理現象的對應關係 呈點狀分布的地理現象 點狀幾何型別 呈線狀分布的地理現象 線...