第6章 目前最完整的数据结构1800题包括完整答案_树和二叉树答案

《第6章 目前最完整的数据结构1800题包括完整答案_树和二叉树答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第6章树和二叉树一、选择题1.D2.B3.C4.D5.D6.A7.1C7.2A7.3C7.4A7.5C8.B9.C10.D11.B12.E13.D14.D15.C16.B17.C18.C19.B20.D21.A22.A23.C24.C25.C26.C27.C28.C29.B30.C31.D32.B33.A34.D35.B36.B37.C38.B39.B40.B41.1F41.2B42.C43.B44.C45.C46.B47.D48.B49.C50.A51.C52.C53.C54.D55.C56.B57.A58

2、.D59.D60.B61.1B61.2A61.3G62.B63.B64.D65.D66.1C66.2D66.3F66.4H66.5I部分答案解释如下。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是最合适

3、的，选C。A或B都不全。由本题可解答44题。47.左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。二、判断题1.×2.×3.×4.√5.√6.√7.√8.×9.√10.×11.×12.×13.×14.√15.×16.×17.√18.√19.×20.√21.×22.√23.×24.×25.√26.×27.×28.×29.√30.×31.×32.√33.×34.×35.×36.

4、√37.√38.×39.×40.×41.(3)42.√43.√44.×45.√46.×47.×48.×49.√50.√部分答案解释如下。6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。19．任何结点至多只有左子树的二叉树的遍历就不需要栈。24.只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n）37.其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。38.新插入的结点都是叶子结点。42.在二叉树上，对有左右

5、子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。三.填空题1.(1)根结点(2)左子树(3)右子树2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法3．p->lchild==null&&p->rchlid==null4.(1)++a*b3*4-cd(2)185.平衡因子6.97.12

6、8.(1)2k-1(2)2k-19.(1)2H-1(2)2H-1(3)H=ëlog2Nû+110.用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t,则结点i和j在同一层上的条件是ëlog2sû=ëlog2tû。11.ëlog2iû=ëlog2jû12.(1)0(2)(n-1)/2(3)(n+1)/2(4)ëlog2nû+113.n14.N2+115.(1)2K+1-1(2)k+116.ëN/2û17.2k-218.6419.992

7、0.1121.(1)n1-1(2)n2+n322.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2)ëlog2iû+123.6924.425.3h-126.ën/2û27.élog2kù+128.(1)完全二叉树(2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。29.N+130.(1)128(第七层满，加第八层１个)　　(2)7　31.0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个数才至多为1。32．213

8、3.(1)2(2)n-1(3)1(4)n(5)1(6)n-134.(1)FEGHDCB(2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是BEF）35.(1)先序（2）中序36.(1)EACBDGF（2）237.任何结点至多只有右子女的二叉树。38.(1)a(2)dbe(3)hfcg39.(1).D.G.B.A.E.H.C.F.(2)...GD.B...HE..FCA40.DGEBFC