设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。

(1)【◆题库问题◆】：[单选] 设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。
A．O（m）
B．O（n）
C．O（m*n）
D．O（nlog2m）

【◆参考答案◆】：A

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

【◆参考答案◆】：
类似于树的层次遍历，从顶点v出发，访问了V之后依次访问v的各个未被访问过的邻接顶点。再依次访问它们的邻接点，并使先被访问的顶点的的邻接点先于后访问的顶点的邻接点。直到图中所有已被访问顶点的邻接点都被访问到。如果图中还有顶点未被访问，则另选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问。

(3)【◆题库问题◆】：[判断题] 完全二叉树某结点有右子树，则必然有左子树。
A．正确
B．错误

【◆参考答案◆】：正确

(4)【◆题库问题◆】：[名词解释] 回路

【◆参考答案◆】：
第一个顶点和最后一个顶点相同的路径称为回路或环。

(5)【◆题库问题◆】：[单选] 顺序表中，插入一个元素所需移动的元素平均数是（）。
A．（n-1）/2
B．n
C．n+1
D．（n+1）/2

【◆参考答案◆】：D

(6)【◆题库问题◆】：[单选] 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
A．O（1）
B．O（log2n）
C．O（n4）
D．O（n2）

【◆参考答案◆】：B

(7)【◆题库问题◆】：[判断题] 采用不同的遍历方法，所得到的无向图的生成树总是相同的。
A．正确
B．错误

【◆参考答案◆】：正确

(8)【◆题库问题◆】：[判断题] 对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点
A．正确
B．错误

【◆参考答案◆】：正确

(9)【◆题库问题◆】：[单选] 按照“后进先出”原则组织数据的数据结构是（）
A．队列
B．栈
C．双向链表
D．二叉树

【◆参考答案◆】：B

(10)【◆题库问题◆】：[单选] 一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。
A．1，2，3，4
B．4，3，2，1
C．1，4，3，2
D．3，4，1，2

【◆参考答案◆】：A