哎呀，因为最近实在是太忙了（忙着学数据结构 刷算法题），当然也有点小摆烂，更新没有跟上，第一篇博文比较水，这一篇争取做得高质量。接下来我会发出我的课程实验作业之类的东西，欢迎大家点评不足！！！
1. (单选题)二叉树的深度为k,则二叉树最多有( )个结点。
A. 2k
B. 2k-1（2的k次方减1）
C. 2k-1（2的k减1次方）
D. 2k-1
解析：深度为k的二叉树，最多结点的情况是满二叉树（也称完美二叉树）（一个二叉树第i层的最大结点数为2的（i-1次方），根据等比数列求和公式，每一层的最大结点数相加得到，结果为2的k次方减1）（k>=1） 选B
2. (单选题)用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中,若结点R[i]有右孩子,则其右孩子是( )。
A. R[2i-1]
B. R[2i+1]
C. R[2i]
D. R[2/i]
解析：略 （太简单了哈哈）选B
3. (单选题)在一棵具有5层的满二叉树中结点总数为( )。
A. 31
B. 32
C. 33
D. 1
解析：根据1中我们得到的公式求解即可 选A
4. (单选题)若以{4,5,6,7,8}作为权值构造哈夫曼树,则该树的带权路径长度为( )。
A. 67
B. 68
C. 69
D. 70
解析：熟知哈夫曼树的构造过程，而且注意带权路径长度只牵扯到根结点的权值
5.(单选题)树最适合用来表示( )。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
解析：根据树的模型可知，元素之间具有分支层次关系 选C
6.表达式A*(B+C)/(D-E+F)的后缀表达式是( )。
A. A*B+C/D-E+F
B. AB*C+D/E-F+
C. ABC+*DE-F+/
D. ABCDED*+/-+
解析：有关前缀、中缀和后缀表达式 简单的方法（在每一个运算符前（后）添加括号） 将其对应的符号写在其对应括号前（后），之后去掉括号即可 选C
7.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序( )。
A. 不发生改变
B. 发生改变
C. 不能确定
D. 以上都不对
解析： 自己找一棵二叉树 写出其遍历序列可知 选A
8.(单选题)假定在一棵二叉树中,度为2的结点数为15,度为1的结点数为30,则叶子结点数为( )个。
A. 15
B. 16
C. 17
D. 47
解析：二叉树的结点个数n=n0+n1+n2(分别对应度为0 度为1 度为2的结点个数）又因为度=n-1
n1+2n2=n-1 联立两式得 n2=n0-1,代入n2=15,得到n0=16 选B
9.(单选题)下面说法中正确的是( )。
A. 度为2的树是二叉树
B. 度为2的有序树是二叉树
C. 子树有严格左右之分的树是二叉树
D. 子树有严格左右之分,且度不超过2的树是二叉树
解析：选D 子树有严格左右之分，且度不超过2的树是二叉树
10.(单选题)按照二叉树的定义,具有3个结点的二叉树有( )种。
A. 3
B. 4
C. 5
D. 6
解析：有五种 （根结点左子树右子树）（根结点只有左子树）（根结点只有右子树）（根结点左子树（左子树有右子树））（根结点（右子树有左子树））
选C
11.(单选题)对一棵二叉排序树按( )遍历,可得到结点值从小到大的排列序列。
A. 先序
B. 中序
C. 后序
D. 层次
解析：根据我们所学的关于二叉排序树的知识，最小值在左子树的最左端，最大值在右子树的最右端，它们分别没有左子树和右子树（根据中序遍历）可知结点值一定是从小到大的，选B
12.(单选题)已知序列25, 13, 10, 12,9是最大堆,在序列尾部插入新元素18,将其再调整为最大堆,调整过程中元素之间进行的比较次数是 ( )。
A. 1
B. 2
C. 4
D. 5
解析：两次，如图：
选B
13.(单选题)对n (n≥2)个权值均不相同的字符构成哈夫曼树。 下列关于该哈夫曼树的叙述中,错误的是 ( )。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
解析：A 哈夫曼树可能是完全二叉树，但不一定是。
18.(单选题)已知一个长度为16的顺序表L,其元素按关键字有序排列。 若采用折半查找法查找一个L中不存在 的元素,则关键字的比较次数最多是 ( )。
A. 4
B. 5
C. 6
D. 7
解析：16个二叉排序树的深度为5，查找一个不存在的最多查到最后一层，即5 选B
19.(单选题)在下述结论中,正确的有 ( )。
① 只有一个结点的二叉树的度为0 ; ② 二叉树的度为2 ; ③ 二叉树的左右子树可任意交换, ④ 深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A. ① ② ③
B. ① ③ ④
C. ② ④
D. ① ④
解析：①正确 ②叉树的度小于等于2 ③二叉树子树有严格左右之分 ④正确 选D
20.(单选题)一个具有1025个结点的二叉树的高g为 ( )。
A. 11
B. 10
C. 11至1025之间
D. 10至1024之间
解析：当它为完全二叉树时，高度为11 线性结构时，高度为1025 选C
21.(单选题)一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足 ( )。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
解析：前序序列是.根左右·,后序序列是.左右根·,若要这两个序列相反,只有单支树才有可能,所 以本题的A项和B项均对,单支树的特点是只有一个叶结点,故C项是最合适的。 A项或B项都不全。 选C
22.(单选题)在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼树的加权平均长度为（ ）。
A. 2.4
B. 2.5
C. 2.67
D. 2.75
解析：构造哈夫曼树后，求加权路径长度，将其除以各个字符出现的频次之和 选B
23. (判断题)由二叉树的前序和后序遍历序列能唯一确定这棵二叉树。
A. 对
B. 错
解析：错 必须要有中序遍历 选B
24. (判断题)二叉树是一般树的特殊情形。
A. 对
B. 错
正确答案: 错
答案解析：树与二叉树是两种不同的树形结构,二叉树中的孩子结点有着严格左右之分的