画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。

(1)【◆题库问题◆】：[问答题] 画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。

【◆参考答案◆】：

(2)【◆题库问题◆】：[单选] 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）
A．2
B．3
C．4
D．5

【◆参考答案◆】：C

(3)【◆题库问题◆】：[单选] 若声明一个浮点数数组如下：froataverage[]＝newfloat[30]；假设该数组的内存起始位置为200，average[15]的内存地址是（）。
A．214
B．215
C．260
D．256

【◆参考答案◆】：C

(4)【◆题库问题◆】：[单选] 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（）。
A．R[2i-1]
B．R[2i+1]
C．R[2i]
D．R[2/i]

【◆参考答案◆】：B

(5)【◆题库问题◆】：[单选] 对n个元素进行直接插入排序时间复杂度为（）。
A．O（1）
B．O（n）
C．O（n2）
D．O（log2n）

【◆参考答案◆】：C

(6)【◆题库问题◆】：[名词解释] 深度优先搜索（DFS）

【◆参考答案◆】：
类似树的先序遍历，在图中任选一个顶点作为出发顶点V0，访问V0后，依次从V0的没被访问过的邻接点出发进行深度优先搜索。直到与V0所连通的所有顶点均被访问。如果，此时图中还有顶点尚未访问，则从剩余的顶点中再任选一个顶点作为出发顶点V0，重复上述过程，直到图中全部顶点均被访问为止。

(7)【◆题库问题◆】：[名词解释] 连通分量

【◆参考答案◆】：
对于一个无向图，其极大连通子图叫做该图一个连通分量。

(8)【◆题库问题◆】：[单选] 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）
A．2h
B．2h-1
C．2h+1
D．h+1

【◆参考答案◆】：B

(9)【◆题库问题◆】：[单选] 在作进栈运算时，应先判别栈是否（）。
A．空
B．满
C．上溢
D．下溢

【◆参考答案◆】：B

(10)【◆题库问题◆】：[问答题] 假设用于通讯的电文仅由8个字母A．B．C．D．E．F．G．H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。

【◆参考答案◆】：