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

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

三.填空题

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技数据结构考研试题精选及答案第6章 树和二叉树答案(2)全文阅读和word下载服务。