第六章课后练习

树形结构单项选择题1.如图所示的4棵二叉树中，不是完全二叉树。3.在线索化二叉树中，t所指结点没有左子树的充要条件是。A.t-left==NULLB.t-ltag==1C.t-ltag==1且t-left==NULLD.以上都不对4.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法。A.正确B.错误5.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法。A.正确B.错误6.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法。A.正确B.错误7.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为。A.2hB.2h-1C.2h+1D.h+18.如图所示二叉树的中序遍历序列是。A.abcdgefB.dfebagcC.dbaefcgD.defbagc9.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是。A.acbedB.decabC.deabcD.cedba10.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的。A.前序B.中序C.后序D.层次序11.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的。A.前序B.中序C.后序D.层次序12某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca13.二叉树为二叉排序树的充分必要条件是任一结点的值均大于其左孩子的值、小于其右孩子的值，这种说法。A.正确B.错误14.按照二叉树的定义，具有3个结点的二叉树有种。A.3B.4C.5D.615.如图所示二叉树的中序遍历序列是。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh16.树的基本遍历策略可分为先根遍历和后根遍历；二叉树基本遍历策略可分为先序遍历、中序遍历和后序遍历。这时，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论是正确的。A.树的先根遍历序列与二叉树的先序遍历序列相同B.树的后根遍历序列与二叉树的后序遍历序列相同C.树的先根遍历序列与二叉树的中序遍历序列相同D.以上都不对17.深度为5的二叉树至多有个结点。A.16B.32C.31D.1018.在一非空二叉树的中序遍历序列中，根结点的右边。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点19.树最适合用来表示。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据20任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。A.不发生改变B.发生改变C.不能确定D.以上都不对21.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构22.对于一个满二叉树，m个树叶，n个结点，深度为h，则。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-123.如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序。A.uwvtsB.vwutsC.wuvtsD.wutsv25.如图所示的T2是由有序树T1转换而来的二叉树，那么树T1有个叶结点。A.4B.5C.6D.726.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙27.线索二叉树是一种结构。A.逻辑B.逻辑和存储C.物理D.线性填空题1.有一棵树如图所示，回答下面问题：（1）这棵树的根结点是；（2）这棵树的叶子结点是；（3）结点c的度是；（4）这棵树的度是；（5）这棵树的深度是；（6）结点c的子女是；（7）结点c的父母结点是。2.指出树和二叉树的三个主要差别、、。3.从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本目的是。4.一棵二叉树的结点数据采用顺序存储结构，存储于数组T中，如图所示，则该二叉树的链接表示形式为。123456789101112131415161718192021eafdgcjihb5.深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下、从左到右次序给结点编号（从1开始），则编最小的叶子结点的编号是。6.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=。7.一棵二叉树的第k层最多有个结点；一棵有n个结点的满二叉树共有个叶子和个非终端结点。8.结点最少的树为，结点最少的二叉树为。9.现有按中序遍历二叉树的结果是abc，问有种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是。10.根据二叉树的定义，具有三个结点的二叉树有种不同的形态，它们分别是。11.由如图所示的二叉树，回答以下问题：（1）其中序遍历序列；（2）其前序遍历序列；（3）其后序遍历序列；（4）该二叉树的中序线索二叉树为；（5）该二叉树的后序线索二叉树为；（6）该二叉树对应的森林是。12.已知一棵树如图所示，其孩子兄弟表示为。13.以数据集｛4，5，6，7，10，12，18｝为结点权值所构造的哈夫曼树为，其带权路径长度为。