数据结构树和二叉树习题及答案.docx

习题六 树和二叉树 一、单项选择题 以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种分支层次结构E．任何只含一个结点的集合是一棵树 下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 任何一棵二叉树中每个结点的度都为2 任何一棵二叉树中的度肯定等于2 任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（ ） A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 树最适合用来表示 ( ) 有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ ） A．9 B．11 C．15 D．不确定 设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2 和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ ）。 A．M1 B．M1+M2 C．M3 D．M2+M3 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ ） A． 250 B． 500 C．254 D．505 E．以上答案都不对 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 二叉树的第I 层上最多含有结点数为（ ） 2I B． 2I-1-1 C． 2I-1 D．2I -1 一棵二叉树高度为h,所有结点的度或为 0，或为 2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 利用二叉链表存储树，则根结点的右指针是（ ）。 指向最左孩子 B．指向最右孩子 C．空 D． 非 空 12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac , 它的前序遍历是 （ ）。 acbed B．decab C．deabc D．cedba 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ） 都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同15．在完全二叉树中，若一个结点是叶结点，则它没（ ）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 在下列情况中，可称为二叉树的是（ ） 每个结点至多有两棵子树的树 哈夫曼树 每个结点至多有两棵子树的有序树 每个结点只有一棵右子树 以上答案都不对 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 0 B. 1 C. 2 D. 不确定 引入二叉线索树的目的是（ ） 加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 19．n 个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 20．由 3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 21．下面几个符号串编码集合中，不是前缀编码的是（ ）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第 i 个结点（i 从 1 开始用上述方法编号）的右孩子在数组A 中的位置是（ ） A．A[2i](2i=n) B．A[2i+1](2i+1=n) C．A[i-2] D．条件不充分，无法确定23、以下说法错误的是 ( ) A．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 B．若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。 C．已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，