哈夫曼树

(1)【◆题库问题◆】：[名词解释] 哈夫曼树

【◆参考答案◆】：
在含有N个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树或最优二叉树。

(2)【◆题库问题◆】：[填空题] 在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0=（）。

【◆参考答案◆】：N2+1

(3)【◆题库问题◆】：[判断题] 一个图的广度优先搜索树是惟一的
A．正确
B．错误

【◆参考答案◆】：正确

(4)【◆题库问题◆】：[问答题] 数据结构涉及哪几个方面？

【◆参考答案◆】：
数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。

(5)【◆题库问题◆】：[单选] 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。
A．j-i
B．i-j-1
C．i-j
D．i-j+1

【◆参考答案◆】：D

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

【◆参考答案◆】：
类似于树的先序遍历，假设从图中某顶点V出发，在访问了V之后一次从V的未被访问的邻接点出发做深度优先遍历，知道图中所有和v有路径相同的顶点都被访问到。若图中还有顶点未访问，则另选图中一个未曾被方位的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问。

(7)【◆题库问题◆】：[单选] 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。
A．O（1）
B．O（n）
C．O（n2）
D．O（nlog2n）

【◆参考答案◆】：B

(8)【◆题库问题◆】：[单选] 直接选择排序在最好情况下的时间复杂度是（）。
A．O（n）
B．O（nlog2n）
C．O（1）
D．O（n2）

【◆参考答案◆】：A

(9)【◆题库问题◆】：[名词解释] 选择排序

【◆参考答案◆】：
每一趟在未排序的记录中选择最小的记录作为有序序列部分的下一个记录。

(10)【◆题库问题◆】：[判断题] 广义表的组成元素可以是不同形式的元素。
A．正确
B．错误

【◆参考答案◆】：正确