二、综合应用题
## 二、综合应用题
01. 在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法以实现上述操作。
02. 试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法（假设该结点唯一）。
03. 试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为 $O(1)$。
04. 设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有处于给定的两个值（作为函数参数给出）之间的元素（若存在）。
05. 给定两个单链表，试分析找出两个链表的公共结点的思想（不用写代码）。
06. 设 $C = \{a_{1}, b_{1}, a_{2}, b_{2}, \dots, a_{m}, b_{n}\}$ 为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 $A = \{a_{1}, a_{2}, \dots, a_{n}\}$ ， $B = \{b_{n}, \dots, b_{2}, b_{1}\}$ 。
07. 在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如 (7, 10,
<!-- page: 56 -->
2027年数据结构考研复习指导
10, 21, 30, 42, 42, 42, 51, 70) 将变为 (7, 10, 21, 30, 42, 51, 70)。
08. 设 $A$ 和 $B$ 是两个单链表（带头结点），其中元素递增有序。设计一个算法从 $A$ 和 $B$ 中的公共元素产生单链表 $C$，要求不破坏 $A$、$B$ 的结点。
09. 已知两个链表 $A$ 和 $B$ 分别表示两个集合，其元素递增排列。编制函数，求 $A$ 与 $B$ 的交集，并存放于 $A$ 链表中。
10. 两个整数序列 $A = a_{1}, a_{2}, a_{3}, \dots, a_{m}$ 和 $B = b_{1}, b_{2}, b_{3}, \dots, b_{n}$ 已经存入两个单链表中，设计一个算法，判断序列 $B$ 是否是序列 $A$ 的连续子序列。
11. 设计一个算法用于判断带头结点的循环双链表是否对称。
12. 有两个循环单链表，链表头指针分别为 $h_1$ 和 $h_2$，编写一个函数将链表 $h_2$ 链接到链表 $h_1$ 之后，要求链接后的链表仍保持循环链表形式。
13. 设有一个带头结点的非循环双链表 L，其每个结点中除有 pre、data 和 next 域外，还有一个访问频度域 freq，其值均初始化为零。每当在链表中进行一次 Locate (L, x) 运算时，令值为 x 的结点中 freq 域的值增 1，并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate (L, x) 函数，返回找到结点的地址，类型为指针型。
14. 设将 $n (n > 1)$ 个整数存放到不带头结点的单链表 $L$ 中，设计算法将 $L$ 中保存的序列循环右移 $k (0 < k < n)$ 个位置。例如，若 $k = 1$，则将链表 $\{0, 1, 2, 3\}$ 变为 $\{3, 0, 1, 2\}$。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
15. 单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（通常单链表的最后一个结点的指针域是空的）。试编写算法判断单链表是否存在环。
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
16. 设有一个长度 $n$（$n$ 为偶数）的不带头结点的单链表，且结点值都大于 0，设计算法求这个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，对于第 $i$ 个结点（从 0 开始），其孪生结点为第 $n - i - 1$ 个结点。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。
3）说明你的算法的时间复杂度和空间复杂度。
17. 【2009统考真题】已知一个带有表头结点的单链表，结点结构为
| data | link |
| --- | --- |
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 $k$ 个位置上的结点（$k$ 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、$\mathrm{C}++$ 或 Java 语言实现），关键之处请给出简要注释。
<!-- page: 57 -->
第2章 线性表
45
18. 【2012统考真题】假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being 的存储映像如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 [data|next]，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求： 1）给出算法的基本设计思想。 2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度。 19. 【2015统考真题】用单链表保存 $m$ 个整数，结点的结构为 [data][link]，且 $|data| \leqslant n$（$n$ 为正整数）。现要求设计一个时间上尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
则删除结点后的 head 为
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
要求：
1）给出算法的基本设计思想。
2）使用 C 或 C++ 语言，给出单链表结点的数据类型定义。
3）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
4）说明你所设计算法的时间复杂度和空间复杂度。
20. 【2019统考真题】设线性表 $L = (a_{1}, a_{2}, a_{3}, \dots, a_{n-2}, a_{n-1}, a_{n})$ 采用带头结点的单链表保存，链表中的结点定义如下：
请设计一个空间复杂度为 $O(1)$ 且时间上尽可能高效的算法，重新排列 $L$ 中的各结点，得到线性表 $L' = (a_{1}, a_{n}, a_{2}, a_{n-1}, a_{3}, a_{n-2}, \dots)$ 。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
3）说明你所设计的算法的时间复杂度。
## 2.3.8 答案与解析
### 一、单项选择题
#### 01. B
两种存储结构适用于不同的场合，不能简单地说谁好谁坏，说法 I 错误。链式存储用指针表
<!-- page: 58 -->
2027年数据结构考研复习指导
示逻辑结构，而指针的设置是任意的，因此比顺序存储结构能更方便地表示各种逻辑结构，说法II正确。在顺序存储中，插入和删除结点需要移动大量元素，效率较低，说法III的描述刚好相反。顺序存储结构既能随机存取又能顺序存取，而链式结构只能顺序存取，说法IV正确。
02. B
首先直接排除选项 A 和 D。散列存储通过散列函数映射到物理空间，不能反映数据之间的逻辑关系，排除选项 C。链式存储能方便地表示各种逻辑关系，且插入和删除操作的时间复杂度为 $O(1)$。
03. A
链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续。
04. D
顺序存储方式同样适用于存储图和树，说法I错误。删除表尾结点时，必须从头开始找到表尾结点的前驱，其时间与表长有关，说法II错误。循环单链表中最后一个结点的指针不是NULL，而是指向头结点，整个链表形成一个环，因此不存在空指针，说法III正确。有序单链表只能依次查找插入位置，时间复杂度为 $O(n)$，说法IV正确。队列需要在表头删除元素，表尾插入元素，采用带尾指针的循环链表较为方便，插入和删除的时间复杂度都为 $O(1)$，说法V正确。
05. A
对于选项A，在单链表和顺序表上实现的时间复杂度都为 $O(n)$，但后者要移动很多元素，因此在单链表上实现效率更高。对于选项B和D，顺序表的效率更高。C无区别。
06. C
s插入后，q成为s的前驱，而p成为s的后继，选择选项C。
注意
可能有读者认为选项 C 中的两条语句交换后才正确。实际上，因为本题插入位置的前后结点都有指针指示（这与前面介绍的插入操作是不同的），所以选项 C 中的语句顺序并不会造成断链。在此提醒读者在学习过程中一定要多动脑思考，而不要生搬硬套。
07. D
若先建立链表，然后依次插入建立有序表，则每插入一个元素就需遍历链表寻找插入位置，即直接插入排序，时间复杂度为 $O(n^{2})$。若先将数组排好序，然后建立链表，建立链表的时间复杂度为 $O(n)$，数组排序的最好时间复杂度为 $O(n\log_2n)$，总时间复杂度为 $O(n\log_2n)$。故选择选项D。
08. C
先遍历长度为 $m$ 的单链表，找到该单链表的尾结点，然后将其 next 域指向另一个单链表的首结点，其时间复杂度为 $O(m)$。
09. C
单链表设置头结点的目的是方便运算的实现，主要好处体现在：第一，有头结点后，插入和删除数据元素的算法就统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素；第二，不论链表是否为空，其头指针是指向头结点的非空指针，链表的头指针不变，因此空表和非空表的处理也就统一了。
10. B
删除单链表的最后一个结点需置其前驱结点的指针域为 NULL，需要从头开始依次遍历找到该前驱结点，需要 $O(n)$ 的时间，与表长有关。其他操作均与表长无关，读者可自行模拟。
11. B, A
在带头结点的单链表中，头指针 head 指向头结点，头结点的 next 域指向第一个元素结点，head->next==NULL 表示该单链表为空。在不带头结点的单链表中，head 直接指向第一个元素结点，head==NULL 表示该单链表为空。
<!-- page: 59 -->
第2章 线性表
47
12. D
线性表有顺序存储和链式存储两种存储结构。若采用链式存储结构，则删除元素 $a_{50}$ 不需要移动元素；若采用顺序存储结构，则需要依次移动50个元素。
13. B
当采用头插法建立单链表时，数组后面的元素插入到单链表 $L$ 的最前端，所以 $L$ 中的元素次序与数组 $a$ 的元素次序相反。
14. C
选项 A 显然错误。选项 B 中第一个元素和最后一个元素不满足题设要求。双链表能很方便地访问前驱和后继，故删除和插入数据较为方便，选项 C 正确。选项 D 未考虑顺序存储的情况。
15. D
为了在 $p$ 之前插入结点 $q$，可以将 $p$ 的前一个结点的 next 域指向 $q$，将 $q$ 的 next 域指向 $p$，将 $q$ 的 prior 域指向 $p$ 的前一个结点，将 $p$ 的 prior 域指向 $q$。仅选项 D 满足条件。
16. A
与上一题的分析基本类似，只不过这里是删除一个结点，注意将p的前、后两结点链接起来。关键是要保证在结点指针的修改过程中不断链！
注意，请读者仔细对比上述两题，弄清双链表的插入和删除方法。
17. A
结点 $A$ 和 $B$ 分别由指针 $p$ 和 $q$ 指示，但结点 $C$ 仅能由 $p->next$ 间接指示，因此在改变 $p->next$ 之前，必须先将 $q->next$ 指向结点 $C$，即①要在③前面，且④要在③前面（因为若先执行③，则④相当于 $q->prior$ 指向其自身，显然矛盾）。故只能选择选项 A。
18. C
当在双链表的两个结点（分别用第一个、第二个结点表示）之间插入一个新结点时，需要修改四个指针域，分别是：新结点的前驱指针域，指向第一个结点；新结点的后继指针域，指向第二个结点；第一个结点的后继指针域，指向新结点；第二个结点的前驱指针域，指向新结点。
19. B
设单链表递增有序，首先要在单链表中找到第一个大于 $x$ 的结点的直接前驱 $p$，在 $p$ 之后插入该结点。查找的时间复杂度为 $O(n)$，插入的时间复杂度为 $O(1)$，总时间复杂度为 $O(n)$。
20. D
在插入和删除操作上，单链表和双链表都不用移动元素，都很方便，但双链表修改指针的操作更为复杂，选项 A 错误。双链表中可以快速访问任何一个结点的前驱和后继结点，选项 D 正确。
21. C
带头结点的循环单链表 L 为空表时，满足 $L->next==L$，即头结点的指针域与 L 的值相等，而不是头结点的指针域与 L 的地址相等。注意，带头结点的循环单链表中不存在空指针。
22. D
循环双链表 L 判空的条件是头结点（头指针）的 prior 和 next 域都指向它自身。
23. A
在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。而寻找尾结点及尾结点的前驱结点时，只有带头结点的循环双链表所需要的时间最少。
24. C
对于选项 A，删除尾结点 *p 时，需要找到 *p 的前一个结点，时间复杂度为 $O(n)$。对于选项 B，删除首结点 *p 时，需要找到 *p 结点，这里没有直接给出头结点指针，而是通过尾结点的 prior 指针找到 *p 结点的时间复杂度为 $O(n)$。对于选项 D，删除尾结点 *p 时，需要找到 *p 的前一个结点，时间复杂度为 $O(n)$。对于 C，执行这四种算法的时间复杂度均为 $O(1)$。
<!-- page: 60 -->
2027年数据结构考研复习指导
25. B
要求用 $O(1)$ 的时间将两个循环单链表头尾相接，并未指明哪个链表接在另一个链表之后，所以对两个链表都要在 $O(1)$ 的时间找到头结点和尾结点。因此，两个指针应都指向尾结点。
26. A
在循环单链表中，删除首元结点后，要保持链表的循环性，因此需要找到首元结点的前驱。当链表带头结点时，其前驱就是头结点，因此不论是表头指针还是表尾指针，删除首元结点的时间都为 $O(1)$。当链表不带头结点时，其前驱是尾结点，因此，若有表尾指针，就可在 $O(1)$ 的时间找到尾结点；若只有表头指针，则需要遍历整个链表找到尾结点，时间为 $O(n)$。
27. D
对一个空循环单链表，有 head->next==head，推理 head->next->next==head->next==head。对含有一个元素的循环单链表，头结点（头指针 head 指示）的 next 域指向这个唯一的元素结点，该元素结点的 next 域指向头结点，因此也有 head->next->next=head。
28. D
对于两种双链表，删除首结点的时间复杂度都是 $O(1)$。对于非循环双链表，删除尾结点的时间复杂度是 $O(n)$；对于循环双链表，删除尾结点的时间复杂度是 $O(1)$。
29. D
对于选项 A，在最后一个元素之后插入元素的情况与普通单链表相同，时间复杂度为 $O(n)$；而删除第一个元素时，为保持循环单链表的性质（尾结点指向第一个结点），要先遍历整个链表找到尾结点，再做删除操作，时间复杂度为 $O(n)$。对于选项 B，双链表的情况与单链表的相同，一个是 $O(n)$，一个是 $O(1)$。对于选项 C，在最后一个元素之后插入一个元素，要遍历整个链表才能找到插入位置，时间复杂度为 $O(n)$；删除第一个元素的时间复杂度为 $O(1)$。对于选项 D，与选项 A 的分析对比，有尾结点的指针，省去了遍历链表的过程，因此时间复杂度均为 $O(1)$。
30. B
静态链表采用数组表示，因此需要预先分配较大的连续空间，静态链表同时还具有一般链表的特点，即插入和删除不需要移动元素。
31. B
静态链表的存储空间虽然是顺序分配的，但元素的存储不是顺序的，查找时仍然需要按链依次进行，而插入、删除都不需要移动元素。静态链表的存储空间是一次性申请的，能容纳的最大元素个数在定义时就已确定。并非每个空间都存储了元素，因此会造成存储空间的浪费。
32. D
选项 A 的第二句代码，相当于将 p 前驱结点的后继指针指向其自身，错误；选项 B 和 C 的第一句代码，相当于将 p 后继结点的前驱指针指向其自身，错误。只有选项 D 正确。
33. D
根据存储状态，单链表的结构如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
其中“链接地址”是指结点 next 所指的内存地址。当结点 f 插入后，a 指向 f，f 指向 e，e 指向 b。显然 a、e 和 f 的“链接地址”分别是 f、b 和 e 的内存地址，即 1014H、1004H 和 1010H。 34. D 如图 1 所示，要删除带头结点的非空循环单链表中的第一个元素，就要先用临时指针 q 指向待 <!-- page: 61 --> 第2章线性表 49 删结点，q=h->next；然后将q从链表中断开，h->next=q->next（这一步也可写成h->next=h->next->next）；此时要考虑一种特殊情况，若待删结点是链表的尾结点，即循环单链表中只有一个元素（p和q指向同一个结点），如图2所示，则在删除后要将尾指针指向头结点，即if (p==q) p=h；最后释放q结点即可，答案选择选项D。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2 ## 35. C 链表的插入操作要保证不会造成断链，画图再依次判断选项。执行语句“① s->next=p->next；② p->next=s；”后的结构如下图所示（虚线表示prev，实线表示next）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
对于选项A，s->next->prev=p，错误。对于选项B，p->next->prev=s，让s的prev指向s，错误。对于选项D，两句代码均错误。对于选项C，执行语句“③ s->prev=s->next->prev；④ s->next->prev=s；”后的结构如下图所示，满足插入的要求。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 36. D 假设单链表L的初始状态如图①所示。执行q=p->next后的状态如图②所示，q指向p的后继结点。执行p->next=q->next后的状态如图③所示，结点p的next指向q的后继结点。执行q->next=h->next后的状态如图④所示，结点q的next指向h的后继结点。执行h->next=q后的状态如图⑤所示，q所指结点移至L的头结点h之后，选项D正确。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 二、综合应用题 ## 01. 【解答】 解法1：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x，则删 <!-- page: 62 --> 2027年数据结构考研复习指导 除，并让 p 移向下一个结点，否则让 pre、p 指针同步后移一个结点。 本题代码如下：本算法是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为 x。实际上，这个条件是可以任意指定的，只要修改 if 条件即可。比如，我们要求删除值介于 mink 和 maxk 之间的所有结点，只需将 if 语句修改为 if (p->data > mink && p->data < maxk)。 解法 2：采用尾插法建立单链表。用 p 指针扫描 L 的所有结点，当其值不为 x 时，将其链接到 L 之后，否则将其释放。 本题代码如下：void Del_X_1(Linklist &amp;L,ElemType x) { LNode *p=L-&gt;next, *pre=L, *q; //置 p 和 pre 的初始值 while (p != NULL) { if (p-&gt;data == x) { q = p; //q 指向被删结点 p = p-&gt;next; pre-&gt;next = p; //将 *q 结点从链表中断开 free(q); //释放 *q 结点的空间 } else { //否则，pre 和 p 同步后移 pre = p; p = p-&gt;next; } //else } //while }上述两个算法扫描一遍链表，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。void Del_X_2(Linklist &amp;L,ElemType x) { LNode *p=L-&gt;next, *r=L, *q; //r 指向尾结点，其初值为头结点 while (p != NULL) { if (p-&gt;data != x) { //*p 结点值不为 x 时将其链接到 L 尾部 r-&gt;next = p; r = p; p = p-&gt;next; //继续扫描 } else { //*p 结点值为 x 时将其释放 q = p; p = p-&gt;next; //继续扫描 free(q); //释放空间 } } //while r-&gt;next = NULL; //插入结束后置尾结点指针为 NULL }