數(shù)據(jù)結(jié)構(gòu)1800例題與答案之樹和二叉樹

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)1800例題與答案之樹和二叉樹第六章樹和二叉樹

一、選擇題

1．已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()

A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE

2．算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為（）

A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++/3.設(shè)有一表示算術(shù)表達式的二叉樹（見下圖），

++它所表示的算術(shù)表達式是（）*-*CA.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)BDEFGAC.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G

則T中的葉子，14.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1

數(shù)為（）

A．5B．6C．7D．85.在下述結(jié)論中，正確的是（）

①只有一個結(jié)點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;

④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度一致的滿二叉樹。A．①②③B．②③④C．②④D．①④6.設(shè)森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（）

A．m-nB．m-n-1C．n+1D．條件不足，無法確定

7.樹是結(jié)點的有限集合，它（(1）)根結(jié)點，記為T。其余結(jié)點分成為m（m>0）個(（2）)的集合T1，T2，?，Ｔm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1≤i≤m）。一個結(jié)點的子結(jié)點個數(shù)稱為該結(jié)點的(（3）)。二叉樹與樹是兩個不同的概念，二叉樹也是結(jié)點的有限集合，它(（4）)根結(jié)點。可以把樹的根結(jié)點的層數(shù)定義為1，其他結(jié)點的層數(shù)等于其父結(jié)點所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結(jié)點數(shù)小于2的結(jié)點中的任意兩個，它們所在的層數(shù)分別為λKi和λKj，當關(guān)系式│λKi-λKj│≤1一定成立時，則稱T為一棵（(5)）。供選擇的答案：

（1）(4)A.有0個或1個B.有0個或多個C.有且只有一個D.有1個或1個以上

（2）A.互不相交B.允許相交C.允許葉結(jié)點相交D.允許樹枝結(jié)點相交（3）A.權(quán)B.維數(shù)C.次數(shù)D.序（5）A.飽滿樹B.查找樹C.平衡樹D.完全樹

8．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（）

A．9B．11C．15D．不確定

9．在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2

個，則度為0的結(jié)點數(shù)為（）個

A．4B．5C．6D．7

10．設(shè)森林F中有三棵樹，第一，其次，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）。

A．M1B．M1+M2C．M3D．M2+M311．具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點，

A．8B．9C．10D．ll12．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）

A．250B．500C．254D．505E．以上答案都不對

13.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為()

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

A．不確定B．2nC．2n+1D．2n-1

15．若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（）。

A．n-1B．?n/m?-1C．?(n-1)/(m-1)?D．?n/(m-1)?-1E．?(n+1)/(m+1)?-1

16.有關(guān)二叉樹以下說法正確的是（）

A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為217．二叉樹的第I層上最多含有結(jié)點數(shù)為（）

II-1I-1I

A．2B．2-1C．2D．2-118.一個具有1025個結(jié)點的二叉樹的高h為（）

A．11B．10C．11至1025之間D．10至1024之間

19．一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有()結(jié)點

A．2hB．2h-1C．2h+1D．h+1

20．對于有n個結(jié)點的二叉樹,其高度為（）

A．nlog2nB．log2nC．?log2n?|+1D．不確定21.一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是（）

A．?logn?+1B．logn+1C．?logn?D．logn-1

22．深度為h的滿m叉樹的第k層有（）個結(jié)點。(1=<k=<h)

k-1kh-1h

A．mB．m-1C．mD．m-123．在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（）

k-1kkk

A．2B．2C．2-1D．?log2?+124．高度為K的二叉樹最大的結(jié)點數(shù)為（）。

A．2B．2C．2-1D．2-125.一棵樹高為K的完全二叉樹至少有（）個結(jié)點

kk-1k-1k

A．2–1B.2–1C.2D.2

26.將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度（）

A．4B．5C．6D．7

27.利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）。

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

A．先序B.中序C.后序D.從根開始按層次遍歷29．樹的后根遍歷序列等同于該樹對應的二叉樹的().

A.先序序列B.中序序列C.后序序列30．若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用()遍歷方法最適合。

A．前序B．中序C．后序D．按層次31．在以下存儲形式中，哪一個不是樹的存儲形式？（）

A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲表示法32．一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）

A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG33．已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。

A．CBEFDAB．FEDCBAC．CBEDFAD．不定

34．已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷是（）。

A．a(chǎn)cbedB．decabC．deabcD．cedba

35.某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：

A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對

36.上題的二叉樹對應的森林包括多少棵樹（）

A．lB．2C．3D．概念上是錯誤的

37．二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：

A、EB、FC、GD、H

38．將一棵樹t轉(zhuǎn)換為孩子—兄弟鏈表表示的二叉樹h，則t的后根序遍歷是h的

A．前序遍歷B．中序遍歷C．后序遍歷（）

39.某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號為1，2，?，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最我號減1，而V的右子樹的結(jié)點中，其最我號等于V左子樹上結(jié)點的最大編號加1。這時是按()編號的。

A.中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次順序

40．下面的說法中正確的是（）.

（1）任何一棵二叉樹的葉子結(jié)點在三種遍歷中的相對次序不變；（2）按二叉樹定義，具有三個結(jié)點的二叉樹共有6種。

A．(1)(2)B．(1)C．(2)D．(1)、(2)都錯

41．對于前序遍歷與中序遍歷結(jié)果一致的二叉樹為（1）;

對于前序遍歷和后序遍歷結(jié)果一致的二叉樹為（2）。

A．一般二叉樹B．只有根結(jié)點的二叉樹C．根結(jié)點無左孩子的二叉樹

D．根結(jié)點無右孩子的二叉樹E．所有結(jié)點只有左子數(shù)的二叉樹F．所有結(jié)點只有右子樹的二叉樹

42．一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）

A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹

43．在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（）

A．都不一致B．完全一致C．先序和中序一致，而與后序不同

D．中序和后序一致，而與先序不同44．某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。

A．空或只有一個結(jié)點B．任一結(jié)點無左子樹C．高度等于其結(jié)點數(shù)D．任一結(jié)點無右子樹

45．在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（）。

A．左子結(jié)點B．右子結(jié)點C．左子結(jié)點和右子結(jié)點D．左子結(jié)點，右子結(jié)點和兄弟結(jié)點

46．在以下狀況中，可稱為二叉樹的是（）

A．每個結(jié)點至多有兩棵子樹的樹B.哈夫曼樹C．每個結(jié)點至多有兩棵子樹的有序樹

D.每個結(jié)點只有一棵右子樹E．以上答案都不對

47.一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：()

A．不確定B.0C.1D.248.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：()。

A.0B.1C.2D.不確定

49.若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為()

A.X的雙親B.X的右子樹中最左的結(jié)點C.X的左子樹中最右結(jié)點D.X的左子樹中最右葉結(jié)點

50.引入二叉線索樹的目的是（）

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

51.線索二叉樹是一種（）結(jié)構(gòu)。

A．規(guī)律B．規(guī)律和存儲C．物理D．線性

52．n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）

A．2nB．n－lC．n＋lD．n53．（）的遍歷仍需要棧的支持.

A．前序線索樹B．中序線索樹C．后序線索樹

54．二叉樹在線索后，仍不能有效求解的問題是（）。

A．前（先）序線索二叉樹中求前（先）序后繼B．中序線索二叉樹中求中序后繼C．中序