一、基础知识题
2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
2.2 何时选用顺序表、何时选用链表作为线性表的结构为宜?
2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
2.4 为什么在单循环链表中设置尾指针比设置头指针更好?
2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去?若可以，其时间复杂度各为多少?
2.6 下述算法的功能是什么?
LinkList Demo
return L;
}// Demo
二、算法设计题
2.7 设线性表的n个结点定义为，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList。
2.8 试分别用顺序表和单链表作为存储结构，实现将线性表就地逆置的操作，所谓"就地"指辅助空间应为O。
2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
2.10 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
2.11写一算法在单链表上实现线性表的ListLength运算。
2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O，请分析算法的时间复杂度。
2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。
2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点s的直接前趋结点。
2.17 已知由单链表表示的线性表中，含有三类字符的数据元素，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 |
