單選題1

在下述結(jié)論中,正確的是( ??)①只有一個結(jié)點的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。
A. ①②③
B. ②③④
C. ②④
D. ①④

正確答案：D

思路：

（1）度的概念：

結(jié)點的度: 結(jié)點擁有的子樹數(shù)稱為結(jié)點的度。

樹的度: 樹的度是樹內(nèi)各結(jié)點度的最大值。

（2）完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號叢1至n的結(jié)點一一對應時，稱之為完全二叉樹。

單選題2

有關二叉樹下列說法正確的是( ??)
A. 二叉樹的度為2
B. 一棵二叉樹的度可以小于2
C. 二叉樹中至少有一個結(jié)點的度為2
D. 二叉樹中任何一個結(jié)點的度都為2

正確答案：B

思路：

單選題3

在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒有( ??)。
A. 左子結(jié)點
B. 右子結(jié)點
C. 左子結(jié)點和右子結(jié)點
D. 左子結(jié)點,右子結(jié)點和兄弟結(jié)點

正確答案：C

思路：

葉結(jié)點:度為0的結(jié)點稱為葉子或終端結(jié)點。

單選題4

由3個結(jié)點可以構(gòu)造出( ??)種不同形態(tài)的二叉樹。
A. 2
B. 3
C. 4
D. 5

正確答案：D

多選題5

二叉樹由( ???)三個基本單元組成。(多選題）
A. 左子樹
B. 右子樹
C. 根結(jié)點

正確答案：A;B;C

單選題6

對于一個具有n個結(jié)點的二元樹，當它為一棵完全二元樹時具有最小高度，當它為一棵單支樹時具有最大高度。( ??)
A. 正確
B. 錯誤

正確答案：A

單選題7

假設根結(jié)點的層數(shù)為1，具有n個結(jié)點的二叉樹的最大高度是( ??)。
A. n
B. n+1
C. n-1
D. 未知

正確答案：A

思路：

每層只有一個結(jié)點。

單選題8

一個具有1025個結(jié)點的二叉樹的高h為( ??)
A. 11
B. 10
C. 11至1025之間
D. 10至1024之間

正確答案：C

思路：

樹最低時：如果當前二叉樹是完全二叉樹，則樹高= ?+1 = 11

樹最高時：如果當前二叉樹的每層只有一個結(jié)點，則樹高=結(jié)點數(shù)= 1025

單選題9

對于有n個結(jié)點的二叉樹, ?其高度為( ????)
A. nlog2n
B. log2n
C. 向下取整(log2n)+1
D. 不確定

正確答案：D

單選題10

一棵二叉樹高度為h（h>0），所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有( ??)結(jié)點
A. 2h
B. 2h-1
C. 2h+1
D. h+1

正確答案：B

思路：

方法1：特殊值法

假設當前樹只有一個根結(jié)點，則它滿足所有結(jié)點的度或為0或為2：此時高度h=1且結(jié)點數(shù)為1，則四個選項：A. 2 ×；B. 1 √；C. 3 ×；D.2 ×；所以答案選B。

方法2：滿足題意的樹的結(jié)構(gòu)應為：

則第一層有1個結(jié)點，剩下的從第二層到第h層，共h-1層都有兩個結(jié)點，所以一共有1+2×(h-1)= 2h-1，所以答案選B。

單選題11

深度為h的滿m叉樹的第k層有( ??)個結(jié)點。(1<=k<=h)
A. m^(k-1)
B. (m^k)-1
C. (m^h)-1
D. m^(h-1)

正確答案：A

思路：

深度h是個迷惑信息。

單選題12

一棵樹高為K的完全二叉樹至少有( ???)個結(jié)點
A. (2^k)–1
B. (2^(k-1))–1
C. 2^(k-1)
D. 2^k

正確答案：C

思路：

單選題13

如果結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是( ??)。
A. 3
B. 4
C. 5
D. 未知

正確答案：B

思路：

B的孩子為結(jié)點A+結(jié)點A的3個兄弟，所以B一共有4個孩子，度為4。

單選題14

具有n個結(jié)點的滿二叉樹，其葉子結(jié)點的個數(shù)是( )。
A. n/2
B. (n-1)/2
C. (n+1)/2
D. 未知

正確答案：C

思路：

滿二叉樹只有度為0或者度為2的結(jié)點，且滿足n0=n2+1，又根據(jù)題意n0+n2=n, 所以n0 = (n+1)/2。

單選題15

引入二叉線索樹的目的是( ???)
A. 加快查找結(jié)點的前驅(qū)或后繼的速度
B. 為了能在二叉樹中方便的進行插入與刪除
C. 為了能方便的找到雙親
D. 使二叉樹的遍歷結(jié)果唯一

正確答案：A

思路：

當以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在任一序列中的前驅(qū)和后繼信息，這種信息只有在遍歷的動態(tài)過程中才能得到，為此引人線索二叉樹來保存這些在動態(tài)過程中得到的有關前驅(qū)和后繼的信息。

單選題16

在二叉樹中,指針p所指結(jié)點為葉子結(jié)點的條件是p->lchild==null && p->rchlid==null。( ??)
A. 正確
B. 錯誤

正確答案：A

思路：

葉子結(jié)點沒有左右孩子。

單選題17

深度為k的完全二叉樹至少有(2^(k-1))個結(jié)點,至多有((2^k)-1)個結(jié)點。( ??)
A. 正確
B. 錯誤

正確答案：A

思路：

① 至多：

② 至少：深度為k-1的滿二叉樹 + 第k層僅有一個結(jié)點?= (2^(k-1) -1)+1?= 2^(k-1)

單選題18

具有N個結(jié)點的二叉樹,采用二叉鏈表存儲，共有( ??)個空鏈域。
A. N
B. N+1
C. N-1
D. 未知

正確答案：B

思路：

注意區(qū)分，題中問的是二叉樹的二叉鏈表存儲，鏈表中每個鏈域指向的是當前結(jié)點的左右孩子；而不是樹的二叉鏈表表示法（孩子兄弟表示法），它的結(jié)點的鏈域指向的是第一個孩子結(jié)點和下一個兄弟結(jié)點。

一個度為0的結(jié)點產(chǎn)生兩個空鏈域，度為1的結(jié)點產(chǎn)生一個空鏈域。所以樹中的空鏈域個數(shù)= 2n0+n1 ①

又由N = n0+n1+n2 且n2 = n0-1，得到N= 2n0+n1-1, 即式①=N+1。所以答案選B

單選題19

設森林F中有三棵樹，第一，第二，第三棵樹總的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是( ????)。
A. M1
B. M1+M2
C. M3
D. M2+M3

正確答案：D

思路：

單選題20

設F是由T1，T2，T3三棵樹組成的森林，與F對應的二叉樹為B，已知T1，T2，T3的結(jié)點數(shù)分別為n1，n2和n3，則二叉樹B的左子樹中有n1-1個結(jié)點，右子樹中有n2+n3個結(jié)點。( ??)
A. 正確
B. 錯誤

正確答案：A

思路：

單選題21

設給定權(quán)值總數(shù)為n個，則其構(gòu)建的哈夫曼樹的結(jié)點總數(shù)為( ??)
A. 不確定
B. 2n
C. 2n+1
D. 2n-1

正確答案：D

單選題22

含有n個葉子的哈夫曼樹的結(jié)點總數(shù)為( ??)。
A. 不確定
B. 2n
C. 2n+1
D. 2n-1

正確答案：D

思路：

單選題23

下面幾個符號串的編碼集合中，不是前綴編碼的是( ??)。
A. { 0，10，110，1111 }
B. { 11，10，001，101，0001 }
C. { 00，010，0110，1000 }
D. { b，c，aa，ac，aba，abb，abc }

正確答案：B

思路：

前綴編碼無前綴。{ 11，10，001，101，0001 }

單選題24

利用二叉鏈表存儲樹，則根結(jié)點的右指針是( ??????)。
A. 指向最左孩子
B. 指向最右孩子
C. 空
D. 非空

正確答案：C

思路：

用二叉鏈表存儲樹時，結(jié)點的兩個鏈域分別指向第一個孩子結(jié)點和下一個兄弟結(jié)點。而根結(jié)點沒有兄弟結(jié)點，所以根結(jié)點的右指針指向為空。

單選題25

樹的后根遍歷序列等同于該樹對應的二叉樹的( ??)。
A. 先序序列
B. 中序序列
C. 后序序列

正確答案：B

思路：

樹的后根遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點。如下圖中，樹的后根遍歷序列為：BCDA

樹轉(zhuǎn)化成二叉樹：當前結(jié)點的孩子結(jié)點成為其左孩子，兄弟結(jié)點變成其右孩子。將下圖中樹轉(zhuǎn)為二叉樹后，對二叉樹進行中序遍歷得到的結(jié)果為：BCDA

????????????

單選題26

在下列存儲形式中，哪一個不是樹的存儲形式?( ??)
A. 雙親表示法
B. 孩子鏈表表示法
C. 孩子兄弟表示法
D. 順序存儲表示法

正確答案：D

思路：

（1）雙親表示法：

這種表示方法中，以一組連續(xù)的存儲單元存儲樹的結(jié)點，每個結(jié)點除了數(shù)據(jù)域data 外，還附設一個parent 域用以指示其雙親結(jié)點的位置。

（2）孩子表示法：

由于樹中每個結(jié)點可能有多棵子樹，則可用多重鏈表，即每個結(jié)點有多個指針域，其中每個指針指向一棵子樹的根結(jié)點。

（3）孩子兄弟法：

又稱二叉樹表示法，或二叉鏈表表示法，即以二叉鏈表做樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點，分別命名為firstchild 域和 nextsibling域。

單選題27

樹在計算機內(nèi)的表示方式有( ??)。
A. 雙親鏈表表示法
B. 孩子鏈表表示法
C. 孩子兄弟表示法
D. 以上都是

正確答案：D

思路：

（1）雙親表示法：

這種表示方法中，以一組連續(xù)的存儲單元存儲樹的結(jié)點，每個結(jié)點除了數(shù)據(jù)域data 外，還附設一個parent 域用以指示其雙親結(jié)點的位置。

（2）孩子表示法：

由于樹中每個結(jié)點可能有多棵子樹，則可用多重鏈表，即每個結(jié)點有多個指針域，其中每個指針指向一棵子樹的根結(jié)點。

（3）孩子兄弟法：

又稱二叉樹表示法，或二叉鏈表表示法，即以二叉鏈表做樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點，分別命名為firstchild 域和 nextsibling域。

單選題28

利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為二叉樹。( ??）
A. 正確
B. 錯誤

正確答案：A

思路：

① 樹的孩子兄弟法：即以二叉鏈表做樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點，分別命名為firstchild 域和 nextsibling域。

② 二叉樹的二叉鏈表表示法，鏈表中的結(jié)點的兩個鏈域分別指向該結(jié)點的左右孩子：

③ 樹轉(zhuǎn)化成二叉樹：當前結(jié)點的第一個孩子結(jié)點成為其左孩子，其兄弟結(jié)點變成其右孩子。

這種存儲結(jié)構(gòu)的優(yōu)點是便于將一般的樹結(jié)構(gòu)轉(zhuǎn)換為二叉樹進行處理，利用二叉樹的算法來實現(xiàn)對樹的操作。

單選題29

先根次序周游樹林正好等同于按先根次序遍歷對應的二叉樹；后根次序遍歷樹林正好等同于按中根次序遍歷對應的二叉樹。( ??)
A. 正確
B. 錯誤

正確答案：A

森林轉(zhuǎn)化成二叉樹：

① 先根次序周游樹林：對于森林中的每棵樹，都先訪問根結(jié)點，再以先根次序訪問其子樹。

② 先根次序遍歷二叉樹：先訪問根結(jié)點，再以先根次序訪問其左子樹和其右子樹。

③ 后根次序遍歷森林：對于森林中的每棵樹，都以后根次序訪問其子樹，再訪問其根結(jié)點。

④ 中根次序遍歷二叉樹：先以中根次序訪問左子樹，再訪問根結(jié)點，最后以中根次序訪問右子樹。

單選題30

設森林F對應的二叉樹為B，F(xiàn)有m個結(jié)點，B的根為p，p的右子樹結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點個數(shù)是( ????)
A. m-n
B. m-n-1
C. n+1
D. 條件不足，無法確定

正確答案：A

單選題31

二叉樹的第I層上最多含有結(jié)點數(shù)為( ??)
A. 2^I
B. (2^(I-1)) -1
C. 2^(I-1)
D. (2^I)-1

正確答案：C

思路：

單選題32

在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為( ????)
A. 2^(k-1)
B. 2^k
C. (2^k)-1
D. log2k+1

正確答案：C

思路：

單選題33

高度為K的二叉樹最大的結(jié)點數(shù)為( ??)。
A. 2^k
B. 2^(k-1)
C. (2^k)-1
D. (2^(k-1))-1

正確答案：C

思路：

要達到二叉樹中結(jié)點數(shù)最多，這個二叉樹就是一個滿二叉樹。

單選題34

若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是( ??)
A. 9
B. 11
C. 15
D. 不確定

正確答案：B

思路：

n0 = n2 + 1 = 10 + 1 = 11

單選題35

具有10個葉結(jié)點的二叉樹中有( ??)個度為2的結(jié)點。
A. 8
B. 9
C. 10
D. ll

正確答案：B

思路：

n2 = n0 - 1 = 10 - 1 = 9

單選題36

如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)為( ??)。
A. 69
B. 70
C. 71
D. 未知

正確答案：A

思路：

?n0=20; n1=30; n2= n0-1 = 19；所以二叉樹中總結(jié)點數(shù)=n2+n1+n0=69

單選題37

含4個度為2的結(jié)點和5個葉子結(jié)點的二叉樹，可有0至多個度為1的結(jié)點。( ??)
A. 正確
B. 錯誤

正確答案：A

思路：

單選題38

一棵完全二叉樹上有1001個結(jié)點,其中葉子結(jié)點的個數(shù)是( ????)。
A. 250
B. 500
C. 254
D. 501

正確答案：D

思路：

單選題39

一棵具有 n個結(jié)點的完全二叉樹的樹高度(深度)是(. )
A. 向下取整(logn)+1
B. 向上取整(logn)+1
C. logn
D. logn-1

正確答案：A

思路：

單選題40

具有256個結(jié)點的完全二叉樹的深度為( ??)。
A. 9
B. 8
C. 10
D. 未知

正確答案：A

思路：

單選題41

將有關二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是( ??)
A. 4
B. 5
C. 6
D. 7

正確答案：C

思路：

單選題42

一個有2001個結(jié)點的完全二叉樹的高度為( ??)。
A. 10
B. 12
C. 11
D. 未知

正確答案：C

思路：

單選題43

設有N個結(jié)點的完全二叉樹順序存放在向量A[1:N]中，其下標值最大的分支結(jié)點為(N/2)(向下取整)。( ??)
A. 正確
B. 錯誤

正確答案：A

思路：

下標值最大的葉子結(jié)點是N，這個葉子結(jié)點的父結(jié)點就是下標值最大的分支結(jié)點，序號為(N/2)(向下取整)

單選題44

當一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[l..n]中時，數(shù)組中第i個結(jié)點的左孩子為( ??)
A. A[2i] ??(2i<=n)
B. A[2i+1] ??(2i+1<=n)
C. A[i/2]
D. 無法確定

正確答案：D

思路：

舉例：

單選題45

已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有( ??)個葉子結(jié)點。
A. 10
B. 12
C. 11
D. 未知

正確答案：B

思路：

根據(jù)題意n1=2, n2=3, n3= 4;假設總結(jié)點數(shù)為n,則

n = n0+n1+n2+n3 ①

且除根結(jié)點外，其余結(jié)點都有一個分支進入，設B為分支總數(shù)，則

n=B+1 ②

由于這些分支是由度為1,2,3的結(jié)點射出的，因此又有B=n1+2n2+3n3 = 2+2*3+3*4 = 20。則根據(jù)式②：n=B+1= 21。進一步的，根據(jù)式①可得n0 = n-n1-n2-n3 = 21-2-3-4=12，即葉子結(jié)點有12個

單選題46

設樹T的度為4,其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1，則T中的葉子數(shù)為( ??)
A. 5
B. 6
C. 7
D. 8

正確答案：D

思路：

根據(jù)題意n1=4, n2=2, n3=1，n4= 1;假設總結(jié)點數(shù)為n,則

n = n0+n1+n2+n3 ①

且除根結(jié)點外，其余結(jié)點都有一個分支進入，設B為分支總數(shù)，則

n=B+1 ②

由于這些分支是由度為1,2,3,4的結(jié)點射出的，因此又有B=n1+2n2+3n3+4n4 = 4+2×2+3×1+4×1 = 15。則根據(jù)式②：n=B+1= 16。進一步的，根據(jù)式①可得n0 = n-n1-n2-n3-n5 = 16-4-2-1-1=8，即葉子結(jié)點有8個

單選題47

已知算術表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( )
A. -A+B*C/DE
B. -A+B*CD/E
C. -+*ABC/DE
D. -+A*BC/DE

正確答案：D

單選題48

對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( )次序的遍歷實現(xiàn)編號。
A. 先序
B. 中序
C. 后序
D. 從根開始按層次遍歷

正確答案：C

思路：

單選題49

已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為( ?)。
A. CBEFDA
B. FEDCBA
C. CBEDFA
D. 不定

正確答案：A

單選題50

已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac，它的前序遍歷是( ??)。
A. acbed
B. decab
C. deabc
D. cedba

正確答案：D

單選題51

下面的說法中正確的是( )。(1)任何一棵二叉樹的葉子結(jié)點在三種遍歷中的相對次序不變;(2)按二叉樹定義,具有三個結(jié)點的二叉樹的形態(tài)共有6種。
A. (1)(2)
B. (1)
C. (2)
D. (1)、(2)都錯

正確答案：B

單選題52

某二叉樹的前序序列和后序序列正好相反,則該二叉樹一定是( ?)的二叉樹。
A. 空或只有一個結(jié)點
B. 任一結(jié)點無左子樹
C. 高度等于其結(jié)點數(shù)
D. 任一結(jié)點無右子樹

正確答案：C

前序：根左右；后續(xù)：左右根

單選題53

已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg,則該二叉樹的根為a。( ）
A. 正確
B. 錯誤

正確答案：A