计算机学科专业基础综合数据结构-树与二叉树(二)
(总分：100.00，做题时间：90分钟)
一、{{B}}单项选择题{{/B}}(总题数：44，分数：44.00)
1.在下面关于树的相关概念的叙述中，正确的是______。
∙ A.只有一个结点的二叉树的度为1
∙ B.二叉树的度一定为2
∙ C.二叉树的左右子树可任意交换
∙ D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树

（分数：1.00）
 A.
 B.
 C.
 D. √
解析：只有一个结点的二叉树的度为零。二叉树的度可以为0、1、2；二叉树的左右子树不能任意交换。
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


（分数：1.00）
 A.
 B.
 C.
 D. √
解析：根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)-D/E，前缀表达式：-+A*BC/DE。
3.算术表达式a+b*(c+d/e)转为后缀表达式后为______。
∙ A.ab+cde/*
∙ B.abcde/+*+
∙ C.abcde/*++
∙ D.abcde*/++

（分数：1.00）
 A.
 B. √
 C.
 D.
解析：根据表达式a+b*(c+d/e)可知其后缀表达式为abcde/+*+。
4.某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是______。
∙ A.JLKMNOI
∙ B.LKNJOMI
∙ C.LKJNOMI
∙ D.LKNOJMI

（分数：1.00）
 A.
 B.
 C. √
 D.
解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。 [*] 由
此图可以确认后序遍历的序列为LKJNOMI。
5.设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是______。
∙ A.m-n
∙ B.m-n-1
∙ C.n+1
∙ D.条件不足，无法确定

（分数：1.00）
 A. √
 B.
 C.
 D.
解析：F对应的二叉树共有m个结点，右子树上n个，左子树上有(m-n-1)个，第一株树包括根和左子树，共(m-n)个。
6.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是______。
∙ A.先序遍历二叉树
∙ B.判断两个指定位置的结点是否在同一层上
∙ C.层次遍历二叉树
∙ D.根据结点的值查其存储位置

（分数：1.00）
 A.
 B. √
 C.
 D.
解析：选项A、C、D运算的时间复杂度都是O(n)，而选项B的运算的时间复杂度为O(1)，因为对于指定位置p和q的两个结点，判断是否在同一层上，只需判断两者[*]是否成立。
7.设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树中所包含的结点数最少为______。
∙ A.188
∙ B.200
∙ C.199
∙ D.201

（分数：1.00）
 A.
 B.
 C. √
 D.
解析：除根结点层只有1个结点外，其他各层均有两个结点，结点总数=2×(100-1)+1=199。
8.树是结点的有限集合，一棵树中有______根结点。
∙ A.有0个或1个
∙ B.有0个或多个
∙ C.有且只有一个
∙ D.有1个或1个以上

（分数：1.00）
 A.
 B.
 C. √
 D.
解析：根据树的基本定义可知，每个树只能有且只有一个根结点。
9.下列二叉排序树中，满足平衡二叉树定义的是______。 A． B． C． D．
（分数：1.00）
 A.
 B. √
 C.
 D.
解析：考查平衡二叉树的定义。 根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个选项均可以到不符合的结点。
10.把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。设T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式|λKi-λKj|≤1一定成立时，则称T为一棵______。
∙ A.满二叉树
∙ B.二叉查树
∙ C.平衡二叉树
∙ D.完全二叉树

（分数：1.00）
 A.
 B.
 C. √
 D.
解析：此题干的叙述符合平衡二叉树的定义。
11.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是______。
∙ A.M1
∙ B.M1+M2
∙ C.M3
∙ D.M2+M3

（分数：1.00）
 A.
 B.
 C.
 D. √
解析：森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的，因此结点数为M2+M3。
12.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是______。
∙ A.10
∙ B.11
∙ C.16
∙ D.不确定

（分数：1.00）
 A.
 B. √
 C.
 D.
解析：根据二叉树的性质可知，度为0的结点个数比度为2结点个数多一个，即n0=n2+1。
13.具有10个叶结点的二叉树中有______个度为2的结点。
∙ A.8
∙ B.9
∙ C.10
∙ D.11

（分数：1.00）
 A.
 B. √
 C.
 D.
解析：根据二叉树的性质n0=n2+1，可知度为2的结点个数为9。
14.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为______个。
∙ A.4
∙ B.5
∙ C.6
∙ D.7
二叉树定义
（分数：1.00）
 A.
 B.
 C. √
 D.
解析：一棵度为3的树，总结点数n=n0+n1+n2+n3，而总分支总数为n0×0+n1×2+n2×1+n3×2，由于分支总数加1为结点总数，可得出n0=6。
15.已知一棵二叉树，共有n个结点，那么此二叉树的高度为______。
A．nlog2n
B．log2n
C．
D．不确定
（分数：1.00）
 A.
 B.
 C.
 D. √
解析：已知一棵二叉树共有n个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。
16.已知一棵二叉树，第m层上最多含有结点数为______。
∙ A.2m
∙ B.2m-1-1
∙ C.2m-1
∙ D.2m-1

（分数：1.00）
 A.
 B.
 C. √
 D.
解析：根据二叉树的性质，二叉树的第m层上最多有2m-1。
17.有关二叉树下列说法正确的是______。
∙ A.二叉树就是度为2的树
∙ B.一棵二叉树的度可以小于2
∙ C.二叉树中至少有一个结点的度为2
∙ D.二叉树中任何一个结点的度都为2


（分数：1.00）
 A.
 B. √
 C.
 D.
解析：本题考查二叉树的概念。
18.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是______。
∙ A.CABDEFG
∙ B.ABCDEFG
∙ C.DACEFBG
∙ D.BAECFDG

（分数：1.00）
 A.
 B. √
 C.
 D.
解析：由题可得A为根结点，并且B为A的孩子结点。选项A，C应为A的左孩子，其前序序列应为AC……。选项B，当B为A的右孩子，C为B的右孩子时，满足题目要求。选项C，类似选项A，其前序序列应为AD……。选项D，B为A的左孩子，C为A的右子树的根，E为C的左子树，FDG为C的右子树，其前序序列应为ABEC……。
19.已知一个二叉树有1025个结点，那么由此推断二叉树的高h为______。
∙ A.11
∙ B.10
∙ C.11～1025
∙ D.10～1024

（分数：1.00）
 A.
 B.
 C. √
 D.
解析：右完全二叉树中1025＞210，即最少需要11层，最多需要有1025层。
20.一棵完全二叉树，共有n个结点，那么，其叶结点数共有______个。
∙ A.n/2
∙ B.n
∙ C.(n-1)/2
∙ D.(n+1)/2

（分数：1.00）
 A.
 B.
 C.
 D. √
解析：此问题可以利用二叉树及完全二叉树的性质来求解。 设i、j、k分别为度为0、1、2的结点数目，则n=i+j+k。 根据二叉树的性质有i=k+1，即k=i-1，代入上式，得n=2i+j-1，即i=(n-j+1)/2。 由于完全二叉树中最多只有一个度为1的结点，同时考虑到i为整数， (1)当j=0时，此时n=i+k=2k+1为奇数，则i=(n+1)/2： (2)当j=1时，此时n=i+k+1=2k+2为偶数，则i=(n+1)/2向下取整。 所以选D。

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