关于结构体，排序，递推的详细讲解（从属于GESP四级）

本章内容

排序算法基础

结构体

递推

简单双指针

一、排序算法基础三剑客

冒泡 Bubble、选择 Selection、插入 Insertion

---

1. 预备知识

1.1 排序算法评价指标

指标	含义	影响答题的典型问法
时间复杂度	算法在最坏、平均或最好情况下所需比较 / 交换次数	“写出此算法最坏复杂度”
空间复杂度	额外占用的内存字节数	“此算法是否原地排序”
稳定性	等值元素排序后相对次序是否保持	“选择排序稳定吗？为什么”
交换/移动次数	对不同硬件代价不同	真题曾考“哪种简单排序交换次数最少”

1.2 大 O 回顾

• • 常数 → O(1)
• • 线性 → O(n)
• • 二次 → O(n²)
• • 对数 → O(log n)
• • 线性对数 → O(n log n)

本讲的三种算法最坏与平均时间复杂度均为 O(n²)，但细节存在差异。

---

2. 冒泡排序 Bubble Sort

2.1 算法原理

• • 第 i 轮扫描，把区间 [0, n-i-1] 内相邻元素两两比较并交换，使当前“最大”或“最小”元素“冒”到末尾。
• • 共 n-1 轮 ⇒ 最终有序。

关键点	说明
思路	相邻元素两两比较，较大者向后“冒泡”；重复 n-1 轮
伪码	for i=0→n-2 : for j=0→n-2-i : if a[j]>a[j+1] swap
时间复杂度	最好 O(n) (加“是否交换”早停)，最坏/平均 O(n²)
空间复杂度	O(1)
稳定性	稳定 （相等元素次序不变）
何时用	n≤1e4 且需稳定；教学演示；排序后常要“冒最大值到尾”的场景

2.2 手动推演（升序）

数组 5 2 4 3

1. 1. 第一轮

• • • 5>2 → 2 5 4 3
  • • 5>4 → 2 4 5 3
  • • 5>3 → 2 4 3 5 （最大 5 就位）

1. 2. 第二轮

• • • 2<4 ✔
  • • 4>3 → 2 3 4 5

1. 3. 第三轮

• • • 2<3 ✔ （已排序）

2.3 代码（带“早停”优化）

void bub(vector<int>& a){
    int n = a.size();
    for(int i = 0; i+1 < n; i++){
        bool sw = 0;                  // 本轮有无交换
        for(int j = 0; j+1 < n-i; j++)
            if(a[j] > a[j+1]){
                swap(a[j],a[j+1]);
                sw=1;
            }
        if(!sw) break;              // 数据已整体有序
    }
}

• • 最坏/平均时间：O(n²)
• • 最好时间：已排好 + 早停 ⇒ O(n)
• • 空间：O(1)
• • 稳定：相等元素不会交换 → ✔

2.4 真题陷阱

1. 1. 内层上界 写成 j<n-i 而非 j<n-i-1 ⇒ 越界。
2. 2. 忘记早停 出题人给“几乎有序”数据，时间仍算 O(n²)。
3. 3. 考输出：问“第一轮结束后数组状态”，注意是“最大”冒到末尾。

---

3. 选择排序 Selection Sort

3.1 算法原理

• • 第 i 轮在 [i, n-1] 中选最小元素，与 a[i] 交换。
• • n-1 轮后有序。

关键点	说明
思路	每轮在未排区间选最小值，与首元素交换
伪码	for i=0→n-2 : pos=min(j=i→n-1) swap a[i] a[pos]
时间复杂度	最好/最坏/平均均 O(n²)（比较次数固定）
空间复杂度	O(1)
稳定性	不稳定 （最小值与前元素交换破坏次序）
何时用	内存极紧 & 交换次数希望最少（n-1 次）；不关心稳定性的简单场合

3.2 代码

void sel(vector<int>& a){
    int n = a.size();
    for(int i = 0; i+1 < n; i++){
        int p = i;                    // 最小元素下标
        for(int j = i+1; j < n; j++)
            if(a[j] < a[p]) p = j;
        if(p != i) swap(a[i], a[p]);   // 每轮最多一次交换
    }
}

• • 时间：所有情况均 O(n²) （比较次数固定）
• • 交换次数：恰好 n-1
• • 空间：O(1)
• • 稳定：✘ 若最小值后有相同键，会被交换到前面。

3.3 为什么不稳定

原序列   (3,a) (1,x) (1,y)
第一轮找到最小(1,x)，与 (3,a) 交换 →
         (1,x) (3,a) (1,y)  // 同键 y 被后移

3.4 适用场景

• • 交换成本 >> 比较成本（机械硬盘写、多维结构体拷贝）
• • 内存极少环境：O(1) 空间
• • 不关心稳定性

---

4. 插入排序 Insertion Sort

4.1 算法原理

• • 类似打牌插牌：维护 [0,i-1] 已排好，对 key=a[i] 在左侧找到插入位置并右移元素。

关键点	说明
思路	将元素逐个插入已排好序的左侧区间
伪码	for i=1→n-1 : key=a[i]; j=i-1; while j>=0 && a[j]>key : a[j+1]=a[j--]; a[j+1]=key
时间复杂度	最好 O(n)（已近乎有序），最坏/平均 O(n²)
空间复杂度	O(1)
稳定性	稳定 （移动而非交换）
何时用	数据量小 (≤1e4) 或 已基本有序；也是高级算法（Shell、TimSort、STL sort 小块优化）的子过程

4.2 代码

void ins(vector<int>& a){
    int n = a.size();
    for(int i = 1; i < n; i++){
        int key = a[i], j = i-1;
        while(j >= 0 && a[j] > key){
            a[j+1] = a[j];            // 右移
            --j;
        }
        a[j+1] = key;
    }
}

4.3 运行示意

2 4 1 3

• • i=1 已有序。
• • i=2：key=1，比较 4>1 → 移，比较 2>1 → 移 → 插入开头 ⇒ 1 2 4 3。
• • i=3: key=3，右移 4 → 1 2 3 4。

4.4 复杂度

情况	比较次数	复杂度
最好（已排好）	n-1	O(n)
最坏（逆序）	n(n-1)/2	O(n²)

• • 空间：O(1)
• • 稳定：✔ 因为是元素后移而不是交换。

4.5 场景优势

• • 数据量 ≤ 1e4
• • 几乎有序（宏观递增），速度非常快
• • 高级排序内部的小数组优化（STL sort、TimSort）

---

5. 三者对比 & 选用建议

属性	冒泡	选择	插入
最坏时间	O(n²)	O(n²)	O(n²)
最好时间	O(n)	O(n²)	O(n)
额外空间	O(1)	O(1)	O(1)
交换次数	多，≤n²/2	最少 ，n-1	中等 (移动)，取决于逆序对
稳定性	✔	✘	✔
编码易度	★	★★	★★
适合	教学、稳定	交换贵、空间 O(1)	小/近序列、插入数据流
真题常考点	“冒泡第 k 轮后最大元素位置”	“交换次数最少的简单排序”	“用插入排序对几乎有序数组计最少移动次数”

“对号入座”：
给片段代码，下列哪个排序？下列哪个排序交换次数最少？ —— 答：选择排序。

---

6. 真题拆解 & 易错点

6.1 选择题：写复杂度

题干给出冒泡双层 for，考生计算复杂度。技巧：内层整体运行 O(n²/2) → 填 O(n²)。

6.2 判断题：稳定性

“插入排序一定稳定。”
—— 对；理由：等值键不会换相对次序，只是后移。

6.3 填空题：插入排序条件

while(j>=0 && ______ ) { ... }

应填 a[j] > key；常错写成 a[j] >= key（破坏稳定）。

6.4 代码输出

• • “第一轮冒泡后数组状态” —— 记住 最大在末尾。
• • “选择排序第 k 轮后 a[k] 的值” —— a[k] = 数组第 k 小。

---

7. 练习（附答案简述）

1. 1. 推演冒泡：手算 4 3 2 1 冒泡第一轮结果？

3 2 1 4

1. 2. 判断稳定性：选择排序若增加“先找到最小，再在相同行中选最靠后元素交换”，是否稳定？

仍不稳定，只是改变交换对象。

1. 3. 写函数 void sort2(int* a,int n) 用插入排序降序排列。

将比较改为 a[j] < key。

1. 4. 给不完整代码，补齐选择排序找最小下标逻辑。
2. 5. 时间复杂度：插入排序处理几乎有序 + 早停，最坏仍 O(n²) 吗？

是；早停仅影响最好情况。

1. 6. 写段代码统计冒泡交换次数。
2. 7. 读取 n≤10000 整数，用插入排序并输出移动次数。
3. 8. 判断题：冒泡双向优化（鸡尾酒排序）最坏仍 O(n²)。

对。

1. 9. 多选：稳定排序有哪些？（给四个）选冒泡、插入。
2. 10. 问答：为什么快速排序实际比 O(n²) 的插入要快？

平均 O(n log n)、缓存局部性、高常数差等。

---

小结 ✅

• • 三种简单排序均 O(n²)，但 最优、稳定性、交换次数、场景 不同。
• • 真题高频考 “最坏复杂度 / 稳定 or not / 第一轮结果 / 代码填空”。
• • 理解差异→灵活选用；牢记“选择最少交换、不稳定”“插入近序列最优、稳定”。

二、结构体使用全攻略

---

1. 自定义结构体类型

struct Stu{           // Student 缩写
    int  id;          // 学号
    char nm[20];      // 姓名（C 风格串演示）
    double sc;        // 成绩
};

• • struct 关键字在 C++ 中同时声明类型与定义。
• • 若需面向对象特性，再加成员函数或构造；四级仅考数据封装。

---

2. 结构体数组

Stu cls[100];         // 最多 100 名学生
cls[0] = {1001,"Li",95.5};

• • 遍历

for(int i = 0; i < n; i++)
    cout << cls[i].nm <<" "<< cls[i].sc <<"\n";

---

3. 结构体嵌套

struct Date{ int y,m,d; };

struct Info{
    Stu  st;          // 内嵌“学生”结构
    Date bd;          // 出生日期
};

使用时链式访问：

Info a;
a.st.id = 2001;
a.bd.y  = 2005;

---

4. 作为函数参数

4.1 按值传递（会拷贝）

void show(Stu s){           // 形参副本
    cout << s.nm <<" "<< s.sc <<"\n";
}

适合小结构且只读。

4.2 按引用 / 指针（无拷贝，可改）

void inc(Stu &s,double d){  // 引用传递
    s.sc += d;
}

4.3 只读大对象 → const&

double avg(const Stu &a,const Stu &b){
    return (a.sc + b.sc)/2;
}

• • const 保证函数内不修改实参。
• • 与按值效果相同但避免 O(size) 拷贝。

---

5. 结构体大小

5.1 sizeof 的三条硬规则

1. 1. 字节对齐（Alignment）

• • • 每个成员地址必须是 自身对齐系数 的倍数。
  • • 对齐系数 = min(成员类型大小, 编译器默认对齐上限)，典型上限 4 或 8。

1. 2. 填充(Padding)

• • • 编译器自动插入填充字节，使下一个成员满足对齐。
  • • 结构体整体大小也要是 最大对齐系数 的倍数（便于数组）。

1. 3. sizeof 结果 ≥ 每个成员大小之和；不会因为空洞而小于求和。

---

5.2 对齐 & 填充（Alignment / Padding）基础

类型	sizeof (字节)	常见对齐要求
int	4	4
long long	8	8

• • 结构体自身的对齐 = 其成员中 最大对齐要求
• • 成员偏移 必须满足该成员的对齐；若不满足，编译器会自动插入 填充字节 (padding)
• • 结构体总大小 向上补齐到「结构体对齐要求」的整数倍，保证结构体数组中每个元素都对齐

---

5.3 示例：只含 int 与 long long 的结构体

源码

#include <bits/stdc++.h>
using namespace std;
struct A {
    int        a;  // 4 字节
    long long  b;  // 8 字节
};
struct B {
    long long  b;  // 8
    int        a;  // 4
};
int main() {
    cout << "sizeof(A) = " << sizeof(A) << "\n";
    cout << "offsetof(A, b) = " << offsetof(A, b) << "\n\n";

    cout << "sizeof(B) = " << sizeof(B) << "\n";
    cout << "offsetof(B, a) = " << offsetof(B, a) << "\n";
    return 0;
}

内存布局解析

结构体	成员顺序	过程示意	结果 (sizeof)
A	int a → long long b	0‒3：a；4‒7：填充；8‒15：b	16
B	long long b → int a	0‒7：b；8‒11：a；12‒15：尾部填充	16

结构体对齐均为 8，故大小皆补齐到 8 的倍数。

典型运行结果（x86-64）

sizeof(A) = 16
offsetof(A, b) = 8

sizeof(B) = 16
offsetof(B, a) = 8

---

5.4 改变对齐 / 填充

#pragma pack（MSVC / GCC）

#pragma pack(push, 1)      // 强制 1 字节对齐
struct Packed {
    int        a;  // 4
    long long  b;  // 8
};
#pragma pack(pop)

static_assert(sizeof(Packed) == 12, "packed size");

⚠ 对 8 字节类型做“非对齐访问”可能极大拖慢性能，甚至在某些平台导致硬件异常。

** alignas / alignof**

struct alignas(4) A4 {
    int        a;
    long long  b;
};

• • 尝试把整体对齐降低为 4，但成员 b 仍需 8 字节对齐
• • 某些编译器会自动升级为 8，对齐约束不能被弱化到破坏成员安全

---

5.5 小结

1. 1. 结构体对齐 = 内部最大成员对齐
2. 2. 结构体大小 向上补齐到该对齐的整数倍
3. 3. 含 int + long long 的普通结构体大小通常是 16 字节
4. 4. 若必须去掉填充可用 #pragma pack(1) / __attribute__((packed))，但务必衡量性能与可移植性
5. 5. alignas 可提高最小对齐，不一定能降低对齐

6. 简单演示：按成绩排序

#include<bits/stdc++.h>
using namespace std;

struct Stu{
    int  id;
    char nm[20];
    double sc;
};

bool cmp(const Stu &l,const Stu &r){   // 只读引用
    return l.sc > r.sc;
}

int main(){
    int n; cin>>n;
    vector<Stu> v(n);
    for(auto &s:v) cin >> s.id >> s.nm >> s.sc;

    sort(v.begin(),v.end(),cmp);       // 结构体数组排序

    for(const auto &s:v)
        cout << s.id <<" "<< s.nm <<" "<< s.sc <<"\n";
    
    return 0;
}

---

7. 易错提示

⚠️ 场景	说明	纠正
结构体之间直接比较	无 < 运算	自定义 cmp
大结构按值传递	拷贝耗时	改 const&
嵌套 char[] 读串	可能溢出	指定宽度 cin>>setw(19)

---

三、递推

1. 什么是递推？

递推（iterative recurrence）= 用 已知的较小规模答案 直接 推算 更大规模答案，并且自底向上迭代求值。

概念	关键词	计算路径	栈消耗
递归	“自我调用”	自顶向下，靠回溯合并	深度 × 常数
递推	“公式+循环”	自底向上，顺序累推	O(1) / O(n)
DP	“最优子结构+重叠子问题”	先抽象状态再递推	视数组规模

为什么推崇递推？

• • 效率：避免函数栈，时间易界定。
• • 安全：无爆栈风险。
• • 易调优：滚动数组/状态压缩天然适配。

---

2. 如何构造递推式

下面五种套路覆盖 90 % 竞赛/考级题目：

名称	核心问题	样例
前缀累加	“前 i 项的某和/积/最值”	s[i]=s[i-1]+a[i]
相邻差分	“相邻元素差与原序列”	diff[i]=a[i]-a[i-1]
位移枚举	“本状态由固定 k 步前状态合并”	斐波那契：F[n]=F[n-1]+F[n-2]
枚举决策	“遍历所有上一步决策求最优”	背包：dp[v]=max(dp[v],dp[v-w]+val)
组合分拆	“拆掉最后一块/最后一位”	走台阶：dp[i]=dp[i-1]+dp[i-2]

构造步骤

1. 1. 描述目标：用 f(n)、dp[i][j]…
2. 2. 找子问题：把规模 n 拆成 < n。
3. 3. 写数学式：确保左右变量类型一致。
4. 4. 给边界：f(0)、f(1)。
5. 5. 验证样例：手算对几组小 n。

⚠ 兜底原则：找不到递推式＝建模失败；宁可多画状态转移图。

---

3. 从递推到程序：迭代 6 步法

1. 1. 申请数组 / 变量

• • • 如果只依赖最近 k 个历史值 → k 个滚动变量即可。

1. 2. 写边界值f[0]=0; f[1]=1; // 斐波那契例
2. 3. 决定循环方向

• • • 基本都是 index 小→大。
  • • 一维背包优化要反向（防止覆盖）。

1. 4. 填递推公式for(int i=2; i<=n; i++) f[i] = f[i-1]+f[i-2];
2. 5. 模数/大数处理（必要时）
3. 6. 返回 f[n] / 输出全部

---

4. 经典模型 7 例

4.1 斐波那契

递推式

F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2)

滚动实现

long long fib(int n){
    if(n < 2) return n;
    long long a = 0, b = 1;
    for(int i = 2; i <= n; i++){
        long long c = a+b; a=b; b=c;
    }
    return b;
}

• • 时空：O(n), O(1)
• • 优化：矩阵快速幂 O(log n)（见 §6）。

---

4.2 前缀和 / 差分

• • 求区间 [l,r] 和：提前算 pre[i]=pre[i-1]+a[i]，O(1) 查询。
• • 更新区间 加 val：用差分 diff[l]+=val; diff[r+1]-=val，最后前缀化得到新数组。

---

4.3 台阶走法

一次可上 1 或 2 级，求走 n 级方案数。
递推与斐波那契同式。边界 dp[0]=1,dp[1]=1。

---

4.4 1 维 0/1 背包

for(int i = 1; i <= n; i++)
  for(int v = V; v >= w[i]; v--)
    dp[v] = max(dp[v], dp[v-w[i]]+val[i]);

• • 外循环物品，内循环容量 逆序，防止同一轮物品被重复取。
• • 时间 O(nV)，空间 O(V)。

---

4.5 最长公共子序列 LCS

dp[i][j]：A 前 i、B 前 j 最长公共子序列长。

if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1]+1
else dp = max(dp[i-1][j], dp[i][j-1])

• • 二维 O(nm)；可滚动成 2×(m+1)。

---

4.6 Catalan（卡特兰）数

解决 括号匹配数、二叉树形态数 等。

---

4.7 数字计数（位 DP 雏形）

思路：枚举数位，高位固定、当前位遍历、低位自由组合。对 1…n，统计某数字出现次数常用 O(log n) 解。

---

5. 时间 & 空间优化

1. 1. 滚动数组：只留最近 k 行。
2. 2. 状态压缩：用 bitset / int 压多维布尔。
3. 3. 单调队列 DP：窗口最值转移 O(n)。
4. 4. 分治+FFT：高阶线性同余/卷积递推。
5. 5. 打表 + 递推：预处理 1…1e7 所有答案后 O(1) 查询。

---

6. 进阶拓展

6.1 矩阵快速幂求线性递推

• • 把 k 阶递推写成 k×k 矩阵乘法。
• • 指数级优化：O(k³ log n) 或 O(k².373 log n)。
• • 经典：斐波那契 2×2 矩阵。

6.2 生成函数

• • 把序列 映射到 。
• • 乘积、组合等运算转系数运算，适合 计数类递推。

6.3 主定理

• • 解决 分治递归 。
• • 在 GESP 四级中仅需会背结论：

• • • 若 → 等。

---

总结：递推 = 写公式、立边界、用循环。先会一阶、二阶线性，再扩展到多维 & DP，你就具备攻克递推/动态规划题目的硬实力。

四、双指针（Two-Pointers）简单介绍

四级编程题出现双指针，在此简单介绍“双指针”技巧在排序对撞与滑动窗口两类场景中的典型用法。

模式	关键思路	真题映射	典型指针移动
对撞型	两序列都已排序，比较头尾元素，配对或缩区间	田忌用最慢马对对方最慢/最快	l1++, l2++ / r1--, r2--
滑窗型	一个序列，维护 [left,right] 区间的动态性质	宝箱统计满足条件的最短/最多段	right++ 扩张，条件不符时 left++ 收缩

---

1. 田忌赛马：排序 + 头尾对撞

故事化描述

• • 你与田忌各有 n 匹马，进行任意匹配比赛，最多能获胜几轮。
• • 经典贪心：把两人马力从小到大排序，用双指针贪心配对。

vector<int> a(n), b(n);
sort(a.begin(),a.end());
sort(b.begin(),b.end());

int la=0, ra=n-1, lb=0, rb=n-1, score=0;
while(la <= ra){
    if(a[ra] > b[rb]){         // 田忌最快能赢
        score++; ra--; rb--;
    }else if(a[la] > b[lb]){   // 用最慢赢对方最慢
        score++; la++; lb++;
    }else{                   // 不可赢，用最慢换对方最快
        la++; rb--;
    }
}

双指针对撞 (la/lb 指向最慢，ra/rb 指向最快) ，每步决定哪一端前进。

---

2. 宝箱：滑动窗口统计

题干抽象

• • 给定数组 a，找出包含 满足 x−y≤k 的最大价值区间， x为最大值，y为最小值。
• • 本质 = 最大覆盖子串 → 典型滑窗。

#include<bits/stdc++.h>
using namespace std;
int n, k, a[1005], res, ans;
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    
    int r = 1;
    for (int l = 1; l <= n; l++){
        while(a[r]-a[l]<=k and r<=n) res += a[r], r++;
        ans = max(ans, res);
        res -= a[l];
    }
    cout << ans;
    
    return 0;
}

双指针滑窗 (l 左界收缩 / r 右界扩张)。
时间 O(n)、空间 O(K)。

---

3. 小结口诀

对撞选端点，排序区间缩；
滑窗保性质，左右此消长。

• • 对撞型：两端比较 → 更新分数 / 交换指针
• • 滑窗型：右扩满足，左收最优

五、精选选择题

✅ 1.【结构体】

题目：下列关于 C++ 结构体定义的语句，哪一条编译可通过？
A. struct { int x; } p; B. struct Node { int d; }; Node;
C. struct Stu { int id; } s; D. struct Stu; Stu{}
答案：C
解析：A 匿名结构体不能直接声明变量再用类型；B 重复标识符；D 前向声明不能立刻定义对象。
【24 年 6 月单 9】

---

✅ 2.【排序·真题】

题目：在简单排序算法中，哪一种在最坏情况下的交换次数最少？
A. 冒泡排序 B. 选择排序 C. 插入排序 D. 三者相同
答案：B
解析：选择排序每轮最多一次交换，总计 n-1 次。
【23 年 12 月单 5】

---

✅ 3.【递推】

题目：斐波那契数列迭代版若使用两变量滚动，计算 F(n) 的空间复杂度为
A. O(1) B. O(log n) C. O(n) D. O(n²)
答案：A
解析：只需常数级变量保存 F(n-2)、F(n-1)。

---

✅ 4.【结构体】

题目：已知

struct S{ int x; double y; };   // int 4B，double 8B
S a[100];

忽略内存对齐的填充，sizeof(a) 为
A. 800 B. 1200 C. 1600 D. 2400
答案：B
解析：单个 S 占 4 + 8 = 12 B，100 × 12 = 1200 B。
【24 年 6 月选择题 10】

---

✅ 5.【排序·真题】

题目：下列简单排序中，在已基本有序的数据集上实际运行最快的是
A. 冒泡排序 B. 选择排序 C. 插入排序 D. 三者相同
答案：C
解析：插入排序最好时间 O(n)，另外两种仍 O(n²)。
【25 年 3 月选择题 7】

---

✅ 6.【递推】

题目：已知递推 F(n)=F(n-1)+n²，F(0)=0。以下循环正确实现该递推的是
A.for(i=1;i<=n;i++) F+=i*i;
B.for(i=0;i<=n;i++) F+=i*i;
C.for(i=1;i<n;i++) F+=i*i;
D.for(i=1;i<=n;i++) F+=i;
答案：A
解析：i 从 1 到 n，加上 i² 累积。B 多算 F(0)；C 少算 n；D 公式错误。

---

✅ 7.【结构体参数】

题目：要在函数中只读大结构体 Info，并避免拷贝，应使用形参
A.Info obj B.Info* p C.const Info& r D.Info& r
答案：C
解析：常量引用零拷贝且限制写操作，最符合题意。

---

✅ 8.【排序】

题目：以下关于稳定性的说法正确的是
A. 选择排序稳定 B. 插入排序不稳定
C. 冒泡排序稳定 D. 稳定排序执行交换次数一定更少
答案：C
解析：冒泡稳定；选择不稳定；插入稳定；交换次数与稳定性无固定关联。

---

✅ 9.【递推·真题】

题目：求斐波那契数列第 n 项若使用 2×2 矩阵快速幂，时间复杂度为
A. O(n) B. O(log n) C. O(n log n) D. O(n²)
答案：B
解析：幂指数对数增长，多次矩阵乘法。
【24 年 12 月选择题 11】

---

✅ 10.【结构体嵌套】

题目：若

struct Pos{ int x,y; };
struct Nod{ Pos p; int id; };

下列访问第 5 个节点 y 坐标的表达式正确的是
A.nod[4].y B.nod[4].p.y C.nod->p.y D.(nod+5)->y
答案：B
解析：p 为嵌套结构体成员，需两级点运算访问。

---

✅ 11.【排序交换】

题目：对长度 n 数组，选择排序的交换次数恰好是
A.n B.n-1 C.≤n-1 D.不确定
答案：B
解析：每轮固定把最小值换到 a[i]，共 n-1 轮。

---

✅ 12.【递推空间】

题目：使用滚动数组压缩 0/1 背包的 dp 表时，额外空间复杂度是
A. O(1) B. O(n) C. O(V) D. O(nV)
答案：C
解析：只保留一维容量大小 V 的数组。

---

✅ 13.【结构体排序】

题目：sort(v.begin(),v.end(),cmp) 排结构体时保持稳定性的做法是
A. 使用 stable_sort B. 让 cmp 返回 <=
C. 添加“序号”再二次 sort D. C++ STL 无法稳定
答案：A
解析：sort 不稳定，stable_sort 才保证相对顺序。

---

✅ 14.【递推】

题目：以下哪个问题不适合用简单一维递推解决
A. 台阶上楼 B. 一维前缀和 C. 最长公共子序列 D. 斐波那契
答案：C
解析：LCS 需二维状态。

---

六、精选判断题

✅ 1. 【结构体】

题目：在 C++14 中，结构体内部不能直接为成员变量写默认初值。
答案：错
解析：从 C++11 起即可在结构体或类内为成员做默认初始化（如 int x = 0;）。若仅使用纯 C 语法则不允许，但题目限定 C++14。

---

✅ 2. 【排序—插入】

题目：插入排序在最坏情况下需要进行 n(n-1)/2 次比较。
答案：对
解析：最坏输入（完全逆序）时，内层 while 将 key 与所有已排元素比较，比较次数等于逆序对数 n(n-1)/2。

---

✅ 3. 【指针与参数传递】

题目：使用 const StructType& 作为函数形参既可避免拷贝又能阻止在函数体内修改该对象。
答案：对
解析：常量左值引用只绑定现有对象地址，不触发复制；const 属性禁止写操作。
【出自：24 年 12 月判断题】

---

✅ 4. 【排序—冒泡】

题目：冒泡排序每完成一轮，最小元素一定被移动到序列最前端。
答案：错
解析：标准冒泡比较相邻元素把“大”值推向末端，因此一轮后最大值在最末，最小值位置不确定。

---

✅ 5. 【递推 / 递归】

题目：用递推迭代实现算法通常比等价的递归实现占用更少的栈空间。
答案：对
解析：递推通过显式循环保存状态，不需要为每层递归调用分配栈帧，故栈消耗更小。

---

✅ 6. 【排序—选择】

题目：选择排序之所以不稳定，是因为它的比较次数过多。
答案：错
解析：不稳定的原因在于最小元素与前面元素交换可能打乱相等键的相对次序，与比较次数无关。

---

✅ 7. 【递推 / 动态规划】

题目：若定义二维数组 dp[n][m] 存储状态，其额外空间复杂度为 O(n m)。
答案：对
解析：数组大小与行列乘积成正比，没有额外压缩时空间复杂度即 O(n m)。

---

✅ 8. 【结构体】

题目：在 C++ 中，struct 与 class 默认成员访问权限相同，都是 private。
答案：错
解析：struct 默认 public，class 默认 private。

---

✅ 9. 【指针与参数传递】

题目：当结构体通过引用传递给函数时，不会调用结构体的拷贝构造函数。
答案：对
解析：引用绑定到已有对象，不构造新副本，自然不会触发拷贝构造。

---

✅10. 【排序—STL 使用】

题目：若在 std::sort 的比较器中写 return a <= b; 将导致编译错误。
答案：错
解析：编译不会报错，但该比较器违反“严格弱序”要求，运行结果未定义或错误排序。

---

七、精选编程题

✅编程题 ① 成绩排序

题目
输入整数 n (1 ≤ n ≤ 1000)，随后 n 行给出学生信息 id name score。
按 成绩降序；若成绩相同按 id 升序 排序输出。

思路分析

• • 定义结构体 Stu { int id; string nm; int sc; }。
• • 用 vector 存；自定义 cmp：sc 大在前，若等则 id 小在前。
• • 使用 stable_sort 保证相等成绩时原序名次不变（可加分）。

#include<bits/stdc++.h>
using namespace std;

struct Stu{
    int id, sc; 
    string nm;
}a[1005];

bool cmp(Stu x, Stu y){
    if(x.sc != y.sc) return x.sc > y.sc;
    return x.id < y.id;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> a[i].id >> a[i].nm >> a[i].sc;
    } 

    sort(a+1, a+n+1, cmp);   // 关键排序
    for (int i = 1; i <= n; i++){
        cout << a[i].id <<' '<< a[i].nm <<' '<< a[i].sc <<'\n';
    }
    return 0;
}

注释：stable_sort 使同分学生保持输入顺序。

---

✅ 编程题 ② 爬楼梯

题目
楼梯共有 n 级（1 ≤ n ≤ 10 000 000）。
每次可以上 1 级或 2 级，问登顶的不同方案数，结果对 1 000 000 007 取模后输出。

提示：这是经典“台阶走法”递推，亦等价于斐波那契数列第 n 项。

---

思路分析

• • 设 dp[i] 为到达第 i 级的方案数。
• • 递推关系

（第 i 级可以由 i-1 级走 1 步来，或 i-2 级走 2 步来）

• • 由于只依赖前两项，用 滚动变量 降到 O(1) 额外空间。
• • n ≤ 1e7，O(n) 循环在 1 秒内可通过；若需更快可改矩阵快速幂 O(log n)。

---

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;                       // n 最多 1e7
    cin >> n;

    long long a = 1;                   // dp[0]
    long long b = 1;                   // dp[1]
    for (long long i = 2; i <= n; ++i) {
        long long c = (a + b) % MOD;   // 递推公式
        a = b;                         // a<-dp[i-1]
        b = c;                         // b<-dp[i]
    }
    cout << b % MOD << '\n';
    return 0;
}

代码要点注释

1. 1. a、b 两个滚动变量即可，无需数组，空间 O(1)。
2. 2. 每步都 %MOD 避免 64 位溢出。
3. 3. 当 n==0 时答案应是 1（仅“站在地面”一种方式）；题目约束 n≥1，故不需特判，若想完整可加。

---