一、单选题（共 20 道试题，共 40 分。）V 1. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（）
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF
满分：2 分
2. 折半搜索与二叉搜索树的时间性能()
A. 相同
B. 完全不同
C. 有时不相同
D. 数量级都是O（log2n）
满分：2 分
3. 深度优先遍历类似于二叉树的()
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
满分：2 分
4. 单链表的存储密度（）
A. 大于1
B. 等于1
C. 小于1
D. 不能确定
满分：2 分
5. 在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ）
A. ＡＳＬ＝ｎ
B. ＡＳＬ＝（ｎ＋１）／２
C.
D.
满分：2 分
6. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
A. n-1
B. n
C. n+1
D. n+2
满分：2 分
7. 二叉树是非线性数据结构，所以（）
A. 它不能用顺序存储结构存储
B. 它不能用链式存储结构存储
C. 顺序存储结构和链式存储结构都能存储
D. 顺序存储结构和链式存储结构都不能使用
满分：2 分
8. 具有n(n>0)个结点的完全二叉树的深度为（ ）
A.
B.
C.
D.
满分：2 分
9. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
A.
B.
C.
D.
满分：2 分
10. 有8个结点的无向连通图最少有（）条边
A. 5
B. 6
C. 7
D. 8
满分：2 分
11.
已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A.
0 1 3 2
B.
0 2 3 1
C.
0 3 2 1
D.
0 1 2 3
满分：2 分
12.
已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A.
0 2 4 3 1 6 5
B. 0 1 3 5 6 4 2
C. 0 1 2 3 4 6 5
D.
0 1 2 3 4 5 6
满分：2 分
13. 串是一种特殊的线性表，其特殊性体现在（）
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链式存储
D. 数据元素可以是多个字符
满分：2 分
14. 引入二叉线索树的目的是（ ）
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一
满分：2 分
15.
已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
A.
0 2 4 3 1 5 6
B.
0 1 3 6 5 4 2
C.
0 4 2 3 1 6 5
D.
0 3 6 1 5 4 2
满分：2 分
16. 用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A. 栈
B. 队列
C. 树
D. 图
满分：2 分
17. 判定一个队列QU（最多元素为m0）为满队列的条件是（）
A.
QU->rear － QU->front = = m0
B. QU->rear － QU->front －1= = m0
C. QU->front = = QU->rear
D. QU->front = = QU->rear+1
满分：2 分
18. 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
A. 从小到大排列好的
B. 从大到小排列好的
C. 元素无序
D. 元素基本有序
满分：2 分
19. 从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
A. 希尔排序
B. 归并排序
C. 插入排序
D. 选择排序
满分：2 分
20. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A. 1/2
B. 1
C. 2
D. 4
满分：2 分