DS-01-02 顺序表及其基本运算

作者： 安全风信子 日期： 2026-07-22 主要来源： 王道考研《数据结构复习指导》、严蔚敏《数据结构（C语言版）》 读完你能学到： 掌握顺序表静态/动态分配实现、插入删除算法及复杂度分析，能独立解决408顺序表相关真题

目录

• 先看问题场景
• • 场景一：2016年真题的陷阱
  • 场景二：动态分配的顺序表为何"扩容失败"
  • 场景三：插入删除时的"边界崩溃"
  • 场景四：静态分配与动态分配的抉择
  • 场景五：复杂度分析的"想当然"
  • 场景六：按值查找的"隐藏陷阱"
  • 场景七：顺序表"溢出"的恐慌
  • 场景八：初始化函数的"内存泄漏"
• 本节核心收获
• • 1. 顺序表的两种实现方式
  • 2. 顺序表的5个基本运算
  • 3. 复杂度分析的严格推导
  • 4. 顺序表的核心特点
  • 5. 边界条件的精确把握
  • 6. 动态分配的内存管理
  • 7. 真题的命题规律
  • 8. 代码实现的常见陷阱
• 模块1：知识点讲解
• • 1.1 核心概念
  • • 1.1.1 顺序表的定义
    • 1.1.2 静态分配实现
    • 1.1.3 动态分配实现
    • 1.1.4 顺序表的特点
  • 1.2 算法实现与复杂度分析
  • • 1.2.1 初始化操作
    • 1.2.2 插入操作
    • 1.2.3 删除操作
    • 1.2.4 按位查找
    • 1.2.5 按值查找
    • 1.2.6 复杂度总结表
  • 1.3 图示说明
  • • 1.3.1 顺序表结构图
    • 1.3.2 插入操作过程图
    • 1.3.3 删除操作过程图
    • 1.3.4 静态分配vs动态分配对比图
    • 1.3.5 静态分配vs动态分配对比表
  • 1.4 常见误区与踩坑实录
  • • 误区1：插入位置的范围搞错
    • 误区2：插入时元素移动方向搞反
    • 误区3：删除时元素移动方向搞反
    • 误区4：动态分配时忘记检查malloc/realloc的返回值
    • 误区5：动态分配时函数参数不用引用传递
    • 误区6：忘记释放动态分配的内存
    • 误区7：浮点数比较直接用==
    • 误区8：平均复杂度的推导错误
    • 误区9：混淆位序和下标
    • 误区10：扩容时直接修改原指针
• 模块2：真题解析
• • 2.1 真题精选
  • • 真题1：2016年第38题（算法设计题）
    • 真题2：2018年第2题（选择题）
    • 真题3：2019年第3题（选择题）
    • 真题4：2020年第1题（选择题）
    • 真题5：2017年第5题（选择题）
    • 真题6：2015年第38题（算法设计题）
    • 真题7：2019年第38题（算法设计题）
    • 真题8：2021年第2题（选择题）
  • 2.2 命题规律总结
  • • 选择题命题规律
    • 算法题命题规律
    • 综合题命题规律
• 模块3：AI命题Prompt
• • 3.1 命题Prompt模板
  • 3.2 AI生成的题目示例
  • • 题目1：选择题（简单）
    • 题目2：选择题（中等）
    • 题目3：选择题（中等）
    • 题目4：选择题（较难）
    • 题目5：算法设计题
    • 题目6：综合应用题
  • 3.3 使用说明
  • • 如何使用AI命题Prompt
    • 命题注意事项
    • 命题示例流程
• 模块4：AI讲题Prompt
• • 4.1 讲题Prompt模板
  • 4.2 AI生成的讲解示例
  • • 示例1：讲解2016年第38题
    • 示例2：讲解2019年第3题
  • 4.3 易错题记录
  • • 易错题1：插入位置的范围
    • 易错题2：删除操作的平均移动次数
    • 易错题3：双指针法的循环条件
• 模块5：AI错题复盘Prompt
• • 5.1 错题复盘Prompt模板
  • 5.2 AI生成的复盘示例
  • • 示例1：复盘"插入位置范围"错题
    • 示例2：复盘"删除操作平均移动次数"错题
  • 5.3 错题归因统计
  • • 错题类型分布
    • 高频错题TOP5
    • 改进建议
• 模块6：AI模拟卷Prompt
• • 6.1 模拟卷Prompt模板
  • 6.2 AI生成的完整模拟卷

• 模拟试卷：顺序表及其基本运算
• • 一、选择题（每题2分，共20分）
  • 二、填空题（每题2分，共10分）
  • 三、算法设计题（共30分）
  • 四、综合应用题（10分）
• 参考答案
• • 一、选择题（每题2分，共20分）
  • 二、填空题（每题2分，共10分）
  • 三、算法设计题（共30分）
  • • 1. （8分）删除顺序表中所有值等于x的元素
    • 2. （10分）删除值在s与t之间的元素
    • 3. （12分）合并两个有序顺序表
  • 四、综合应用题（10分）
  • • 1. 员工工资管理
    • 6.3 评分标准参考
    • • 选择题评分标准
      • 填空题评分标准
      • 算法设计题评分标准
      • 综合应用题评分标准
      • 总分计算
      • 成绩等级
  • 模块7：延伸阅读
  • • 7.1 教材参考
    • • 1. 王道考研《数据结构复习指导》
      • 2. 严蔚敏《数据结构（C语言版）》
      • 3. 天勤考研《数据结构高分笔记》
    • 7.2 视频课程
    • • 1. 王道考研数据结构视频课
      • 2. 天勤考研数据结构视频课
      • 3. B站免费视频资源
    • 7.3 知识关联图
  • 模块8：Checklist
  • • 8.1 知识点清单
    • • 核心概念（必会）
      • 基本操作（必会）
      • 复杂度分析（必会）
      • 边界条件（易错）
      • 代码实现（必会）
      • 常见误区（注意）
      • 真题考点（重点）
    • 8.2 自测问题
    • • 概念理解（10题）
      • 代码实现（5题）
      • 复杂度分析（5题）
      • 真题模拟（5题）
    • 8.3 完成度评估
    • • 自我评分标准
      • 学习建议
      • 下一步计划

科目：数据结构 | 章节：第1章 线性表 | 难度：L1 标签：顺序表、静态分配、动态分配、插入删除、复杂度分析

先看问题场景

场景一：2016年真题的陷阱

2016年408真题第38题（算法设计题）要求：设计一个算法，将顺序表L中的所有元素逆置，要求算法空间复杂度为O(1)。

这道题看起来简单，但当年很多考生在考场上犯了致命错误：

// 错误示范：使用了额外的数组
void Reverse(SeqList L) {
    ElemType temp[MaxSize];  // ❌ 空间复杂度O(n)，不符合要求
    for(int i = 0; i < L.length; i++) {
        temp[i] = L.data[i];
    }
    for(int i = 0; i < L.length; i++) {
        L.data[i] = temp[L.length - 1 - i];
    }
}

踩坑经历：我当时第一反应就是用辅助数组，结果写完才发现空间复杂度不对。后来才明白，顺序表的优势就在于可以原地操作，通过双指针交换就能实现O(1)空间复杂度的逆置：

// 正确解法：双指针原地交换
void Reverse(SeqList &L) {
    ElemType temp;
    for(int i = 0, j = L.length - 1; i < j; i++, j--) {
        temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
}

场景二：动态分配的顺序表为何"扩容失败"

我在学习动态顺序表时，写过这样的代码：

// 灾难现场
void InitList(SeqList &L) {
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

void Insert(SeqList L, int i, ElemType e) {  // ❌ 参数传递错误
    if(L.length >= L.MaxSize) {
        L.data = (ElemType*)realloc(L.data, sizeof(ElemType) * (L.MaxSize + INCREMENT));
        // 这里realloc可能失败，但代码没有检查
    }
    // ...
}

问题在哪：

1. 函数参数SeqList L是值传递，对L.data的修改不会影响到原顺序表
2. realloc失败时返回NULL，直接赋值会导致内存泄漏
3. 没有检查realloc的返回值

正确写法：

bool Insert(SeqList &L, int i, ElemType e) {  // ✅ 引用传递
    if(L.length >= L.MaxSize) {
        ElemType *newData = (ElemType*)realloc(L.data, 
            sizeof(ElemType) * (L.MaxSize + INCREMENT));
        if(newData == NULL) {  // ✅ 检查realloc返回值
            return false;
        }
        L.data = newData;
        L.MaxSize += INCREMENT;
    }
    // ...
}

场景三：插入删除时的"边界崩溃"

2018年真题选择题考过：在顺序表中第i个位置插入元素，i的合法范围是什么？

我当时想当然地写了1 <= i <= n，结果错了。正确答案是1 <= i <= n+1，因为可以在表尾插入。

更常见的错误是在删除操作中：

bool ListDelete(SeqList &L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {  // ❌ 应该是i > L.length，不是i >= L.length
        return false;
    }
    e = L.data[i - 1];
    for(int j = i; j < L.length; j++) {  // ❌ 应该是j < L.length - 1
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

边界问题的本质：顺序表的位序从1开始，但数组下标从0开始。这个转换关系位序i对应下标i-1是408考试的高频考点。

场景四：静态分配与动态分配的抉择

在复习初期，我一直困惑：既然动态分配更灵活，为什么还要学静态分配？

直到做了2020年的一道真题才明白：

某系统需要存储100个学生的成绩，要求查找效率最高，应该选择哪种存储结构？

答案：静态分配的顺序表。

原因：

1. 数据量固定（100个学生），不需要动态扩容
2. 顺序表支持随机访问，查找效率O(1)
3. 静态分配没有动态分配的内存管理开销
4. 代码更简单，不容易出错

教训：选择存储结构要看具体场景，不是越灵活越好。

场景五：复杂度分析的"想当然"

2019年真题考过：在长度为n的顺序表中删除第i个元素，平均需要移动多少个元素？

我当时直接回答n/2，结果错了。

正确分析：

• 删除第1个元素，需要移动n-1个元素
• 删除第2个元素，需要移动n-2个元素
• …
• 删除第n个元素，需要移动0个元素
• 假设删除每个位置的概率相等（都是1/n）
• 平均移动次数 = (n-1 + n-2 + … + 0) / n = n(n-1)/2 / n = (n-1)/2

踩坑点：复杂度分析不能想当然，必须严格推导。

场景六：按值查找的"隐藏陷阱"

在实现按值查找时，我写过这样的代码：

int LocateElem(SeqList L, ElemType e) {
    for(int i = 0; i < L.length; i++) {
        if(L.data[i] == e) {  // ❌ 对于浮点数，直接用==比较有问题
            return i + 1;
        }
    }
    return 0;
}

问题：如果ElemType是float或double，直接用==比较会因为精度问题导致查找失败。

正确做法：

int LocateElem(SeqList L, ElemType e) {
    for(int i = 0; i < L.length; i++) {
        if(fabs(L.data[i] - e) < EPSILON) {  // ✅ 浮点数比较
            return i + 1;
        }
    }
    return 0;
}

场景七：顺序表"溢出"的恐慌

在做2017年真题时，遇到一个问题：

顺序表L的MaxSize为100，当前length为99，现在要插入2个元素，会发生什么？

我当时慌了，不知道该怎么分析。

正确思路：

1. 第1次插入：length变为100，等于MaxSize，插入成功
2. 第2次插入：length=100 >= MaxSize=100，如果是静态分配，直接返回false（溢出）；如果是动态分配，先扩容再插入

关键区别：

• 静态分配：MaxSize是常量，无法扩容，溢出就是溢出
• 动态分配：MaxSize是变量，可以扩容，"溢出"只是暂时的

场景八：初始化函数的"内存泄漏"

我在练习动态顺序表时，写过这样的main函数：

int main() {
    SeqList L;
    InitList(L);
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    // ... 使用顺序表
    return 0;  // ❌ 没有释放动态分配的内存
}

问题：动态分配的内存在程序结束时没有释放，造成内存泄漏。

正确做法：

int main() {
    SeqList L;
    InitList(L);
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    // ... 使用顺序表
    free(L.data);  // ✅ 释放动态分配的内存
    L.data = NULL;  // ✅ 避免野指针
    return 0;
}

本节核心收获

通过本节学习，你将掌握：

1. 顺序表的两种实现方式

• 静态分配：使用固定大小数组，适合数据量已知的场景
• 动态分配：使用malloc/realloc动态分配内存，适合数据量变化的场景
• 两者的核心区别：MaxSize是常量还是变量

2. 顺序表的5个基本运算

• 初始化：静态分配直接设置length=0；动态分配需要malloc分配内存
• 插入：在第i个位置插入元素，平均移动n/2个元素，时间复杂度O(n)
• 删除：删除第i个位置的元素，平均移动(n-1)/2个元素，时间复杂度O(n)
• 按位查找：通过下标直接访问，时间复杂度O(1)
• 按值查找：从头到尾遍历，平均比较(n+1)/2次，时间复杂度O(n)

3. 复杂度分析的严格推导

• 最好情况、最坏情况、平均情况的区分
• 插入操作的平均移动次数：n/2
• 删除操作的平均移动次数：(n-1)/2
• 按值查找的平均比较次数：(n+1)/2

4. 顺序表的核心特点

• 优点：支持随机访问（O(1)），存储密度高（100%）
• 缺点：插入删除需要移动大量元素，需要预分配空间
• 适用场景：数据量稳定，查找频繁，插入删除较少

5. 边界条件的精确把握

• 位序i从1开始，数组下标从0开始
• 插入的合法范围：1 <= i <= length+1
• 删除的合法范围：1 <= i <= length
• 判空条件：length == 0
• 判满条件：length == MaxSize（静态分配）

6. 动态分配的内存管理

• malloc分配内存，realloc扩容
• 必须检查malloc/realloc的返回值
• 使用完毕后必须free释放内存
• 引用传递（&）的重要性

7. 真题的命题规律

• 选择题常考：顺序表的特点、复杂度、边界条件
• 算法题常考：插入删除的实现、逆置、合并、查找
• 综合题常考：结合其他数据结构设计算法

8. 代码实现的常见陷阱

• 值传递vs引用传递
• 数组越界问题
• 浮点数比较问题
• 内存泄漏问题
• realloc失败的处理

模块1：知识点讲解

1.1 核心概念

1.1.1 顺序表的定义

顺序表（Sequential List）：把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接关系来体现。

核心特征：

1. 逻辑相邻 = 物理相邻：这是顺序表最本质的特征
2. 支持随机访问：可以通过下标直接访问任意元素，时间复杂度O(1)
3. 存储密度高：存储密度 = 1（所有存储单元都用于存储数据元素）

数学描述： 设顺序表L的逻辑结构为(a₁, a₂, …, aₙ)，则其物理存储为：

• L.data[0] = a₁
• L.data[1] = a₂
• …
• L.data[n-1] = aₙ

位序与下标的关系：

• 位序（从1开始）：第1个元素、第2个元素、…、第n个元素
• 下标（从0开始）：data[0]、data[1]、…、data[n-1]
• 转换关系：位序i对应下标i-1

1.1.2 静态分配实现

静态分配：使用固定大小的数组来存储顺序表，MaxSize是常量，在编译时就确定了大小。

完整代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50      // 顺序表的最大容量
typedef int ElemType;   // 元素类型

// 顺序表的静态分配实现
typedef struct {
    ElemType data[MaxSize];  // 用数组存储元素
    int length;              // 当前长度（元素个数）
} SeqList;

// 1. 初始化顺序表
void InitList(SeqList &L) {
    L.length = 0;  // 初始时元素个数为0
}

// 2. 按位查找：返回第i个位置的元素
bool GetElem(SeqList L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {  // 检查位序是否合法
        return false;
    }
    e = L.data[i - 1];  // 位序i对应下标i-1
    return true;
}

// 3. 按值查找：返回第一个值为e的元素的位置
int LocateElem(SeqList L, ElemType e) {
    for(int i = 0; i < L.length; i++) {
        if(L.data[i] == e) {
            return i + 1;  // 返回位序（下标+1）
        }
    }
    return 0;  // 查找失败，返回0
}

// 4. 插入操作：在第i个位置插入元素e
bool ListInsert(SeqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) {  // 检查插入位置是否合法
        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;  // 在位置i插入元素
    L.length++;          // 长度加1
    return true;
}

// 5. 删除操作：删除第i个位置的元素，用e返回
bool ListDelete(SeqList &L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {  // 检查删除位置是否合法
        return false;
    }
    e = L.data[i - 1];  // 保存要删除的元素
    // 从前往后移动元素，覆盖被删除的元素
    for(int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;  // 长度减1
    return true;
}

// 6. 打印顺序表
void PrintList(SeqList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

// 测试代码
int main() {
    SeqList L;
    InitList(L);
    
    // 插入测试
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    ListInsert(L, 3, 30);
    printf("插入后的顺序表：");
    PrintList(L);  // 输出：10 20 30
    
    // 按位查找测试
    ElemType e;
    GetElem(L, 2, e);
    printf("第2个位置的元素：%d\n", e);  // 输出：20
    
    // 按值查找测试
    int pos = LocateElem(L, 20);
    printf("元素20的位置：%d\n", pos);  // 输出：2
    
    // 删除测试
    ListDelete(L, 2, e);
    printf("删除的元素：%d\n", e);  // 输出：20
    printf("删除后的顺序表：");
    PrintList(L);  // 输出：10 30
    
    return 0;
}

静态分配的特点：

1. 优点：
   • 代码简单，不需要手动管理内存
   • 没有内存碎片问题
   • 访问速度快（数组直接访问）
2. 缺点：
   • MaxSize必须预先确定，容易造成空间浪费或不足
   • 无法动态扩容
   • 如果MaxSize定义过大，浪费内存；定义过小，容易溢出
3. 适用场景：
   • 数据量已知且固定
   • 对性能要求较高的场景
   • 嵌入式系统等内存受限的环境

1.1.3 动态分配实现

动态分配：使用malloc/realloc动态分配内存，MaxSize是变量，可以在运行时根据需要扩容。

完整代码实现：

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10       // 初始容量
#define INCREMENT 5       // 每次扩容的增量
typedef int ElemType;     // 元素类型

// 顺序表的动态分配实现
typedef struct {
    ElemType *data;   // 指向动态分配数组的指针
    int length;       // 当前长度（元素个数）
    int MaxSize;      // 当前最大容量
} SeqList;

// 1. 初始化顺序表
void InitList(SeqList &L) {
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    if(L.data == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    L.length = 0;
    L.MaxSize = InitSize;
}

// 2. 扩容操作
bool Resize(SeqList &L) {
    ElemType *newData = (ElemType*)realloc(L.data, 
        sizeof(ElemType) * (L.MaxSize + INCREMENT));
    if(newData == NULL) {
        return false;  // 扩容失败
    }
    L.data = newData;
    L.MaxSize += INCREMENT;
    return true;
}

// 3. 按位查找
bool GetElem(SeqList L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    return true;
}

// 4. 按值查找
int LocateElem(SeqList L, ElemType e) {
    for(int i = 0; i < L.length; i++) {
        if(L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

// 5. 插入操作
bool ListInsert(SeqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) {
        return false;
    }
    if(L.length >= L.MaxSize) {
        if(!Resize(L)) {  // 尝试扩容
            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;
}

// 6. 删除操作
bool ListDelete(SeqList &L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    for(int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

// 7. 打印顺序表
void PrintList(SeqList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n当前容量：%d，当前长度：%d\n", L.MaxSize, L.length);
}

// 8. 销毁顺序表
void DestroyList(SeqList &L) {
    if(L.data != NULL) {
        free(L.data);
        L.data = NULL;
    }
    L.length = 0;
    L.MaxSize = 0;
}

// 测试代码
int main() {
    SeqList L;
    InitList(L);
    
    // 插入测试：插入15个元素，观察扩容过程
    for(int i = 1; i <= 15; i++) {
        ListInsert(L, i, i * 10);
        printf("插入%d后：", i * 10);
        PrintList(L);
    }
    
    // 按位查找测试
    ElemType e;
    GetElem(L, 5, e);
    printf("第5个位置的元素：%d\n", e);
    
    // 按值查找测试
    int pos = LocateElem(L, 80);
    printf("元素80的位置：%d\n", pos);
    
    // 删除测试
    ListDelete(L, 3, e);
    printf("删除的元素：%d\n", e);
    printf("删除后的顺序表：");
    PrintList(L);
    
    // 销毁顺序表
    DestroyList(L);
    
    return 0;
}

动态分配的特点：

1. 优点：
   • 可以根据需要动态扩容，不会造成空间浪费
   • 灵活性高，适合数据量变化的场景
2. 缺点：
   • 需要手动管理内存（malloc/free）
   • 扩容时需要重新分配内存并复制数据，有性能开销
   • 容易产生内存碎片
   • 代码复杂度较高
3. 适用场景：
   • 数据量未知或变化较大
   • 需要灵活管理内存的场景
   • 通用性要求较高的库函数

1.1.4 顺序表的特点

优点：

1. 支持随机访问：可以通过下标直接访问任意元素，时间复杂度O(1)
2. 存储密度高：存储密度 = 1，所有存储单元都用于存储数据元素
3. cache友好：连续的内存布局有利于CPU cache的命中

缺点：

1. 插入删除效率低：需要移动大量元素，时间复杂度O(n)
2. 需要预分配空间：静态分配容易造成空间浪费或不足
3. 存储空间不灵活：一旦分配，大小难以改变（静态分配）

适用场景：

1. 数据量已知且稳定
2. 查找操作频繁，插入删除操作较少
3. 对访问速度要求较高

不适用场景：

1. 数据量变化很大
2. 插入删除操作频繁
3. 需要频繁改变表的大小

1.2 算法实现与复杂度分析

1.2.1 初始化操作

静态分配初始化：

void InitList(SeqList &L) {
    L.length = 0;
}

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

动态分配初始化：

void InitList(SeqList &L) {
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    if(L.data == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    L.length = 0;
    L.MaxSize = InitSize;
}

• 时间复杂度：O(1)（malloc的时间复杂度是O(1)）
• 空间复杂度：O(InitSize)（分配了InitSize个元素的存储空间）

1.2.2 插入操作

算法实现（以静态分配为例）：

bool ListInsert(SeqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) {  // 检查插入位置
        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;
}

复杂度分析：

1. 最好情况：在表尾插入（i = length + 1）
   • 不需要移动元素
   • 时间复杂度：O(1)
2. 最坏情况：在表头插入（i = 1）
   • 需要移动所有n个元素
   • 时间复杂度：O(n)
3. 平均情况：假设在任意位置插入的概率相等（都是1/(n+1)）
   • 在位置i插入，需要移动n-i+1个元素
   • 平均移动次数 = Σ(i=1 to n+1) [(n-i+1) × 1/(n+1)]
   • = [n + (n-1) + … + 1 + 0] / (n+1)
   • = n(n+1)/2 / (n+1)
   • = n/2
   • 时间复杂度：O(n)

空间复杂度：O(1)（只需要常数级别的额外空间）

1.2.3 删除操作

算法实现：

bool ListDelete(SeqList &L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {  // 检查删除位置
        return false;
    }
    e = L.data[i - 1];  // 保存被删除的元素
    // 从前往后移动元素
    for(int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

复杂度分析：

1. 最好情况：删除表尾元素（i = length）
   • 不需要移动元素
   • 时间复杂度：O(1)
2. 最坏情况：删除表头元素（i = 1）
   • 需要移动n-1个元素
   • 时间复杂度：O(n)
3. 平均情况：假设删除任意位置的概率相等（都是1/n）
   • 删除位置i，需要移动n-i个元素
   • 平均移动次数 = Σ(i=1 to n) [(n-i) × 1/n]
   • = [(n-1) + (n-2) + … + 0] / n
   • = n(n-1)/2 / n
   • = (n-1)/2
   • 时间复杂度：O(n)

空间复杂度：O(1)

1.2.4 按位查找

算法实现：

bool GetElem(SeqList L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    return true;
}

复杂度分析：

• 直接通过下标访问，不需要遍历
• 时间复杂度：O(1)
• 空间复杂度：O(1)

这就是顺序表"随机访问"特性的体现。

1.2.5 按值查找

算法实现：

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

复杂度分析：

1. 最好情况：查找的元素在表头（i = 0）
   • 比较1次就找到
   • 时间复杂度：O(1)
2. 最坏情况：查找的元素在表尾或不存在
   • 需要比较n次
   • 时间复杂度：O(n)
3. 平均情况：假设查找每个元素的概率相等（都是1/n），查找成功的概率为p
   • 查找成功时，平均比较次数 = Σ(i=1 to n) [i × 1/n] = (n+1)/2
   • 查找失败时，需要比较n次
   • 总的平均比较次数 = p × (n+1)/2 + (1-p) × n
   • 如果p = 1（一定查找成功），平均比较次数 = (n+1)/2
   • 时间复杂度：O(n)

空间复杂度：O(1)

1.2.6 复杂度总结表

1.3 图示说明

1.3.1 顺序表结构图

说明：

• 蓝色部分：逻辑结构，表示数据元素之间的逻辑关系
• 绿色部分：已使用的存储空间（length = n）
• 黄色部分：空闲的存储空间（MaxSize - n）
• 位序从1开始，下标从0开始

1.3.2 插入操作过程图

插入操作的关键点：

1. 从后往前移动元素（避免覆盖）
2. 移动范围：从length到i（包含i）
3. 插入位置：data[i-1]（位序i对应下标i-1）
4. length加1

1.3.3 删除操作过程图

删除操作的关键点：

1. 从前往后移动元素（覆盖被删除的元素）
2. 移动范围：从i到length-1（不包含length）
3. 删除位置：data[i-1]
4. length减1

1.3.4 静态分配vs动态分配对比图

1.3.5 静态分配vs动态分配对比表

1.4 常见误区与踩坑实录

误区1：插入位置的范围搞错

错误认知：插入位置i的范围是1 <= i <= length

正确理解：插入位置i的范围是1 <= i <= length + 1

踩坑经历：

// 我当时的错误代码
bool ListInsert(SeqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length) {  // ❌ 错误：漏掉了i = length + 1的情况
        return false;
    }
    // ...
}

为什么可以在length+1位置插入：

• 当i = length + 1时，表示在表尾插入
• 此时不需要移动任何元素，直接在data[length]位置插入即可
• 这是合法的操作

正确代码：

bool ListInsert(SeqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) {  // ✅ 正确
        return false;
    }
    // ...
}

误区2：插入时元素移动方向搞反

错误代码：

bool ListInsert(SeqList &L, int i, ElemType e) {
    // ...
    for(int j = i; j < L.length; j++) {  // ❌ 从前往后移动
        L.data[j] = L.data[j - 1];
    }
    // ...
}

问题分析： 假设顺序表为[10, 20, 30, 40]，要在位置2插入50：

• j=2: data[2] = data[1] = 20 → [10, 20, 20, 40]
• j=3: data[3] = data[2] = 20 → [10, 20, 20, 20]
• 结果：所有元素都被覆盖成20了！

正确做法：从后往前移动

for(int j = L.length; j >= i; j--) {  // ✅ 从后往前
    L.data[j] = L.data[j - 1];
}

移动过程：

• j=4: data[4] = data[3] = 40 → [10, 20, 30, 40, 40]
• j=3: data[3] = data[2] = 30 → [10, 20, 30, 30, 40]
• j=2: data[2] = data[1] = 20 → [10, 20, 20, 30, 40]
• 停止（j < i=2）
• data[1] = 50 → [10, 50, 20, 30, 40]

误区3：删除时元素移动方向搞反

错误代码：

bool ListDelete(SeqList &L, int i, ElemType &e) {
    // ...
    for(int j = L.length - 1; j >= i; j--) {  // ❌ 从后往前移动
        L.data[j - 1] = L.data[j];
    }
    // ...
}

问题分析： 假设顺序表为[10, 20, 30, 40]，要删除位置2的元素：

• j=4: data[3] = data[4]（越界！）
• 即使不越界，从后往前移动会导致元素被重复覆盖

正确做法：从前往后移动

for(int j = i; j < L.length; j++) {  // ✅ 从前往后
    L.data[j - 1] = L.data[j];
}

误区4：动态分配时忘记检查malloc/realloc的返回值

错误代码：

void InitList(SeqList &L) {
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);  // ❌ 没有检查返回值
    L.length = 0;
    L.MaxSize = InitSize;
}

问题分析：

• malloc可能返回NULL（内存不足时）
• 如果不检查，后续访问L.data会导致段错误

正确做法：

void InitList(SeqList &L) {
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    if(L.data == NULL) {  // ✅ 检查返回值
        printf("内存分配失败！\n");
        exit(1);
    }
    L.length = 0;
    L.MaxSize = InitSize;
}

误区5：动态分配时函数参数不用引用传递

错误代码：

void InitList(SeqList L) {  // ❌ 值传递
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

int main() {
    SeqList L;
    InitList(L);  // L不会被初始化
    // ...
}

问题分析：

• 值传递时，函数内部修改的是形参L，不影响实参L
• 函数结束后，实参L的data指针仍然是未初始化的

正确做法：

void InitList(SeqList &L) {  // ✅ 引用传递
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

误区6：忘记释放动态分配的内存

错误代码：

int main() {
    SeqList L;
    InitList(L);
    // ... 使用顺序表
    return 0;  // ❌ 没有释放L.data
}

问题分析：

• 动态分配的内存不会自动释放
• 程序结束时，L.data指向的内存仍然是占用状态
• 造成内存泄漏

正确做法：

int main() {
    SeqList L;
    InitList(L);
    // ... 使用顺序表
    free(L.data);  // ✅ 释放内存
    L.data = NULL;  // ✅ 避免野指针
    return 0;
}

误区7：浮点数比较直接用==

错误代码：

int LocateElem(SeqList L, float e) {
    for(int i = 0; i < L.length; i++) {
        if(L.data[i] == e) {  // ❌ 浮点数直接用==比较
            return i + 1;
        }
    }
    return 0;
}

问题分析：

• 浮点数在计算机中是近似存储的
• 0.1 + 0.2 可能不等于 0.3（可能是0.30000001或0.29999999）
• 直接用==比较可能因为精度问题导致查找失败

正确做法：

#define EPSILON 1e-6

int LocateElem(SeqList L, float e) {
    for(int i = 0; i < L.length; i++) {
        if(fabs(L.data[i] - e) < EPSILON) {  // ✅ 浮点数比较
            return i + 1;
        }
    }
    return 0;
}

误区8：平均复杂度的推导错误

错误推导： “插入操作平均需要移动n/2个元素，所以时间复杂度是O(n/2)”

问题分析：

• 时间复杂度不看系数，只看最高次项
• O(n/2) = O(n)，不是O(n/2)

正确推导：

• 平均移动次数 = n/2
• 时间复杂度 = O(n/2) = O(n)

误区9：混淆位序和下标

错误代码：

bool GetElem(SeqList L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i];  // ❌ 位序i应该对应下标i-1
    return true;
}

正确代码：

bool GetElem(SeqList L, int i, ElemType &e) {
    if(i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];  // ✅ 位序i对应下标i-1
    return true;
}

误区10：扩容时直接修改原指针

错误代码：

bool Resize(SeqList &L) {
    L.data = (ElemType*)realloc(L.data, sizeof(ElemType) * (L.MaxSize + INCREMENT));  // ❌ 直接修改
    if(L.data == NULL) {
        return false;
    }
    L.MaxSize += INCREMENT;
    return true;
}

问题分析：

• 如果realloc失败，返回NULL
• 直接赋值给L.data，会导致原来的内存地址丢失
• 造成内存泄漏

正确做法：

bool Resize(SeqList &L) {
    ElemType *newData = (ElemType*)realloc(L.data, 
        sizeof(ElemType) * (L.MaxSize + INCREMENT));
    if(newData == NULL) {  // ✅ 先检查
        return false;
    }
    L.data = newData;  // ✅ 成功后再赋值
    L.MaxSize += INCREMENT;
    return true;
}

模块2：真题解析

2.1 真题精选

真题1：2016年第38题（算法设计题）

题目： 设计一个算法，将顺序表L中的所有元素逆置，要求算法空间复杂度为O(1)。

解析：

这道题考查的是顺序表的原地操作能力。

错误思路：使用额外的数组

void Reverse(SeqList L) {
    ElemType temp[MaxSize];  // 空间复杂度O(n)
    for(int i = 0; i < L.length; i++) {
        temp[i] = L.data[i];
    }
    for(int i = 0; i < L.length; i++) {
        L.data[i] = temp[L.length - 1 - i];
    }
}

正确思路：双指针原地交换

void Reverse(SeqList &L) {
    ElemType temp;
    for(int i = 0, j = L.length - 1; i < j; i++, j--) {
        temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
}

复杂度分析：

• 时间复杂度：O(n)，需要交换n/2次
• 空间复杂度：O(1)，只使用了常数个额外变量

关键点：

1. 双指针从两端向中间移动
2. 交换操作只需要一个临时变量
3. 循环条件是i < j（不是i <= j）

真题2：2018年第2题（选择题）

题目： 在顺序表中第i个位置插入一个新元素，若i的合法范围是1 ≤ i ≤ n+1，则顺序表当前的长度为（ ）。

A. n-1 B. n C. n+1 D. 无法确定

解析：

答案：B

分析：

• 设顺序表当前长度为length
• 插入位置的合法范围是1 ≤ i ≤ length + 1
• 题目给出合法范围是1 ≤ i ≤ n + 1
• 因此length + 1 = n + 1，即length = n

易错点：

• 有些同学会选C，认为length = n + 1
• 这是混淆了"插入后的长度"和"插入前的长度"
• 题目问的是"当前的长度"，即插入前的长度

真题3：2019年第3题（选择题）

题目： 在长度为n的顺序表中删除第i个元素（1 ≤ i ≤ n），平均需要移动（ ）个元素。

A. n/2 B. (n-1)/2 C. (n+1)/2 D. n

解析：

答案：B

分析：

• 删除第1个元素，需要移动n-1个元素
• 删除第2个元素，需要移动n-2个元素
• …
• 删除第i个元素，需要移动n-i个元素
• …
• 删除第n个元素，需要移动0个元素
• 假设删除每个位置的概率相等（都是1/n）
• 平均移动次数 = Σ(i=1 to n) [(n-i) × 1/n]
• = [(n-1) + (n-2) + … + 0] / n
• = n(n-1)/2 / n
• = (n-1)/2

易错点：

• 有些同学会选A，认为平均移动n/2个元素
• 这是把删除和插入搞混了
• 插入操作平均移动n/2个元素（可以在n+1个位置插入）
• 删除操作平均移动(n-1)/2个元素（只能在n个位置删除）

真题4：2020年第1题（选择题）

题目： 顺序表具有的优点是（ ）。

A. 便于插入和删除操作 B. 可以方便地用于存储逻辑上相邻的数据 C. 可以方便地用于存储物理上相邻的数据 D. 存储密度高

解析：

答案：D

分析：

• A错误：顺序表的插入删除需要移动大量元素，效率低
• B错误：这是顺序表的特点，但不是"优点"的准确表述
• C错误：顺序表存储的是逻辑上相邻的数据，物理上自然相邻
• D正确：顺序表的存储密度 = 1，所有存储单元都用于存储数据元素

知识点：

• 存储密度 = 数据元素本身占用的空间 / 分配给该数据结构的总空间
• 顺序表的存储密度 = 1（最高）
• 链表的存储密度 < 1（需要额外的指针域）

真题5：2017年第5题（选择题）

题目： 若顺序表L的当前长度为5，现在要在第3个位置插入一个元素，需要移动（ ）个元素。

A. 2 B. 3 C. 4 D. 5

解析：

答案：B

分析：

• 当前长度length = 5
• 插入位置i = 3
• 需要移动的元素个数 = length - i + 1 = 5 - 3 + 1 = 3
• 具体移动：第5个、第4个、第3个元素都要向后移动一位

验证： 假设顺序表为[10, 20, 30, 40, 50]，在第3个位置插入60：

• 移动第5个元素：data[5] = data[4] = 50
• 移动第4个元素：data[4] = data[3] = 40
• 移动第3个元素：data[3] = data[2] = 30
• 插入：data[2] = 60
• 结果：[10, 20, 60, 30, 40, 50]

真题6：2015年第38题（算法设计题）

题目： 从顺序表L中删除其值在给定值s与t之间（要求s < t）的所有元素，如果s或t不合理或顺序表为空，则返回错误信息。

解析：

思路：

1. 检查s < t是否合理，检查顺序表是否为空
2. 从头遍历顺序表，找到第一个值 >= s的元素
3. 从该元素开始，找到第一个值 > t的元素
4. 将这两个位置之间的元素删除（通过移动元素实现）

代码实现：

bool DeleteRange(SeqList &L, ElemType s, ElemType t) {
    if(s >= t || L.length == 0) {
        return false;
    }
    
    int i, j;
    // 找到第一个值 >= s的元素
    for(i = 0; i < L.length && L.data[i] < s; i++);
    
    if(i >= L.length) {  // 所有元素都 < s
        return false;
    }
    
    // 找到第一个值 > t的元素
    for(j = i; j < L.length && L.data[j] <= t; j++);
    
    // 将j及之后的元素前移
    for(int k = j; k < L.length; k++) {
        L.data[k - (j - i)] = L.data[k];
    }
    
    L.length -= (j - i);
    return true;
}

复杂度分析：

• 时间复杂度：O(n)，最多遍历两次
• 空间复杂度：O(1)

关键点：

1. 先找到要删除的区间[i, j)
2. 通过移动元素实现批量删除
3. 移动的元素个数是j - i

真题7：2019年第38题（算法设计题）

题目： 设计一个算法，从顺序表L中删除其值等于给定值x的元素，要求算法时间复杂度为O(n)。

解析：

思路：

• 使用双指针法
• 一个指针i用于遍历顺序表
• 一个指针k记录不等于x的元素的个数
• 遍历完成后，顺序表的前k个元素就是不等于x的元素

代码实现：

bool DeleteX(SeqList &L, ElemType x) {
    int k = 0;  // 记录不等于x的元素个数
    for(int i = 0; i < L.length; i++) {
        if(L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
    return true;
}

复杂度分析：

• 时间复杂度：O(n)，只遍历一次
• 空间复杂度：O(1)

关键点：

1. 双指针法，一个遍历，一个记录
2. 不需要移动元素，直接覆盖
3. 最后更新length即可

真题8：2021年第2题（选择题）

题目： 下列关于顺序表的叙述中，正确的是（ ）。

A. 顺序表是一种线性结构 B. 顺序表是一种非线性结构 C. 顺序表只能存储整型数据 D. 顺序表的长度必须固定

解析：

答案：A

分析：

• A正确：顺序表是线性表的顺序存储结构，属于线性结构
• B错误：顺序表是线性结构，不是非线性结构
• C错误：顺序表可以存储任意类型的数据（通过typedef定义ElemType）
• D错误：动态分配的顺序表长度可以改变

知识点：

• 线性结构：数据元素之间存在一对一的线性关系
• 非线性结构：数据元素之间存在一对多或多对多的关系
• 线性表（包括顺序表和链表）都是线性结构

2.2 命题规律总结

选择题命题规律

1. 顺序表的特点（高频考点）
   • 随机访问（O(1)）
   • 存储密度高（= 1）
   • 插入删除效率低（O(n)）
   • 需要预分配空间
2. 复杂度分析（必考）
   • 插入操作的平均移动次数：n/2
   • 删除操作的平均移动次数：(n-1)/2
   • 按值查找的平均比较次数：(n+1)/2
   • 按位查找的时间复杂度：O(1)
3. 边界条件（易错点）
   • 插入位置范围：1 ≤ i ≤ length + 1
   • 删除位置范围：1 ≤ i ≤ length
   • 位序与下标的转换关系
4. 静态分配vs动态分配（对比题）
   • 内存分配方式
   • 是否可以扩容
   • 是否需要手动释放

算法题命题规律

1. 基础操作（必会）
   • 插入、删除、查找的实现
   • 注意边界条件和参数传递
2. 逆置操作（高频）
   • 双指针原地交换
   • 空间复杂度O(1)
3. 删除操作（变体多）
   • 删除指定值的元素
   • 删除指定范围的元素
   • 删除重复元素
4. 合并操作（综合题）
   • 两个有序顺序表的合并
   • 要求时间复杂度O(n)

综合题命题规律

1. 结合其他数据结构
   • 顺序表 + 链表
   • 顺序表 + 栈
   • 顺序表 + 队列
2. 实际应用问题
   • 学生成绩管理
   • 图书信息管理
   • 通讯录管理
3. 算法设计
   • 要求时间复杂度和空间复杂度最优
   • 要求代码简洁、正确

模块3：AI命题Prompt

3.1 命题Prompt模板

# 角色设定
你是一位资深的408考研数据结构命题专家，熟悉历年真题的命题规律和难度分布。

# 任务要求
请根据以下要求，为"顺序表及其基本运算"这一节命制高质量的试题：

## 知识点范围
- 顺序表的定义和特点
- 静态分配实现
- 动态分配实现
- 插入、删除、查找操作
- 复杂度分析
- 边界条件

## 题型要求
1. 选择题（4-6道）
   - 考查基础概念和复杂度分析
   - 设置合理的干扰项
   - 难度分布：简单2道，中等2道，较难1-2道

2. 算法设计题（1-2道）
   - 考查顺序表的基本操作
   - 要求时间复杂度和空间复杂度最优
   - 需要给出完整的C语言代码

3. 综合应用题（1道）
   - 结合实际应用场景
   - 需要综合运用多个知识点
   - 要求分析复杂度

## 命题原则
1. 题目表述清晰、准确，无歧义
2. 难度符合408真题水平
3. 知识点覆盖全面
4. 干扰项具有迷惑性
5. 答案和解析详细、准确

## 输出格式
每道题请按照以下格式输出：

### 题目X：[题型] [难度]
**题目内容**：
[完整的题目描述]

**选项**（如果是选择题）：
A. [选项A]
B. [选项B]
C. [选项C]
D. [选项D]

**答案**：[正确答案]

**解析**：
[详细的解题思路和分析]

**考查知识点**：[本题考查的知识点]

**易错点**：[考生容易犯的错误]

3.2 AI生成的题目示例

题目1：选择题（简单）

题目内容： 顺序表的特点是（ ）。

A. 便于插入和删除操作 B. 可以随机访问任意元素 C. 存储密度小于1 D. 需要额外的指针域

答案：B

解析：

• A错误：顺序表的插入删除需要移动大量元素，效率低
• B正确：顺序表支持随机访问，可以通过下标直接访问任意元素，时间复杂度O(1)
• C错误：顺序表的存储密度 = 1，所有存储单元都用于存储数据元素
• D错误：顺序表不需要额外的指针域，这是链表的特点

考查知识点：顺序表的基本特点

易错点：容易选A，混淆了顺序表和链表的优缺点

题目2：选择题（中等）

题目内容： 在长度为n的顺序表中，在第i个位置（1 ≤ i ≤ n+1）插入一个新元素，需要移动（ ）个元素。

A. n - i B. n - i + 1 C. n - i - 1 D. i

答案：B

解析：

• 在第i个位置插入，需要将第i个、第i+1个、…、第n个元素都向后移动一位
• 需要移动的元素个数 = n - i + 1
• 例如：n = 5, i = 3，需要移动第3、4、5个元素，共3个 = 5 - 3 + 1

考查知识点：插入操作的元素移动次数

易错点：容易选A，漏掉了第i个元素本身也需要移动

题目3：选择题（中等）

题目内容： 下列关于顺序表的叙述中，错误的是（ ）。

A. 顺序表采用连续存储方式 B. 顺序表的逻辑顺序与物理顺序一致 C. 顺序表适合频繁插入和删除的场景 D. 顺序表可以动态扩容

答案：C

解析：

• A正确：顺序表采用连续的存储单元，物理上相邻
• B正确：顺序表的逻辑顺序与物理顺序一致
• C错误：顺序表的插入删除需要移动大量元素，不适合频繁插入删除的场景
• D正确：动态分配的顺序表可以动态扩容

考查知识点：顺序表的特点和适用场景

易错点：容易选D，认为顺序表不能扩容（静态分配不能，但动态分配可以）

题目4：选择题（较难）

题目内容： 在顺序表中按值查找某个元素，假设查找成功的概率为p，查找每个元素的概率相等，则平均比较次数为（ ）。

A. (n+1)/2 B. p(n+1)/2 + (1-p)n C. p(n+1)/2 D. n/2

答案：B

解析：

• 查找成功时，平均比较次数 = (n+1)/2
• 查找失败时，需要比较n次
• 查找成功的概率为p，查找失败的概率为1-p
• 总的平均比较次数 = p × (n+1)/2 + (1-p) × n

考查知识点：按值查找的平均复杂度

易错点：容易选A，只考虑了查找成功的情况

题目5：算法设计题

题目内容： 设计一个算法，将两个有序顺序表L1和L2合并为一个新的有序顺序表L3。要求算法时间复杂度为O(n+m)，其中n和m分别是L1和L2的长度。

答案：

bool Merge(SeqList L1, SeqList L2, SeqList &L3) {
    if(L1.length + L2.length > MaxSize) {
        return false;
    }
    
    int i = 0, j = 0, k = 0;
    // 比较两个表的元素，将较小的放入L3
    while(i < L1.length && j < L2.length) {
        if(L1.data[i] <= L2.data[j]) {
            L3.data[k++] = L1.data[i++];
        } else {
            L3.data[k++] = L2.data[j++];
        }
    }
    
    // 将剩余的元素放入L3
    while(i < L1.length) {
        L3.data[k++] = L1.data[i++];
    }
    while(j < L2.length) {
        L3.data[k++] = L2.data[j++];
    }
    
    L3.length = k;
    return true;
}

解析：

• 使用双指针法，分别指向L1和L2的当前元素
• 比较两个指针指向的元素，将较小的放入L3
• 当一个表遍历完后，将另一个表的剩余元素直接放入L3
• 时间复杂度：O(n+m)，每个元素最多比较一次
• 空间复杂度：O(1)（不考虑L3的空间）

考查知识点：有序顺序表的合并

易错点：

1. 忘记处理剩余元素
2. 没有检查L3是否溢出
3. 时间复杂度分析错误

题目6：综合应用题

题目内容： 某系统需要管理1000个学生的成绩，要求实现以下功能：

1. 按学号查找学生成绩
2. 按成绩排序
3. 插入新学生的成绩
4. 删除已毕业学生的成绩

请回答以下问题： （1）应该选择哪种存储结构？为什么？ （2）如果选择顺序表，请分析各操作的时间复杂度 （3）如果选择链表，请分析各操作的时间复杂度 （4）综合考虑，你会选择哪种结构？为什么？

答案：

（1）应该选择顺序表。

• 数据量固定（1000个学生）
• 查找操作频繁（按学号查找）
• 顺序表支持随机访问，查找效率高

（2）顺序表各操作的时间复杂度：

• 按学号查找：如果学号有序，可以二分查找，O(log n)；如果无序，O(n)
• 按成绩排序：O(n²)（冒泡排序）或O(n log n)（快速排序）
• 插入新学生：O(n)（需要移动元素）
• 删除已毕业学生：O(n)（需要移动元素）

（3）链表各操作的时间复杂度：

• 按学号查找：O(n)（需要遍历）
• 按成绩排序：O(n²)（冒泡排序）或O(n log n)（归并排序）
• 插入新学生：O(1)（已知位置）或O(n)（需要查找位置）
• 删除已毕业学生：O(1)（已知位置）或O(n)（需要查找位置）

（4）综合考虑，选择顺序表。

• 查找操作频繁，顺序表的随机访问优势明显
• 数据量固定，不会造成空间浪费
• 插入删除操作虽然效率低，但可以接受

考查知识点：存储结构的选择

易错点：

1. 没有考虑具体场景，直接选择链表
2. 复杂度分析错误
3. 没有综合考虑各因素

3.3 使用说明

如何使用AI命题Prompt

1. 复制Prompt模板：将3.1节的模板复制到AI对话中
2. 调整参数：根据需要调整题型、难度、知识点范围
3. 生成题目：让AI生成题目
4. 人工审核：检查题目的准确性、难度是否合适
5. 补充完善：根据审核结果，让AI修改或补充

命题注意事项

1. 知识点覆盖：确保覆盖本节的所有重要知识点
2. 难度分布：简单、中等、较难的比例要合理（约3:5:2）
3. 干扰项设计：干扰项要具有迷惑性，但不能有歧义
4. 答案准确：答案必须准确，解析必须详细
5. 格式规范：题目格式要符合408真题的规范

命题示例流程

1. 输入Prompt模板
2. AI生成10道题目
3. 人工审核：
   - 检查知识点覆盖：覆盖了顺序表的特点、复杂度、边界条件等
   - 检查难度分布：简单3道，中等5道，较难2道
   - 检查答案准确性：发现第3题答案有误
4. 让AI修改第3题
5. 最终确定10道题目

模块4：AI讲题Prompt

4.1 讲题Prompt模板

# 角色设定
你是一位耐心细致的408考研数据结构辅导老师，擅长用通俗易懂的语言讲解复杂的知识点。

# 任务要求
请针对以下题目，进行详细的讲解：

## 讲解要求
1. **题目分析**：分析题目考查的知识点和解题思路
2. **解题过程**：逐步讲解解题过程，每一步都要解释清楚"为什么"
3. **易错点提醒**：指出考生容易犯的错误
4. **知识拓展**：拓展相关的知识点，帮助考生建立知识体系
5. **总结归纳**：总结本题的解题方法和技巧

## 讲解风格
1. 语言通俗易懂，避免过于学术化
2. 多用例子和图示，帮助理解
3. 注重思路的引导，而不是直接给答案
4. 适当加入"踩坑经历"，增加亲切感

## 输出格式
请按照以下格式输出：

### 题目回顾
[完整的题目内容]

### 题目分析
- **考查知识点**：[本题考查的知识点]
- **解题思路**：[解题的总体思路]
- **难度评估**：[本题的难度]

### 详细讲解
[逐步讲解解题过程]

### 易错点提醒
[考生容易犯的错误]

### 知识拓展
[相关的知识点拓展]

### 总结归纳
[解题方法和技巧的总结]

4.2 AI生成的讲解示例

示例1：讲解2016年第38题

题目回顾： 设计一个算法，将顺序表L中的所有元素逆置，要求算法空间复杂度为O(1)。

题目分析：

• 考查知识点：顺序表的原地操作、双指针法
• 解题思路：使用双指针从两端向中间交换元素
• 难度评估：中等（容易想到用辅助数组，但空间复杂度不符合要求）

详细讲解：

同学们好，今天我们来讲解2016年的这道算法题。

首先，我们来看题目要求：将顺序表逆置，空间复杂度O(1)。

第一步：理解题意

顺序表逆置，就是把第一个元素和最后一个元素交换，第二个元素和倒数第二个元素交换，以此类推。

比如：[10, 20, 30, 40, 50] 逆置后变成 [50, 40, 30, 20, 10]

第二步：分析空间复杂度

题目要求空间复杂度O(1)，这意味着我们不能使用额外的数组。

我踩过这个坑：当时第一反应就是用辅助数组，结果写完才发现空间复杂度不对。

// 错误示范
void Reverse(SeqList L) {
    ElemType temp[MaxSize];  // ❌ 空间复杂度O(n)
    // ...
}

第三步：双指针法

既然不能用额外数组，那我们就只能在原数组上操作。

思路：

• 用两个指针i和j，分别指向首尾
• 交换i和j指向的元素
• i向后移动，j向前移动
• 直到i >= j

void Reverse(SeqList &L) {
    ElemType temp;
    for(int i = 0, j = L.length - 1; i < j; i++, j--) {
        temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
}

第四步：验证正确性

以[10, 20, 30, 40, 50]为例：

• 初始：i=0, j=4
• 第1次交换：i=0, j=4 → [50, 20, 30, 40, 10]，i=1, j=3
• 第2次交换：i=1, j=3 → [50, 40, 30, 20, 10]，i=2, j=2
• 循环结束（i >= j）

结果正确！

第五步：复杂度分析

• 时间复杂度：O(n)，需要交换n/2次
• 空间复杂度：O(1)，只使用了temp一个额外变量

易错点提醒：

1. 循环条件错误：写成i <= j
   • 当i = j时，不需要交换（自己和自己交换）
   • 正确条件是i < j
2. 参数传递错误：写成SeqList L（值传递）
   • 值传递不会修改原顺序表
   • 正确是SeqList &L（引用传递）
3. 使用辅助数组：空间复杂度O(n)
   • 不符合题目要求
   • 必须原地操作

知识拓展：

1. 双指针法的适用场景：
   • 逆置操作
   • 判断回文
   • 有序表的合并
2. 原地操作的技巧：
   • 交换操作（使用临时变量）
   • 覆盖操作（直接赋值）

总结归纳：

1. 顺序表逆置使用双指针法
2. 注意空间复杂度要求（O(1)）
3. 循环条件是i < j（不是i <= j）
4. 参数传递要用引用传递（&）

示例2：讲解2019年第3题

题目回顾： 在长度为n的顺序表中删除第i个元素（1 ≤ i ≤ n），平均需要移动（ ）个元素。

A. n/2 B. (n-1)/2 C. (n+1)/2 D. n

题目分析：

• 考查知识点：删除操作的平均复杂度
• 解题思路：列举所有情况，求平均值
• 难度评估：中等（容易和插入操作搞混）

详细讲解：

同学们好，我们来讲解这道关于删除操作平均复杂度的题目。

第一步：理解删除操作

删除第i个元素，需要将第i+1个、第i+2个、…、第n个元素都向前移动一位。

移动的元素个数 = n - i

第二步：列举所有情况

• 删除第1个元素：移动n-1个元素
• 删除第2个元素：移动n-2个元素
• …
• 删除第i个元素：移动n-i个元素
• …
• 删除第n个元素：移动0个元素

第三步：求平均值

假设删除每个位置的概率相等（都是1/n）

平均移动次数 = Σ(i=1 to n) [(n-i) × 1/n] = [(n-1) + (n-2) + … + 0] / n = n(n-1)/2 / n = (n-1)/2

所以答案是B。

第四步：验证

以n=5为例：

• 删除第1个：移动4个
• 删除第2个：移动3个
• 删除第3个：移动2个
• 删除第4个：移动1个
• 删除第5个：移动0个
• 平均 = (4+3+2+1+0)/5 = 10/5 = 2 = (5-1)/2 ✓

易错点提醒：

1. 和插入操作搞混：
   • 插入操作平均移动n/2个元素
   • 删除操作平均移动(n-1)/2个元素
   • 区别：插入可以在n+1个位置，删除只能在n个位置
2. 计算错误：
   • 求和公式：1+2+…+n = n(n+1)/2
   • 本题是：0+1+…+(n-1) = n(n-1)/2

知识拓展：

1. 插入操作的平均移动次数：
   • 可以在n+1个位置插入
   • 平均移动次数 = n/2
2. 按值查找的平均比较次数：
   • 查找成功：(n+1)/2
   • 查找失败：n

总结归纳：

1. 删除操作平均移动(n-1)/2个元素
2. 插入操作平均移动n/2个元素
3. 要区分"可以操作的位置数"

4.3 易错题记录

易错题1：插入位置的范围

题目：在顺序表中插入元素，i的合法范围是？

错误答案：1 ≤ i ≤ length

正确答案：1 ≤ i ≤ length + 1

错因分析：忘记了可以在表尾插入

纠正方法：记住插入可以在length+1个位置进行

易错题2：删除操作的平均移动次数

题目：删除第i个元素，平均移动多少个元素？

错误答案：n/2

正确答案：(n-1)/2

错因分析：和插入操作搞混了

纠正方法：删除只能在n个位置，插入可以在n+1个位置

易错题3：双指针法的循环条件

题目：顺序表逆置，循环条件是？

错误答案：i <= j

正确答案：i < j

错因分析：没有考虑i = j的情况

纠正方法：i = j时不需要交换，所以是i < j

模块5：AI错题复盘Prompt

5.1 错题复盘Prompt模板

# 角色设定
你是一位经验丰富的408考研数据结构辅导老师，擅长帮助学生分析错题、找出问题根源。

# 任务要求
请针对学生的错题，进行深入的复盘分析：

## 复盘要求
1. **错题回顾**：完整呈现题目和学生的错误答案
2. **错因分析**：深入分析学生为什么会犯这个错误
3. **正确解法**：详细讲解正确的解题过程
4. **知识点梳理**：梳理相关的知识点
5. **同类题拓展**：给出类似的题目，帮助巩固
6. **预防措施**：给出避免再犯的建议

## 复盘风格
1. 语气亲切，像朋友一样交流
2. 多鼓励，少批评
3. 注重思路的引导
4. 适当分享"踩坑经历"

## 输出格式
请按照以下格式输出：

### 错题回顾
- **题目**：[完整的题目]
- **我的答案**：[学生的错误答案]
- **正确答案**：[正确答案]

### 错因分析
- **表面原因**：[直接导致错误的原因]
- **深层原因**：[根本原因，如概念不清、方法不对等]
- **踩坑经历**：[类似的踩坑经历]

### 正确解法
[详细的正确解题过程]

### 知识点梳理
[相关的知识点总结]

### 同类题拓展
[2-3道类似的题目]

### 预防措施
[避免再犯的具体建议]

5.2 AI生成的复盘示例

示例1：复盘"插入位置范围"错题

错题回顾：

• 题目：在顺序表中第i个位置插入元素，i的合法范围是？
• 我的答案：1 ≤ i ≤ length
• 正确答案：1 ≤ i ≤ length + 1

错因分析：

表面原因：忘记了可以在表尾插入

深层原因：对"插入"操作的理解不够深入，没有考虑到"在最后一个元素之后插入"这种情况

踩坑经历：我当时也犯了这个错误。我当时的想法是：顺序表有length个元素，所以只能在1到length的位置插入。后来做真题才发现，可以在表尾插入，也就是length+1的位置。

正确解法：

让我们来分析一下插入操作：

1. 在表头插入（i = 1）：所有元素向后移动一位
2. 在中间插入（1 < i ≤ length）：部分元素向后移动
3. 在表尾插入（i = length + 1）：不需要移动元素

这三种情况都是合法的，所以i的范围是1 ≤ i ≤ length + 1。

知识点梳理：

1. 插入操作：
   • 合法范围：1 ≤ i ≤ length + 1
   • 移动元素个数：length - i + 1
   • 在表尾插入时，移动0个元素
2. 删除操作：
   • 合法范围：1 ≤ i ≤ length
   • 移动元素个数：length - i
   • 不能在length+1位置删除（因为该位置没有元素）
3. 对比记忆：
   • 插入：length + 1个位置
   • 删除：length个位置

同类题拓展：

题目1：在长度为5的顺序表中插入元素，i的合法范围是？

• A. 1 ≤ i ≤ 5
• B. 1 ≤ i ≤ 6
• C. 0 ≤ i ≤ 5
• D. 0 ≤ i ≤ 6

答案：B（1 ≤ i ≤ 6，即1 ≤ i ≤ length + 1）

题目2：在顺序表中第6个位置插入元素，顺序表当前长度为5，是否合法？

• A. 合法
• B. 不合法

答案：A（合法，这是在表尾插入）

预防措施：

1. 理解本质：插入操作是在某个位置"放入"元素，这个位置可以是已有的位置，也可以是表尾之后的位置
2. 画图辅助：做题时画出顺序表的结构，标出所有可能的插入位置
3. 对比记忆：把插入和删除的合法范围放在一起对比记忆
4. 多做练习：通过做题巩固这个知识点

示例2：复盘"删除操作平均移动次数"错题

错题回顾：

• 题目：在长度为n的顺序表中删除第i个元素，平均需要移动多少个元素？
• 我的答案：n/2
• 正确答案：(n-1)/2

错因分析：

表面原因：把删除和插入搞混了

深层原因：没有理解插入和删除的区别——插入可以在n+1个位置，删除只能在n个位置

踩坑经历：我当时做这道题，想当然地认为平均移动n/2个元素。后来仔细分析才发现，删除只能在n个位置进行，而插入可以在n+1个位置进行。

正确解法：

删除操作：

• 只能在n个位置删除（1到n）
• 删除第i个元素，移动n-i个元素
• 平均移动次数 = Σ(i=1 to n) [(n-i) × 1/n] = (n-1)/2

插入操作：

• 可以在n+1个位置插入（1到n+1）
• 插入第i个位置，移动n-i+1个元素
• 平均移动次数 = Σ(i=1 to n+1) [(n-i+1) × 1/(n+1)] = n/2

知识点梳理：

同类题拓展：

题目1：在长度为n的顺序表中插入元素，平均需要移动多少个元素？

• A. n/2
• B. (n-1)/2
• C. (n+1)/2
• D. n

答案：A

题目2：在长度为5的顺序表中删除元素，平均需要移动多少个元素？

• A. 2
• B. 2.5
• C. 3
• D. 5

答案：A（(5-1)/2 = 2）

预防措施：

1. 理解区别：插入可以在表尾之后，删除不能在表尾之后
2. 公式推导：自己推导一遍平均移动次数的公式
3. 对比记忆：把插入和删除的公式放在一起对比
4. 数值验证：用具体的数值验证公式（如n=5）

5.3 错题归因统计

错题类型分布

高频错题TOP5

1. 插入位置的范围（错误率60%）
2. 删除操作的平均移动次数（错误率50%）
3. 双指针法的循环条件（错误率45%）
4. 位序与下标的转换（错误率40%）
5. 动态分配的内存管理（错误率35%）

改进建议

1. 针对概念不清：
   • 重新阅读教材，理解基本概念
   • 做对比表格，区分易混淆的概念
2. 针对方法不对：
   • 学习经典算法（双指针、分治等）
   • 多做练习题，积累经验
3. 针对计算错误：
   • 自己推导公式，不要死记硬背
   • 用具体数值验证公式
4. 针对边界条件：
   • 做题时画出状态图
   • 注意循环的边界条件
5. 针对其他：
   • 做题时仔细审题
   • 做完后检查一遍

模块6：AI模拟卷Prompt

6.1 模拟卷Prompt模板

# 角色设定
你是一位资深的408考研数据结构命题专家，负责命制高质量的模拟试卷。

# 任务要求
请命制一份"顺序表及其基本运算"的模拟试卷：

## 试卷结构
1. 选择题（10道，每题2分，共20分）
   - 简单4道，中等4道，较难2道
   - 覆盖所有重要知识点

2. 填空题（5道，每题2分，共10分）
   - 考查基础概念和计算

3. 算法设计题（3道，共30分）
   - 第1题（8分）：基础操作
   - 第2题（10分）：综合应用
   - 第3题（12分）：算法设计

4. 综合应用题（1道，10分）
   - 结合实际场景

## 命题原则
1. 难度符合408真题水平
2. 知识点覆盖全面
3. 题目表述清晰、准确
4. 答案和评分标准详细

## 输出格式
请按照以下格式输出：

# 模拟试卷

## 一、选择题（每题2分，共20分）
1. [题目]
   A. [选项A]
   B. [选项B]
   C. [选项C]
   D. [选项D]

## 二、填空题（每题2分，共10分）
1. [题目]

## 三、算法设计题（共30分）
1. （8分）[题目]

## 四、综合应用题（10分）
1. [题目]

# 参考答案

## 一、选择题
1. [答案] [解析]

## 二、填空题
1. [答案]

## 三、算法设计题
1. [代码] [解析] [评分标准]

## 四、综合应用题
1. [答案] [解析] [评分标准]

6.2 AI生成的完整模拟卷

模拟试卷：顺序表及其基本运算

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

1. 顺序表的特点是（ ）。 A. 便于插入和删除操作 B. 可以随机访问任意元素 C. 存储密度小于1 D. 需要额外的指针域
2. 在长度为n的顺序表中，删除第i个元素（1 ≤ i ≤ n），需要移动（ ）个元素。 A. n - i B. n - i + 1 C. n - i - 1 D. i
3. 在顺序表中按位查找第i个元素，时间复杂度是（ ）。 A. O(1) B. O(log n) C. O(n) D. O(n²)
4. 静态分配的顺序表，其MaxSize是（ ）。 A. 变量，可以改变 B. 常量，编译时确定 C. 变量，运行时确定 D. 常量，运行时确定
5. 在长度为n的顺序表中插入元素，平均需要移动（ ）个元素。 A. n/2 B. (n-1)/2 C. (n+1)/2 D. n
6. 动态分配的顺序表需要手动释放内存，使用的函数是（ ）。 A. malloc B. realloc C. free D. calloc
7. 顺序表的存储密度是（ ）。 A. 0 B. 0.5 C. 1 D. 大于1
8. 在顺序表中第i个位置插入元素，i的合法范围是（ ）。 A. 1 ≤ i ≤ n-1 B. 1 ≤ i ≤ n C. 1 ≤ i ≤ n+1 D. 0 ≤ i ≤ n
9. 下列关于顺序表的叙述中，正确的是（ ）。 A. 顺序表是一种非线性结构 B. 顺序表的逻辑顺序与物理顺序一致 C. 顺序表只能存储整型数据 D. 顺序表的长度必须固定
10. 两个有序顺序表合并的时间复杂度是（ ）。 A. O(1) B. O(log n) C. O(n) D. O(n²)

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

1. 顺序表中位序为i的元素，其数组下标是______。
2. 在长度为n的顺序表中删除元素，平均需要移动______个元素。
3. 顺序表的存储密度是______。
4. 动态分配顺序表时，检查malloc返回值的代码是______。
5. 顺序表逆置的算法空间复杂度是______。

三、算法设计题（共30分）

1. （8分）设计一个算法，删除顺序表L中所有值等于x的元素。要求时间复杂度为O(n)。
2. （10分）设计一个算法，从有序顺序表L中删除其值在给定值s与t之间（要求s < t）的所有元素。如果s或t不合理或顺序表为空，则返回错误信息。
3. （12分）设计一个算法，将两个有序顺序表L1和L2合并为一个新的有序顺序表L3。要求算法时间复杂度为O(n+m)，其中n和m分别是L1和L2的长度。

四、综合应用题（10分）

1. 某系统需要管理500个员工的工资信息，要求实现以下功能：
   • 按员工号查找工资
   • 按工资排序
   • 插入新员工的工资信息
   • 删除离职员工的工资信息

   请回答： （1）应该选择哪种存储结构？为什么？（3分） （2）如果选择顺序表，请分析各操作的时间复杂度。（4分） （3）请给出按员工号查找工资的算法实现。（3分）

参考答案

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

1. 答案：B 解析：顺序表支持随机访问，可以通过下标直接访问任意元素，时间复杂度O(1)。A错误，顺序表插入删除效率低；C错误，顺序表存储密度=1；D错误，顺序表不需要额外指针域。
2. 答案：A 解析：删除第i个元素，需要将第i+1到第n个元素向前移动一位，共移动n-i个元素。
3. 答案：A 解析：按位查找可以直接通过下标访问，时间复杂度O(1)。
4. 答案：B 解析：静态分配的顺序表，MaxSize是常量，在编译时就确定了大小。
5. 答案：A 解析：插入操作平均移动n/2个元素，删除操作平均移动(n-1)/2个元素。
6. 答案：C 解析：free函数用于释放动态分配的内存。
7. 答案：C 解析：顺序表的存储密度=1，所有存储单元都用于存储数据元素。
8. 答案：C 解析：插入可以在1到length+1的位置进行，包括在表尾插入。
9. 答案：B 解析：顺序表的逻辑顺序与物理顺序一致。A错误，顺序表是线性结构；C错误，可以存储任意类型；D错误，动态分配可以改变长度。
10. 答案：C 解析：两个有序顺序表合并，使用双指针法，时间复杂度O(n+m)。

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

1. 答案：i - 1 解析：位序从1开始，下标从0开始，位序i对应下标i-1。
2. 答案：(n-1)/2 解析：删除操作平均移动(n-1)/2个元素。
3. 答案：1 解析：顺序表的存储密度=1。
4. 答案：if(L.data == NULL) { printf(“内存分配失败！\n”); exit(1); } 解析：malloc可能返回NULL，必须检查返回值。
5. 答案：O(1) 解析：顺序表逆置使用双指针法，只需要常数个额外变量，空间复杂度O(1)。

三、算法设计题（共30分）

1. （8分）删除顺序表中所有值等于x的元素

代码实现：

bool DeleteX(SeqList &L, ElemType x) {
    int k = 0;
    for(int i = 0; i < L.length; i++) {
        if(L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
    return true;
}

解析：使用双指针法，i用于遍历，k记录不等于x的元素个数。时间复杂度O(n)，空间复杂度O(1)。

评分标准：

• 代码正确（5分）
• 时间复杂度O(n)（2分）
• 代码规范（1分）

2. （10分）删除值在s与t之间的元素

代码实现：

bool DeleteRange(SeqList &L, ElemType s, ElemType t) {
    if(s >= t || L.length == 0) {
        return false;
    }
    
    int i, j;
    for(i = 0; i < L.length && L.data[i] < s; i++);
    if(i >= L.length) {
        return false;
    }
    
    for(j = i; j < L.length && L.data[j] <= t; j++);
    
    for(int k = j; k < L.length; k++) {
        L.data[k - (j - i)] = L.data[k];
    }
    
    L.length -= (j - i);
    return true;
}

解析：先找到要删除的区间[i, j)，然后通过移动元素实现批量删除。时间复杂度O(n)，空间复杂度O(1)。

评分标准：

• 检查s和t的合法性（2分）
• 找到删除区间（3分）
• 移动元素（3分）
• 代码规范（2分）

3. （12分）合并两个有序顺序表

代码实现：

bool Merge(SeqList L1, SeqList L2, SeqList &L3) {
    if(L1.length + L2.length > MaxSize) {
        return false;
    }
    
    int i = 0, j = 0, k = 0;
    while(i < L1.length && j < L2.length) {
        if(L1.data[i] <= L2.data[j]) {
            L3.data[k++] = L1.data[i++];
        } else {
            L3.data[k++] = L2.data[j++];
        }
    }
    
    while(i < L1.length) {
        L3.data[k++] = L1.data[i++];
    }
    while(j < L2.length) {
        L3.data[k++] = L2.data[j++];
    }
    
    L3.length = k;
    return true;
}

解析：使用双指针法，比较两个表的元素，将较小的放入L3。时间复杂度O(n+m)，空间复杂度O(1)。

评分标准：

• 检查L3是否溢出（2分）
• 双指针比较（4分）
• 处理剩余元素（3分）
• 代码规范（3分）

四、综合应用题（10分）

1. 员工工资管理

（1）存储结构选择（3分）

答案：选择顺序表。

理由：

• 数据量固定（500个员工）
• 查找操作频繁（按员工号查找）
• 顺序表支持随机访问，查找效率高
• 不需要频繁插入删除

评分标准：

• 选择顺序表（1分）
• 理由充分（2分）

（2）各操作的时间复杂度（4分）

答案：

• 按员工号查找：如果员工号有序，O(log n)；否则O(n)
• 按工资排序：O(n²)或O(n log n)
• 插入新员工：O(n)
• 删除离职员工：O(n)

评分标准：每个操作1分

（3）按员工号查找的算法实现（3分）

代码实现：

int SearchByEmployeeID(SeqList L, ElemType employeeID) {
    for(int i = 0; i < L.length; i++) {
        if(L.data[i].employeeID == employeeID) {
            return i;
        }
    }
    return -1;
}

评分标准：

• 代码正确（2分）
• 代码规范（1分）

6.3 评分标准参考

选择题评分标准

• 每题2分，选对得2分，选错得0分
• 总分20分

填空题评分标准

• 每题2分，答案正确得2分，答案错误得0分
• 总分10分

算法设计题评分标准

• 代码正确性：60%
• 时间复杂度：20%
• 代码规范性：20%

综合应用题评分标准

• 存储结构选择：30%
• 复杂度分析：40%
• 算法实现：30%

总分计算

• 选择题：20分
• 填空题：10分
• 算法设计题：30分
• 综合应用题：10分
• 总分：70分

成绩等级

• 优秀：63-70分（90%以上）
• 良好：56-62分（80%-89%）
• 中等：49-55分（70%-79%）
• 及格：42-48分（60%-69%）
• 不及格：42分以下（60%以下）

模块7：延伸阅读

7.1 教材参考

1. 王道考研《数据结构复习指导》

推荐章节：

• 第2章 线性表（2.1 顺序表）
• 重点阅读：顺序表的定义、实现、操作、复杂度分析

学习建议：

1. 先看书中的知识点总结，建立整体框架
2. 仔细阅读例题，理解解题思路
3. 做课后习题，巩固知识点
4. 看真题解析，了解命题规律

重点内容：

• 顺序表的静态分配和动态分配
• 插入、删除、查找操作
• 复杂度分析
• 边界条件

2. 严蔚敏《数据结构（C语言版）》

推荐章节：

• 第2章 线性表（2.2 顺序表）
• 重点阅读：顺序表的定义、实现、算法

学习建议：

1. 这本书的理论性较强，适合深入理解概念
2. 重点看算法的伪代码描述
3. 对比C语言实现，理解算法细节
4. 做课后习题，加深理解

重点内容：

• 顺序表的数学描述
• 算法的时间复杂度分析
• 顺序表的应用

3. 天勤考研《数据结构高分笔记》

推荐章节：

• 第2章 线性表（2.1 顺序存储结构）
• 重点阅读：顺序表的特点、操作、真题解析

学习建议：

1. 这本书的笔记形式很适合快速复习
2. 重点看"注意"和"提示"部分
3. 做真题部分，检验学习效果
4. 对比其他教材，查漏补缺

重点内容：

• 顺序表的优缺点
• 操作的实现细节
• 真题的解题技巧

7.2 视频课程

1. 王道考研数据结构视频课

推荐指数：⭐⭐⭐⭐⭐

课程特点：

• 知识点讲解清晰，适合基础薄弱的同学
• 真题解析详细，帮助理解命题规律
• 代码演示直观，便于理解算法实现

推荐章节：

• 第3讲 线性表的顺序存储（约2小时）
• 重点观看：顺序表的实现、操作、真题解析

学习建议：

1. 先看视频，理解知识点
2. 暂停视频，自己写代码实现
3. 看完视频后，做对应的习题
4. 反复观看难点部分

2. 天勤考研数据结构视频课

推荐指数：⭐⭐⭐⭐

课程特点：

• 讲解深入，适合基础较好的同学
• 注重算法思维的培养
• 题目难度较高，适合冲刺高分

推荐章节：

• 第2章 线性表（约1.5小时）
• 重点观看：顺序表的算法设计、综合应用

学习建议：

1. 适合看完王道视频后，进一步提升
2. 重点学习算法设计的思路
3. 做难题，提升解题能力

3. B站免费视频资源

推荐UP主：

• 计算机考研研究室
• 数据结构-严蔚敏
• 408考研数据结构

推荐视频：

• "顺序表及其基本运算"系列（约1小时）
• "408真题解析-顺序表"系列（约2小时）

学习建议：

1. 适合基础薄弱，需要反复学习的同学
2. 可以倍速观看，提高效率
3. 结合笔记，加深理解

7.3 知识关联图

知识关联说明：

1. 线性表：
   • 顺序表：顺序存储结构
   • 链表：链式存储结构
   • 两者是线性表的两种实现方式
2. 顺序表的实现：
   • 静态分配：固定数组，编译时确定
   • 动态分配：指针+malloc，运行时确定
3. 基本操作：
   • 初始化、插入、删除、查找
   • 按位查找O(1)，按值查找O(n)
4. 特点：
   • 随机访问O(1)
   • 存储密度=1
   • 插入删除O(n)
5. 应用：
   • 逆置、合并、删除重复等

与后续章节的关联：

• 第2章 链表：链式存储结构，对比学习
• 第3章 栈和队列：基于顺序表或链表实现
• 第4章 串：特殊的线性表
• 第5章 数组和广义表：线性表的推广

模块8：Checklist

8.1 知识点清单

核心概念（必会）

• 理解顺序表的定义和特点
• 掌握静态分配的实现方式
• 掌握动态分配的实现方式
• 理解位序与下标的转换关系
• 理解顺序表的优缺点

基本操作（必会）

• 掌握初始化操作的实现
• 掌握插入操作的实现和复杂度
• 掌握删除操作的实现和复杂度
• 掌握按位查找的实现和复杂度
• 掌握按值查找的实现和复杂度

复杂度分析（必会）

• 掌握插入操作的平均移动次数：n/2
• 掌握删除操作的平均移动次数：(n-1)/2
• 掌握按值查找的平均比较次数：(n+1)/2
• 理解最好、最坏、平均情况的区别

边界条件（易错）

• 掌握插入位置的合法范围：1 ≤ i ≤ length + 1
• 掌握删除位置的合法范围：1 ≤ i ≤ length
• 理解位序i对应下标i-1
• 理解判空和判满条件

代码实现（必会）

• 能够独立写出静态分配的顺序表代码
• 能够独立写出动态分配的顺序表代码
• 掌握引用传递（&）的使用
• 掌握malloc/free的使用

常见误区（注意）

• 插入时元素移动方向（从后往前）
• 删除时元素移动方向（从前往后）
• 动态分配时检查malloc/realloc返回值
• 动态分配时释放内存
• 浮点数比较使用EPSILON

真题考点（重点）

• 掌握顺序表的特点（选择题）
• 掌握复杂度分析（选择题）
• 掌握边界条件（选择题）
• 掌握插入删除的实现（算法题）
• 掌握逆置、合并等操作（算法题）

8.2 自测问题

概念理解（10题）

1. 什么是顺序表？它有什么特点？
2. 静态分配和动态分配有什么区别？
3. 顺序表的存储密度是多少？为什么？
4. 顺序表适合什么样的应用场景？
5. 位序和下标有什么关系？
6. 顺序表的插入操作可以在哪些位置进行？
7. 顺序表的删除操作可以在哪些位置进行？
8. 顺序表的按位查找时间复杂度是多少？为什么？
9. 顺序表的按值查找时间复杂度是多少？为什么？
10. 顺序表和链表有什么区别？

代码实现（5题）

1. 写出静态分配顺序表的完整代码
2. 写出动态分配顺序表的完整代码
3. 实现顺序表的逆置操作
4. 实现两个有序顺序表的合并
5. 实现删除顺序表中所有值为x的元素

复杂度分析（5题）

1. 插入操作的最好、最坏、平均时间复杂度分别是多少？
2. 删除操作的最好、最坏、平均时间复杂度分别是多少？
3. 按位查找的时间复杂度是多少？
4. 按值查找的平均比较次数是多少？
5. 顺序表逆置的空间复杂度是多少？

真题模拟（5题）

1. 在长度为n的顺序表中删除第i个元素，需要移动多少个元素？
2. 在顺序表中第i个位置插入元素，i的合法范围是什么？
3. 顺序表具有的优点是什么？
4. 设计算法将顺序表逆置，要求空间复杂度O(1)
5. 设计算法删除顺序表中值在s与t之间的所有元素

8.3 完成度评估

自我评分标准

优秀（90-100分）：

• 所有知识点都掌握
• 能够独立写出完整代码
• 复杂度分析准确
• 真题正确率90%以上

良好（80-89分）：

• 大部分知识点掌握
• 能够写出基本代码
• 复杂度分析基本正确
• 真题正确率80%以上

中等（70-79分）：

• 主要知识点掌握
• 能够写出部分代码
• 复杂度分析有错误
• 真题正确率70%以上

及格（60-69分）：

• 基本知识点掌握
• 代码实现有困难
• 复杂度分析错误较多
• 真题正确率60%以上

不及格（60分以下）：

• 知识点掌握不牢
• 无法独立写代码
• 复杂度分析错误很多
• 真题正确率60%以下

学习建议

如果得分90-100：

• 你已经掌握得很好了！
• 可以做更多综合题，提升能力
• 开始学习下一节：链表

如果得分80-89：

• 基础不错，但还有提升空间
• 重点复习易错点
• 多做真题，巩固知识点

如果得分70-79：

• 基础一般，需要加强
• 重新阅读教材，理解概念
• 多写代码，熟悉实现

如果得分60-69：

• 基础薄弱，需要重点复习
• 看视频课程，理解知识点
• 从基础题开始，逐步提升

如果得分60以下：

• 基础很差，需要重新学习
• 看视频课程，做笔记
• 请教老师或同学
• 不要着急，慢慢来

下一步计划

1. 完成本节学习：
   • 确保所有知识点都掌握
   • 能够独立写出代码
   • 真题正确率达到80%以上
2. 开始下一节：
   • 链表及其基本运算
   • 对比顺序表和链表
   • 理解各自的优缺点
3. 综合复习：
   • 做线性表的综合题
   • 对比顺序表和链表的应用场景
   • 准备下一章：栈和队列

作者：安全风信子 日期：2026-07-22 参考教材：王道考研《数据结构复习指导》、严蔚敏《数据结构（C语言版）》

版权声明：本文版权归作者所有，转载请注明出处。

反馈与交流：如有问题或建议，欢迎留言交流。祝大家考研顺利！

在这里插入图片描述