计算机专业基础综合数据结构（树与二叉树）-试卷1
(总分62,考试时间90分钟)
1. 单项选择题
单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1. 在下面关于树的相关概念的叙述中，正确的是(    )。
A. 只有一个结点的二叉树的度为1
B. 二叉树的度一定为2
C. 二叉树的左右子树可任意交换
D. 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树
2. 已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／一，其前缀形式为(    )。
A. 一A+B*C／DE        B. 一A+B*CD／E
C. 一+*ABC／DE        D. 一+A*BC／DE
3. 算术表达式a+b*(c+d／e)转为后缀表达式后为(    )。
A. ab+cde／*        B. abcde／+*+
C. abcde／*++        D. abcde*／++
4. 某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是(    )。
A. JLKMNOI        B. LKNJOMI
C. LKJNOMI        D. LKNOJMI
5. 设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是(    )。
A. m-n        B. m一n—1
C. n+1        D. 条件不足，无法确定
6. 二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是(    )。
A. 先序遍历二叉树        B. 判断两个指定位置的结点是否在同一层上
C. 层次遍历二叉树        D. 根据结点的值查其存储位置
7. 设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树中所包含的结点数最少为(    )。
A. 188        B. 200
C. 199        D. 201
8. 树是结点的有限集合，一棵树中有(    )根结点。
A. 有0个或1个        B. 有0个或多个
C. 有且只有一个        D. 有1个或1个以上
9. 下列二叉排序树中，满足平衡二叉树定义的是(    )。
A.          B.
C.          D.
二叉树公式10. 把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。设T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式|λKi一λKj|≤1一定成立时，则称T为一棵(    )。
A. 满二叉树        B. 二叉查树
C. 平衡二叉树        D. 完全二叉树
11. 设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(    )。
A. M1
B. M1+M2
C. M3
D. M2+M3
12. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是(    )。
A. 10        B. 11
C. 16        D. 不确定
13. 具有10个叶结点的二叉树中有(    )个度为2的结点。
A. 8        B. 9
C. 10        D. 11
14. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为O的结点数为(    )个。
A. 4        B. 5
C. 6        D. 7
15. 已知一棵二叉树，共有n个结点，那么此二叉树的高度为(    )。
A. nlog2n
B. log2n
C. [log2n]+1
D. 不确定
16. 已知一棵二叉树，第m层上最多含有结点数为(    )。
A. 2m
B. 2m-1一1
C. 2m-1
D. 2m一1
17. 有关二叉树下列说法正确的是(    )。
A. 二叉树就是度为2的树        B. 一棵二又树的度可以小于2
C. 二叉树中至少有一个结点的度为2        D. 二叉树中任何一个结点的度都为2
18. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是(    )。
A. CABDEFG        B. ABCDEFG
C. DACEFBG        D. BAECFDG
19. 已知一个二叉树有1025个结点，那么由此推断二叉树的高h为(    )。
A. 11        B. 10
C. 11一1025        D. 10～1024
20. 一棵完全二叉树，共有n个结点，那么，其叶结点数共有(    )个。
A. n／2        B. n
C. (n-1)／2        D. (n+1)／2
21. (    )的遍历仍需要栈的支持。
A. 前序线索树        B. 中序线索树
C. 后序线索树        D. 中序线索树和前序线索树
22. 已知一棵二叉树高度为h，在此二叉树中只有度为0和度为2的结点，那么这棵二叉树的结点个数最少为(    )。
A. 2h        B. 2h一1
C. 2h+1        D. h+1
2. 综合应用题
综合应用题41-47小题。
1. 已知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。
2. 判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描述结构体)。
3. 以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。
4. 已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L；中序序列为：D，J，G，B，E，H，A，C，K，I，L，F。(1)写出该二叉树的后序序列。(2)画出该二叉树。(3)求该二叉树的高度以及该二叉树中度为2、1、0的结点个数。
5. 有n个结点的二又树，已知叶结点个数为n0。(1)写出求度为1的结点的个数的n1的计算公
式。(2)若此树是深度为k的完全二叉树，写出n为最小的公式。(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。
6. 已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉树。
7. 在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2：：在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1，b∈S2，c∈S3，是否总有a≤b≤c?为什么?

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。