第6章習題(帶答案)

《第6章習題(帶答案)》由會員分享，可在線閱讀，更多相關《第6章習題(帶答案)（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1.在一棵具有5層的滿二叉樹中結點總數(shù)為 ( )。 A. 31 B. 32 C. 33 D. 16 2.深度為d的二叉樹中第k（k≤d）層最多有 2k-1 個結點，最少有 1 個結點。 3.若一棵二叉樹中某結點的度為1，則該結點僅有一棵子樹。（ 對 ） 4.一個具有1025個結點的二叉樹的高h為（ ） A．11 B．10 C．11至1025之間 D．10至1024之間 5.一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是（ ） A． 250 B． 500 C．254 D．505 E．以上答案都不對 6.將一棵有80個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號是1，則編號為30的結點的左孩子編號為 60 ，雙親編號為 15 。 7.在一個非空二叉樹的中根遍歷序列中，根結點的右邊 ( ) A)只有左子樹上的所有結點 B) 只有左子樹上的部分結點 C)只有右子樹上的所有結點 D) 只有右子樹上的部分結點 8.在一棵二叉樹中，第5層上的結點數(shù)最多為 ( )。 A） 8 B）15 C）16 D）32 9.一棵深度為h的完全二叉樹的結點總數(shù)的最小值為( 2h-1 )，從左到右次序給結點編號(從1開始)則編號最小的葉子結點的編號是( 2h-2 +1 )，最大值為( 2h-1 )。 10.在深度為5的完全二叉樹中，度為2的結點數(shù)最多為( 15 )個。 已知一顆完全二叉樹的第6層(設根為第1層)有8個葉結點，則該完全二叉樹的結點個數(shù)最少是( )。 A.39 B.52 C.111 D.119 11.某二叉樹中度為2的結點有12個，則該二叉樹中有( 13 )個葉子結點。 已知二叉樹有50個葉子結點，則此二叉樹至少有 99 個結點。 12. 3個結點可構成 2 棵不同形狀的樹， 5 棵不同形狀的二叉樹。 13.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉中包含的結點數(shù)至少為 。 A. h +1 B. 2h C.2h-1 D. 2h+1 14.一棵二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹． A．空或只有一個結點 B．高度等于其結點數(shù) C．任一結點無左孩子 D．任一結點無右孩子 15.下列關于樹的說法中正確的是 。 A.可有任意多個孩子、任意多個雙親 B.可有一個孩子、任意多個雙親 C.可有任意多個孩子、只有一個雙親 D.只有一個孩子、一個雙親 16.若某二叉樹的中序序列和后序序列相同，則該二叉樹一定滿足( )。 A. 該二叉樹為空 B. 其中任意一個結點均無左子樹 C. 只有根結點 D. 其中任意一個結點均無右子樹 17.在有n個結點的二叉鏈表中，空指針域有 n+1 個，利用這些空指針域，存放某種遍歷序列中直接前驅或直接后繼的指針，這種附加的指針稱為 線索 。 18.若已知某二叉樹的先序和后序序列相同，則該二叉樹一定滿足( )。 A. 其中任意一個結點均無左子樹 B. 其中任意一個結點均無右子樹 C. 只有根結點 D. 該二叉樹為空 19.已知完全二叉樹的第6層有5個結點，則其葉子結點數(shù)是 18 。 20.樹的后根遍歷序列等同于該樹對應的二叉樹的（ ）。 A、先序遍歷 B、中序遍歷 C、后序遍歷 D、層次遍歷 21.已知二叉樹先根遍歷的序列為“CDHAFEGB”, 中根遍歷的序列為“HDFAECBG”, 則后根遍歷的序列為 ___HFEADBGC 。 22.若一棵滿二叉樹深度為h, 葉子數(shù)為m, 結點數(shù)為n, 則_____。 A) n = h + m B) h + m = 2n C) m = h - 1 D) n = 2h - 1 23.樹可以轉換成二叉樹, 下面關于樹和對應的二叉樹的說法, _____是正確的。 A) 樹的先根遍歷序列與對應的二叉樹的先根遍歷序列相同 B) 樹的先根遍歷序列與對應的二叉樹的中根遍歷序列相同 C) 樹的后根遍歷序列與對應的二叉樹的先根遍歷序列相同 D) 樹的后根遍歷序列與對應的二叉樹的后根遍歷序列相同 24.n個葉子結點的哈夫曼樹, 結點總數(shù)為_____。 A) 不確定 B) 2n - 1 C) 2n D) 2n + 1 25.在線索二叉樹中, 判斷指針p所指結點沒有左子樹的條件是_____。 A) p->lch == NULL B) p->ltag == 1 C) p->lch == NULL＆＆ p->ltag == 1 D) 以上都不對 26.下圖所示表達式二叉樹的后綴表示式為_____。 A) a * b + c - d / e B) + * a b / - c d e C) a b * c d - e / + D) a b * + c d - e / + * a b / c d e - 26.下面關于樹和二叉樹的說法中, _____是正確的。 A) 度為m的樹第i層至多有mi - 1個結點 B) 二叉樹只能采用鏈式存儲結構 C) 二叉樹就是度為2的樹 D) 度為2的樹轉換為二叉樹后, 形態(tài)完全一樣 27.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系( ) A．不一定相同 B．都相同 C．都不相同 D．互為逆序