线索

(1)【◆题库问题◆】：[名词解释] 线索

【◆参考答案◆】：
在二叉树的存储结构中，必有N+1空域，利用这些空域存放某种遍历的前驱和后继，其中指向前驱和后继的指针叫线索。

(2)【◆题库问题◆】：[填空题] 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。

【◆参考答案◆】：20.5；41

(3)【◆题库问题◆】：[单选] 以下数据结构中，（）是线性结构。
A．哈希表
B．二叉树
C．有向图
D．串

【◆参考答案◆】：D

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

【◆参考答案◆】：3

(5)【◆题库问题◆】：[名词解释] 算法设计的要求

【◆参考答案◆】：
正确性、可读性、健壮性、效率与低存储量需求。

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

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

(7)【◆题库问题◆】：[判断题] 链式存储的线性表可以随机存取
A．正确
B．错误

【◆参考答案◆】：正确

(8)【◆题库问题◆】：[判断题] 一个广义表的表头总是一个广义表
A．正确
B．错误

【◆参考答案◆】：正确

(9)【◆题库问题◆】：[名词解释] 查找

【◆参考答案◆】：
在数据集合中寻找满足某种条件的数据元素的过程称为查找。

(10)【◆题库问题◆】：[名词解释] 判定树

【◆参考答案◆】：
树中每个结点表示表中的一个记录，结点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为判定树。