6.3练习题及参考答案.doc-数据结构.doc

6.3练习题及参考答案 6.3.1 练习题 一．选择题 1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最合适的数据结构为（）。 A． 向量 B. 树 C. 图 D二叉树 2．树最合适用来表示（）。 A.有序数据元素 B.元素之间具有分支层次关系的数据 C. 无序数据元素 D. 元素之间无联系的数据. 3．树B的层号表示为1a,2b,3d,3e,2c,对应于下面选择的（）。 A.1a(2b(3d,3e),2c) B.a(b(D.,e),c) C. a(b(d,e),c) D.a(b,d(e),c) 4．对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左，右孩子的编号，同一结点的左，右孩子中，其左孩子编号小于其右孩子编号，则可采用（ ）次序的遍历实现 二叉树的结点编号。 A.先序 B. 中序 C. 后序 D. 从根开始按层次遍历 5．假定一棵三叉树的结点为50，则它的最小高度为（）。 A. 3 B. 4 C 5 D 6 6. 在一棵具有K层的满三叉树中，结点总数为（） A. (3k-1)/2 B. 3k-1 C. (3k-1)/3 D. 3k 7.按照二叉树的定义，具有3个结点的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 8.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为一的结点数为n1,度为0的结点数为n0，则树的最大高度为（ ），其叶结点数为（）；树的最小高度为（），其叶结点 数为（ ）；若采用链表存储结构，则有（）个空链域。 A. n/2 B. [log2 n+1] C . log2 n D. n E n0 + n1 + n2 F. n1 + n2 G. n2+ 1 H. 1 I. n + 1 J. n1 K. n2 L. n1 + 1 9. 对一个满二叉树，m个树叶，n个结点，深度为h,则 （）。 A. n = h + m B. h + m = 2n C. m = h -1 D. n = 2h – 1 10. 设高度为h的二叉树中只有度为0和度为2 的结点，则此类二叉树中所包含的结点数至少为（），至多为（）。 A. 2h B. 2h – 1 C. 2h + 1 D. h +1 E. 2h-1 F.2h – 1 G. 2h+1 +1 H.2h+1 11. 在一棵二叉树上第5层的结点数最多为（）。（假设根结点的层数为0） A. 8 B. 16 C. 15 D. 32 12. 深度为5 的二叉树至多有（） 个结点。 A. 16 B. 32 C. 31 D. 10 13．一棵有124个叶结点的完全二叉树，最多有（） 个结点。 A. 247 B. 248 C. 249 D. 250 E. 251 14.含有129个叶结点的完全二叉树，最多有（）个结点。 A. 254 B.255 C.256 D. 257 E. 258 15.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（）。 A.R[2i+1] B. R[2i] C. R[i/2] D. R[2i -1] 17．在一非空二叉树的中序遍历序列中，根结点的左边（） A． 只有右子树上的所有结点 B. 只有右子树上的部分结点 C．只有左子树上的部分结点 D. 只有左子树上的所有结点 18 . 任何一棵二叉树的叶结点在先序，中序和后序遍历中的相对次序（）。 A．不发生改变 B. 发生改变 C.不能确定 D.以上都不对 19．设n,m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（）。 A. n在m右方 B。 n是m祖先 C。 n在m左方 D。 n是m 子孙 20．一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E 的直接前趋为（），后序遍历中结点B 的直接后继是（）。 （1）B （2）D （3）A（4）I （5）F （6）C 21． 已知某二叉树的后序遍历是d a b e c ，中序遍历序列是d e b a c，它的前序遍历序列是（）。 A. acbed B. decab C. deabc D .cedba 22．若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。 A前序 B。 中序 C 后