文档库

最新最全的文档下载
当前位置:文档库 > 树

树和二叉树

一、选择题

1.已知一算术表达式的中缀形式为 A+B*C- D/E,后缀形式为ABC*+DE/-,其前缀形式为

( D )

A.-A+B*C/DE B. -A+B*CD/E C.-+*ABC/DE D. -+A*BC/DE

4. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子

数为( D )

A.5 B.6 C.7 D.8

5. 在下述结论中,正确的是( D )

①只有一个结点的二叉树的度为0; ②二叉树的度为2;③二叉树的左右子树可任意

交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③ B.②③④ C.②④ D.①④

8.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( B )A.9 B.11 C.15 D.不确定

10.设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林

F对应的二叉树根结点的右子树上的结点个数是( D )。

A.M1 B.M1+M2 C.M3 D.M2+M3

11.具有10个叶结点的二叉树中有( B )个度为2的结点,

A.8 B.9 C.10 D.ll

12.一棵完全二叉树上有1001个结点,其中叶子结点的个数是( E)

A. 250 B. 500 C.254 D.505 E.以上答案都不对

13. 设给定权值总数有n 个,其哈夫曼树的结点总数为( D )

A.不确定 B.2n C.2n+1 D.2n-1

16. 有关二叉树下列说法正确的是( B )

A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2

17.二叉树的第I层上最多含有结点数为( C )

A.2I B. 2I-1-1 C. 2I-1 D.2I -1

18. 一个具有1025个结点的二叉树的高h为(C)

A.11 B.10 C.11至1025之间 D.10至1024之间

19.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( B )结点A.2h B.2h-1 C.2h+1 D.h+1

20.对于有n 个结点的二叉树, 其高度为( D )

A.nlog

2n B.log

2

n C.?log

2

n?|+1 D.不确定

21. 一棵具有 n个结点的完全二叉树的树高度(深度)是( A )

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

22.深度为h的满m叉树的第k层有( A )个结点。(1=

A.m k-1 B.m k-1 C.m h-1 D.m h-1

23.在一棵高度为k的满二叉树中,结点总数为( C )

A.2k-1 B.2k C.2k-1 D.?log2k?+1

28.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,

同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用( C )次序的遍历实现编号。

A.先序 B. 中序 C. 后序 D. 从根开始按层次遍历31.在下列存储形式中,哪一个不是树的存储形式?( D )

A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法

32.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是( B )A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 33.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( A )。

A.CBEFDA B. FEDCBA C. CBEDFA D.不定

36. 上题的二叉树对应的森林包括多少棵树(B)

A.l B.2 C.3 D.概念上是错误的

37.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历: HFIEJKG 。该二叉树根的右子树的根是: C

A、 E

B、 F

C、 G

D、 H

41.对于前序遍历与中序遍历结果相同的二叉树为(1F);

对于前序遍历和后序遍历结果相同的二叉树为(2B)。

A.一般二叉树 B.只有根结点的二叉树 C.根结点无左孩子的二叉树

D.根结点无右孩子的二叉树 E.所有结点只有左子数的二叉树 F.所有结点只有右子树的二叉树

42.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( C )

A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树

44.某二叉树的前序序列和后序序列正好相反,则该二叉树一定是(C)的二叉树。

A.空或只有一个结点 B.任一结点无左子树 C.高度等于其结点数 D.任一结点无右子树

45.在完全二叉树中,若一个结点是叶结点,则它没(C)。

A.左子结点 B.右子结点 C.左子结点和右子结点 D.左子结点,右子结点和兄弟结点

50. 引入二叉线索树的目的是( A )

A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲 D.使二叉树的遍历结果唯一

52.n个结点的线索二叉树上含有的线索数为( C)

A.2n B.n-l C.n+l D.n 【中山大学 1998 二、8 (2分)】

二、填空题

1.二叉树由_(1)根节点__,__(2)左子树_,_(3)右子树__三个基本单元组成。

2.树在计算机内的表示方式有_(1)双亲链表表示法__,_(2)孩子链表表示法_,_(3)孩子兄弟表示法_。

3.在二叉树中,指针p所指结点为叶子结点的条件是__p->lchild==null&&p->rchild==null____。

5.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的__平衡因子__。

6.具有256个结点的完全二叉树的深度为___9___。

7.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树有____12__个叶子结点。

8.深度为k的完全二叉树至少有___(1)__ 2k-1__个结点,至多有___(2) 2k-1____个结点。

11.在完全二叉树中,编号为i和j的两个结点处于同一层的条件是__?log

2i?=?log

2

j?_。

13.假设根结点的层数为1,具有n个结点的二叉树的最大高度是__n____。

17.高度为K的完全二叉树至少有___2k-2 ___个叶子结点

19.已知二叉树有50个叶子结点,则该二叉树的总结点数至少是___99___。

20.一个有2001个结点的完全二叉树的高度为__11____。

22.一个深度为k的,具有最少结点数的完全二叉树按层次,(同层次从左到右)用自然数依此对结点编号,则编号最小的叶子的序号是__(1) 2k-2+1_;编号是i的结点所在的层次号是_(2) ?log

2

i?+1 (根所在的层次号规定为1层)。

24.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是___4___。

25.高度为h的2-3树中叶子结点的数目至多为__3h-1____。

26.完全二叉树中,结点个数为n,则编号最大的分支结点的编号为______。

28.对于一个具有n个结点的二元树,当它为一棵_(1)完全二叉树_二元树时具有最小高度,当它为一棵_(2)除叶子结点外只有左子树或右子树_时,具有最大高度。

29.具有N个结点的二叉树,采用二叉链表存储,共有___n+1__个空链域。

30.8层完全二叉树至少有____128__个结点,拥有100个结点的完全二叉树的最大层数为____7__。

34.每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH,对称序列是FEBGCHD,则它的后序序列是_(1)_FEGHDCB_。

36.二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1) _EACBDGF_,则该二叉树对应的树林包括_(2)2__棵树。

50.线索二元树的左线索指向其___前驱___,右线索指向其__后继____。

一、选择题

树

12. 由二叉树结点的公式:n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1,因为n=1001,所以1002=2n0+n1,在完全二叉树树中,n1只能取0或1,在本题中只能取0,故n=501,因此选E。

42.前序序列是“根左右”,后序序列是“左右根”,若要这两个序列相反,只有单支树,所

以本题的A和B均对,单支树的特点是只有一个叶子结点,故C是最合适的,选C。A或B 都不全。由本题可解答44题。

47. 左子树为空的二叉树的根结点的左线索为空(无前驱),先序序列的最后结点的右线索为空(无后继),共2个空链域。

52.线索二叉树是利用二叉树的空链域加上线索,n个结点的二叉树有n+1个空链域。

二.填空题

1.(1)根结点(2)左子树(3)右子树

2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法

3.p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡因子

6. 9

7. 12

8.(1)2k-1(2)2k-1

9.(1)2H-1(2)2H-1 (3)H=?log

2

N?+1

10. 用顺序存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条

件是?log

2s?=?log

2

t?。

11. ?log

2i?=?log

2

j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log

2

n?+1

13.n

14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64

19. 99 20. 11 21.(1) n1-1 (2)n2+n3

22.(1)2k-2+1(第k层1个结点,总结点个数是2H-1,其双亲是2H-1/2=2k-2)(2) ?log

2

i?+1

23.69

24. 4 25.3h-1 26. ?n/2? 27. ?log

2

k?+1

28.(1)完全二叉树 (2)单枝树,树中任一结点(除最后一个结点是叶子外),只有左子女或

只有右子女。

29.N+1 30.(1) 128(第七层满,加第八层1个) (2) 7

31. 0至多个。任意二叉树,度为1的结点个数没限制。只有完全二叉树,度为1的结点个

数才至多为1。

32.21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1

34.(1) FEGHDCB (2)BEF(该二叉树转换成森林,含三棵树,其第一棵树的先根次序是

BEF)

35.(1)先序(2)中序 36. (1)EACBDGF (2)2 37.任何结点至多只有右子女

的二叉树。

38.(1)a (2) dbe (3) hfcg 39.(1) .D.G.B.A.E.H.C.F. (2) ...GD.B...HE..FCA

40.DGEBFCA 41.(1)5 (2)略 42.二叉排序树 43.二叉树 44.

前序

45.(1)先根次序(2)中根次序46.双亲的右子树中最左下的叶子结点47.2

48.(n+1)/2

49.31(x的后继是经x的双亲y的右子树中最左下的叶结点) 50.(1)前驱 (2)后