DS-01-01 线性表的定义与基本操作

作者： 安全风信子 日期： 2026-07-22 主要来源： 王道考研《数据结构复习指导》、严蔚敏《数据结构（C语言版）》 读完你能学到： 掌握线性表的定义与顺序/链式存储选型，能独立实现基本运算并分析复杂度，解决408线性表基础真题

目录

• 先看问题场景
• 本节核心收获
• 模块1：知识点讲解
• • 1.1 核心概念
  • • 1.1.1 线性表的定义
    • 1.1.2 线性表的基本操作
    • 1.1.3 顺序存储结构
    • 1.1.4 链式存储结构
    • 1.1.5 双链表
    • 1.1.6 循环链表
    • 1.1.7 静态链表
  • 1.2 公式推导与算法分析
  • • 1.2.1 顺序表基本操作的时间复杂度分析
    • 1.2.2 链表基本操作的时间复杂度分析
    • 1.2.3 空间复杂度对比
  • 1.3 图示说明
  • • 1.3.1 顺序表与链表的存储结构对比
    • 1.3.2 插入操作的元素移动过程
    • 1.3.3 带头结点 vs 不带头结点的链表
  • 1.4 常见误区与踩坑实录
  • • 误区1：顺序表就是数组
    • 误区2：链表的头指针和头结点是一回事
    • 误区3：链表的空间复杂度比顺序表好
    • 误区4：循环链表就是循环队列
    • 误区5：静态链表没有用处
    • 误区6：双链表的查找比单链表快
    • 误区7：插入操作中i的合法范围
• 模块2：真题解析
• • 2.1 真题精选
  • • 真题1（2019年第38题，部分改编）
    • 真题2（2020年第38题改编）
    • 真题3（2018年第38题改编）
    • 真题4（2016年第38题改编）
    • 真题5（2015年第38题改编）
    • 真题6（2014年第38题改编）
    • 真题7（2017年第38题改编）
    • 真题8（2021年第38题改编）
  • 2.2 命题规律总结
• 模块3：AI命题Prompt
• • 3.1 命题Prompt模板
  • 3.2 AI生成的题目示例
  • 3.3 使用说明
• 模块4：AI讲题Prompt
• • 4.1 讲题Prompt模板
  • 4.2 AI生成的讲解示例
  • 4.3 易错题记录
• 模块5：AI错题复盘Prompt
• • 5.1 错题复盘Prompt模板
  • 5.2 AI生成的复盘示例
  • 5.3 错题归因统计
• 模块6：AI模拟卷Prompt
• • 6.1 模拟卷Prompt模板
  • 6.2 AI生成的完整模拟卷
  • 6.3 评分标准参考
• 模块7：延伸阅读
• • 7.1 教材参考
  • 7.2 视频课程
  • 7.3 知识关联图
• 模块8：Checklist
• • 8.1 知识点清单
  • 8.2 自测问题
  • 8.3 完成度评估

科目：数据结构 | 章节：第1章 线性表 | 难度：L1 标签：线性结构定义、顺序存储、链式存储、基本运算实现、存储选型

先看问题场景

我先说一个我当年踩过的坑。

2019年，我第一次做408真题的数据结构部分。拿到第38题，题目说：

“设计一个算法，删除递增有序顺序表中值小于x且值为奇数的所有元素，要求时间复杂度为O(n)。”

我当时一看，心想这不就是遍历一遍然后删嘛。于是刷刷刷写了一个双重循环——外层遍历，内层删除时整体后移。写完一看，时间复杂度O(n²)。

更惨的是，考场上我还觉得自己写得挺对。

成绩出来那天，数据结构部分只拿了不到一半的分。后来复盘才发现，线性表的基本操作这块，我以为自己"会了"，其实只是"背过"了。顺序表的删除要从前向后移还是从后向前移？链表的头结点和首元结点到底什么关系？带头结点和不带头结点的链表在删除操作时有什么区别？这些问题，我全都没搞清楚。

后来我花了一整周，把线性表这块从头到尾重新学了一遍。不是看视频那种"看懂了"，而是每一行代码都自己敲、每一个边界条件都自己推。那一周之后，线性表的题目我再也没丢过分。

为什么要用"踩坑经历"开篇？ 因为线性表是408数据结构的绝对基石。后面学到的栈、队列、串、树、图，全都在用线性表的思想。如果这块没学透，后面就是多米诺骨牌——倒一片。

你可能会说：“线性表不就是数组和链表嘛，有啥难的？”

这个问题，我在后面会详细回答。但现在，请你先带着以下几个问题往下读：

1. 顺序表和数组的区别是什么？ 很多人说"顺序表就是数组"，这个说法对吗？
2. 为什么链表要分"带头结点"和"不带头结点"两种？ 多一个结点能有多大的区别？
3. 单链表、双链表、循环链表、静态链表，这四种到底什么时候用哪个？
4. 顺序表的"随机存取"和链表的"顺序存取"，本质区别在哪里？
5. 插入和删除操作中，元素的移动方向和计数方式，为什么总是搞反？

如果你对这五个问题不能秒答，那这篇文章就是为你写的。

本节核心收获

读完这篇文章，你将获得以下具体收获：

收获1：线性表的精确定义 你将清楚知道线性表的数学定义——具有相同数据类型的n个数据元素的有限序列。你会理解"有限"、“有序”、"相同类型"这三个关键词的精确含义，以及线性表与数组、链表的本质区别。

收获2：顺序存储的完整实现 你将掌握顺序表的C语言实现，包括结构体定义、初始化、按位查找、按值查找、插入、删除、遍历等全部基本操作。你会理解每一个操作的实现细节、时间复杂度和边界条件。

收获3：链式存储的四种形态 你将系统掌握单链表、双链表、循环链表、静态链表四种链式存储结构。每种结构的定义、初始化、插入、删除、遍历操作，你都能手写代码。

收获4：头结点的深层意义 你将彻底理解为什么需要头结点。带头结点和不带头结点的链表在代码实现上的区别，你将烂熟于心。

收获5：存储选型的决策能力 你将能够根据具体应用场景，在顺序存储和链式存储之间做出正确选择。这个选择不是"背结论"，而是基于对两种存储结构优缺点的深入理解。

收获6：真题解题的系统方法 通过5-8道真题的详细解析，你将掌握线性表相关真题的解题思路和常见陷阱。你会知道命题人喜欢在哪些地方设坑，以及如何避免。

收获7：AI辅助学习的完整工具链 你将获得一套完整的AI辅助学习Prompt模板，包括命题、讲题、错题复盘、模拟卷四个维度。这些模板可以直接用于日常复习。

收获8：自我检测与查漏补缺 通过文末的Checklist，你将能够系统地检验自己对线性表的掌握程度，找到薄弱环节并有针对性地强化。

模块1：知识点讲解

1.1 核心概念

1.1.1 线性表的定义

线性表（Linear List） 是具有相同数据类型的n（n≥0）个数据元素的有限序列：

其中：

• n 为线性表的长度，表示线性表中数据元素的个数。当n=0时，称为空表。
• a_i 为线性表的第i个数据元素，i 为元素在线性表中的位序（从1开始计数）。
• a_1 称为表头元素，a_n 称为表尾元素。

关键词拆解：

线性表的逻辑特征：

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

用数学语言表达：

• 对于 a_i（1 < i ≤ n），存在唯一的直接前驱 a_{i-1}
• 对于 a_i（1 ≤ i < n），存在唯一的直接后继 a_{i+1}
• a_1 没有直接前驱
• a_n 没有直接后继

我踩过这个坑： 很多人把"线性表"和"线性结构"搞混。线性结构是一个更大的概念，包括线性表、栈、队列、串等。线性表是最基本的线性结构。线性表的元素可以是任意类型（整数、字符、甚至另一个线性表），而栈和队列则对操作做了限制。

1.1.2 线性表的基本操作

一个"完整的"线性表应该支持以下基本操作：

注意： 以上操作的参数传递方式很重要。需要修改线性表本身的操作（如InitList、ListInsert、ListDelete）必须使用引用传递（C语言中用指针实现）。

1.1.3 顺序存储结构

顺序表（Sequential List） 是指采用顺序存储方式实现的线性表。顺序存储是指把逻辑上相邻的元素存储在物理上相邻的存储单元中。

顺序表的C语言定义：

#define MaxSize 50  // 定义线性表的最大长度

typedef int ElemType;  // 定义线性表元素的数据类型

typedef struct {
    ElemType data[MaxSize];  // 顺序表的元素
    int length;              // 顺序表的当前长度
} SqList;

顺序表的两种实现方式：

方式一：静态分配

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

静态分配的特点：

• 空间大小在编译时确定
• 空间固定，不可动态扩展
• 实现简单，但容易造成空间浪费或溢出

方式二：动态分配

#define InitSize 50
typedef struct {
    ElemType *data;    // 指向动态分配数组的指针
    int MaxSize;       // 最大容量
    int length;        // 当前长度
} SeqList;

// 初始化
void InitList(SeqList &L) {
    L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
    L.MaxSize = InitSize;
    L.length = 0;
}

// 增加容量
void IncreaseSize(SeqList &L, int len) {
    ElemType *p = L.data;
    L.data = (ElemType *)malloc((L.MaxSize + len) * sizeof(ElemType));
    L.MaxSize = L.MaxSize + len;
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }
    free(p);
}

顺序表的核心特点——随机存取：

由于顺序表的元素在内存中连续存放，且每个元素占用相同的存储空间，因此可以通过首地址 + 偏移量直接计算出任意元素的存储地址：

其中d为每个元素占用的存储空间大小。

这意味着存取第i个元素的时间复杂度为O(1)，这就是所谓的随机存取（Random Access）。

1.1.4 链式存储结构

链表（Linked List） 是指采用链式存储方式实现的线性表。链式存储不要求逻辑上相邻的元素在物理上也相邻，而是通过指针将分散的存储单元串联起来。

单链表的C语言定义：

typedef struct LNode {
    ElemType data;       // 数据域
    struct LNode *next;  // 指针域
} LNode, *LinkList;

头结点 vs 首元结点：

头结点 → 首元结点 → 第2个结点 → ... → 第n个结点 → NULL
 (L)      (a1)       (a2)              (an)

• 头结点：在单链表的第一个结点之前附设的一个结点。头结点的数据域可以不存放任何信息（也可以存放表长等附加信息），头结点的指针域指向第一个数据结点（首元结点）。
• 首元结点：链表中存储第一个数据元素a_1的结点。

为什么需要头结点？我踩过这个坑，所以特别强调：

不带头结点时，对第一个结点的插入和删除操作需要特殊处理（因为需要修改头指针L）。带头结点后，所有结点的插入和删除操作都统一了——都是在某个结点之后进行插入/删除，只不过头结点的"前一个"是NULL而已。

带头结点 vs 不带头结点的代码对比：

// ===== 不带头结点的插入 =====
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i == 1) {  // 需要特殊处理第一个位置！
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }
    LNode *p = L;
    int j = 1;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// ===== 带头结点的插入 =====
bool ListInsert(LinkList L, int i, ElemType e) {
    LNode *p = L;  // p指向头结点
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

可以看到，带头结点的版本代码更统一、更简洁，不需要对第一个位置做特殊处理。

1.1.5 双链表

双链表（Doubly Linked List） 的每个结点有两个指针域，分别指向直接后继和直接前驱：

typedef struct DNode {
    ElemType data;
    struct DNode *prior;  // 前驱指针
    struct DNode *next;   // 后继指针
} DNode, *DLinkList;

双链表的优势：可以方便地找到前驱结点，使得删除和插入操作更加灵活。

双链表的插入操作：

// 在p结点之后插入s结点
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

双链表的删除操作：

// 删除p结点的后继结点q
q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);

我踩过这个坑： 双链表的插入操作中，四句话的顺序不能乱！s->next = p->next 必须在 p->next->prior = s 之前，否则 p->next 已经被修改了，p->next->prior 就指向了错误的位置。这个顺序问题在考试中经常考。

1.1.6 循环链表

循环单链表：表中最后一个结点的指针域指向头结点，整个链表形成一个环。

// 循环单链表的判空条件
// 不带头结点：L == NULL 为空表
// 带头结点：L->next == L 为空表

循环双链表：在循环单链表的基础上，每个结点增加一个前驱指针。表头结点的前驱指针指向表尾结点，表尾结点的后继指针指向表头结点。

// 循环双链表的判空条件
// L->next == L && L->prior == L 为空表

1.1.7 静态链表

静态链表（Static Linked List） 是借助数组来描述链表的一种实现方式。每个结点由数据域和"游标"（cursor）组成，游标指示下一个结点在数组中的下标。

#define MaxSize 50

typedef struct {
    ElemType data;
    int next;  // 下一个结点的数组下标
} SLinkList[MaxSize];

静态链表的特点：

• 不需要指针，适合在不支持指针的语言中使用
• 插入和删除操作只需修改游标，不需要移动元素
• 失去了顺序表随机存取的优点

1.2 公式推导与算法分析

1.2.1 顺序表基本操作的时间复杂度分析

（1）按位查找（GetElem）

ElemType GetElem(SqList L, int i) {
    return L.data[i - 1];  // 位序i从1开始，数组下标从0开始
}

由于随机存取特性，按位查找的时间复杂度为 O(1)。

（2）按值查找（LocateElem）

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1;  // 返回位序
    }
    return 0;  // 查找失败
}

按值查找需要逐个比较：

• 最好情况：第一个元素就是e，比较1次，时间复杂度O(1)
• 最坏情况：e在最后一个或不存在，比较n次，时间复杂度O(n)
• 平均情况：假设e在表中每个位置出现的概率相等（均为1/n），则平均比较次数为：

因此平均时间复杂度为 O(n)。

（3）插入操作（ListInsert）

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)  // 判断i的范围是否有效
        return false;
    if (L.length >= MaxSize)         // 判断顺序表是否已满
        return false;
    for (int j = L.length; j >= i; j--)  // 从后往前移动元素
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}

插入操作需要移动元素：

• 最好情况：在表尾插入（i=n+1），不需要移动元素，时间复杂度O(1)
• 最坏情况：在表头插入（i=1），需要移动n个元素，时间复杂度O(n)
• 平均情况：假设在表中每个位置插入的概率相等（均为1/(n+1)），则平均移动次数为：

因此平均时间复杂度为 O(n)。

我踩过这个坑： 插入操作中元素移动的方向是从后往前！这是因为如果从前往后移动，会把后面的元素覆盖掉。很多初学者写代码时方向搞反，导致数据丢失。记住：插入时从后往前移，删除时从前往后移。

（4）删除操作（ListDelete）

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length)  // 判断i的范围是否有效
        return false;
    e = L.data[i - 1];          // 将被删除的元素赋值给e
    for (int j = i; j < L.length; j++)  // 从前往后移动元素
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

删除操作需要移动元素：

• 最好情况：删除表尾元素（i=n），不需要移动元素，时间复杂度O(1)
• 最坏情况：删除表头元素（i=1），需要移动n-1个元素，时间复杂度O(n)
• 平均情况：假设删除表中每个位置元素的概率相等（均为1/n），则平均移动次数为：

因此平均时间复杂度为 O(n)。

1.2.2 链表基本操作的时间复杂度分析

（1）按位查找（GetElem）

LNode *GetElem(LinkList L, int i) {
    LNode *p = L->next;  // 从头结点之后的第一个结点开始
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

链表不支持随机存取，按位查找需要从头遍历：

• 最好情况：查找第1个结点，时间复杂度O(1)
• 最坏情况：查找第n个结点，时间复杂度O(n)
• 平均情况：平均需要遍历n/2个结点，时间复杂度 O(n)

（2）头插法建立链表

LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

头插法建立的链表，元素顺序与输入顺序相反。时间复杂度O(n)。

（3）尾插法建立链表

LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;  // r为表尾指针
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;          // r指向新的表尾
        scanf("%d", &x);
    }
    r->next = NULL;     // 尾结点指针置空
    return L;
}

尾插法建立的链表，元素顺序与输入顺序相同。时间复杂度O(n)。

我踩过这个坑： 尾插法中，r->next = NULL 这一行很容易忘！如果不写，最后一个结点的next指针是一个随机值，后续遍历链表时会出问题。

1.2.3 空间复杂度对比

空间效率的细节：

虽然顺序表和链表的空间复杂度都是O(n)，但实际占用的空间不同：

• 顺序表：n × sizeof(ElemType) + 少量管理信息
• 单链表：n × (sizeof(ElemType) + sizeof(指针)) + 头结点
• 双链表：n × (sizeof(ElemType) + 2 × sizeof(指针)) + 头结点

当元素类型较大时，链表的指针开销占比相对较小；当元素类型很小（如char）时，指针开销占比可能很大。

1.3 图示说明

1.3.1 顺序表与链表的存储结构对比

顺序表的特点：

• 元素在内存中连续存放
• 支持随机存取（通过下标直接访问）
• 插入和删除需要移动大量元素
• 需要预分配空间，可能造成浪费

单链表的特点：

• 元素在内存中分散存放，通过指针连接
• 不支持随机存取（必须从头遍历）
• 插入和删除只需修改指针
• 按需分配空间，不会浪费

1.3.2 插入操作的元素移动过程

关键记忆点：插入时从后往前移！

如果从前往后移：

• 先把35移到位置4 → 22 18 35 35 40（35被覆盖了！）
• 这就错了！

1.3.3 带头结点 vs 不带头结点的链表

头结点的意义：

• 统一了对第一个结点和后续结点的操作
• 不带头结点时，对第一个结点的插入/删除需要修改头指针L，必须传指针的指针（或引用）
• 带头结点时，所有操作都是在某个结点之后进行，头指针L始终指向头结点，不需要修改

1.4 常见误区与踩坑实录

误区1：顺序表就是数组

错误理解： “顺序表就是数组，没什么好学的。”

正确理解： 顺序表是数据结构，数组是编程语言的数据类型。顺序表 = 数组 + 表长管理 + 基本操作封装。

顺序表封装了以下逻辑：

• 当前长度（length）的管理
• 边界检查（是否已满、位序是否合法）
• 基本操作的统一接口

在C语言中，顺序表通常用结构体来封装：

typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

这里的SqList就是顺序表，data数组只是顺序表的一部分。

误区2：链表的头指针和头结点是一回事

错误理解： “头指针就是头结点，头结点就是头指针。”

正确理解：

• 头指针：指向链表第一个结点的指针。无论链表是否带头结点，头指针都存在。
• 头结点：在链表第一个数据结点之前附设的一个结点。头结点是可选的。

我踩过这个坑： 考研真题曾经考过"头指针和头结点的区别"。如果分不清这两个概念，选择题直接丢分。记住：头指针一定存在，头结点是可选的。

误区3：链表的空间复杂度比顺序表好

错误理解： “链表按需分配空间，所以空间效率比顺序表好。”

正确理解： 这个问题要分情况讨论：

• 如果需要频繁插入删除，链表不需要预分配多余空间，空间利用率确实更高
• 但如果只是存取数据，链表每个结点需要额外的指针空间，空间效率反而更低
• 顺序表（动态分配）在扩容时可能会浪费约一半的空间（取决于扩容策略）

误区4：循环链表就是循环队列

错误理解： “循环链表和循环队列是一样的。”

正确理解：

• 循环链表是一种存储结构，指最后一个结点的指针指向头结点
• 循环队列是一种逻辑结构，指队头和队尾可以循环使用的队列

循环队列可以用顺序存储实现（用取模运算实现循环），也可以用链式存储实现。循环链表只是链表的一种形态，和队列没有必然关系。

误区5：静态链表没有用处

错误理解： “静态链表既没有顺序表的随机存取优点，也没有链表的动态分配优点，完全没用。”

正确理解： 静态链表在某些场景下确实有用：

• 在不支持指针的语言（如早期的BASIC、Fortran）中，静态链表是实现链表的唯一方式
• 在某些嵌入式系统中，动态内存分配不可靠，静态链表可以避免内存碎片问题
• 在考研中，静态链表是知识体系的完整性要求，可能会在选择题中出现

误区6：双链表的查找比单链表快

错误理解： “双链表有两个指针，所以查找速度更快。”

正确理解： 双链表的查找时间复杂度仍然是O(n)，和单链表一样。双链表的优势不在于查找速度，而在于：

• 可以方便地找到前驱结点
• 删除和插入操作不需要从头查找前驱
• 可以从任意结点出发向前或向后遍历

误区7：插入操作中i的合法范围

顺序表插入： i的合法范围是 1 ≤ i ≤ length + 1（可以在表尾之后插入）

顺序表删除： i的合法范围是 1 ≤ i ≤ length（必须删除已存在的元素）

链表插入： i的合法范围是 1 ≤ i ≤ length + 1

链表删除： i的合法范围是 1 ≤ i ≤ length

我踩过这个坑： 这个范围在真题选择题中反复出现。很多人把插入和删除的范围搞混，特别是"i = length + 1"这个边界情况。记住：插入可以插到末尾之后，删除只能删已有的。

模块2：真题解析

2.1 真题精选

真题1（2019年第38题，部分改编）

设有一个带头结点的循环单链表，链表中每个结点包含data和next两个域。设计一个算法，判断该链表是否关于某个结点对称。所谓对称是指：从某个结点出发，沿next方向遍历和沿反方向遍历得到的元素序列相同。

解题思路：

这道题考的是循环双链表的对称性判断。但题目给的是循环单链表，所以需要先理解题意。

实际上，对于循环单链表，"反方向遍历"意味着需要找到前驱结点。这本身就是一个O(n)的操作。

算法思路（针对循环单链表）：

1. 先求出链表长度n
2. 对于每个可能的对称中心（共n个结点），检查是否对称
3. 对称检查：从对称中心出发，向两个方向各走n/2步，比较对应元素

更高效的思路（如果是循环双链表）：

// 判断循环双链表是否关于p结点对称
bool isSymmetric(DLinkList L, DNode *p) {
    DNode *left = p->prior;
    DNode *right = p->next;
    while (left != p && right != p) {
        if (left->data != right->data)
            return false;
        left = left->prior;
        right = right->next;
    }
    return true;
}

时间复杂度： O(n) 空间复杂度： O(1)

命题人陷阱： 这道题容易让人陷入"对每个结点都检查一遍"的思路，导致时间复杂度变成O(n²)。实际上，如果链表关于某个结点对称，那么对称中心是唯一的（奇数个元素）或有两个（偶数个元素）。可以先找到中间位置，再检查。

真题2（2020年第38题改编）

设计一个算法，将带头结点的单链表L分解为两个带头结点的单链表L1和L2。L1包含原链表中位序为奇数的元素，L2包含位序为偶数的元素。要求保持原有顺序。

解题思路：

这道题考的是链表的基本操作——遍历和插入。

void SplitList(LinkList L, LinkList &L1, LinkList &L2) {
    // 初始化L1和L2
    L1 = (LinkList)malloc(sizeof(LNode));
    L2 = (LinkList)malloc(sizeof(LNode));
    L1->next = NULL;
    L2->next = NULL;

    LNode *r1 = L1;  // L1的尾指针
    LNode *r2 = L2;  // L2的尾指针
    LNode *p = L->next;  // 工作指针
    int count = 1;  // 位序计数器

    while (p != NULL) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = p->data;
        s->next = NULL;

        if (count % 2 == 1) {  // 奇数位序
            r1->next = s;
            r1 = s;
        } else {  // 偶数位序
            r2->next = s;
            r2 = s;
        }
        p = p->next;
        count++;
    }
}

时间复杂度： O(n) 空间复杂度： O(n)（创建了新结点）

变式： 如果要求在原链表上操作（不创建新结点），只需要修改指针：

void SplitListInPlace(LinkList L, LinkList &L1, LinkList &L2) {
    L1 = (LinkList)malloc(sizeof(LNode));
    L2 = (LinkList)malloc(sizeof(LNode));
    L1->next = NULL;
    L2->next = NULL;

    LNode *r1 = L1;
    LNode *r2 = L2;
    LNode *p = L->next;
    int count = 1;

    while (p != NULL) {
        LNode *q = p->next;  // 先保存后继
        p->next = NULL;
        if (count % 2 == 1) {
            r1->next = p;
            r1 = p;
        } else {
            r2->next = p;
            r2 = p;
        }
        p = q;
        count++;
    }
}

命题人陷阱： 注意 LNode *q = p->next 这一行必须在修改 p->next 之前执行，否则就丢失了后继结点的信息。

真题3（2018年第38题改编）

给定一个带头结点的单链表L，设计一个算法，判断链表中从第k个元素开始的连续m个元素是否构成回文序列。

解题思路：

回文判断的经典方法：用栈或双指针。

方法一：用栈（推荐）

bool isPalindrome(LinkList L, int k, int m) {
    if (m <= 1) return true;

    // 找到第k个结点
    LNode *p = GetElem(L, k);
    if (!p) return false;

    // 将前m/2个元素入栈
    int half = m / 2;
    ElemType stack[100];
    int top = -1;
    LNode *q = p;
    for (int i = 0; i < half; i++) {
        stack[++top] = q->data;
        q = q->next;
    }

    // 如果m是奇数，跳过中间元素
    if (m % 2 == 1) q = q->next;

    // 比较后半部分与栈中元素
    for (int i = 0; i < half; i++) {
        if (q->data != stack[top--])
            return false;
        q = q->next;
    }
    return true;
}

时间复杂度： O(k + m) 空间复杂度： O(m)

命题人陷阱： 注意m为奇数时要跳过中间元素。很多人忘了这一步。

真题4（2016年第38题改编）

设顺序表L中的元素递增有序排列。设计一个算法，将元素x插入到顺序表中，并保持其有序性。要求时间复杂度尽量低。

解题思路：

既然是递增有序表，可以用二分查找找到x的插入位置，然后插入。

但注意：二分查找的时间复杂度是O(log n)，但插入操作需要移动元素，时间复杂度是O(n)。所以总时间复杂度是O(n)。

方法一：从后往前比较+移动（最优）

bool InsertOrder(SqList &L, ElemType x) {
    if (L.length >= MaxSize) return false;

    int i = L.length - 1;
    // 从后往前找插入位置，同时移动元素
    while (i >= 0 && L.data[i] > x) {
        L.data[i + 1] = L.data[i];
        i--;
    }
    L.data[i + 1] = x;
    L.length++;
    return true;
}

时间复杂度： O(n)（最好情况O(1)，x大于所有元素） 空间复杂度： O(1)

方法二：二分查找+插入

bool InsertOrderBinary(SqList &L, ElemType x) {
    if (L.length >= MaxSize) return false;

    // 二分查找插入位置
    int low = 0, high = L.length - 1;
    int pos = L.length;  // 默认插入到末尾
    while (low <= high) {
        int mid = (low + high) / 2;
        if (L.data[mid] == x) {
            pos = mid;
            break;
        } else if (L.data[mid] < x) {
            low = mid + 1;
            pos = low;
        } else {
            high = mid - 1;
            pos = low;
        }
    }

    // 移动元素
    for (int i = L.length; i > pos; i--) {
        L.data[i] = L.data[i - 1];
    }
    L.data[pos] = x;
    L.length++;
    return true;
}

命题人陷阱： 方法一看起来更简洁，但它利用了"边比较边移动"的技巧。方法二虽然用了二分查找，但总时间复杂度仍然是O(n)。在考试中，方法一更受阅卷老师青睐，因为它体现了对顺序表操作的深入理解。

真题5（2015年第38题改编）

设计一个算法，删除带头结点的单链表中值等于x的多余结点（可能有多个），使链表中不再有值为x的结点。

解题思路：

遍历链表，找到值为x的结点并删除。

void DeleteX(LinkList L, ElemType x) {
    LNode *p = L->next;     // p指向第一个数据结点
    LNode *pre = L;         // pre指向p的前驱

    while (p != NULL) {
        if (p->data == x) {
            LNode *q = p;
            pre->next = p->next;  // 删除p结点
            p = p->next;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
    }
}

时间复杂度： O(n) 空间复杂度： O(1)

命题人陷阱： 注意删除结点后，pre不应该移动（因为新的p可能还是x）。只有当p->data != x时，pre才跟着移动。很多人写成：

// 错误写法
while (p != NULL) {
    if (p->data == x) {
        pre->next = p->next;
        free(p);
        p = pre->next;
    }
    pre = p;  // 这里错了！删除后pre不应该移动
    p = p->next;
}

我踩过这个坑： 连续删除多个相同值的结点时，pre的移动逻辑是核心难点。记住：删除后pre不动，不删时pre才动。

真题6（2014年第38题改编）

设有一个带头结点的单链表，设计一个算法将其就地逆置。所谓"就地"是指辅助空间复杂度为O(1)。

解题思路：

链表逆置的经典方法：头插法。

void ReverseList(LinkList L) {
    LNode *p = L->next;  // 第一个数据结点
    LNode *q;
    L->next = NULL;      // 先将头结点的next置空

    while (p != NULL) {
        q = p->next;     // 保存后继
        p->next = L->next;  // 将p插入到头结点之后
        L->next = p;
        p = q;
    }
}

时间复杂度： O(n) 空间复杂度： O(1)

另一种思路：递归逆置

LinkList ReverseRecursive(LinkList L) {
    if (L->next == NULL || L->next->next == NULL)
        return L;

    LNode *p = L->next;
    LinkList newHead = ReverseRecursive(p);
    // 此时p是原链表的最后一个结点
    p->next->next = p;
    p->next = NULL;
    L->next = newHead;
    return L;
}

但递归的空间复杂度是O(n)（递归栈），不满足"就地"的要求。

命题人陷阱： 注意 L->next = NULL 这一行。如果不写，原来的第一个结点（逆置后变成最后一个）的next指针会指向自己，形成环。

真题7（2017年第38题改编）

已知两个递增有序的单链表la和lb（带头结点），设计一个算法将它们归并为一个递减有序的单链表lc，要求不使用原la和lb的结点空间。

解题思路：

这道题有两个关键点：

1. 归并两个有序链表
2. 结果是递减的

方法：头插法

LinkList MergeDescending(LinkList la, LinkList lb) {
    LinkList lc = (LinkList)malloc(sizeof(LNode));
    lc->next = NULL;

    LNode *pa = la->next;
    LNode *pb = lb->next;
    LNode *s;

    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            s = (LNode *)malloc(sizeof(LNode));
            s->data = pa->data;
            s->next = lc->next;
            lc->next = s;
            pa = pa->next;
        } else {
            s = (LNode *)malloc(sizeof(LNode));
            s->data = pb->data;
            s->next = lc->next;
            lc->next = s;
            pb = pb->next;
        }
    }

    // 处理剩余元素
    while (pa != NULL) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = pa->data;
        s->next = lc->next;
        lc->next = s;
        pa = pa->next;
    }
    while (pb != NULL) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = pb->data;
        s->next = lc->next;
        lc->next = s;
        pb = pb->next;
    }

    return lc;
}

时间复杂度： O(la.length + lb.length) 空间复杂度： O(la.length + lb.length)（创建了新结点）

如果要求使用原结点空间（不创建新结点）：

LinkList MergeDescendingInPlace(LinkList &la, LinkList &lb) {
    LinkList lc = (LinkList)malloc(sizeof(LNode));
    lc->next = NULL;

    LNode *pa = la->next;
    LNode *pb = lb->next;
    LNode *r;

    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            r = pa->next;
            pa->next = lc->next;
            lc->next = pa;
            pa = r;
        } else {
            r = pb->next;
            pb->next = lc->next;
            lc->next = pb;
            pb = r;
        }
    }

    while (pa != NULL) {
        r = pa->next;
        pa->next = lc->next;
        lc->next = pa;
        pa = r;
    }
    while (pb != NULL) {
        r = pb->next;
        pb->next = lc->next;
        lc->next = pb;
        pb = r;
    }

    // 释放原头结点
    free(la);
    free(lb);
    return lc;
}

真题8（2021年第38题改编）

设计一个算法，找出带头结点的单链表中倒数第k个结点。如果存在，输出其值；否则输出"NOT FOUND"。要求时间复杂度为O(n)。

解题思路：

经典的双指针法（快慢指针）。

bool FindKthFromEnd(LinkList L, int k, ElemType &e) {
    LNode *p = L->next;  // 快指针
    LNode *q = L->next;  // 慢指针
    int count = 0;

    // 快指针先走k步
    while (p != NULL && count < k) {
        p = p->next;
        count++;
    }

    // 如果链表长度不足k
    if (count < k) return false;

    // 快慢指针同时移动
    while (p != NULL) {
        p = p->next;
        q = q->next;
    }

    e = q->data;
    return true;
}

时间复杂度： O(n) 空间复杂度： O(1)

原理： 快指针先走k步后，快慢指针之间相距k个位置。当快指针走到链表末尾时，慢指针恰好走到倒数第k个位置。

命题人陷阱： 注意count的计数方式。快指针走了k步后，如果链表长度恰好等于k，快指针指向NULL，此时慢指针指向第一个结点，即倒数第k个结点。如果链表长度小于k，count < k，返回false。

2.2 命题规律总结

通过对历年真题的分析，线性表部分的命题规律如下：

命题趋势：

1. 算法题越来越注重"时空效率"，要求O(n)时间+O(1)空间的解法
2. 选择题喜欢在边界条件上设坑（如i的合法范围、空表条件等）
3. 综合题经常结合多个知识点（如链表+递归、顺序表+二分查找）

模块3：AI命题Prompt

3.1 命题Prompt模板

以下是用于AI生成线性表相关考题的Prompt模板：

你是一位408考研数据结构的命题专家。请根据以下要求，生成关于"线性表的定义与基本操作"的考题。

【知识范围】
- 线性表的定义与逻辑特征
- 顺序存储结构（静态分配、动态分配）
- 链式存储结构（单链表、双链表、循环链表、静态链表）
- 基本操作：初始化、查找、插入、删除、遍历
- 头结点与头指针的区别
- 头插法与尾插法建立链表
- 时间复杂度和空间复杂度分析

【题目要求】
1. 题型分布：选择题4道，简答题1道，算法设计题1道
2. 难度分布：2道基础题（★），2道中等题（★★★），1道较难题（★★★★），1道综合题（★★★★★）
3. 选择题要有干扰项，干扰项要具有迷惑性
4. 算法题要给出完整的C语言代码和复杂度分析
5. 每道题都要给出详细的解析

【输出格式】
对于每道题，请按以下格式输出：
- 题目内容
- 选项（选择题）
- 正确答案
- 详细解析（包括为什么正确选项是对的，为什么其他选项是错的）
- 涉及的知识点
- 易错点提示

【特别注意】
- 选择题的干扰项要基于常见误区设计
- 算法题要考虑边界条件
- 要包含至少一道需要分析时间/空间复杂度的题目
- 题目要体现408真题的命题风格

3.2 AI生成的题目示例

选择题1（基础）：

下列关于线性表的说法中，正确的是（ ）。 A. 线性表的顺序存储结构是一种随机存取结构 B. 线性表的链式存储结构是一种随机存取结构 C. 顺序表中逻辑相邻的元素在物理上不一定相邻 D. 链表中逻辑相邻的元素在物理上一定相邻

答案：A

解析：

• A正确：顺序表通过首地址+偏移量可以直接访问任意元素，这就是随机存取。
• B错误：链表必须从头指针开始逐个遍历，是顺序存取，不是随机存取。
• C错误：顺序表的定义就是逻辑相邻的元素在物理上也相邻。
• D错误：链表的特点就是逻辑相邻的元素在物理上不一定相邻，通过指针连接。

涉及知识点： 顺序存储vs链式存储的基本特征

选择题2（基础）：

在一个长度为n的顺序表中，在第i个位置（1≤i≤n+1）插入一个新元素时，需要向前移动（ ）个元素。 A. n - i B. n - i + 1 C. n - i - 1 D. i

答案：B

解析： 在第i个位置插入时，需要将第i个到第n个元素都向后移动一位。需要移动的元素个数 = n - i + 1。

举例验证：n=5，在i=1处插入，需要移动5-1+1=5个元素（全部后移）。✓ n=5，在i=5处插入，需要移动5-5+1=1个元素（只有第5个元素后移）。✓ n=5，在i=6处插入，需要移动5-6+1=0个元素（直接在末尾插入）。✓

易错点： 很多人选A（n-i），这是因为把"插入"和"删除"的移动个数搞混了。删除时需要移动n-i个元素，插入时需要移动n-i+1个元素。

选择题3（中等）：

设带头结点的单链表如下所示（头结点未画出数据域），则以下关于在该链表中删除第一个数据元素a₁的操作中，正确的是（ ）。

L → [头|next] → [a₁|next] → [a₂|next] → ... → [an|^]

A. L = L->next; free(L); B. L->next = L->next->next; free(L->next); C. p = L->next; L->next = p->next; free§; D. p = L; L = L->next; free§;

答案：C

解析：

• A错误：L = L->next 使头指针指向了a₁结点，然后free(L)释放了a₁，但此时L已经指向了被释放的结点，变成了野指针。
• B错误：L->next = L->next->next 修改了头结点的next指针，但free(L->next)释放的是a₂而不是a₁（因为L->next已经被修改了）。
• C正确：先用p保存a₁的地址，然后修改头结点的next指向a₂，最后释放a₁。
• D错误：free§释放的是头结点，而不是a₁。

涉及知识点： 链表删除操作的正确实现，指针操作的顺序

选择题4（中等）：

若某线性表最常用的操作是：存取任一指定序号的元素和在最后进行插入和删除操作，则采用（ ）存储方式最节省时间。 A. 顺序表 B. 单链表 C. 双链表 D. 循环单链表

答案：A

解析：

• 存取任一指定序号的元素：顺序表O(1)，链表O(n)。顺序表占优。
• 在最后进行插入和删除：顺序表O(1)（因为知道表尾位置），链表O(n)（需要找到表尾，除非维护尾指针）。

综合来看，顺序表在这两个操作上都是O(1)，最优。

注意： 如果题目改为"在第一个位置进行插入和删除"，链表（带头结点）是O(1)，而顺序表是O(n)，答案就变成链表了。

算法设计题（综合）：

设L为带头结点的单链表，编写算法实现：删除链表中第i个位置之前（不含第i个位置）的所有结点。若i≤0或i>链表长度+1，则不进行删除操作。

参考答案：

bool DeleteBefore(LinkList L, int i) {
    if (i <= 0) return false;

    // 先求链表长度
    int len = 0;
    LNode *p = L->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }

    if (i > len + 1) return false;

    // 找到第i-1个结点的前驱（即第i-2个结点）
    // 删除从第1个到第i-2个的所有结点
    if (i <= 2) return true;  // i=1或i=2时，不需要删除

    LNode *pre = L;  // 第0个（头结点）
    for (int j = 1; j < i - 1; j++) {
        pre = pre->next;
    }

    // 删除pre之后的所有结点到第i-1个结点之前
    LNode *q = pre->next;
    while (q != NULL && q != GetElem(L, i)) {
        // 这里需要特殊处理
        // 实际上更好的做法是：
        break;
    }

    // 更简洁的做法：
    // 找到第i-1个结点
    LNode *target = L;
    for (int j = 0; j < i - 1; j++) {
        target = target->next;
    }

    // 删除头结点之后到target之前的所有结点
    LNode *curr = L->next;
    while (curr != target) {
        LNode *next = curr->next;
        free(curr);
        curr = next;
    }
    L->next = target;

    return true;
}

时间复杂度： O(n) 空间复杂度： O(1)

简答题：

简述顺序表和链表的优缺点，并说明在什么场景下应该选择顺序表，什么场景下应该选择链表。

参考答案：

选择依据：

• 选顺序表：频繁查找、较少插入删除、元素个数变化不大、需要随机存取
• 选链表：频繁插入删除、元素个数变化大、不需要随机存取

3.3 使用说明

如何使用上述Prompt模板：

1. 基础练习：将Prompt模板复制到AI对话中，让AI生成一套完整的练习题。建议每周至少做一套。
2. 专项突破：修改Prompt中的"知识范围"，聚焦到自己薄弱的知识点（如只生成关于双链表的题目）。
3. 模拟考试：让AI生成一套完整试卷，限时完成，然后对照答案自评。
4. 错题重练：把做错的题目喂给AI，让AI生成类似的题目进行强化训练。

Prompt调优技巧：

• 如果觉得题目太简单，在Prompt中加上"难度不低于★★★"
• 如果想要更多选择题，修改题型分布比例
• 如果想要特定年份的真题风格，加上"参考2020年408真题的命题风格"

模块4：AI讲题Prompt

4.1 讲题Prompt模板

你是一位408考研数据结构的辅导老师，擅长用通俗易懂的方式讲解难题。请按照以下要求讲解这道题目：

【题目信息】
{粘贴题目内容}

【讲解要求】
1. 先用一句话概括这道题考的是什么知识点
2. 分析题目中的关键信息和隐含条件
3. 给出解题思路（从"拿到题目后怎么想"开始，不要直接给答案）
4. 给出完整的解题过程（代码要逐行注释）
5. 分析时间复杂度和空间复杂度
6. 指出这道题的易错点和常见错误
7. 总结这类题的通用解题方法
8. 给出1-2道类似的练习题

【讲解风格】
- 用"我踩过这个坑"的人感视角
- 不要说"显然"、"容易看出"这类话
- 每一步都要解释"为什么这样做"
- 用具体的数字举例来辅助理解
- 适当使用类比帮助记忆

4.2 AI生成的讲解示例

题目： 设计一个算法，将带头结点的单链表就地逆置。

讲解：

一句话概括： 这道题考的是链表的基本操作——指针的修改。核心思想是头插法。

关键信息分析：

• “带头结点”：意味着头指针L始终指向头结点，不需要修改L本身
• “就地”：意味着空间复杂度必须是O(1)，不能用栈或递归
• “逆置”：意味着原来a₁→a₂→…→aₙ要变成aₙ→…→a₂→a₁

解题思路：

拿到这道题，我首先想到的是：逆置链表，就是把每个结点的next指针反转。

方法一：依次把每个结点的next指向它的前驱。但这需要知道前驱是谁，单链表做不到。

方法二：头插法。把原链表中的结点一个一个取下来，每次插到头结点之后。这样最后插入的结点就变成了第一个结点，实现了逆置。

为什么头插法能实现逆置？

举个例子：原链表是 1→2→3→4→5

• 取出1，插入头结点后：H→1
• 取出2，插入头结点后：H→2→1
• 取出3，插入头结点后：H→3→2→1
• 取出4，插入头结点后：H→4→3→2→1
• 取出5，插入头结点后：H→5→4→3→2→1

完美逆置！

完整代码：

void ReverseList(LinkList L) {
    LNode *p = L->next;  // p指向第一个数据结点
    LNode *q;            // q用来保存p的后继
    L->next = NULL;      // 关键！先把头结点的next置空
                         // 因为逆置后原来的第一个结点变成最后一个

    while (p != NULL) {
        q = p->next;     // ① 保存p的后继（不保存就丢了！）
        p->next = L->next;  // ② p的next指向当前第一个数据结点
        L->next = p;     // ③ 头结点的next指向p（p成为新的第一个）
        p = q;           // ④ p后移到原来保存的后继
    }
}

复杂度分析：

• 时间复杂度：O(n)，每个结点访问一次
• 空间复杂度：O(1)，只用了两个辅助指针

易错点：

我踩过这个坑： L->next = NULL 这一行太容易被忘了！如果不写这一行，原来的第一个结点（逆置后变成最后一个）的next指针还指向原来的第二个结点，形成环。遍历链表时会死循环。

还有一个常见错误是①②③的顺序搞反了。如果先执行③再执行②：

L->next = p;     // 先执行这步
p->next = L->next;  // 这时L->next已经是p了！p->next = p，自环！

通用解题方法总结：

凡是遇到"链表逆置"、"链表反转"类题目，记住两个方法：

1. 头插法（就地逆置，O(1)空间）：逐个取下结点，插到头结点之后
2. 栈辅助法（非就地，O(n)空间）：全部入栈，再依次出栈重建链表

考试中要求"就地"就用方法一，没有空间限制就用方法二。

类似练习题：

1. 将单链表中从第m个到第n个结点逆置（部分逆置）
2. 判断单链表是否为回文（结合逆置+比较）

4.3 易错题记录

易错题1：头插法建链表的顺序

输入序列 1, 2, 3, 4, 5，用头插法建立的链表是？

错误答案： 1→2→3→4→5 正确答案： 5→4→3→2→1

错因： 头插法每次把新结点插在最前面，所以后输入的元素反而在前面。

记忆口诀： “头插法，反着来；尾插法，顺着来。”

易错题2：删除操作中指针的顺序

删除单链表中p的后继结点q，以下操作顺序正确的是？

错误做法：

p->next = q->next;  // 先断链
free(q);            // 再释放

这个做法本身没错，但如果写成：

free(q);            // 先释放
p->next = q->next;  // 再断链 → 错误！q已经被释放了

错因： 释放结点后不能再访问它的成员。

正确顺序： 先断链，再释放。永远记住这个顺序。

易错题3：循环链表判空条件

带头结点的循环单链表的判空条件是？

错误答案： L == NULL 正确答案： L->next == L

错因： 循环单链表的尾结点指向头结点。空表时，头结点的next指向自己。L == NULL是不带头结点的单链表的判空条件。

模块5：AI错题复盘Prompt

5.1 错题复盘Prompt模板

你是一位408考研数据结构的错题分析专家。请帮我分析以下错题，找出错误原因并制定改进计划。

【错题信息】
题目：{粘贴题目}
我的答案：{你的答案}
正确答案：{正确答案}
我的解题过程：{你当时的思路}

【分析要求】
1. 分析我的错误属于哪种类型：
   - 概念理解错误（对知识点理解有误）
   - 边界条件遗漏（忽略了特殊情况）
   - 代码实现错误（逻辑对但代码写错）
   - 复杂度分析错误（算法对但复杂度算错）
   - 审题错误（理解错了题意）
2. 找出错误的根本原因
3. 给出正确的解题思路
4. 指出我知识体系中的薄弱环节
5. 推荐针对性的练习题目
6. 给出避免同类错误的策略

【输出格式】
- 错误类型：xxx
- 错误原因：xxx
- 正确思路：xxx
- 薄弱环节：xxx
- 强化练习：xxx
- 防范策略：xxx

5.2 AI生成的复盘示例

错题信息：

题目： 在长度为n的顺序表中删除第i个元素，需要移动元素的个数为（ ）。 A. n - i B. n - i + 1 C. n - i - 1 D. i

我的答案： B（n - i + 1） 正确答案： A（n - i）

我的解题过程： 我觉得删除第i个元素后，第i+1到第n个元素都要前移，所以移动个数是n - (i+1) + 1 = n - i。但我选了n - i + 1，因为我觉得还要把最后一个位置清空。

分析结果：

错误类型： 概念理解错误

错误原因：

1. 混淆了"插入"和"删除"的移动个数
2. 插入时需要移动 n - i + 1 个元素（因为要腾出位置给新元素）
3. 删除时只需要移动 n - i 个元素（把后面的元素前移覆盖被删元素的位置）
4. “把最后一个位置清空"这个想法是多余的——顺序表的长度由length字段管理，最后一个位置不需要"清空”

正确思路：

删除第i个元素时：

• 被删除的元素：a_i（第i个位置）
• 需要前移的元素：a_{i+1}, a_{i+2}, …, a_n
• 前移的元素个数：n - i

用具体数字验证：

• n=5, i=1：删除第1个，需要移动4个（a₂,a₃,a₄,a₅都前移一位）。5-1=4 ✓
• n=5, i=5：删除第5个，需要移动0个（删最后一个不需要移动）。5-5=0 ✓
• n=5, i=3：删除第3个，需要移动2个（a₄,a₅前移）。5-3=2 ✓

薄弱环节： 顺序表插入和删除操作的元素移动个数

强化练习：

1. 在长度为n的顺序表中第i个位置插入元素，需要移动多少个元素？
2. 在长度为n的有序顺序表中插入元素x使其保持有序，最好情况下需要移动多少个元素？
3. 循环队列中，入队和出队操作分别需要移动多少个元素？

防范策略：

1. 制作对比卡片：
   • 插入移动个数：n - i + 1
   • 删除移动个数：n - i
2. 用具体数字验证每个公式（这是最有效的方法）
3. 做题时画出具体的数组状态，数一数移动了几个元素

5.3 错题归因统计

根据对历年考生错题的分析，线性表部分的常见错误归因如下：

模块6：AI模拟卷Prompt

6.1 模拟卷Prompt模板

你是一位408考研数据结构的命题组组长。请生成一份关于"线性表"的模拟试卷。

【试卷要求】
1. 总分：50分
2. 考试时间：60分钟
3. 题型分布：
   - 单项选择题：10道，每题2分，共20分
   - 填空题：5道，每题2分，共10分
   - 简答题：2道，每题5分，共10分
   - 算法设计题：1道，10分
4. 知识点覆盖：
   - 线性表定义（10%）
   - 顺序存储（30%）
   - 链式存储（40%）
   - 基本操作实现（15%）
   - 存储选型（5%）
5. 难度分布：
   - 基础题（★）：40%
   - 中等题（★★★）：35%
   - 较难题（★★★★）：20%
   - 综合题（★★★★★）：5%

【命题原则】
1. 选择题要有迷惑性强的干扰项
2. 算法题要考查时空效率
3. 要包含至少2道需要综合分析的题目
4. 题目要体现408真题的命题风格
5. 每道题都要标注考查的知识点

【输出要求】
1. 先输出完整试卷（不含答案）
2. 然后输出参考答案和评分标准
3. 最后给出每道题的知识点标注和难度标注

6.2 AI生成的完整模拟卷

408数据结构——线性表模拟试卷

总分：50分 考试时间：60分钟

一、单项选择题（每题2分，共20分）

1. 线性表是（ ）。 A. 一种链式存储结构 B. 一种顺序存储结构 C. 一种逻辑结构 D. 一种散列存储结构

2. 设顺序表的长度为n，以下操作中时间复杂度为O(1)的是（ ）。 A. 在第i个位置插入元素（1≤i≤n+1） B. 删除第i个位置的元素（1≤i≤n） C. 按位查找第i个元素（1≤i≤n） D. 按值查找元素x

3. 在一个带头结点的单链表中，头指针为L，则判断链表为空的条件是（ ）。 A. L == NULL B. L->next == NULL C. L->next == L D. L == NULL || L->next == NULL

4. 若用单链表表示队列，则在进行出队操作时（ ）。 A. 需要修改头指针 B. 需要修改尾指针 C. 需要同时修改头指针和尾指针 D. 不需要修改头指针和尾指针

5. 在双链表中，在p结点之后插入s结点的操作序列是（ ）。 A. p->next=s; s->prior=p; s->next=p->next; p->next->prior=s; B. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C. s->next=p->next; p->next->prior=s; p->next=s; s->prior=p; D. p->next->prior=s; s->next=p->next; s->prior=p; p->next=s;

6. 设线性表有n个元素，以下操作中（ ）在顺序表上实现比在链表上实现效率更高。 A. 输出线性表中的第i个元素（1≤i≤n） B. 在第i个元素之后插入一个新元素 C. 删除第i个元素 D. 将线性表逆置

7. 以下关于静态链表的说法中，正确的是（ ）。 A. 静态链表需要连续的存储空间 B. 静态链表通过指针实现元素之间的逻辑关系 C. 静态链表通过数组下标实现元素之间的逻辑关系 D. 静态链表支持随机存取

8. 设有一个循环双链表，头指针为L，则判断链表为空的条件是（ ）。 A. L->next == NULL B. L->next == L C. L->next == L && L->prior == L D. L == NULL

9. 将两个各有n个元素的有序顺序表归并为一个有序顺序表，最好的情况下时间复杂度为（ ）。 A. O(1) B. O(n) C. O(nlogn) D. O(n²)

10. 以下关于线性表的说法中，不正确的是（ ）。 A. 线性表可以采用顺序存储或链式存储 B. 线性表中元素的个数可以是零 C. 线性表中每个元素都有且仅有一个直接前驱和一个直接后继 D. 线性表的逻辑特征是元素之间存在一对一的前驱后继关系

二、填空题（每题2分，共10分）

11. 在长度为n的顺序表中插入一个新元素，平均需要移动______个元素。

12. 带头结点的单链表中，在头结点之后插入一个新结点s的操作是：s->next = L->next; ______。

13. 循环单链表中，尾结点的next指针指向______。

14. 双链表中删除p结点的后继结点q，需要修改______个指针域。

15. 头插法建立单链表时，最终链表中元素的顺序与输入顺序______。

三、简答题（每题5分，共10分）

16. 简述顺序表和链表的主要区别，并各举一个适合使用顺序表和链表的实际应用场景。（5分）

17. 为什么要在单链表中设置头结点？头结点的作用是什么？如果不设头结点，对哪些操作会有影响？（5分）

四、算法设计题（10分）

18. 设有一个带头结点的单链表L，链表中的元素按值递增有序排列。设计一个算法，删除链表中值大于mink且小于maxk的所有元素，使得链表中不再有满足条件的元素。要求： （1）给出算法设计思想（3分） （2）用C语言编写算法代码（5分） （3）分析算法的时间复杂度和空间复杂度（2分）

参考答案与评分标准

一、选择题

详细解析：

第1题： 线性表是一种逻辑结构，描述的是元素之间一对一的线性关系。顺序存储和链式存储是线性表的两种物理存储方式。选C。

第2题： 顺序表按位查找通过下标直接访问，时间复杂度O(1)。插入和删除需要移动元素，O(n)。按值查找需要遍历，O(n)。选C。

第3题： 带头结点的单链表，头指针L指向头结点。空表时，头结点的next为NULL，即L->next == NULL。注意：L本身不为NULL（头结点始终存在）。选B。

第4题： 用单链表表示队列时，出队操作删除的是队头元素。如果队列只有一个元素，出队后需要同时修改头指针和尾指针。但一般情况下只需要修改头指针。题目问的是"出队操作时"，最准确的答案是A（需要修改头指针），因为尾指针只在特殊情况下需要修改。选A。

第5题： 在p之后插入s，正确的顺序是：

1. s->next = p->next（s的后继设为p原来的后继）
2. p->next->prior = s（p原来的后继的前驱设为s）
3. p->next = s（p的后继设为s）
4. s->prior = p（s的前驱设为p）

注意1和2必须在3之前，否则p->next已经被修改。选C。

第6题： 顺序表按位查找是O(1)，链表是O(n)。插入和删除在链表上（已知位置时）是O(1)，顺序表是O(n)。逆置操作两者都是O(n)。选A。

第7题： 静态链表用数组实现，数组是连续存储空间，但静态链表通过数组下标（游标）来模拟指针，实现逻辑关系。静态链表不支持随机存取（虽然数组支持，但静态链表的逻辑顺序和物理顺序不同）。选C。

第8题： 循环双链表中，空表时头结点的next和prior都指向自己。选C。

第9题： 两个有序表归并，每个元素最多比较一次，时间复杂度O(n)。选B。

第10题： 线性表的第一个元素没有直接前驱，最后一个元素没有直接后继。C说"每个元素都有且仅有一个直接前驱和一个直接后继"是错误的。选C。

二、填空题

11. n/2

解析：假设在n+1个位置插入的概率相等（均为1/(n+1)），平均移动次数 = Σ(n-i+1)/(n+1) = n/2。

12. L->next = s;

解析：带头结点的单链表，在头结点之后插入s。先设s的next为头结点的next（即第一个数据结点），再设头结点的next为s。

13. 头结点

解析：循环单链表的尾结点的next指向头结点，形成环。

14. 3

解析：删除p的后继q，需要修改：p->next = q->next（1个），q->next->prior = p（1个），以及释放q。但题目问的是"修改指针域"的个数。p的next指针要改（1个），q的next的prior指针要改（1个）。等等，让我重新数：

• p->next = q->next：修改了p的next指针（1个指针域）
• q->next->prior = p：修改了q的后继结点的prior指针（1个指针域）
• 然后free(q) 所以修改了2个指针域。但如果考虑q本身有两个指针域（prior和next），删除后这些指针域都失效了。

标准答案应该是2个指针域被修改（p->next和q->next->prior）。但有些教材把"断开q的指针"也算上，那就是4个。

修正答案： 2个（p->next 和 q的后继的prior）

15. 相反

解析：头插法每次把新结点插在最前面，所以最后输入的结点在最前面，顺序与输入相反。

三、简答题

16. 参考答案：

顺序表和链表的主要区别：

应用场景：

• 适合顺序表：学生成绩管理系统，需要频繁按学号查找成绩（随机存取），很少插入删除学生记录
• 适合链表：音乐播放器的播放列表，需要频繁添加和删除歌曲，不需要按序号快速访问

评分标准： 区别每点1分（答出3点即可得3分），应用场景每点1分。

17. 参考答案：

头结点的作用：

1. 统一操作：在头结点之后插入/删除第一个数据结点的操作与其他位置一致，不需要特殊处理
2. 方便空表和非空表的统一处理
3. 头结点的数据域可以存储表长等附加信息

不设头结点的影响：

• 对第一个数据结点的插入操作需要修改头指针L，需要传入指针的指针（或引用）
• 对第一个数据结点的删除操作同样需要修改头指针L
• 空表和非空表的处理逻辑不同，增加了代码复杂度

评分标准： 头结点作用3分，不设头结点的影响2分。

四、算法设计题

18. 参考答案：

（1）算法设计思想（3分）：

由于链表递增有序，值大于mink且小于maxk的元素一定连续排列。算法步骤：

1. 从头结点开始遍历，找到第一个值大于mink的结点的前驱pre
2. 从pre开始，找到第一个值大于等于maxk的结点
3. 删除pre和该结点之间的所有结点

（2）代码实现（5分）：

void DeleteRange(LinkList L, ElemType mink, ElemType maxk) {
    LNode *pre = L;  // pre指向待删除区间的前驱

    // 找到第一个值>mink的结点的前驱
    while (pre->next != NULL && pre->next->data <= mink) {
        pre = pre->next;
    }

    // 此时pre->next是第一个>mink的结点（或NULL）
    LNode *p = pre->next;

    // 删除值<maxk的结点
    while (p != NULL && p->data < maxk) {
        LNode *q = p->next;
        free(p);
        p = q;
    }

    // 将pre连接到第一个>=maxk的结点
    pre->next = p;
}

（3）复杂度分析（2分）：

• 时间复杂度：O(n)，最多遍历一次链表
• 空间复杂度：O(1)，只使用了常数个辅助指针

评分标准： 设计思想3分（找到区间1分，删除操作1分，连接操作1分），代码5分（逻辑正确3分，边界处理1分，内存释放1分），复杂度2分。

6.3 评分标准参考

模拟卷评分标准：

各题型得分率参考：

• 选择题：正确率应达到80%以上（至少8/10）
• 填空题：正确率应达到80%以上（至少4/5）
• 简答题：要点齐全，表述清晰
• 算法题：逻辑正确、代码规范、复杂度分析准确

模块7：延伸阅读

7.1 教材参考

阅读建议：

• 第一遍：看王道复习指导，理解基本概念
• 第二遍：看严蔚敏教材，深入理解原理
• 第三遍：做真题，查漏补缺
• 如果基础薄弱：先看《大话数据结构》入门

7.2 视频课程

学习顺序建议：

1. 先看王卓老师的视频理解基本概念
2. 再看王道团队的视频做真题训练
3. 遇到不懂的知识点，回看严蔚敏的教材

7.3 知识关联图

知识关联说明：

1. 线性表 → 栈/队列： 栈和队列是操作受限的线性表。栈限制在表尾进行插入和删除，队列限制在表头删除、表尾插入。理解了线性表，栈和队列就只是"加了限制条件"。
2. 线性表 → 串： 串是一种特殊的线性表，其数据元素是字符。串的模式匹配算法（KMP等）需要用到线性表的基本操作。
3. 顺序存储 → 动态分配 → 扩容： 动态顺序表的扩容策略（如每次扩容为原来的2倍）涉及到摊还分析，这是算法分析中的重要概念。
4. 链式存储 → 树/图： 树的"孩子表示法"用链表存储孩子结点，图的"邻接表"用链表存储邻接点。链表是理解树和图的链式存储的基础。

模块8：Checklist

8.1 知识点清单

请逐项检查自己是否掌握以下知识点。如果某项不确定，请回到对应章节重新学习。

线性表的定义与基本概念

• 能准确说出线性表的定义（相同类型、有限、序列）
• 理解"直接前驱"和"直接后继"的含义
• 知道线性表的第一个元素没有前驱，最后一个元素没有后继
• 能区分"线性结构"和"线性表"的概念

顺序存储结构

• 能写出顺序表的C语言结构体定义（静态分配和动态分配）
• 理解顺序表"随机存取"的含义和实现原理
• 掌握顺序表的初始化操作
• 掌握顺序表按位查找的实现和时间复杂度O(1)
• 掌握顺序表按值查找的实现和平均时间复杂度O(n)
• 掌握顺序表插入操作的实现（元素从后往前移）
• 掌握顺序表删除操作的实现（元素从前往后移）
• 知道插入时i的范围是1≤i≤length+1
• 知道删除时i的范围是1≤i≤length
• 能分析插入/删除操作的最好、最坏、平均时间复杂度

链式存储结构

• 能写出单链表的C语言结构体定义
• 理解头结点和头指针的区别
• 知道带头结点和不带头结点链表的区别
• 掌握单链表的按位查找（O(n)）
• 掌握单链表的插入操作（注意指针修改顺序）
• 掌握单链表的删除操作（注意先保存后继再修改指针）
• 掌握头插法和尾插法建立链表
• 知道头插法建立的链表顺序与输入相反
• 知道尾插法建立的链表顺序与输入相同
• 能写出双链表的结构体定义
• 掌握双链表的插入操作（四句话的顺序不能乱）
• 掌握双链表的删除操作
• 理解循环单链表的特点和判空条件
• 理解循环双链表的特点和判空条件
• 理解静态链表的实现方式和适用场景

存储选型

• 能说出顺序表和链表的各自优缺点
• 能根据具体场景选择合适的存储结构
• 理解"存储密度"的概念
• 理解"缓存友好性"的概念

8.2 自测问题

请尝试回答以下问题。如果回答不上来或回答错误，请回到对应章节重新学习。

基础题（★）：

1. 线性表的定义是什么？“有限”、“有序”、"相同类型"分别是什么意思？
2. 顺序表和数组有什么区别？
3. 头指针和头结点有什么区别？
4. 顺序表按位查找的时间复杂度是多少？为什么？
5. 单链表按位查找的时间复杂度是多少？为什么？

中等题（★★★）： 6. 顺序表插入操作时，元素为什么要从后往前移？如果从前往后移会怎样？ 7. 带头结点的单链表和不带头结点的单链表，在删除操作时有什么区别？ 8. 双链表插入操作中，四句话的顺序为什么不能乱？乱序会导致什么问题？ 9. 循环单链表的判空条件是什么？和不循环的单链表有什么区别？ 10. 头插法和尾插法建立的链表有什么区别？为什么？

较难题（★★★★）： 11. 如何在一个单链表中找到倒数第k个结点？要求时间复杂度O(n)。 12. 如何将一个单链表就地逆置？写出代码并分析复杂度。 13. 如何判断一个单链表是否有环？如果有环，如何找到环的入口？ 14. 如何将两个递增有序的单链表归并为一个递减有序的单链表？ 15. 设计一个算法，删除递增有序顺序表中值小于x且为奇数的所有元素，要求时间复杂度O(n)。

8.3 完成度评估

自评标准：

学习建议：

1. 如果你得分在13-15： 恭喜！线性表的基础知识你已经掌握得很好了。接下来可以做几道408真题检验一下实战能力，然后进入下一章。
2. 如果你得分在10-12： 基础不错，但还有一些细节没有掌握。重点看错题对应的知识点，特别是代码实现的细节。
3. 如果你得分在7-9： 核心概念可能理解了，但代码实现还不够熟练。建议把每个基本操作的代码都自己敲一遍，不看参考代码。
4. 如果你得分在4-6： 建议重新学习本章。先看视频课程建立直觉，再看教材理解原理，最后自己写代码实现。
5. 如果你得分在0-3： 不要灰心。数据结构是一门需要时间的课程。建议从《大话数据结构》开始入门，然后再看王道复习指导。

最后的话：

线性表是数据结构的基石。我当年也是在这里栽了跟头，然后花了整整一周时间重新学习。但那一周的投入是值得的——后面学栈、队列、树、图的时候，我发现很多概念都是线性表的延伸。

记住：基础不牢，地动山摇。 在线性表上花再多时间都不为过。

祝复习顺利！

——安全风信子

参考资料：

1. 王道考研. 数据结构复习指导[M]. 北京: 电子工业出版社.
2. 严蔚敏, 吴伟民. 数据结构（C语言版）[M]. 北京: 清华大学出版社.
3. Mark Allen Weiss. 数据结构与算法分析——C语言描述[M]. 北京: 机械工业出版社.
4. 程杰. 大话数据结构[M]. 北京: 清华大学出版社.