1 . 每棵树都能唯一地转换成对应的二叉树，由树转换的二叉树中，一个节点N的右孩子是它在原树里对应节点的__________。 (1 分)
A. 最左孩子
B. 最右孩子
C. 右邻兄弟
D. 左邻兄弟
2 . 每棵树都能唯一地转换成对应的二叉树，由树转换的二叉树中，一个节点N的左孩子是它在原树对应节点的__________。 (1 分)
A. 最左孩子
B. 最右孩子
C. 右邻兄弟
D. 左邻兄弟
3 . 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用_________。 (1 分)
A. 二叉链表
B. 孩子链表
C. 顺序表
D. 三叉链表
4 . 具有m个叶子节点的哈夫曼树，共有________个节点。 (1 分)
A. 2m-1
B. 2m+1
C. m
D. am
5 . 具有n个顶点的连通图至少有_______条边 (1 分)
A. n-1
B. n
C. n+1
D. 2n
6 . G是一个非连通无向图，共有28条边，则该图至少有_____个顶点。 (1 分)
A. 7
B. 8
C. 9
D. 10
7 . 任一个连通图的生成树_________。 (1 分)
A. 可能不存在
B. 只有一棵
C. 一棵或者多棵
D. 一定有多棵
8 . 广度优先搜索遍历类似于二叉树的_________。 (1 分)
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
9 . 深度优先遍历类似于二叉树的_________。 (1 分)
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
10 . 具有8个顶点的有向图最多有_________条边。 (1 分)
A. 8
B. 28
C. 56
D. 78
11 . 具有8个顶点的无向图最多有_______条边。 (1 分)
A. 8
B. 28
C. 56
D. 72
12 . 一个具有n个顶点e条边的图中，所有顶点的度数之和等于_______。 (1 分)
A. n
B. 2n
C. e
D. 2e
13 . 下面的各种图中，哪个图的邻接矩阵一定是的______。 (1 分)
A. AOE网
B. AOV网
C. 无向图
D. 有向图
14 . 一棵具有124个叶子节点的完全二叉树，最多有_____节点。 (1 分)
A. 247
B. 248
C. 249
D. 250
15 . 判断线索二叉树中p节点有右孩子的条件是______。 (1 分)
A. p!=NULL
B. p->rchild != NULL
C. p->rtag = 0
D. p-> rtag = 1
16 . 具有n个节点（n>1）的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子节点外每个节点______。 (1 分)
A. 仅有左孩子
B. 仅有右孩子
C. 仅有一个孩子
D. 都右左右孩子
17 . 遍历一棵具有n个节点的二叉树，在前序序列、中序序列和后序序列中所有叶子节点的相对次序________。 (1 分)
A. 都不相同
B. 完全相同
C. 前序和中序相同
D. 中序和后序相同
18 . 在具有200个节点的完全二叉树中，设根节点的层次编号为1，则层次编号为60的节点，其双亲节点的层次编号为________。 (1 分)
A. 30
B. 60
C. 120
D. 121
19 . 在具有200个节点的完全二叉树中，设根节点的层次编号为1，则层次编号为60的节点，其右孩子节点的层次编号为_________。 (1 分)
A. 30
B. 60
C. 120
D. 121
20 . 在具有200个节点的完全二叉树中，设根节点的层次编号为1，则层次编号为60的节点，其左孩子节点的层次编号_________。 (1 分)
A. 30
B. 60
C. 120
D. 121
21 . 若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为_______。 (1 分)
A. BCAGFED
B. DAEBCFG
C. ABCDEFG
D. BCAEFGD
22 . 若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其后序序列为_______。 (1 分)
A. BCAGFED
B. DAEBCFG
C. ABCDEFG
D. BCAEFGD
23 . 前序序列为ABC的不同二叉树有________种不同形态。 (1 分)
A. 3
B. 4
C. 5
D. 6
24 . 深度为k的完全二叉树至少有_________个节点。 (1 分)
A. 2的（k-1）次方-1
B. 2的（k-1）次方
C. 2的k次方-1
D. 2的k次方
25 . 深度为K的完全二叉树至多有________个节点。 (1 分)
A. 2的(k-1）次方-1
B. 2的（k-1）方
C. 2的k次方-1
D. 2的k次方
26 . 若一棵二叉树中某节点无左孩子，则该节点一定是_______。 (1 分)
A. 度为1的节点
B. 度为2的节点
C. 分支节点
D. 叶子节点
27 . 在树中，若节点A有4个兄弟，而且B是A的双亲，则B的度为________。 (1 分)
A. 3
B. 4
C. 5
D. 6
28 . 设深度为h(h>0)的二叉树中只有度为0和度为2的节点，则此二叉树中所含的节点总数至少为_________。 (1 分)
A. 2h
B. 2h-1
C. 2h+1
D. h+1
29 . 从二叉搜索树中查找一个元素时，其时间复杂度大致为________。 (1 分)
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
30 . 关于二叉树的下列说法正确的是________。 (1 分)
A. 二叉树的度为2
B. 二叉树的度可以小于2
C. 每一个节点的度都为2
D. 至少有一个节点的度为2
