17. 【解答】
## 17. 【解答】 1）算法的基本设计思想： 问题的关键是设计一个尽可能高效的算法，通过链表的一次遍历，找到倒数第 $k$ 个结点的位置。定义两个指针变量 $p$ 和 $q$，初始时均指向头结点的下一个结点（链表的第一个结点），$p$ 指针沿链表移动；当 $p$ 指针移动到第 $k$ 个结点时，$q$ 指针开始与 $p$ 指针同步移动；当 $p$ 指针移动到最后一个结点时，$q$ 指针所指示结点为倒数第 $k$ 个结点。以上过程对链表仅进行一遍扫描。 2）算法的详细实现步骤如下： ① count=0，p 和 q 指向链表表头结点的下一个结点。 ② 若 $p$ 为空，转⑤。 ③ 若 count 等于 k，则 q 指向下一个结点；否则，count=count+1。 ④ $p$ 指向下一个结点，转②。 ⑤ 若 count 等于 $k$，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 $k$ 值超过了线性表的长度，查找失败，返回 0。 ⑥ 算法结束。 3）算法实现如下：## 评分说明 若所给算法采用一遍扫描方式就能得到正确结果，则可给满分15分；若采用两遍或多遍扫描才能得到正确结果，则最高分为10分。若采用递归算法得到正确结果，则最高给10分；若实现算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，则最高给10分。 ## 18. 【解答】 顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 $k$ 个结点，我们先在长链表上遍历 $k$ 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。因为两个链表从第一个公共结点到 <!-- page: 72 --> 2027年数据结构考研复习指导 链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。 1）算法的基本设计思想： ① 分别求出 str1 和 str2 所指的两个链表的长度 $m$ 和 $n$。 ② 将两个链表以表尾对齐：令指针 $p$、$q$ 分别指向 $\mathrm{str1}$ 和 $\mathrm{str2}$ 的头结点，若 $m \geqslant n$，则指针 $p$ 先走，使 $p$ 指向链表中的第 $m - n + 1$ 个结点；若 $m < n$，则使 $q$ 指向链表中的第 $n - m + 1$ 个结点，即使指针 $p$ 和 $q$ 所指的结点到表尾的长度相等。 ③ 反复将指针 $p$ 和 $q$ 同步向后移动，并判断它们是否指向同一结点。当 $p$、$q$ 指向同一结点，则该点即所求的共同后缀的起始地址。 2）本题代码如下：typedef int ElemType; //链表数据的类型定义 typedef struct LNode{ //链表结点的结构定义 ElemType data; //结点数据 struct LNode *link; //结点链接指针 }LNode, *LinkList; int Search_k{LinkList list, int k} { LNode *p=list-&gt;link, *q=list-&gt;link; //指针 p、q 指示第一个结点 int count=0; while (p != NULL) { //遍历链表直到最后一个结点 if (count &lt; k) count++; //计数，若 count &lt; k 只移动 p else q = q-&gt;link; p = p-&gt;link; //之后让 p、q 同步移动 } //while if (count &lt; k) return 0; //查找失败返回 0 else { printf("%d", q-&gt;data); return 1; } }3）时间复杂度为 $O(\mathrm{len1} + \mathrm{len2})$ 或 $O(\max(\mathrm{len1}, \mathrm{len2}))$，其中 len1、len2 分别为两个链表的长度。 ## 19. 【解答】 1）算法的基本设计思想： - 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。 - 因为 $|\mathrm{data}| \leqslant n$，故辅助数组 $q$ 的大小为 $n + 1$，各元素的初值均为 0。依次扫描链表中的各结点，同时检查 $q[|\mathrm{data}|]$ 的值，若为 0 则保留该结点，并令 $q[|\mathrm{data}|] = 1$；否则将该结点从链表中删除。 2）使用 C 语言描述的单链表结点的数据类型定义：typedef struct Node{ char data; struct Node *next; } SNode; /*求链表长度的函数*/ int listlen(SNode *head) { int len = 0; while (head-&gt;next != NULL) { len++; head = head-&gt;next; } return len; } /*找出共同后缀的起始地址*/ SNode * find_list(SNode * str1, SNode * str2) { int m, n; SNode * p, * q; m = listlen(str1); //求 str1 的长度，O(m) n = listlen(str2); //求 str2 的长度，O(n) for (p = str1; m &gt; n; m--) //若 m &gt; n，使 p 指向链表中的第 m - n + 1 个结点 p = p-&gt;next; for (q = str2; m &lt; n; n--) //若 m &lt; n，使 q 指向链表中的第 n - m + 1 个结点 q = q-&gt;next; while (p-&gt;next != NULL &amp;&amp; p-&gt;next != q-&gt;next) { //查找共同后缀的起始地址 p = p-&gt;next; //两个指针同步向后移动 q = q-&gt;next; } return p-&gt;next; //返回共同后缀的起始地址 }3）算法实现如下：typedef struct node { int data; struct node *link; } <!-- page: 73 --> 第2章 线性表 61 ```c }NODE; Typedef NODE *PNODE;4）参考答案所给算法的时间复杂度为 $O(m)$，空间复杂度为 $O(n)$。 20. 【解答】 1）算法的基本设计思想： 先观察 $L = (a_{1}, a_{2}, a_{3}, \dots, a_{n-2}, a_{n-1}, a_{n})$ 和 $L' = (a_{1}, a_{n}, a_{2}, a_{n-1}, a_{3}, a_{n-2}, \dots)$，发现 $L'$ 是由 $L$ 摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素，需要先将 $L$ 后半段原地逆置［题目要求空间复杂度为 $O(1)$，不能借助栈］，否则每取最后一个结点都需要遍历一次链表。① 先找出链表 $L$ 的中间结点，为此设置两个指针 $p$ 和 $q$，指针 $p$ 每次走一步，指针 $q$ 每次走两步，当指针 $q$ 到达链尾时，指针 $p$ 正好在链表的中间结点；② 然后将 $L$ 的后半段结点原地逆置。③ 从单链表前后两段中依次各取一个结点，按要求重排。 2）算法实现如下：void func (PNODE h, int n) { PNODE p = h, r; int *q, m; q = (int *)malloc(sizeof(int) * (n + 1)); //申请 n + 1 个位置的辅助空间 for (int i = 0; i &lt; n + 1; i++) //数组元素初值置 0 *(q + i) = 0; while (p-&gt;link != NULL) { m = p-&gt;link-&gt;data &gt; 0; p-&gt;link-&gt;data; if (*(q + m) == 0) { *(q + m) = 0; } //判断该结点的 data 是否已出现过 *(q + m) = 1; } //首次出现 p = p-&gt;link; } //保留 } else { //重复出现 r = p-&gt;link; p-&gt;link = r-&gt;link; free(r); } } free(q); }3）第一步找中间结点的时间复杂度为 $O(n)$，第二步逆置的时间复杂度为 $O(n)$，第三步合并链表的时间复杂度为 $O(n)$，所以该算法的时间复杂度为 $O(n)$。 ## 归纳总结 本章是算法设计题的重点考查内容。线性表相关的算法题通常代码量较小，却蕴含一定的设计技巧，非常适合用于笔试考查。此类题目常采用“三段式”结构命题。 在给出题目背景和具体要求的前提下： ① 给出算法的基本设计思想。 ② 采用C或C++语言描述算法，关键之处给出注释。 ③ 分析所设计算法的时间复杂度和空间复杂度。 算法具体的设计思路灵活多变，难以一概而论。因此读者务必勤加练习，反复研读本章的典型例题，尝试用多种方法求解，并对比其时间与空间效率，从而逐步掌握各类题型的分析视角与最优解法。为此，编者整理了几种常用的算法设计技巧，供参考：针对链表，常用方法包括头插法、尾插法、逆置法、归并法、双指针法等，需根据具体问题灵活运用；针对顺序表，因其支持随机访问，常结合经典排序与查找策略进行设计，如归并排序、二分查找等。 ## 注意 在算法设计题中，若能正确定义数据结构并清晰阐述算法思想，通常可获得至少一半的分数；若能进一步用规范代码实现，则得分更有保障；逻辑较复杂的部分可直接用文字说明，确保思路完整。 ## 思维拓展 一个长度为 $n$ 的整型数组 $A[1\dots n]$，给定整数 $x$，设计一个时间复杂度不超过 $O(n\log_2n)$ 的算法，查找出这个数组中所有两两之和等于 $x$ 的整数对（每个元素只输出一次）。 提示：本题若想到排序，则问题便迎刃而解。先用一种时间复杂度为 $O(n\log_2n)$ 的排序算法将 $A[1\dots n]$ 从小到大排序，然后分别从数组的小端 $(i = 1)$ 和大端 $(j = n)$ 开始查找；若 $A[i] + A[j] < x$，$i++$；若 $A[i] + A[j] > x$，$j--$；否则输出 $A[i]$、$A[j]$，然后 $i++$，$j--$；直到 $i>=j$ 时停止。 请读者思考本题是否有其他求解算法。 <!-- page: 75 --> 第3章 # 栈、队列和数组 ## 【考纲内容】 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）多维数组的存储 （五）特殊矩阵的压缩存储 （六）栈、队列和数组的应用 ## 【知识框架】void change_list(NODE * h) { NODE *p, *q, *r, *s; p = q = h; while (q-&gt;next != NULL) { //寻找中间结点 p = p-&gt;next; //p走一步 q = q-&gt;next; //p 所指结点为中间结点，q 为后半段链表的首结点 p-&gt;next = NULL; while (q != NULL) { //将链表后半段逆置 r = q-&gt;next; q-&gt;next = p-&gt;next; p-&gt;next = q; q = r; } s = h-&gt;next; //s指向前半段的第一个数据结点，即插入点 q = p-&gt;next; //q指向后半段的第一个数据结点 p-&gt;next = NULL; while (q != NULL) { //将链表后半段的结点插入到指定位置 <!-- page: 74 --> 2027年数据结构考研复习指导 ```txt r=q-&gt;next; //r指向后半段的下一个结点 q-&gt;next=s-&gt;next; //将q所指结点插入到s所指结点之后 s-&gt;next=q; s=q-&gt;next; //s指向前半段的下一个插入点 q=r; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
视频讲解
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 【复习提示】
本章通常以选择题形式考查，题目难度不大，但命题方式较为灵活。其中，栈（如入栈/出栈过程、出栈序列的合法性）和队列的操作及其特征是考查重点。由于二者都是线性表的典型应用与推广，也常出现在算法设计题中。此外，栈和队列的顺序存储与链式存储及其特点、双端队列的特性、栈和队列的常见应用，以及数组与特殊矩阵的压缩存储，均为必须掌握的内容。
## 3.1 栈
### 3.1.1 栈的基本概念
#### 1. 栈的定义
考点图1 栈的特点（2017）
栈（Stack）是仅允许在一端进行插入和删除操作的线性表。作为一种特殊的线性表，栈的插入（入栈）和删除（出栈）操作被限制在表的一端进行，如图3.1所示。
<!-- page: 76 -->
2027年数据结构考研复习指导
栈顶（Top）：允许进行插入和删除操作的一端。
栈底（Bottom）：固定不变、不允许进行插入和删除操作的另一端。
安栈：不含任何元素的栈。
**考虑点击** 出入栈序列的分析（2010、2011、2013、2018、2020、2022）
假设某栈 $S = (a_{1}, a_{2}, a_{3}, a_{4}, a_{5})$，如图3.1所示，其中 $a_{1}$ 为栈底元素，$a_{5}$ 为栈顶元素。栈的入栈和出栈操作只能在栈顶进行。若元素按顺序 $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}$ 入栈，则出栈顺序为 $a_{5}, a_{4}, a_{3}, a_{2}, a_{1}$。由此可见，栈的操作特性可概括为后进先出（Last In First Out，LIFO）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.1 栈的示意图
**注意**
每接触一种新的数据结构，都应从其逻辑结构、存储结构和基本运算三方面进行系统理解。
## 2. 栈的基本操作
不同教材对基本操作的命名略有差异，但含义基本一致，本文采用严蔚敏教材的命名规范。
- InitStack(&S)：初始化一个空栈 S。
- StackEmpty(S)：判断栈是否为空。若栈 S 为空，返回 true；否则返回 false。
- Push(&S, x)：入栈操作；若栈未满，则 x 成为新的栈顶元素。
- Pop(&S, &x)：出栈操作；若栈非空，则弹出栈顶元素，并通过 x 返回该值。
- GetTop(S, &x)：读取栈顶元素但不出栈；若栈非空，则通过 x 返回栈顶元素。
- DestroyStack(&S)：销毁栈 S，并释放其所占用的存储空间（&表示引用调用）。
在解答算法题时，若题目未作特殊限制，可直接使用上述基本操作函数。
**考虑点击** Catalan 数的应用（2015）
栈的数学性质：当 $n$ 个不同元素按固定次序入栈时，可能的出栈序列总数为 $\frac{1}{n+1} C_{2n}^{n}$。该数列称为卡特兰（Catalan）数，可通过数学归纳法证明，有兴趣的读者可参考组合数学教材。
## 3.1.2 栈的顺序存储结构
与线性表类似，栈也有两种基本的存储方式：顺序存储和链式存储。
### 1. 顺序栈的实现
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放从栈底到栈顶的数据元素，并附设一个整型指针（top）指示当前栈顶元素的位置。
顺序栈的类型可定义如下
栈顶指针：S.top，初始时设为 S.top=-1；栈顶元素：S.data[S.top]。
入栈操作：当栈未满时，先将栈顶指针加 1，再将元素存入栈顶。
出栈操作：当栈非空时，先取出栈顶元素，再将栈顶指针减 1。
栈空条件：S.top==-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。
另一种常见的方式是：栈顶指针初始化为 S.top=0；入栈时先将元素存入栈顶，再将栈顶指针加 1；出栈时先将栈顶指针减 1，再取出栈顶元素；栈空条件为 S.top==0；栈满条件为
<!-- page: 77 -->
第3章 栈、队列和数组
65
S.top==MaxSize。
顺序栈的入栈操作受数组上界约束。若对栈的最大使用空间估计不足，则可能发生栈上溢，此时，应向用户报告错误信息，以便及时处理，避免程序异常。
## 注意
栈和队列的判空、判满条件，会因实际给出的条件不同而变化，下面的代码实现是在栈顶指针初始化为-1的条件下的相应方法，而其他情况则需具体问题具体分析。
## 2. 顺序栈的基本操作
**等式图15** $\succ$ 出/入栈操作的模拟（2009）
栈操作的示意图如图3.2所示，图3.2(a)为空栈，图3.2(c)为A、B、C、D、E依次入栈后的状态，图3.2(d)为在图3.2(c)基础上E、D、C相继出栈后的结果，此时栈中剩余2个元素。尽管C、D、E可能仍保留在原存储单元中，但top指针已指向新的栈顶，因此它们已不属于当前栈的内容。读者应结合该图理解栈顶指针的作用：它标识了栈中有效元素的边界。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 空栈
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 1个元素
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 5个元素
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d) 2个元素 图3.2 栈顶指针和栈中元素之间的关系 以下是顺序栈常用基本操作的实现（基于top=-1初始化）。 （1）初始化 （2）判栈空 （3）入栈（4）出栈bool Push(SqStack &amp;S, ElemType x) { if (S.top==MaxSize-1) //栈满，报错 return false; S.data[++S.top]=x; //指针先加1，再入栈 return true; }该操作不改变栈的状态，栈顶元素依然保留在栈中。 ## 注意 此处，top指向栈顶元素本身。因此入栈为S.data[++S.top]=x，出栈为x=S.data[S.top--]。若top初始化为0（指向栈顶元素的下一个位置），则入栈变为S.data[S.top++]=x，出栈变为x=S.data[--S.top]，相应的判空、判满条件也随之改变。请读者仔细体会差异，做题时务必根据题目设定灵活应时。 ## 3. 共享栈 利用栈底位置相对固定的特性，可让两个顺序栈共享同一段一维数组空间，将两个栈的栈底分别置于数组两端，栈顶向中间延伸，如图3.3所示。bool Pop(SqStack &amp;S, ElemType &amp;x) { if (S.top==-1) //栈空，报错 return false; x=S.data[S.top--]; //先出栈，指针再减1 return true; } <!-- page: 78 --> 2027年数据结构考研复习指导 ## （5）读栈顶元素 ```c bool GetTop(SqStack S,ElemType &amp;x) { if (S.top == -1) //栈空，报错 return false; x = S.data[S.top]; //x 记录栈顶元素 return true; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.3 两个顺序栈共享存储空间 0号栈栈顶指针为top0，1号栈栈顶指针为top1，均指向各自的栈顶元素；初始时top0=-1（0号栈空），top1=MaxSize（1号栈空）；栈满条件为top1-top0==1（两栈顶相邻）。当0号栈入栈时，top0先加1，再赋值；当1号栈入栈时，top1先减1，再赋值；出栈操作的顺序相反。 共享栈能更高效地利用存储空间，两个栈的空间可动态调节，仅当整个数组被占满时，才发生栈溢出。其存取数据的时间复杂度均为 $O(1)$，对存取效率无影响。