计算机专业基础综合数据结构（树与二叉树）模拟试卷1
单选题
1.在下面关于树的相关概念的叙述中，正确的是( )。(D)
A. 只有一个结点的二叉树的度为1
B. 二叉树的度一定为2
C. 二叉树的左右子树可任意交换
D. 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树
解析：只有一个结点的二叉树的度为零。二叉树的度可以为0、1、2；二叉树的左右子树不能任意交换。
2.已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／一，其前缀形式为( )。(D)
A. 一A+B*C／DE
B. 一A+B*CD／E
C. 一+*ABC／DE
D. 一+A*BC／DE
解析：根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)一D／E，前缀表达式：一+A*BC／DE。
3.算术表达式a+b*(c+d／e)转为后缀表达式后为( )。(B)
A. ab+cde／*
B. abcde／+*+
C. abcde／*++
D. abcde*／++
解析：根据表达式a+b*(c+d／e)可知其后缀表达式为abcde／+*+。
4.某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是( )。(C)
A. JLKMNOI
B. LKNJOMI
C. LKJNOMI
D. LKNOJMI
解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。
5.设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是( )。(A)
A. m-n
B. m一n—1
C. n+1
D. 条件不足，无法确定
解析：F对应的二叉树共有m个结点，右子树上n个，左子树上有(m—n一1)个，第一株树包括根和左子树，共(m一n)个。
6.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是( )。(B)
A. 先序遍历二叉树
B. 判断两个指定位置的结点是否在同一层上
C. 层次遍历二叉树
D. 根据结点的值查找其存储位置
解析：选项A、C、D运算的时间复杂度都是O(n)，而选项B的运算的时间复杂度为O(1)，因为对于指定位置p和q的两个结点，判断是否在同一层上，只需判断两者［log2p]=[log2q]是否成立。
7.设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树中所包含的结点数最少为( )。(C)
A. 188
B. 200
C. 199
D. 201
解析：除根结点层只有1个结点外，其他各层均有两个结点，结点总数=2×(100一1)+1=199。
8.树是结点的有限集合，一棵树中有( )根结点。(C)
A. 有0个或1个
B. 有0个或多个
C. 有且只有一个
D. 有1个或1个以上
解析：根据树的基本定义可知，每个树只能有且只有一个根结点。
9.下列二叉排序树中，满足平衡二叉树定义的是( )。
(B)
A.
B.
C.
D.
解析：考查平衡二叉树的定义。
根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个选项均可以找到不符合的结点。
10.把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。设T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式|λKi一λKj|≤1一定成立时，则称T为一棵( )。(C)
A. 满二叉树
B. 二叉查找树
C. 平衡二叉树
D. 完全二叉树
解析：此题干的叙述符合平衡二又树的定义。
11.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。(D)
A. M1
B. M1+M2
C. M3
D. M2+M3
解析：森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的，因此结点数为M2+M3。
12.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。(B)
A. 10
B. 11
C. 16
D. 不确定
解析：根据二叉树的性质可知，度为0的结点个数比度为2结点个数多一个，即n0=n2+1。
13.具有10个叶结点的二叉树中有( )个度为2的结点。(B)
A. 8
B. 9
C. 10
D. 11
解析：根据二叉树的性质n0=n2+1，可知度为2的结点个数为9。
14.在一棵度为3的树中
本文档预览：3000字符，共8664字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
