线性表（a1，a2，…，an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。

(1)【◆题库问题◆】：[单选] 线性表（a1，a2，…，an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。
A．O（i）
B．O（1）
C．O（n）
D．O（i-1）

【◆参考答案◆】：C

(2)【◆题库问题◆】：[单选] 空串与空格字符组成的串的区别在于（）
A．没有区别
B．两串的长度不相等
C．两串的长度相等
D．两串包含的字符不相同

【◆参考答案◆】：B

(3)【◆题库问题◆】：[名词解释] 双向链表

【◆参考答案◆】：
线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点的直接后继，一个指向该结点的直接前驱，这种方式构成的链表，即为双向链表。

(4)【◆题库问题◆】：[判断题] KMP算法时间代价为O（n）。
A．正确
B．错误

【◆参考答案◆】：正确

(5)【◆题库问题◆】：[填空题] 在具有n个元素的循环队列中，队满时具有（）个元素。

【◆参考答案◆】：n-1

(6)【◆题库问题◆】：[判断题] 冒泡排序算法关键字比较的次数与记录的初始排列次序无关
A．正确
B．错误

【◆参考答案◆】：正确

(7)【◆题库问题◆】：[单选] 下列对于线性链表的描述中正确的是（）。
A．存储空间不一定是连续，且各元素的存储顺序是任意的
B．存储空间不一定是连续，且前件元素一定存储在后件元素的前面
C．存储空间必须连续，且前件元素一定存储在后件元素的前面
D．存储空间必须连续，且各元素的存储顺序是任意的

【◆参考答案◆】：A

(8)【◆题库问题◆】：[判断题] 对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足以下关系：E=I+3n，其中n是内部结点个数。
A．正确
B．错误

【◆参考答案◆】：正确

(9)【◆题库问题◆】：[单选] 下面哪一方法可以判断出一个有向图是否有环（回路）（）。
A．求节点的度
B．拓扑排序
C．求最短路径
D．求关键路径

【◆参考答案◆】：B

(10)【◆题库问题◆】：[问答题,简答题] 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19；②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

【◆参考答案◆】：用队列长度计算公式：（N＋r－F)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32