单链表

(1)【◆题库问题◆】：[名词解释] 单链表

【◆参考答案◆】：
每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接后继结点的地址（指针），称为指针域，元素的存储空间可以连续，也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。

(2)【◆题库问题◆】：[名词解释] 平衡因子

【◆参考答案◆】：
该结点的左子树深度减去它的右子树深度。

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

【◆参考答案◆】：B

(4)【◆题库问题◆】：[判断题] 强连通分量是有向图中的极大强连通子图。
A．正确
B．错误

【◆参考答案◆】：正确

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

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

(6)【◆题库问题◆】：[单选] 设单循环链表中结点的结构为（data，link），且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是（）。
A．current->link=null
B．first->link=current
C．first=current
D．current->link=first

【◆参考答案◆】：D

(7)【◆题库问题◆】：[判断题] 在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p－＞next；
A．正确
B．错误

【◆参考答案◆】：正确

(8)【◆题库问题◆】：[填空题] 函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype *e){LinkList p；int j；p=L->next;j=1;while(p&&ji)return ERROR;*e= (2) ;return OK;}

【◆参考答案◆】：(1)p=p->next (2)p->data

(9)【◆题库问题◆】：[判断题] 折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树
A．正确
B．错误

【◆参考答案◆】：正确

(10)【◆题库问题◆】：[单选] 对一个算法的评价，不包括如下（）方面的内容。
A．健壮性和可读性
B．并行性
C．正确性
D．时空复杂度

【◆参考答案◆】：B