1.一棵具有n个结点的完全二叉树的树高度（深度）是
A.[logn]+1
B.logn+1
C.[logn]
D.logn-1 答案：A。二叉树的性质4。[]向下取整。 知识点：二叉树的性质：http://blog.****.net/tianlihua306/article/details/44621827
★某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A.不存在这样的二叉树
B.200
C.198
D.199
2.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()
A.（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90） C.（100，60，80，90，120，110，130）D. (100，80，60，90，120，130，110) 答案：C。 3.下图的四个二叉树中，（ ）不是完全二叉树。 答案：D。 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。
A.先序和后序序列 B.中序 C.知道任意一种
D.后序和中序 答案：D。有中序和另一种即可，只知道前序和后序不能得到左右子节点的关系。 5.堆是满二叉树() A.对 B.错 答案：B。堆是完全二叉树 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。即如果一棵二叉树的结点要么是叶子要么有两个孩子结点，则为满二叉树。 完全二叉树最后一行不满。最后一行满了，是满二叉树。 6.将一棵二叉树的根节点放入队列，然后非递归的执行如下操作：将出队节点的所有子节点入队。以上操作可以实现哪种遍历 A.前序遍历 B.中序遍历 C.后序遍历 D.层序遍历
答案：D.
1.入列 A
2.出列A，入列B E3.出列B E，入列CD FG
最后结果就是ABECDFG是层序遍历
7.设只含根结点的二叉树高度为1，现有一颗高度为h（h＞1）的二叉树上只有出度为0和出度为2的结点，则此二叉树中所包含的结点数至少为多少个？
A.2^h-1 B.2h-1 C.2h D.2h+1
答案：B.除了根节点以外，要么一次增加0个节点，要么一次增加2个节点，最少增加两个节点，所以是1+2*（h-1）=2*h-1
A.2^k-1 B.2K+1 C.2K-1D.2^(k-1) 答案：D. 9.已知一棵有2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点的个数是（ ）。
A.115 B.116 C.1895 D.1896
答案：D.树转换为二叉树：http://blog.****.net/dean_deng/article/details/44540805
B.错误
11将整数序列（7-2-4-6-3-1-5）按所示顺序构建一棵二叉排序树a（亦称二叉搜索树），之后将整数8按照二叉排序
树规则插入树a中，请问插入之后的树a中序遍历结果是____。
A.1-2-3-4-5-6-7-8 B.7-2-1-4-3-6-5-8 C.1-3-5-2-4-6-7-8 D.1-3-5-6-4-2-8-7 E.7-2-8-1-4-3-6-5 F.5-6-3-4-1-2-7-812.由权值为29,12,15,6,23的五个叶子节点构造的哈夫曼树为,其带权路径长度为()
A.222
B.192
C.85
D.188
答案：D。
13.递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为______。
A.O（n）
B.O（d）
C.O（logn）
D.O（nlogn）
答案：B。遇到一个根节点压入栈中，因此栈中最大即为树的深度。
14.由树转化成二叉树，该二叉树的右子树不一定为空。（）
A.正确
B.错误
15.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A.M1+M2
B.M3
C.M2+M3
D.M1
答案：C。
16.二叉树在线索化后，仍不能有效求解的问题是（）。
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前驱
D.后序线索二叉树中求后序后继
17.后序线索二叉树是不完善的,要对它进行遍历,还需要使用栈()
A.对
B.错
在后序线索二叉树中查找结点*p的后继：若结点*p为根，则无后继；若结点*p为其双亲的右孩子，则其后继为其双亲；若结点*p为其双亲的左孩子，且双亲无右子女，则其后继为其双亲；若结点*p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。所以，求后序线索二叉树中结点的后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。
A.39
B.52
C.111
D.119
答案：C.
完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第
6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺
失了8×2=16个叶结点，故完全二叉树的结点个数最多为(27-1)-16=111个结点。
19.一棵124个叶结点的完全二叉树,最多有()个结点
A.247 B.248 C.249 D.250 E.251
答案:B.
完全二叉树，出度为1的点有0或1个，所以有123（出度为2点）+124（叶节点）+0/1（出度为1）=247/248,最多有248个点.
20.一个4叉树，度为4的结点个数为6，度为3的节点个数是10，度为2的节点个数是5，叶子节点个数为()
A.40 B.42 C.38 D.4421.某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E。该二叉树对应的森林结
点的层次序列为什么？
A.E、G、F、A、C、D、B B.E、A、C、B、D、G、F C.E、A、G、C、F、B、D D.E、G、A、C、D、F、B
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 B.都会生成唯一一棵树 C.权值之和可能是不同的值D.权值之和是唯一的
24.n个结点的线索二叉树上含有的线索数为
A.n－l B.2n C.n＋l D.n25.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是
A.100 B.101 C.102 D.10326.在一棵二叉树中有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有() 个结点
A.79 B.76 C.56
D.8127. 某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号,编号为1,2,…,n,且有如下性质:T中任一结点V,
其编号等于左子树上的最小编号减1,而V的右子树的结点中,其最小编号等于V左子树上结点的最大编号加1。这时是
按()编号
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序28.在线索化二叉树中，节点t没有左子树的充要条件是（）
A.t->lchild==NULL
B.t->ltag==1
C.t->ltag==1且t->lchild==NULL
D.以上答案都不对
答案：B
29.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和()
A.对
B.错
树的带权路径长度定义为树中所有叶结点的带权路径长度之和。--> 即等于所有结点（叶结点 + 分支结点）的权值之和，而不是分支结点权值之和。而一颗树的权，也就是根节点的权，等于它的叶结点的权值之和。
p.s. a). 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积；
b). 度为零的结点称为叶结点。 度不为零的结点称分支结点。
30.前缀表达式为-+a*b-cd/ef，后缀表达式为abcd-*+ef/-，对应二叉树的中序遍历序列是（）。
A.a+b*-e/fc-d
B.a+b*c-d-e/f
C.a+b*-e/fcd-
D.a+b-*e/fc-d
A.对
B.错
32.有A,B,C,D,E五个字符,出现的频率分别为2,5,3,3,4,由A,B,C,D,E生成的最优二叉树中,该树的带权路径长是多少()
A.35
B.49
C.39
D.45
答案：C。 WPL=2*3+3*3+5*2+3*2+4*2=39;
33.下列关于m阶B-树的说法错误的是( )
A.根结点至多有m棵子树
B.所有叶子都在同一层次上
C.非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
D.根结点中的数据是成链的
A.B树和B+树都是平衡的多叉树
B.B树和B+树都可用于文件的索引结构
C.B树和B+树都能有效的支持顺序检索
D.B树和B+树都能有效的支持随机检索
35.以下是一个tree的遍历算法，queue是FIFO队列，请参考下面的tree，正确的输出是
queue.push(tree.root)while(true){ node=queue.pop( ); output(node.value);//输出节点对应数字 if(null= =node) break; for(child_node in node.children){ queue.push(child_node); }}
A.1234567
B.1245367
C.1376254
D.1327654
36.树的后序遍历序列等同于该树对应的二叉树的()
A.前序序列
B.中序序列
C.后序序列
答案：B。树的先序对应二叉树的先序，树的后序对应二叉树的中序
37.不含任何结点的空树是什么
A.是一棵树;
B.是一棵二叉树;
C.是一棵树也是一棵二叉树;
D.既不是树也不是二叉树
38.二叉树是度为2的有序树()
A.对
B.错 答案：B。一棵度为二的有序树与一棵二叉树的区别在于:
有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树 无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。
39.有n个元素的完全二叉树的深度是
A.D(n)=log2(n)
B.D(n)=1+log2(n)
C.D(n)=n+log2(n)
D.D(n)=1+n*log2(n)
，
40.下面关于二叉搜索树正确的说法包括________。
A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点。
B.给定一棵二叉搜索树的前序和后序遍率历结果，无法确定这棵二叉搜索树。
C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的。
D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树。
41.一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到()个不同的码字
A.107
B.108
C.214
D.215
因为n0 = n2 + 1，n = n0 + n2; 所以 n = 2n0 - 1，即n0 = (n + 1) / 2;叶子结点n0对应的即是不同的编码。
42.在一个10阶的B-树上，每个树根结点中所含的关键字数目最多允许为( )个，最少允许为( )个。
A.10,5
B.9,4
C.8,3
D.7,6
43.设有一棵3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是（ ）。
A.60
B.60， 62
C.62， 65
D.65
答案：D。
在B-树叶结点上删除一个关键字的方法是：
首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：
（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)（即向上取整），说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。
（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。
调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中
44.折半查找与二元查找树的时间性能在最坏的情况下是相同的()
A.对
B.错
答案：B。折半查找最坏的情况下查找log(n)+1次，而二叉查找树最坏的情况是查找n次。
45.若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为()
A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右的结点 D.X的左子树中最右的叶结点
46.若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
47.已知一棵有2011个结点的树,其叶结点个数为116，该树对应的二叉树无右孩子的结点个数为
A.115
B.116
C.1895
E.1896