一、单选题
1、已知一算术表达式的中缀形式为 A-B/C+D*E，前缀形式为+-A/BC*DE，其后缀形式为( )。 A.ABC/-DE*+ B.AB/C-D*E+ C. A-BC/DE*+ D. ABCDE/-*+ 正确答案：A
2、有关二叉树下列说法正确的是（ ）。 A.二叉树中任何一个结点的度都为2 B.一棵二叉树的度可以小于2 C.二叉树中每个结点的度都为2 D.二叉树中至少有一个结点的度为2 正确答案：B
3、在一棵高度为k的满二叉树中，结点总数为（ ）。 A.2k-1 B. 2k-1 C. 2k-1+1 D.2k 正确答案：B
4、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（A.不确定 B.60 C.59 D.61 正确答案：C
）。 解析：任意二叉树中，n0=n2+1
5、高度为7的完全二叉树，最少有（ ）个结点。 A.127 B.128 C.63 D. 正确答案：D
解析： 前6层都是满的，最后一层（第7层）近1个结点。可保证题目条件。 6、高度为7的二叉树，最少有（ ）个结点。 A.7 B.127 C.13 D. 正确答案：A
解析： 每层只有1个结点。共7个即可构成一个高度为7的二叉树。 7、对任意一棵有n个结点的树，这n个结点的度之和为( )。 A.n-1 B.2*n C.n+2 D.n
正确答案：A
解析： 所有结点的度之和为分支个数，分支个数即为结点个数-1 8、在下列存储形式中，（ ）不是树的存储形式。 A.双亲表示法 B.孩子-兄弟表示法 C.孩子链表表示法
D.顺序存储表示法 正确答案：D
9、对二叉树中的结点进行编号，要求根结点的编号最小，左孩子结点编号比右孩子结点编号小。则应该采用（ ）遍历方法对其进行编号。 A.层次 B.先序 C.后序 D.中序 正确答案：B
10、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（A. 59 B.61 C.60 D.不一定 正确答案：A
11、树的后根遍历，相当于对应二叉树的（ ）遍历。 A.中序 B.后序 C.层次 D.先序 正确答案：A 二、判断题
1、完全二叉树一定存在度为1的结点。(×)
2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。(√) 3、二叉树只能用二叉链表表示。(×)
）。6、哈夫曼树的带权路径长度等于其中所有结点的带权路径之和。(×) 解析：哈夫曼树的带权路径长度是所有叶子结点的带权路径长度之和。
7、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是哈夫曼树。(√) 三、填空题
1、有10个叶子结点的哈夫曼树，总结点个数是（ ） 。 正确答案：19
2、将一棵树转换为二叉树时，遵循的规则是左孩子、（ ） 。 正确答案：右兄弟
3、假设T是一棵高度为5的二叉树,T中只有度为0和度为2的结点，那么T树最少应该有（ ）个结点。 正确答案：9
