Appearance
第6章 数据结构
🎯 本章学习目标
学完本章，你将能够：
- 理解数组的本质：连续内存、相同类型、下标访问三大核心特征
- 掌握一维数组的定义与初始化方式（全部初始化、部分初始化、清零初始化）
- 熟练使用下标访问数组元素，并牢记"下标从 0 开始"的铁律
- 理解数组越界访问的危害，能够识别代码中的越界错误
- 掌握数组的正序、逆序遍历方法，以及范围 for 循环的使用
- 理解数组作为函数参数时"退化为指针"的特性，以及为何要传长度
- 明确数组大小必须是编译期常量，能判断变长数组（VLA）的非法性
- 熟练运用数组实现统计频次、求最值、查找、逆序等经典操作
- 了解数组与排序（
sort）、二分查找的结合使用（拓展 · 超纲，属四级内容） - 能够独立完成数组相关的编程题，包括去重、插入、删除等综合应用
🗺️ 本章知识图谱
一维数组
├── 基本概念
│ ├── 什么是数组（连续内存、相同类型、下标访问）
│ ├── 数组 vs 普通变量
│ └── 为什么要学数组
├── 定义与初始化
│ ├── 定义格式：类型 数组名[长度]
│ ├── 全部初始化：int a[5] = {1,2,3,4,5}
│ ├── 部分初始化：int a[5] = {1,2} // 其余补0
│ ├── 清零初始化：int a[10] = {0} // 全部为0
│ └── 自动推断长度：int a[] = {1,2,3}
├── 下标访问
│ ├── 下标从 0 开始，范围 0 ~ n-1
│ ├── 内存连续存放：地址 = 首地址 + i × 元素大小
│ └── 越界访问：未定义行为（读垃圾值、写崩溃）
├── 数组遍历
│ ├── 正序遍历：for (int i=0; i<n; i++)
│ ├── 逆序遍历：for (int i=n-1; i>=0; i--)
│ └── 范围 for：for (int x : a)
├── 函数参数
│ ├── 退化为指针，丢失长度信息
│ ├── 必须同时传数组和长度 n
│ └── 传址效果：函数内修改影响原数组
├── 注意事项
│ ├── 数组大小必须是编译期常量
│ ├── 变长数组（VLA）非法
│ └── 竞赛套路：开大数组 + 变量记录有效元素
├── 经典应用
│ ├── 统计与计数（频次统计、求和、求平均）
│ ├── 最值查找（最大值、最小值及其位置）
│ ├── 逆序与反转
│ ├── 查找（顺序查找、二分查找）
│ └── 排序（sort 升序/降序）
└── 综合应用
├── 去重
├── 插入元素
└── 删除元素一、什么是数据结构？
数据结构就是数据在计算机中的组织方式。同样是一批整数，你可以把它们"一个个零散地放着"，也可以"排成一排连续存放"——不同的组织方式，决定了你能多快找到它们、多方便修改它们。
打个比方：同样是 50 本书，堆在地上也能找，但放在书架上编好号，找起来就快得多。"书架 + 编号"就是一种数据结构。
1.1 为什么三级要学数组？
C++ 三级阶段，考纲要求掌握的核心数据结构是——一维数组。
为什么是它？
- 它最简单：数组是"把同类型数据排成一排，每人一个编号（下标）"，最符合直觉
- 它最快：通过下标访问元素，一步到位（O(1) 时间复杂度），不需要从头翻起
- 它是基础：后续所有更复杂的数据结构（字符串、栈、队列、二维数组等）都建立在数组之上
- 它是载体：三级编程题中，枚举、模拟、排序、查找，几乎都要用数组来存储和处理数据
高频考点 🔥： GESP 三级只考查一维数组，二维数组是四级内容。也就是说，三级范围内你能遇到的"数据结构题"，全都围绕一维数组展开。
1.2 数组 vs 普通变量：有什么不一样？
cpp
// 不用数组：存 5 个成绩，要定义 5 个变量
int score1, score2, score3, score4, score5; // 5 个独立变量，毫无关联
// 想遍历？做不到。想用循环？也用不了。想写函数统一处理？得传 5 个参数。
// 用数组：定义 1 个数组，连续存放 5 个成绩
int scores[5] = {90, 85, 78, 92, 88};
// 可以用循环遍历，可以用下标访问任意一个，可以传给函数统一处理数组的本质是：用一段连续的内存空间，存储多个相同类型的数据，通过下标（0, 1, 2, ...）快速定位每一个。
学完本章，你会掌握数组的定义、访问、遍历、传参以及与排序/查找结合的全部用法——这些是三级所有编程题的"基本功"。
二、C++ 一维数组
2.1 数组的定义与初始化
数组是相同类型元素的集合，在内存中连续存放，通过下标访问。
cpp
#include <iostream>
using namespace std;
int main() {
// ① 定义但不初始化：局部数组元素是随机值（垃圾值），不要直接使用！
int a[10];
// ② 定义并全部初始化
int b[5] = {1, 2, 3, 4, 5};
// ③ 全部初始化为 0 —— 最常用的写法！
int c[10] = {0}; // 10 个元素全是 0
// ④ 部分初始化：给出的元素按顺序赋值，其余自动补 0
int d[5] = {1, 2}; // d = {1, 2, 0, 0, 0}
// ⑤ 不写长度，由初始化列表自动推断
int e[] = {1, 2, 3}; // 长度自动为 3
cout << b[0] << " " << b[4] << endl; // 输出：1 5
cout << d[2] << endl; // 输出：0
return 0;
}易错点 ⚠️：
int a[10] = {0};是把所有元素清零；但int a[10] = {5};只是把第一个元素设为 5，其余全是 0，而不是全部为 5！想全部赋成 5 必须用循环。
2.2 下标访问：从 0 开始
长度为 n 的数组，合法下标范围是 0 ~ n-1。
cpp
int a[5] = {10, 20, 30, 40, 50};
// 下标: 0 1 2 3 4
cout << a[0] << endl; // 10，第一个元素
cout << a[4] << endl; // 50，最后一个元素
a[2] = 300; // 修改下标为 2 的元素
cout << a[2] << endl; // 300内存中数组元素连续存放，假设 a[0] 的地址是 2000，每个 int 占 4 字节：
| 元素 | a[0] | a[1] | a[2] | a[3] | a[4] |
|---|---|---|---|---|---|
| 地址 | 2000 | 2004 | 2008 | 2012 | 2016 |
这就是数组访问极快的原因：
a[i]的地址 = 首地址 + i × 元素大小，一次乘法加法就能定位。
2.3 越界访问的危害
cpp
int a[5] = {1, 2, 3, 4, 5};
cout << a[5] << endl; // ❌ 越界！合法下标只有 0~4
cout << a[-1] << endl; // ❌ 越界！高频考点 🔥： C++ 编译器不会检查数组下标是否越界！越界访问读到的是相邻内存的随机数据（可能输出奇怪数字），越界写入则可能破坏其他变量、导致程序崩溃甚至死循环。考试常考"以下程序输出什么"——遇到越界，行为是未定义的，要能识别出这是错误代码。
2.4 数组的遍历
cpp
#include <iostream>
using namespace std;
int main() {
int a[5] = {3, 1, 4, 1, 5};
// 正序遍历：i 从 0 到 n-1
for (int i = 0; i < 5; i++) {
cout << a[i] << " ";
}
cout << endl; // 输出：3 1 4 1 5
// 逆序遍历
for (int i = 4; i >= 0; i--) {
cout << a[i] << " ";
}
cout << endl; // 输出：5 1 4 1 3
// 范围 for 循环（C++11），只读遍历更简洁
for (int x : a) {
cout << x << " ";
}
cout << endl; // 输出：3 1 4 1 5
// 边读入边处理：实际竞赛中最常用
int b[1005], n;
cin >> n; // 先读元素个数
for (int i = 0; i < n; i++) {
cin >> b[i]; // 读入 n 个元素
}
return 0;
}编程习惯： 竞赛题中数组通常开得比数据范围略大，如
int a[1005];（数据最多 1000 个时），防止边界问题。
2.5 数组作为函数参数：退化为指针
cpp
#include <iostream>
using namespace std;
// ❌ 错误示范：函数内无法用 sizeof 得到数组长度
void badFunc(int a[]) {
// 数组作参数时"退化"为指针，sizeof(a) 是指针的大小（8字节），
// 而不是整个数组的大小！
cout << sizeof(a) << endl;
}
// ✅ 正确写法：数组 + 长度 n 一起传
int sumArray(int a[], int n) {
int s = 0;
for (int i = 0; i < n; i++) {
s += a[i];
}
return s;
}
// 修改数组元素不需要返回值——数组传的是"地址"，函数内改的就是原数组
void addOne(int a[], int n) {
for (int i = 0; i < n; i++) {
a[i]++;
}
}
int main() {
int a[5] = {1, 2, 3, 4, 5};
cout << sumArray(a, 5) << endl; // 输出：15
addOne(a, 5);
cout << a[0] << " " << a[4] << endl; // 输出：2 6
return 0;
}高频考点 🔥： 数组作函数参数有两大考点：① 必须额外传长度（数组退化为指针，丢失长度信息）；② 函数内对数组元素的修改会直接影响实参数组（传址效果）。
2.6 数组大小必须是编译期常量（不支持变长数组 VLA）
cpp
int n;
cin >> n;
int a[n]; // ❌ 错误！标准 C++ 不支持变长数组（VLA）数组的长度必须在编译时就能确定，只能用字面量或 const 常量：
cpp
const int MAXN = 1005; // ✅ const 常量
int a[MAXN]; // 正确
int b[1005]; // ✅ 字面量，正确
// 竞赛常用套路：开一个足够大的数组，用变量 n 记录实际元素个数
int arr[1005], n;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];易错点 ⚠️： 有些编译器（如部分版本的 GCC）扩展支持
int a[n];，但这不是标准 C++，GESP 考试环境下按错误处理。三级试卷中出现int a[n];这样的代码，要能判断为非法。
2.7 数组与排序、查找结合
📚 拓展 · 超纲：本节用到的
sort()、binary_search()（<algorithm>）与greater<int>()（<functional>）属于四级内容（排序、二分查找），不在三级考纲范围内。这里仅作为"数组常见的搭档"提前认识；三级考试只考一维数组的基本应用，若需要排序，应能手写冒泡/选择排序。
数组最常与排序、查找搭配考查：
cpp
#include <iostream>
#include <algorithm> // sort、binary_search
#include <functional> //greater<int>()
using namespace std;
int main() {
int a[6] = {3, 1, 4, 1, 5, 9};
int n = 6;
// 排序：sort(首地址, 尾地址的下一个位置)
sort(a, a + n); // 升序：1 1 3 4 5 9
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
sort(a, a + n, greater<int>()); // 降序：9 5 4 3 1 1
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
// 二分查找：前提是数组已升序排好
sort(a, a + n); // 先升序：1 1 3 4 5 9
cout << binary_search(a, a + n, 5) << endl; // 找到，输出 1（true）
cout << binary_search(a, a + n, 7) << endl; // 没有，输出 0（false）
// 顺序查找最大值及其位置
int b[6] = {3, 1, 4, 1, 5, 9};
int maxVal = b[0], maxPos = 0;
for (int i = 1; i < n; i++) {
if (b[i] > maxVal) {
maxVal = b[i];
maxPos = i;
}
}
cout << "最大值" << maxVal << " 位于下标" << maxPos << endl;
// 输出：最大值9 位于下标5
return 0;
}三、数组的经典应用场景 🔥
数组是编程题的"万能容器"，几乎所有算法都要借助数组来存储和处理数据。下面介绍三级考试中最常考的几类数组应用，每类都配完整代码，务必掌握。
3.1 应用一：频次统计（计数数组）
问题： 输入 n 个学生的考试分数（0~100 的整数），统计每个分数出现的次数，并找出出现次数最多的分数。
思路： 开辟一个大小为 101 的计数数组 cnt[101]（下标 0~100 对应 0~100 分），初始全部为 0。每读到一个分数 score，就执行 cnt[score]++。最后遍历计数数组找最大值。
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt[101] = {0}; // 下标 0~100 对应分数 0~100，初始全 0
for (int i = 0; i < n; i++) {
int score;
cin >> score;
cnt[score]++; // 对应分数的计数器 +1
}
// 输出每个分数的出现次数
for (int i = 0; i <= 100; i++) {
if (cnt[i] > 0) {
cout << i << "分：" << cnt[i] << "人" << endl;
}
}
// 找出出现次数最多的分数（众数）
int maxCnt = 0, mode = 0;
for (int i = 0; i <= 100; i++) {
if (cnt[i] > maxCnt) {
maxCnt = cnt[i];
mode = i;
}
}
cout << "最高分的分数：" << mode << "分，出现了" << maxCnt << "次" << endl;
return 0;
}
/*
输入：
10
85 90 85 95 90 85 100 90 85 92
输出：
85分：4人
90分：3人
92分：1人
95分：1人
100分：1人
最高分的分数：85分，出现了4次
*/🍎 生活比喻： 计数数组就像一排邮箱，每个邮箱上写着分数（0~100），每收到一封"分数信"就投进对应邮箱。最后数每个邮箱里有几封信，就知道每个分数出现了多少次。
💡 小技巧： 计数数组的大小 = 数据范围的最大值 + 1（因为下标从 0 开始）。如果数据范围是 1~100，可以开
cnt[101]，下标 0 空着不用也没关系，代码写起来更直观。
3.2 应用二：数组逆序与反转
问题： 将数组中的元素顺序颠倒，如 {1,2,3,4,5} 变成 {5,4,3,2,1}。
思路： 用两个指针（下标）分别指向数组首尾，交换它们指向的元素，然后首指针右移、尾指针左移，直到两指针相遇。
cpp
#include <iostream>
using namespace std;
int main() {
int a[5] = {1, 2, 3, 4, 5};
int n = 5;
// 双指针法：首尾交换，向中间靠拢
int i = 0, j = n - 1;
while (i < j) {
// 交换 a[i] 和 a[j]
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
for (int k = 0; k < n; k++) {
cout << a[k] << " ";
}
cout << endl; // 输出：5 4 3 2 1
return 0;
}🔥 高频考点： 反转数组的交换次数是
n/2次（不是 n 次！），因为每交换一次搞定两个元素。考试常考"循环执行了几次"。
3.3 应用三：顺序查找
问题： 在数组中查找指定的数，找到则返回它的下标，找不到返回 -1。
思路： 从头到尾逐个比较，找到就返回位置；遍历完还没找到就返回 -1。
cpp
#include <iostream>
using namespace std;
// 顺序查找：返回 key 在数组 a 中的下标，找不到返回 -1
int findIndex(int a[], int n, int key) {
for (int i = 0; i < n; i++) {
if (a[i] == key) {
return i; // 找到，立即返回下标
}
}
return -1; // 遍历完都没找到
}
int main() {
int a[6] = {3, 1, 4, 1, 5, 9};
cout << findIndex(a, 6, 5) << endl; // 输出：4（下标4）
cout << findIndex(a, 6, 7) << endl; // 输出：-1（找不到）
return 0;
}⚠️ 易错点： 如果数组中有多个相同的元素，顺序查找返回的是第一个出现的位置。如果题目要求返回"最后一个出现的位置"，就要从后往前遍历。
3.4 应用四：在数组中插入元素
问题： 给定一个有序（升序）数组和一个新元素，将新元素插入到合适的位置，保持数组仍然有序。
思路： ① 找到插入位置（第一个比新元素大的位置）；② 从数组末尾开始，把插入位置及其后的元素都向后挪一位；③ 把新元素放入插入位置。
cpp
#include <iostream>
using namespace std;
int main() {
int a[10] = {1, 3, 5, 7, 9}; // 升序数组，容量10，当前有5个元素
int n = 5; // 当前元素个数
int x = 6; // 要插入的新元素
// 第1步：找插入位置 pos（第一个比 x 大的元素的下标）
int pos = 0;
while (pos < n && a[pos] < x) {
pos++;
}
// 此时 pos 就是插入位置：a[0..pos-1] < x <= a[pos..n-1]
// 第2步：从后往前挪，腾出位置
for (int i = n; i > pos; i--) {
a[i] = a[i - 1];
}
// 第3步：插入新元素
a[pos] = x;
n++; // 元素个数 +1
// 输出结果
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl; // 输出：1 3 5 6 7 9
return 0;
}⚠️ 易错点： 挪动元素必须从后往前挪！如果从前往后挪，会把后面的元素覆盖掉（因为前一个挪到后一个时，后一个的值还没来得及挪走就被覆盖了）。这是插入操作最经典的"坑"。
3.5 应用五：在数组中删除元素
问题： 删除数组中指定位置的元素，后面的元素依次前移填补空缺。
思路： 从删除位置开始，把后面的元素依次往前挪一位，最后元素个数减一。
cpp
#include <iostream>
using namespace std;
int main() {
int a[10] = {1, 3, 5, 7, 9};
int n = 5;
int idx = 2; // 删除下标为 2 的元素（即数字 5）
// 从 idx 开始，后面的元素依次往前挪一位
for (int i = idx; i < n - 1; i++) {
a[i] = a[i + 1];
}
n--; // 元素个数 -1
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl; // 输出：1 3 7 9
return 0;
}💡 小技巧： 删除是从前往后挪（跟前一个看齐），插入是从后往前挪（跟后一个看齐）。可以这样记：删除时"后面的往前挤"，插入时"后面的往后让"。
3.6 应用六：前缀和数组
📚 拓展 · 超纲：前缀和不在三级考纲范围内，但它是最常用的"区间求和"优化技巧，非常实用。这里供学有余力的同学提前了解，考试不作要求。
问题： 给定一个数组 a，快速求任意区间 a[l] + a[l+1] + ... + a[r] 的和。如果每次都从头累加，查询多了会很慢。
思路： 预先计算前缀和数组 s，其中 s[i] 表示前 i 个元素的和（即 a[0]+a[1]+...+a[i-1]）。那么区间 [l, r] 的和 = s[r+1] - s[l]。
cpp
#include <iostream>
using namespace std;
int main() {
int a[5] = {3, 1, 4, 1, 5};
int n = 5;
// 计算前缀和数组 s，s[i] = a[0]+a[1]+...+a[i-1]
int s[6] = {0}; // s[0] = 0，s[1] = a[0]，s[2] = a[0]+a[1] ...
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + a[i];
}
// s = {0, 3, 4, 8, 9, 14}
// 求 a[1] + a[2] + a[3]（即下标 1~3）：s[4] - s[1] = 9 - 3 = 6
int l = 1, r = 3;
cout << "区间和：" << s[r + 1] - s[l] << endl; // 输出：6
// 验证：1 + 4 + 1 = 6 ✓
return 0;
}🍎 生活比喻： 前缀和就像楼梯台阶的总高度。
s[5]是爬到第 5 阶的总高度，s[2]是爬到第 2 阶的总高度。那么从第 3 阶到第 5 阶的高度差 =s[5] - s[2]，不用一阶一阶重新数。
🔥 高频考点： 前缀和是三级竞赛题的常用优化技巧——把"每次求和 O(n)"变成"预处理 O(n) + 每次查询 O(1)"。遇到"多次查询区间和"的题目，第一反应就应该是前缀和。
四、📝 实战练习
练习题 1（程序阅读题）
题目： 阅读以下程序，写出运行结果：
cpp
#include <iostream>
using namespace std;
int func(int a[], int n) {
int s = 0;
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 0) s += a[i];
}
return s;
}
int main() {
int a[6] = {3, 1, 4, 1, 5, 9};
cout << func(a, 6) << endl;
return 0;
}🔑 点击查看答案与解析
答案： 4
解析： 数组 a 传给函数时退化为指针，因此同时传入长度 6。函数遍历数组，累加其中的偶数：元素为 3、1、4、1、5、9，偶数只有 4，所以输出 4。
考点：数组作函数参数需传长度；遍历 + 条件累加。
练习题 2（编程题）
题目： 输入 n 个整数（n ≤ 1000），将它们去重后按升序输出，元素之间用空格分隔。
输入样例：
8
3 1 4 1 5 9 2 3输出样例：
1 2 3 4 5 9🔑 点击查看答案与解析
C++ 参考代码：
cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005]; // 数组大小用编译期常量，不能写 a[n]
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n); // 先升序排序
// 排序后重复元素相邻，输出时跳过与前一个相同的元素即可去重
bool first = true; // 标记是否为第一个输出的元素，用来控制空格
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1]) continue; // 与前一个相同，重复，跳过
if (!first) cout << " "; // 不是第一个元素，前面先输出空格
cout << a[i];
first = false;
}
cout << endl;
return 0;
}解析：
- C++ 思路：数组长度必须是编译期常量（开
a[1005]）→sort排序 → 排序后相同元素相邻，遍历时跳过与前一个相等的元素即完成去重；
练习题 3（单选题）
题目： 下列关于 C++ 一维数组的说法，正确的有（ ）
① 数组的下标从 1 开始 ② int a[5] = {0}; 会把数组所有元素初始化为 0 ③ 数组作函数参数时，函数内可以用 sizeof(a) 得到数组的总字节数 ④ int a[n]; （n 为变量）是标准 C++ 允许的写法 ⑤ 数组越界写入可能导致程序崩溃
A. ①②③ B. ②⑤ C. ②③⑤ D. ②④⑤
🔑 点击查看答案与解析
答案： B
解析：
- ① 错误 ❌：数组下标从 0 开始，不是 1。
- ② 正确 ✅：
{0}初始化时，第一个元素为 0，其余自动补 0，所以全部为 0。 - ③ 错误 ❌：数组作函数参数时退化为指针，
sizeof(a)得到的是指针大小（8 字节），不是整个数组的大小。 - ④ 错误 ❌：标准 C++ 不支持变长数组（VLA），数组大小必须是编译期常量。
- ⑤ 正确 ✅：越界写入会破坏其他变量的数据，可能导致程序崩溃、死循环等未定义行为。
正确的有 ②⑤，选 B。
练习题 4（判断题）
题目： 判断下列说法是否正确，正确的打"√"，错误的打"×"。
(1) int a[5] = {1, 2}; 执行后，a[2] 的值是 2。（ ） (2) 数组名可以作为函数参数传递，函数内修改数组元素会影响实参数组。（ ） (3) 数组在内存中不一定是连续存放的。（ ） (4) 长度为 n 的数组，合法下标范围是 1 ~ n。（ ） (5) int a[] = {1, 2, 3}; 是合法的，数组长度自动为 3。（ ）
🔑 点击查看答案与解析
答案： (1) × (2) √ (3) × (4) × (5) √
解析：
- (1) ×：部分初始化时，给出的元素按顺序赋值，其余自动补 0。
a[2]是第 3 个元素（下标 2），没有初始化，所以是 0，不是 2。 - (2) √：数组名传参时传递的是首地址（传址），函数内通过下标修改的就是原数组的元素。
- (3) ×：数组的核心特征就是连续存放，这是下标快速访问的基础。
- (4) ×：合法下标范围是 0 ~ n-1，从 0 开始。
- (5) √：不写长度时，编译器根据初始化列表中元素的个数自动推断数组长度。
练习题 5（程序阅读题）
题目： 阅读以下 C++ 程序，写出输出结果：
cpp
#include <iostream>
using namespace std;
int main() {
int a[8] = {1, 3, 2, 3, 1, 3, 2, 1};
int cnt[4] = {0};
for (int i = 0; i < 8; i++) {
cnt[a[i]]++;
}
int maxV = 0;
for (int i = 1; i <= 3; i++) {
if (cnt[i] > maxV) maxV = cnt[i];
}
cout << maxV << endl;
return 0;
}🔑 点击查看答案与解析
答案： 3
解析： 这是一个典型的频次统计程序。数组 a 中有 8 个元素（值为 1、2、3），cnt 数组用来计数：
cnt[1]：统计 1 出现的次数 → a 中有 3 个 1 →cnt[1] = 3cnt[2]：统计 2 出现的次数 → a 中有 2 个 2 →cnt[2] = 2cnt[3]：统计 3 出现的次数 → a 中有 3 个 3 →cnt[3] = 3
最后找最大值，cnt[1] 和 cnt[3] 都是 3，最大值为 3。
考点：计数数组（桶排序思想）+ 找最大值。注意
cnt[0]没有使用（因为 a 中没有 0），循环从 i=1 开始。
练习题 6（程序阅读题）
题目： 阅读以下 C++ 程序，写出输出结果：
cpp
#include <iostream>
using namespace std;
int main() {
int a[6] = {10, 20, 30, 40, 50, 60};
int i = 0, j = 5;
while (i < j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
}
cout << a[1] + a[4] << endl;
return 0;
}🔑 点击查看答案与解析
答案： 70
解析： 程序实现的是数组反转（双指针首尾交换法）。
初始：a = {10, 20, 30, 40, 50, 60}
交换过程：
- 第 1 次：i=0, j=5，交换 a[0]=10 和 a[5]=60 →
{60, 20, 30, 40, 50, 10}，i=1, j=4 - 第 2 次：i=1, j=4，交换 a[1]=20 和 a[4]=50 →
{60, 50, 30, 40, 20, 10}，i=2, j=3 - 第 3 次：i=2, j=3，交换 a[2]=30 和 a[3]=40 →
{60, 50, 40, 30, 20, 10}，i=3, j=2 - i >= j，循环结束
最终数组：{60, 50, 40, 30, 20, 10}
a[1] + a[4] = 50 + 20 = 70，输出 70。
💡 小技巧：选择题中遇到反转数组求某下标的值，可以直接"对称映射"——反转后 a[i] = 原 a[n-1-i]。所以 a[1] 对应原 a[4]=50，a[4] 对应原 a[1]=20，加起来还是 70，不用一步步模拟。
练习题 7（编程题）
题目： 输入 n 个学生的成绩（0~100 的整数），输出平均分（保留整数）和高于平均分的人数。
输入样例：
5
80 90 70 60 75输出样例：
75
2🔑 点击查看答案与解析
C++ 参考代码：
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int scores[1005]; // 最多 1000 个学生
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> scores[i];
sum += scores[i]; // 边读边累加总分
}
int avg = sum / n; // 平均分（整数除法，自动取整）
int above = 0; // 高于平均分的人数
for (int i = 0; i < n; i++) {
if (scores[i] > avg) {
above++;
}
}
cout << avg << endl;
cout << above << endl;
return 0;
}解析：
- 第 1 步：读入 n 个成绩，同时累加总分；
- 第 2 步：总分 ÷ 人数 = 平均分（整数除法自动向下取整）；
- 第 3 步：再遍历一次数组，统计高于平均分的人数。
样例验证：
- 总分 = 80+90+70+60+75 = 375，平均分 = 375/5 = 75
- 高于 75 分的有 80、90，共 2 人 ✓
考点：数组存储 + 累加求和 + 条件计数。这是数组题最基础的"三件套"，必须熟练掌握。
练习题 8（编程题）
题目： 输入 n 个整数存入数组，再输入一个整数 x，删除数组中所有值为 x 的元素，输出删除后的数组。
输入样例：
7
3 1 4 1 5 1 9
1输出样例：
3 4 5 9🔑 点击查看答案与解析
C++ 参考代码（方法一：新数组搬运）：
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int b[1005], m = 0; // b 存结果，m 是结果数组的元素个数
for (int i = 0; i < n; i++) {
if (a[i] != x) { // 不等于 x 的元素才搬运到 b
b[m] = a[i];
m++;
}
}
for (int i = 0; i < m; i++) {
if (i > 0) cout << " ";
cout << b[i];
}
cout << endl;
return 0;
}C++ 参考代码（方法二：原地删除，不开新数组）：
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int k = 0; // 有效元素的存放位置
for (int i = 0; i < n; i++) {
if (a[i] != x) {
a[k] = a[i]; // 保留的元素放到前半部分
k++;
}
}
// 此时 a[0..k-1] 就是删除后的结果
for (int i = 0; i < k; i++) {
if (i > 0) cout << " ";
cout << a[i];
}
cout << endl;
return 0;
}解析：
- 方法一（新数组法）：开辟一个新数组 b，遍历原数组 a，把不等于 x 的元素复制到 b 中。思路简单、不易出错，推荐初学者使用。
- 方法二（原地删除）：用一个"慢指针"k 记录有效元素该放哪，"快指针"i 遍历所有元素。遇到不等于 x 的，就放到 k 的位置，k 前移。空间复杂度更低（不需要额外数组）。
样例验证：删除所有 1 后，剩余元素为 3、4、5、9 ✓
考点：数组遍历 + 条件筛选 + 结果输出。这是数组操作的经典题型，两种方法都要理解。
五、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
数组定义与初始化（{0} 清零、部分初始化补0） | ⭐⭐⭐⭐ | 选择/程序阅读 | 误以为 {5} 会把所有元素设为 5（实际只有第一个是 5，其余为 0） |
| 下标从 0 开始、合法范围 0~n-1 | ⭐⭐⭐⭐⭐ | 选择/判断/程序阅读 | 下标从 1 开始记；最后一个元素下标写成 n（应为 n-1） |
| 越界访问的未定义行为 | ⭐⭐⭐⭐⭐ | 选择/判断 | 以为编译器会检查越界；以为越界只会读错值 |
| 数组遍历（正序、逆序、范围 for） | ⭐⭐⭐⭐ | 程序填空/编程 | 逆序遍历时 i 从 n 开始（应从 n-1）；循环条件写成 i > 0（漏掉 a[0]） |
| 数组作函数参数退化为指针、须传长度 | ⭐⭐⭐⭐ | 选择/程序阅读 | 函数内用 sizeof 求数组长度；不知道传址可以修改原数组 |
| 数组大小须为编译期常量（VLA 非法） | ⭐⭐⭐ | 选择/判断 | 以为 int a[n]; 合法；不知道 const 常量可以作数组大小 |
| 频次统计（计数数组） | ⭐⭐⭐⭐ | 程序阅读/编程 | 计数数组大小开错；下标偏移问题 |
| 求最值及其下标 | ⭐⭐⭐⭐ | 程序填空/编程 | 初始值设为 0（应为第一个元素）；只记值不记位置 |
| 数组反转（双指针法） | ⭐⭐⭐⭐ | 程序阅读 | 交换次数搞错；循环条件写成 i <= j |
| 插入/删除元素（挪动方向） | ⭐⭐⭐ | 编程/程序填空 | 插入时从前往后挪（应该从后往前）；删除时漏掉 n-- |
| 前缀和数组 | ⭐⭐⭐⭐ | 编程/程序填空 | 下标错位；公式记错（应为 s[r+1]-s[l]） |
| sort 排序与二分查找 | ⭐⭐⭐⭐ | 编程题 | 尾地址写错（应为 a+n 不是 a+n-1）；二分查找前忘记排序 |
⭐ 必背速记卡
┌──────────────────────────────────────────────────────┐
│ ⭐ 一维数组必背速记卡 │
├──────────────────────────────────────────────────────┤
│ 1. 数组三要素：相同类型、连续存放、下标访问 │
│ 2. 下标从 0 开始，长度 n 的数组合法范围是 0 ~ n-1 │
│ 3. int a[10] = {0}; 所有元素全清零 │
│ 4. int a[5] = {1, 2}; 其余三个元素自动补 0 │
│ 5. C++ 不检查数组越界，越界是未定义行为 │
│ 6. 数组作函数参数退化为指针，必须额外传长度 n │
│ 7. 数组作参数是传址，函数内修改影响原数组 │
│ 8. 数组大小必须是编译期常量，int a[n] 非法（VLA） │
│ 9. 反转数组：双指针 i=0, j=n-1，交换 n/2 次 │
│ 10. 插入元素：从后往前挪；删除元素：从前往后挪 │
│ 11. 前缀和 s[i] = a[0]+...+a[i-1]，区间[l,r]和=s[r+1]-s[l]│
│ 12. 计数数组大小 = 数据最大值 + 1 │
└──────────────────────────────────────────────────────┘