数据结构考研试题精选及答案第6章 树和二叉树答案

数据结构考研试题精选及答案

第6章 树和二叉树

部分答案解释如下。

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

个空链域。

部分答案解释如下。

6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。

19．任何结点至多只有左子树的二叉树的遍历就不需要栈。

24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1

（2i+1<=n）

37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右

孩子。

38 . 新插入的结点都是叶子结点。

42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结

点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该

结点的前驱指针指向祖先）。

44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索

和后继线索为空指针。

数据结构考研试题精选及答案

三.填空题

1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩

子兄弟表示法

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

因子

k-1kH-1H6. 9 7. 12 8.(1)2 (2)2-1 9.(1)2 (2)2-1

(3)H= log2N +1

10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结

点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条

件是 log2s = log2t 。

11. log2i = log2j 12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) log2n +1

13.n

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

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

k-2H-1H-1k-222.(1)2+1（第k层1个结点，总结点个数是2，其双亲是2/2=2）(2) log2i +1

23.69

h-124. 4 25.3 26. n/2 27. log2k +1

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

只有右子女。

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

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

数才至多为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)后

继

51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按

中序线索化)

52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261

55.(1)80 (2)001（不唯一）56.2n0-1

57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x，

则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶

子。

(1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运

算符)(4)A

(5)tempA^.Lchild (6)tempA=NULL (7)q^.Rchild (8)q (9)tempA^.Rchild

数据结构考研试题精选及答案

(10)tempA^.Item<r^.Item

58.(1) IF t=NIL THEN num:=0 ELSE num:=num(t^.l)+num(t^.r)+1

(2) IF (t=NIL) AND (m≤n) OR (t<>NIL) AND (m>n) THEN all:=false

ELSE BEGIN chk(t^.l,2*m);chk (t^.r,2*m+1);END

59. (1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild)

(5)ADDQ(Q,p->rchild)

60.(1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild)

(5)count(t->rchild)

61.(1)p (2)0 (3)height(p->lchild) (4)0 (5)height(p->rchild) (6)lh+1

(7)rh+1 (8)0

62.(1)p<>NIL (2)addx(p) (3)addx(tree) (4)r^.rchild

63.(1)stack[tp]=t (2) p=stack[tp--] (3)p

(4)++tp

64.① 本算法将二叉树的左右子树交换

② (1)new (s) //初始化，申请结点 (2) s^.next=NIL //s是带头结点的

链栈

(3)s^.next^.data //取栈顶元素 (4)s^.next:= p^.next //栈顶指针下移

(5)dispose(p) //回收空间 (6)p^.next:=s^.next //将新结点入链

栈

(7)push(s,p^.rchild) //先沿树的左分支向下，将p的右子女入栈保存

(8)NOT empty(s) (9) finishe:=true //已完成 (10)finish=true （或

s^.next=NIL）

65.(1)new(t) (2)2*i≤n (3)t^.lchild,2*i (4)2*i+1≤n (5)t^.rchild,2*i+1

(6)1

66.(1)Push(s,p) (2)K=2 (3)p->data=ch (4)BT=p (5) ins>>ch

67.(1)result; (2)p:=p^.link; (3) q:=q^.pre （（２）（３）顺序可变）

68.(1)top++ (2) stack[top]=p->rchild (3)top++

(4)stack[top]=p->lchild

69．(1)(i<=j) AND (x<=y) (2)A[i]<>B[k] (3)k-x

(4)creatBT(i+1,i+L,x,k-1,s^.lchild) (5) creatBT(i+L+1,j,k+1,y,s^.rchild)

70. (1)push(s,bt) （2）pop(s) （3）push(s,p^.rchild) // p的右子树进栈

71．(1) p=p->lchild // 沿左子树向下 （2）p=p->rchild

72．(1)0 （2）hl>hr (3)hr=hl

73. (1)top>0 (2)t*2 // 沿左分枝向下 （3）top-1 // 退栈

74．(1)p:=p^.lchild （2）（3）p:=S.data[s.top]^.rchild (4)s.top=0

75. (1)*ppos // 根结点 （2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

76. (1)top>0 (2)stack[top]:=nd^.right (3)nd^.left<>NIL (4)top:=top+1 (左子

树非空)

77. (1) p<>thr // 未循环结束 （2）p->ltag=0 (3)p->lchild

(4)p->rtag=1 && p->rchild!=thr (5) p=p->rchild (6)p=p->rchild

78. 若p^.rtag=1,则p^.rchild 为后继，否则p的后继是p的右子树中最左下的结点

(1)q=p^.rchild (2)q^.ltag=0 (3) q^.lchild

79．（1）tree->lchild (2)null (3)pre->rchild

(4)pre->rtag=1 (5) pre->right=tree; (6) tree->right (注（4）和（5）顺序

数据结构考研试题精选及答案

可换)

80．（1）node->rflag==0 (2)*x=bt (3) *x=node->right

四．应用题

1．树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，

也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并

可使用二叉树的一些算法去解决树和森林中的问题。

树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子

树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；

三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。

2.树和二叉树逻辑上都是树形结构，区别有以上题1所述三点。二叉树不是树的特例。

3．线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也

只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，

每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，

但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义

表中的元素既可以是原子，也可以是子表，子表可以为它表共享。义表也是层次结构。线性结构。如度为1的树，以及广义表中的元素都是原 子时。另外，广义表从元素之间的关系可看成前驱和后继，也符

合线性表，但这时元素有原子，也有子表，即元素并不属于同一

数据对象。 4．方法有二。一是对该算术表达式（二叉树）进行后序遍历，

得到表达式的后序遍历序列，再按后缀表达式求值；二是递归

求出左子树表达式的值，再递归求出右子树表达式的值，最后 按根结点运算符（+、-、*、/ 等）进行最后求值。

5．该算术表达式转化的二叉树如右图所示。 第5题图

6．n（n>0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，

故该树的空链域有nd-(n-1)=n(d-1)+1个。

7．证明：设二叉树度为0和2的结点数及总的结点数分别为n0，n2 和n，则n=n0+n2

(1)

再设二叉树的分支数为B, 除根结点外，每个结点都有一个分支所指，则

n=B+1 (2)

度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为

n=2*n2+1 (3)

由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。 证毕。

h-18．(1)k(h为层数)

h-1（2）因为该树每层上均有K个结点，从根开始编号为1，则结点i的从右向左数第２个

孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2<=n<=ik+1成立，因i是

整数，故结点n的双亲i的编号为 n-2)/k +1。

(3) 结点n(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点 n的

第 i个孩子的编号是(n-1)*k+1+i。

(4) 根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女，即

(n-1)%k!=0，其右兄弟编号是n+1。

9．最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到

h-1h各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2<n<=2-1关系式。解

数据结构考研试题精选及答案

此不等式，并考虑h是整数，则有h= logn +1，即任一结点个数为n 的二叉树的高度至少

为O(logn)。

n10．2-1(本题等价于高度为n的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝

树是不同的二叉树。)

7-111．235。由于本题求二叉树的结点数最多是多少，第7层共有2=64个结点，已知有10

个叶子，其余54个结点均为分支结点。它在第八层上有108个叶子结点。所以该二叉树的

7结点数最多可达(2-1+108)=235。(注意；本题并未明说完全二叉树的高度，但根据题意，

只能8层。)

1012．1023（=2-1）

13．证明：设度为1和2 的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2 (1)

由于二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0 的

结点没有分枝，故二叉树的结点数n与分枝数B有如下关系

n=B+1=n1+2*n2+1 .(2)

由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点

中有（m-1）个度为2，其余度为1。

14．根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是 i/2 ，故A[i]和

A[j]的最近公共祖先可如下求出：

while(i/2!=j/2)

if(i>j) i=i/2; else j=j/2;

退出while后，若i/2=0,则最近公共祖先为根结点，否则最近公共祖先是i/2。

15．N个结点的K叉树，最大高度N（只有一个叶结点的任意k叉树）。设最小高度为H，第

i-12H-1 i(1<=i<=H)层的结点数K，则N=1+k+k+ + k，由此得H= logK(N(K-1)+1)

16. 结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。

17．设分枝结点和叶子结点数分别是为nk和n0，因此有n=n0+nk (1)

另外从树的分枝数B与结点的关系有 n=B+1=K*nk +1

(2)

由（1）和（2）有 n0=n-nk=(n(K-1)+1)/K

18.用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是 i/2 (i=1

时无双亲)，其左子女是2i(若2i<=n,否则i无左子女)，右子女是2i+1(若2i+1<=n,否则无

右子女)。

19. 根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是 n/2 ，这是

最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是

n/2 +1。

20. 按前序遍历对顶点编号，即根结点从１开始，对前序遍历序列的结点从小到大编号。

21. 设树的结点数为n，分枝数为B，则下面二式成立

n=n0+n1+n2+ +nm (1)

n=B+1= n1+2n2+ +mnm (2)

m

由(1)和(2)得叶子结点数n0=1+ (i 1)ni 1i

22. log2n +1 23.15

24. 该结论不成立。对于任一a

本文来源：https://www.bwwdw.com/article/qxqj.html