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

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

一、選擇題

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

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

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

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

++它所表示的算術(shù)表達(dá)式是（）*-*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è)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1

數(shù)為（）

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

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

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

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

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

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

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

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

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

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

個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)

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

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

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

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

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

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

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

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

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

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

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

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

II-1I-1I

A．2B．2-1C．2D．2-118.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（）

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

19．一棵二叉樹(shù)高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少有()結(jié)點(diǎn)

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

20．對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其高度為（）

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

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

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

k-1kh-1h

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

k-1kkk

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

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

kk-1k-1k

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

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

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

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

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

A．先序B.中序C.后序D.從根開(kāi)始按層次遍歷29．樹(shù)的后根遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的().

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

A．前序B．中序C．后序D．按層次31．在以下存儲(chǔ)形式中，哪一個(gè)不是樹(shù)的存儲(chǔ)形式？（）

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

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

A．CBEFDAB．FEDCBAC．CBEDFAD．不定

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

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

35.某二叉樹(shù)中序序列為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．上面的都不對(duì)

36.上題的二叉樹(shù)對(duì)應(yīng)的森林包括多少棵樹(shù)（）

A．lB．2C．3D．概念上是錯(cuò)誤的

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

A、EB、FC、GD、H

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

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

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

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

40．下面的說(shuō)法中正確的是（）.

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

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

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

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

A．一般二叉樹(shù)B．只有根結(jié)點(diǎn)的二叉樹(shù)C．根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)

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

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

A．所有的結(jié)點(diǎn)均無(wú)左孩子B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹(shù)

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

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

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

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

45．在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（）。

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

46．在以下?tīng)顩r中，可稱為二叉樹(shù)的是（）

A．每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù)B.哈夫曼樹(shù)C．每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù)

D.每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù)E．以上答案都不對(duì)

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

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

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

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

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

50.引入二叉線索樹(shù)的目的是（）

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

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

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

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

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

A．前序線索樹(shù)B．中序線索樹(shù)C．后序線索樹(shù)

54．二叉樹(shù)在線索后，仍不能有效求解的問(wèn)題是（）。

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