链表的每个结点中都恰好包含一个指针。

(1)【◆题库问题◆】：[判断题] 链表的每个结点中都恰好包含一个指针。
A．正确
B．错误

【◆参考答案◆】：正确

【◆答案解析◆】：链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

(2)【◆题库问题◆】：[单选] 关于杂凑查找说法不正确的有几个（）。（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集
A．1
B．2
C．3
D．4

【◆参考答案◆】：B

(3)【◆题库问题◆】：[单选] 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
A．O（n）
B．O（nlog2n）
C．O（1）
D．O（n2）

【◆参考答案◆】：C

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

【◆参考答案◆】：
子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。

(5)【◆题库问题◆】：[填空题] 三叉链表比二叉链表多一个指向（）的指针域。

【◆参考答案◆】：双亲结点

(6)【◆题库问题◆】：[填空题] n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。

【◆参考答案◆】：O(n+e)

(7)【◆题库问题◆】：[名词解释] 串

【◆参考答案◆】：
由零个或者多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串。字符在序列中的序号为该字符的位置。

(8)【◆题库问题◆】：[单选] 希尔排序的增量序列必须是（）。
A．递增的
B．递减的
C．随机的
D．非递减的

【◆参考答案◆】：B

【◆答案解析◆】：排序又名缩小增量排序，增量就是指每趟排序当中进行直接插入排序的子序列间的间隔，增量序列则是从第一趟排序开始每趟排序中选择的所有间隔，要求从大到小，单调递减。

(9)【◆题库问题◆】：[填空题] 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈的容量至少应该是（）。

【◆参考答案◆】：3

(10)【◆题库问题◆】：[判断题] 数组元素的下标值越大，存取时间越长
A．正确
B．错误

【◆参考答案◆】：正确