C++机试真题解析：从指针到二分查找的五大高频考点实战复盘

每年一到三四月份，就是各大单位集中组织计算机能力测试的高峰期，C++机试又是其中最常出现的科目。我最近刚带完一轮针对机试的突击训练，自己也完整模拟了一遍整套真题流程。这次要写的是 26.3.12 场次的 t88 到 t92，总共五道题。这五题很有意思，覆盖了指针、字符串处理、排序、质数判断、二分查找这几个机试高频考点，难度梯度也拉得比较开，有送分题也有需要静下心推演的题目。对于准备 C++ 机试的朋友来说，这一套题如果吃透了，应付大多数单位的机试基本问题不大。

我写这篇文章，不是简单把代码贴一遍了事。我会把每一题的核心考点、设计思路、我当时踩过的坑、最后落地可用的代码全部拆开讲清楚，也会把一些机试实战中的时间分配、编译环境选择、边界测试心得一并分享出来。内容偏向实战复盘，适合正在备战机试的在校学生，也适合工作后需要参加晋升或职称机考的开发者。

1. 机试全貌与题目布局

1.1 这套题到底在考什么

t88 到 t92 这五道题，从编号上就能看出是同一场次中连续的一套题。机试的出题逻辑通常不是漫无边际地乱考，而是会按照“基础语法、数据结构、经典算法、数学思维、综合应用”这条主线来设计。这套题也遵循了这个规律：

• t88 考指针与字符串，考察 C++ 最底层的内存操作能力；
• t89 考字符串转换与数组处理，偏向于输入解析和边界处理；
• t90 考排序算法，从手写冒泡到 sort 库函数的选型；
• t91 考质数判断与快速幂，属于典型数论入门；
• t92 考二分查找，是算法题里最常出现的查找范式。

五道题从易到难，我实际做下来的体感是：t88 和 t89 属于热身题，需要求稳拿满分；t90 和 t91 是分水岭，能筛选出有基本功的人；t92 是拉开差距的题目，虽然代码量不大，但边界条件稍不注意就会扣分。

1.2 机试环境的确定性不能忽视

机试和平时开发不一样，环境是固定的。我这次模拟用的是 Windows + Visual Studio 2022 社区版，编译标准选的 C++17。虽然 g++ 在 Linux 环境下也能编译通过这套题的代码，但机试阅卷系统往往以 Windows 平台为准。

有几个环境细节特别重要：

• #include <bits/stdc++.h>这种万能头文件在 VS 里默认是不存在的，必须老老实实包含具体头文件；
• scanf/printf 和 cin/cout 混用的时候要注意，如果关闭了同步（ios::sync_with_stdio(false)），混用很可能导致输入顺序错乱；
• 机试系统通常要求从标准输入读取数据，向标准输出写入结果，不需要做文件读写。

还有一个容易被忽略的点：VS 默认使用的是 UTF-8 编码，但如果系统区域设置为中文，控制台窗口的代码页可能是 GBK。如果题目要求输出中文字符串，最好用英文输出，或者提前设置setlocale(LC_ALL, "chs")，否则会出现乱码导致误判。

1.3 做题顺序与时间分配策略

机试时间一般给得比较紧，2 小时做 5 题，平均每题 24 分钟。我的建议是不要死磕顺序，拿到题先花两分钟把所有题都扫一遍，按难度排序再动手。

我这次的做题顺序是：t88 → t89 → t90 → t91 → t92。理由很简单，t88 和 t89 是基础题，先把该拿的分稳稳装进口袋，心态会稳很多。t90 的排序是中等难度，写完后可以缓一口气。t91 的质数判断如果优化思路清晰，十分钟就能写完。最后集中精力做 t92 的二分查找。

核心原则是：永远不要在某一题上卡超过 30 分钟。如果一道题思路进了死胡同，先跳过，等做完其他题再回头用暴力解法兜底。

2. t88：指针与字符串处理

2.1 题目还原与题意拆解

t88 的题目是一道经典指针应用题，要求实现一个函数，接收一个 C 风格字符串（char*或const char*），统计其中不同字符的个数，并且将只出现一次的字符按原顺序输出。题目会给定一段测试代码，使用指针遍历字符串，不能借助std::string的算法库。

这种题非常典型，机试中的同学容易出现两个问题：

一是对 C 风格字符串的结尾符'\0'不够敏感。写循环条件的时候经常写成for(int i = 0; i < strlen(str); i++)，这在每轮循环都要调用一次strlen，时间复杂度会从 O(n) 变成 O(n²)，数据量一大就会超时。正确的姿势是直接判断*p != '\0'，或者先算出长度存到变量里。

二是指针自增和取值运算符的优先级搞混。*p++和(*p)++是两个完全不同的操作，前者是先取p指向的值、再移动指针，后者是把p指向的值加一。新手在这里非常容易出错。

2.2 指针遍历的两种正确写法

第一种是下标方式，虽然题目要求用指针，但很多同学习惯性用下标，其实效果等价，只是不够“指针”：

int countUnique(const char* str) { if (str == nullptr) return 0; int cnt[256] = {0}; int len = 0; while (str[len] != '\0') { cnt[(unsigned char)str[len]]++; len++; } int unique = 0; for (int i = 0; i < len; i++) { if (cnt[(unsigned char)str[i]] == 1) { unique++; } } return unique; }

这里有个细节：char类型在部分平台可能带符号位，直接用char做数组下标会越界。用(unsigned char)强制转换后再作为下标是必须的，这算是一个隐藏的坑。

第二种是纯指针方式，更贴合题目要求：

int countUnique(const char* str) { if (str == nullptr) return 0; int cnt[256] = {0}; const char* p = str; while (*p != '\0') { cnt[(unsigned char)*p]++; p++; } int unique = 0; for (p = str; *p != '\0'; p++) { if (cnt[(unsigned char)*p] == 1) { unique++; } } return unique; }

2.3 指针参数设计的两个原则

这道题如果要求写函数而不是完整程序，函数的参数设计也需要讲究。接收字符串时，用const char*比char*更安全，因为函数只读数据，不修改内容。如果阅卷系统中有代码审查环节，const的加分效应会很明显。还有一个原则是指针参数永远要先判空。很多同学写指针题时忽略了nullptr的判断，一旦测试数据传入空指针，程序直接崩溃，这一题基本就白卷了。

2.4 我踩过的坑：数组越界的隐蔽来源

我第一版代码用了全局数组int cnt[26]，题目测试用例也全是小写字母，所以当时跑得很顺畅。但在 debug 模式下偶然输入了一个大写字母，cnt['A']的下标是 65，直接越界。虽然数组开在全局区，越界不一定崩溃，但结果肯定是错的。

后来我把数组改成int cnt[256]，把所有单字节字符都覆盖了。最好再写一个assert(str != nullptr)，方便在 debug 阶段就发现问题。

3. t89：字符串数组转换与算术解析

3.1 题目要求与多个易错点

t89 是一个字符串处理题，题目要求输入一串由数字字符和逗号组成的字符串，例如"123,456,789"，把每个由逗号分隔的子串转换成整数存入数组，然后求和输出。

这题看着简单，实际上隐藏了大量字符串转数字的细节：

• 空字符串处理：如果输入是空串，应该输出 0 还是报错？机试阅卷时通常约定为空串输出 0；
• 连续逗号："1,,2"这种情况，中间的空段应该按 0 处理还是跳过？不同题目的要求可能不同，必须仔细读题干；
• 数字溢出：子串转 int 后如果超过INT_MAX，需要改用long long；
• 负数支持：如果数字包含负号，解析逻辑需要额外处理。

用一个表格来说明常见边界输入与合理输出：

3.2 解析实现：手动解析还是直接用 strtok

网上很多代码会推荐strtok分割字符串，但在 C++ 机试场景中我不太建议这么做。strtok会修改原字符串，把分隔符替换成'\0'，如果原字符串是const char*类型的字面量，直接调用strtok会导致只读内存修改，程序崩溃。C++ 更稳的写法是用istringstream加getline，或者直接手写解析循环。

我用的方案是手写解析，核心逻辑很简单：

#include <iostream> #include <string> #include <vector> using namespace std; vector<long long> parseNumbers(const string& s) { vector<long long> res; long long cur = 0; bool inNum = false; bool negative = false; for (char c : s) { if (c == ',') { if (inNum) res.push_back(negative ? -cur : cur); else res.push_back(0); cur = 0; inNum = false; negative = false; } else if (c == '-') { negative = true; inNum = true; } else if (c >= '0' && c <= '9') { cur = cur * 10 + (c - '0'); inNum = true; } // 非法字符直接忽略，或者根据题目要求报错 } if (inNum) res.push_back(negative ? -cur : cur); else if (s.size() > 0 && s.back() == ',') res.push_back(0); return res; } int main() { string input; while (getline(cin, input)) { vector<long long> nums = parseNumbers(input); long long sum = 0; for (long long v : nums) sum += v; cout << sum << endl; } return 0; }

这里有个技巧：用bool inNum来记录当前是否处于一个数字段中，避免连续逗号导致多压入一个 0。很多同学在处理"1,,2"时，遇到第一个逗号 push 了 1，遇到第二个逗号看到inNum == false就不 push，但此时"1,"和","的语义是有区别的，用inNum状态就能统一正确判断。

3.3 getline 循环读入的注意事项

机试的输入经常有多行，每行一组测试数据。用while (getline(cin, input))是最稳的写法。但有一个容易翻车的点：如果前面用了cin >> n读整数，后面再用getline，第一行getline会读到一个空串，因为缓冲区里残留着换行符。解决方案是在cin >> n后加一句cin.ignore()，或者统一用getline读整行再解析。

3.4 long long 的选择与溢出边界

这道题我用long long存储中间结果，主要是考虑解析过程中cur = cur * 10 + digit可能临时溢出。如果题目的子串最长是 10 位数字，int 刚好够，但如果出现 11 位，int 就装不下了。机试阅卷数据经常会刻意放一个极长的数字测边界，所以预先使用long long是性价比最高的防御。

不过long long也不是无限大，如果子串超过 19 位，还是会溢出。在实际代码中，我加了一个判断：如果cur > (LLONG_MAX - digit) / 10，就标记为溢出。这是从工程化角度考虑的，虽然机试中几乎不会遇到这种极值。

4. t90：排序算法与库函数选型

4.1 题目描述与两种解题路线

t90 是一道排序题，输入 n 个整数，要求从小到大输出排序结果。限制条件是：n 的最大值可达 10 万，且相同值的元素需要保持输入时的相对顺序。

这个“保持相对顺序”的要求非常关键，它直接决定了你能否用库函数sort解决。std::sort是不稳定排序，相同元素的相对顺序不保证。而std::stable_sort是稳定排序，时间复杂度同样是 O(n log n)，可以完美满足要求。

不过很多同学在机试时记忆混淆，搞不清sort和stable_sort的区别，直接用了sort，导致在重复元素很多的时候输出顺序不符，被扣掉不少分。

4.2 手写冒泡排序的完整实现与优化

既然题目考察排序，有些阅卷系统会强制要求手写排序算法。手写冒泡是最直观的方案，但如果不加优化，10 万个元素绝对会超时。

冒泡排序的常规写法是两层循环：外层控制轮数，内层做相邻比较和交换。优化点主要有两个：

• 如果某一轮没有发生任何交换，说明数组已经有序，提前终止外层循环；
• 记录最后一次交换的位置，下一轮只需要比较到这个位置为止，因为该位置之后的元素已经有序。

当然，n 达到 10 万时，即便是优化后的冒泡也扛不住，所以这道题的最优解是手写快速排序或者直接用stable_sort。我给出的完整手写冒泡用于平时练习理解，机上实战还是用库函数更稳：

#include <iostream> #include <vector> using namespace std; void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; } }

面试官或阅卷系统如果要求手写，写快排的得分会明显高于冒泡。我现场写的快排是基于 Lomuto 分区方案的递归版本，代码量不大，关键是注意基准值的选取——如果基准每次都取第一个元素，遇到已有序数组会退化到 O(n²)。稳妥起见，三数取中法最保险。

4.3 库函数 sort 与 stable_sort 的底层逻辑

机试是允许使用标准库的，只要题目不明确禁止。std::sort通常在数据量小时使用插入排序，数据量大时使用快速排序，还有堆排序兜底，所以整体性能非常稳定。但它不稳定，这是硬伤。

std::stable_sort的底层是归并排序，时间复杂度稳定在 O(n log n)，且是稳定排序。它额外需要 O(n) 的辅助空间，不过对于 10 万级别的数据来说，内存占用非常小，完全不是问题。

实战建议：如果题目没有明确要求手写排序，直接用std::stable_sort，既满足稳定性要求，效率也达标。如果 n 特别大且数据范围很小（比如 0 到 100 之间），用计数排序能做到 O(n)，效率更高。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } stable_sort(arr.begin(), arr.end()); for (int i = 0; i < n; i++) { if (i > 0) cout << ' '; cout << arr[i]; } cout << endl; return 0; }

4.4 与快速幂算法的联动思考

这道题排序本身难度不大，但在机试的后续题目（特别是 t91 的质数判断）中，排序数组往往能配合数学性质降低复杂度。比如判断一个数组中有多少对质数，可以先排序再用双指针扫描，或者对每个元素判断质数时利用递增特性提前退出。

所以 t90 真正的价值不只是排序本身，而是为后续题目提供一个有序、稳定的数据预处理基础。这也是为什么机关机试总喜欢把排序题放在中间位置——它承上启下。

5. t91：质数判断的数学精妙与快速幂实现

5.1 题目要求：判断质数的基础版与升级版

t91 是一道关于质数的题目。基础版要求判断输入的正整数 n 是否为质数；升级版则要求输出 [m, n] 区间内所有质数，并计算它们的和。这类题目在机试中出现频率极高，几乎可以说是必考题型。

最朴素的试除法是从 2 遍历到 n-1，看是否存在因子。对于单次查询来说没问题，但如果 n 达到 10⁷ 级别，且需要判断区间内所有数，这种做法的复杂度不可接受。这里就需要引入质数判断的经典优化：

• 只需要遍历到 √n：因为如果 n 存在大于 √n 的因子，必然存在小于 √n 的配对因子；
• 排除偶数和 2 的倍数：步长从 1 改为 2，循环次数减半；
• 6k ± 1 规则：大于 3 的质数必然分布在 6 的倍数两侧，进一步压缩循环次数。

5.2 试除法优化后的完整代码

#include <iostream> #include <cmath> using namespace std; bool isPrime(int n) { if (n <= 1) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; } int main() { int m, n; cin >> m >> n; long long sum = 0; for (int i = m; i <= n; i++) { if (isPrime(i)) sum += i; } cout << sum << endl; return 0; }

这个版本对单个数的判断时间是 O(√n / 6)，已经非常快了。但区间 [1, 10⁷] 内每个数都判断一次，总体时间复杂度依然高。真正的大规模区间质数统计必须用筛法。

5.3 埃氏筛：区间质数统计的主流方案

埃拉托斯特尼筛法的核心思想是：从 2 开始，每遇到一个质数，就把它的倍数全部标记为合数。标记完成后，所有未被标记的数就是质数。

#include <iostream> #include <vector> using namespace std; vector<int> sieve(int n) { vector<int> ans; vector<bool> isComposite(n + 1, false); for (int i = 2; i <= n; i++) { if (!isComposite[i]) { ans.push_back(i); if ((long long)i * i <= n) { for (int j = i * i; j <= n; j += i) { isComposite[j] = true; } } } } return ans; }

一个容易被人忽略的优化是：内层循环从i * i开始，而不是从i * 2开始。因为 i 的较小倍数已经被更小的质数标记过了，不需要重复标记。这一点在数据量大时能节省大量时间。

5.4 快速幂：为什么质数题会牵扯幂运算

很多质数相关的题目会同时考察快速幂。比如有一种题：判断a^n mod p是否为质数，或者用费马小定理做素性探测。快速幂的核心思想是把指数二进制拆分，通过迭代平方来减少乘法次数，把 O(n) 的时间降为 O(log n)。

long long quickPow(long long a, long long b, long long mod) { long long result = 1; a %= mod; while (b > 0) { if (b & 1) { result = result * a % mod; } a = a * a % mod; b >>= 1; } return result; }

这段代码的骨架非常重要，在机试中几乎是“标准模板”级别。它的关键点有三个：一是每步取模防止溢出；二是用位运算判断最低位是否为 1；三是平方操作和右移操作的顺序不能被调换。

5.5 实测中遇到的质数范围与溢出问题

我在实际测试时，把区间设到了 [1, 10⁷]，埃氏筛的 vector 大小开到 10000001，内存占用约 10 MB，运行速度在 0.1 秒左右，完全满足机试要求。但如果用bool数组直接开在栈上，可能会因为栈空间不足导致崩溃。建议要么用全局数组，要么用vector<bool>，后者还有空间优化的机制。

还有一点，埃氏筛里isComposite最好用vector<bool>而不是vector<char>或vector<int>，因为vector<bool>做了位压缩，内存能减少到原来的 1/8。当然，位压缩会带来一定的访问开销，但机试数据量下完全可接受。

6. t92：二分查找的边界哲学

6.1 题目描述与前置条件

t92 是一道二分查找题。输入一个有序数组和一个目标值，要求返回目标值在数组中的起始位置和结束位置。如果不存在，返回 “-1 -1”。这是二分查找的经典变种——查找左右边界。

二分查找本身逻辑简单，但边界条件极易出错。机试中这题的通过率通常不高，主要原因就是很多人死记模板，没有理解循环不变量的含义。一旦题目稍微变化（比如找左边界、找右边界、或者查找插入位置），就不知道怎么改了。

6.2 左边界与右边界的统一写法

找左边界的核心思想是：当arr[mid] >= target时，左边界不可能在 mid 右边，所以让right = mid；否则让left = mid + 1。注意这里用的是左闭右闭区间还是左闭右开区间，必须全程一致。

推荐写法是左闭右闭，然后单独封装两个函数：

#include <iostream> #include <vector> using namespace std; int findLeft(vector<int>& arr, int target) { int left = 0, right = arr.size(); // 左闭右开 while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } int findRight(vector<int>& arr, int target) { int left = 0, right = arr.size(); // 左闭右开 while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) { left = mid + 1; } else { right = mid; } } return left - 1; }

调用时，先算l = findLeft(arr, target)，再算r = findRight(arr, target)。如果l >= arr.size()或arr[l] != target，说明不存在，输出 “-1 -1”。否则输出l和r。

6.3 二分查找的三个经典坑位

第一个坑是死循环。用左闭右闭区间时，如果mid = (left + right) / 2且left + right是奇数，mid会偏向左侧。当right = mid时，可能出现left和right始终无法收敛的情况。解决方法是统一用左闭右开区间，并在循环条件里写left < right，这样能天然规避大部分死循环问题。

第二个坑是整数溢出。mid = (left + right) / 2在 left 和 right 都接近INT_MAX时，left + right可能溢出变成负数。正确写法是mid = left + (right - left) / 2。这是很多机试代码即使看起来逻辑正确也会超时的隐藏原因。

第三个坑是二分的适用前提：数组必须是有序的。题目明确说“有序数组”，但如果输入是降序，直接套升序逻辑就会全错。答题前先确认数组的排序方向，或者先做一次升序排序。

6.4 扩展思考：二分答案更值得掌握

t92 考的是基础二分查找，但机试想拿高分，建议进一步掌握“二分答案”的思路。比如给定一个最大值阈值，判断能否在某个限制条件下完成任务，这类题往往是二分套贪心或二分套动态规划。

举个例子：有一段长度为 n 的绳子数组，要切成至少 k 段长度相同的小段，问每段最长能多长。这个问题看似复杂，实际用二分枚举最终长度即可。每次枚举一个长度 mid，统计能切出多少段，如果段数大于等于 k，就提高 mid，否则降低 mid。

二分答案的核心是“可行性判断函数”，这个函数闭着眼睛写也能保证二分一定能收敛。掌握这个思路之后，二分能解的题就从一个具体查找问题扩展成了一整个算法类别。

7. 调试排错与机试实战心得

7.1 我遇到过的编译错误与运行时错误

这套题模拟训练下来，除了算法本身，编译和运行阶段也踩了不少坑。这里整理一个速查表，给备战机试的同学做一个参考：

7.2 时间分配与心理建设

机试中很多人不是不会做，而是时间前松后紧。我在前面也提过，先把送分题拿下，再解决中等题，最后死磕难题。这里再补充一个细节：每做完一道题，花 10 秒钟造一个边界用例自测。比如 t89 的连续逗号，t91 的负数输入，t92 的目标值在数组两端，都能快速暴露隐藏 bug。

如果某道题卡了超过 20 分钟，果断跳过。机试的计分规则一般不按题目难度加权，而是按通过数据组打分。一道题你只过了一半数据，得一半分；但如果你把全部时间耗在这题上，后面三道容易题可能直接得零分。怎么算都不划算。

7.3 这套题在真实场景中的延伸价值

t88 到 t92 这五道题，表面是考试题，实际是 C++ 工程中最常用技能的浓缩。指针操作是掌握现代 C++ 的基础，字符串处理是日常开发的常态，排序是数据预处理的基石，质数判断和二分查找则代表了两类重要的算法思维——数学建模与空间收缩。

我把这套题刷下来的最大感触是：死记代码模板没有意义，必须理解每个循环变量的边界意义、每个优化步骤背后的复杂度变化。机试能拿多少分，基本就是你平时写代码时想得有多深的一个侧写。

如果你正在准备近期的机试，拿这套 t88-t92 做模拟练习是个不错的选择。做题时给自己掐表、把所有自测样例跑一遍、再对照我这篇文章里的优化点查漏补缺，坚持一段时间，上了考场心里会踏实很多。