练习题

一、填空题

1.在顺序表中插入或删除一个元素，需要平均移动____________元素，具体移动的元素个数与____________有关。

2.顺序表中逻辑上相邻的元素的物理位置____________紧邻，单链表中逻辑上相邻的元素的物理位置_____________紧邻。

3.在单链表中除了首元结点外，任意结点位置由____________指示。

4.在单链表中设置头结点的作用是____________。

二、简答题

1.简述以下算法的功能。

2.指出以下算法中的错误和低效之处，并把它改写为一个既正确又高效的算法。

3.试写一算法，对单链表实现就地逆置。

4.假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。

5.画出执行下列各语句后各指针及链表的示意图。

6.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

（a）在P结点后插入S结点的语句序列：

（b）在P结点前插入S结点的语句序列：

（c）删除P结点的直接后继结点的语句序列：

（d）删除P结点的直接前驱结点的语句序列：

（e）删除P结点的语句序列：

（1）P－next＝P－next－next；

（2）P－prior＝p－prior－prior；

（3）P－next＝S；

（4）P－prior＝S；

（5）S－next＝P；

（6）S－prior＝P；

（7）S－next＝P－next；

（8）S－prior＝P－prior；

（9）P－prior－next＝P－next；

（10）P－prior－next＝P；

（11）P－next－prior＝P；

（12）P－next－prior＝S；

（13）P－prior－next＝S；

（14）P－next－prior＝p－prior；

（15）Q＝P－next；

（16）Q＝P－prior；

（17）free（P）；

（18）free（Q）；

7.试编写一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。

8.设有一个双向循环链表，每个结点中除有pre、data和next三个域外还增设了一个访问频度域freq，其值均初始化为零，而每当对链表进行一次LOCATE（L，x）操作后被访问的结点中的频度域的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作算法。