数据结构与算法 习题及解答 机械自考版 -第5--8章 树与二叉树---查找.docx

第五章树与二叉树

一、单项选择题

1．下列关于二叉树的叙述中，正确的是________。

A．二叉树的度为2 B．一棵二叉树的度可以小于2

C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2

答案：B。

树中结点的度的最大值是树的度。对于二叉树，每个结点的度可以是0、1或2。如果二叉树仅含有根结点，则它的度为0。如果二叉树中所有分支结点均仅含有一个子结点，则二叉树的度为1。如果二叉树中有的分支结点含有2个子结点，则二叉树的度为2。所以二叉树的度可以是0，可以是1，也可以是2。

2．下列存储形式中，不是树的存储形式的是________。

A．父结点表示法 B．孩子结点表示法

C．孩子-兄弟表示法 D．顺序存储表示法

答案：D。

二叉树有顺序存储表示，它针对每层的最多结点数，在数组中预留出相应的位置。但对于树而言，因为每层结点的个数没有上限，所以没有办法在数组中预留空间。

另外三种存储形式都是树的存储形式。

3．下列关于二叉树的叙述中，正确的是________。

I．只有一个结点的二叉树的度为0

II．二叉树的度为2

III．二叉树的左右子树可任意交换

IV．深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树

A．仅I、IV B．仅II、IV C．仅I、II、III D．仅II、III、IV

答案：A。

单结点的二叉树只含有根结点，这个结点也是叶结点，度为0，所以树的度为0。I是正确的。但二叉树中结点的度可以是0、1或2，所以树的度不一定必须是2。II不正确。二叉树中左子树与右子树是不同的，不能任意交换。III不正确。满二叉树是完全二叉树的特例，深度一样的完全二叉树与满二叉树，只在最后一层可能存在差异，在这一层上，完全二叉树可能是不满的，而满二叉树一定是满的，前面的所有层中，完全二叉树的结点个数与满二叉树的结点个数都是相同的。IV是正确的。

4．一棵二叉树共有20个结点，其中度为l的结点个数是7个，则叶结点个数是________。

A．4 B．7 C．9 D．13

答案：B。

二叉树中，设n0是叶结点的个数，n1是度为1的结点的个数，n2是度为2的结点的个数，由性质3可知，n0=n2+1，由题目条件知n1=7，则n0+n2=20-n1=13，解得n0=7。

5．深度为4的二叉树中，结点个数最多是________。

A．10 B．16 C．31 D．32

答案：C。

相同高度的满二叉树中结点个数最多。深度为4的满二叉树的高度是5。

6．对含n个结点的完全二叉树从上到下且从左至右进行1至n编号，根结点编号为1，则对树中任意一个编号为i的结点，正确的是________。

A．若2i=n，则结点i无左子结点

B．若2i+1=n，则结点i无右子结点

C．若i为偶数，则i是其父结点的左子结点

D．若i为奇数，则i是其父结点的右子结点

答案：C。

按照题目中给出的编号规则，结点i的左子结点是2i，右子结点是2i+1，故选项A和B中，不等式中取等号时，结论是错误的。反过来看，偶数编号的结点是其父结点的左子结点，奇数编号的结点是其父结点的右子结点，唯一的例外是根结点，根的编号是奇数，没有父结点，所以选项D也是错误的。

7．采用顺序存储方式保存一棵二叉树，根结点保存在数组的A[0]中，若编号为i结点有右子结点，则该子结点的下标为________。

A．2i-1 B．2i C．2i+1 D．2i+2

答案：D。

基本概念。下标从0开始。

8．在一非空二叉树的中序遍历序列中，根结点的右边________。

A．只有左子树上的所有结点 B．只有右子树上的所有结点

C．只有左子树上的部分结点 D．只有右子树上的部分结点

答案：B。

中序遍历序列中，根的前面是左子树中所有结点的中序遍历序列，后面是右子树中所有结点的中序遍历序列。

9．若一棵满二叉树有m个叶结点，n个结点，高度为h，则下列关系式中正确的是________。

A．h+m==2n B．n==h+m C．m==h-1 D．n==2h-1

答案：D。

满二叉树中，高度为h时，结点个数n=2h-1。

10．一棵二叉树高度为h，所有结点的度或为0或为2，则这棵二叉树的结点数最少为________。

A．h+1 B．2h-1 C．2h D．2h+1

答案：B。

基本概念。没有度为1的结点，满二叉树中结点个数最多。

11．设n、m为二叉树T中的两个结点，在中序遍历序列中，n出现在m之前的条件是________。

A．n在m左侧 B．n在m右侧 C．n是m子孙 D．n是m祖先

答案：A。

将二叉树中的各结点向下投影成一个序列，二叉树中若结点n在m的左侧，则中序遍历时先遍历到n后遍历到m。

12．由3个结点可以构造出不同形态的二叉树的数量是________。

A．3个 B．4个