数据结构考研试题精选及答案第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．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索

和后继线索为空指针。

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