GESP四级选择题前8题精解：指针、递归、STL与算法思维全拆解

GESP四级的选择题，前8题向来是“送分题”和“送命题”的分水岭。2025年3月这场考试，不少考生一出考场就对着答案复盘：指针偏移题错了、递归调用数错了层、二分查找的比较次数数错了……这8道题看似基础，实际上每一道都在考察你对C++底层机制和算法细节的熟悉程度，而不是背概念。这篇文章我结合考纲、考生回忆和常见错因，把2025年3月GESP四级第一部分选择题的第1到第8题完整拆一遍，每道题讲清楚“为什么选它”“陷阱在哪”“背后连着哪些考点”，最后再从这8题反推备考策略，帮你把四级选择题的分数稳稳攥在手里。

1. 先盘一盘：2025年3月GESP四级前8题到底在考什么

GESP四级是很多学生从“会写代码”走向“懂算法”的关键台阶，选择题前8题尤其有代表性。这8题覆盖的知识面非常集中：指针与数组、递归、STL容器、排序稳定性、二叉树遍历、二分查找、递推、时间复杂度。从命题角度看，它们不是零散地考知识点，而是成体系地考你“有没有真正理解C++的运行机制和算法的内在逻辑”。

1.1 前8题的价值：16分的基础盘，错一道都很亏

GESP四级考试选择题一共约25道，每题2分，前8题就占了16分。这16分属于“基础盘”，难度通常低于后面的程序填空和编程题，但这不代表容易拿分。我在实际帮学生复盘时发现，很多考生在这8题上的失分不是因为不会，而是因为“想当然”——指针偏移算错、递归展开漏了边界条件、二分查找比较次数数错，都是典型的“基础不牢”表现。这部分分值如果丢了，后边编程题压力会非常大，因为编程题往往只有部分样例分，选择题的确定性分数其实是你通过考试的底气。

1.2 从考纲看命题逻辑：基础题考的是“理解的深度”

GESP四级考纲里明确列出的核心考点包括：指针与引用、函数参数传递、结构体与自定义数据类型、链表、STL基础容器、二叉树与遍历、排序算法、二分查找、递推与简单动态规划、算法复杂度分析。前8题几乎就是把这些考点“打散”成小场景，再埋进干扰项里。比如指针题不会让你背诵“指针是什么”，而是直接给你一段代码，让你写出表达式的值；排序题不会问你“快速排序的步骤”，而是问“哪个排序是稳定的”。这说明命题人默认你已经掌握语法和基本概念，他们更关心你能不能在实际代码执行中得出正确结果。这也是为什么很多只会背概念的同学一到考场就吃亏。

2. 第1-4题精解：指针、递归、容器与排序，四级的前菜

这4道题集中考察C++最核心的语法机制和数据结构基础，也是整张试卷最容易“阴沟翻船”的部分。我把题目还原出来，逐项拆开讲。

2.1 第1题：指针偏移，别把a+2当成a[2]乘了

题目还原（考生回忆版）：

int a[5] = {1, 2, 3, 4, 5}; int *p = a + 2; // 执行后 *p 的值是？

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

正确答案：C（3）

这道题考察的是指针算术中最基础也最容易混淆的概念。数组名a在表达式中会退化为指向首元素的指针，即等价于&a[0]。那么a + 2的含义不是“首地址数值加2”，而是“指向从首元素开始向后偏移2个元素位置的指针”，也就是指向a[2]。所以*p取出的是元素3。

我在给学生讲这道题时，一定会强调一个关键区分：

这个表格看起来简单，实际用起来全是坑。&a虽然数值上和a相等，但类型完全不同，&a + 1会跳过整个数组（5个int），而a + 1只跳过一个int。许多考生就是在这种细节上翻车，不是不懂指针，而是没区分“地址的数值”和“指针的类型”。

注意：GESP四级特别喜欢考“sizeof(a)”与“sizeof(p)”的区别。sizeof(a)是5个int的大小（20字节），sizeof(p)是指针本身的大小（64位系统下8字节）。这道题如果换个问法，就是另一个陷阱点。

再补充一个常考延伸：如果p指向数组中间，那么p[-1]是合法的，等价于*(p - 1)，取到的是a[1]。很多初学者以为下标不能为负，实际上只要指针最终指向的对象仍在数组范围内，负下标语法上完全合法。这个点在四级考试中偶尔会以“判断对错”的形式出现。

2.2 第2题：递归调用，画出调用树就赢了

题目还原（考生回忆版）：

int f(int n) { if (n <= 1) return 1; return f(n - 1) + f(n - 2); } // 调用 f(5) 的返回值是？

A. 5 B. 6 C. 7 D. 8

正确答案：D（8）

这是一个典型的斐波那契式递归，只不过边界条件从n == 0 || n == 1改成了n <= 1都返回1。所以：

• f(0) = 1
• f(1) = 1
• f(2) = f(1) + f(0) = 1 + 1 = 2
• f(3) = f(2) + f(1) = 2 + 1 = 3
• f(4) = f(3) + f(2) = 3 + 2 = 5
• f(5) = f(4) + f(3) = 5 + 3 = 8

逐项代入就能得到8。这块的丢分点有两个：一是边界条件看漏了，把n <= 1当成n == 0，导致f(1)算错；二是递归展开后忘记合并重复子问题，直接从f(5)往下掰，掰到一半自己就乱了。

我在实际教学中发现，递归题最稳的做法是“从底往上递推”，而不是“从顶往下展开”。因为自顶向下展开时，你很容易重复计算相同子树，比如f(3)会被展开两次。虽然手算时重复展开不影响结果，但容易数错层数。自底向上按顺序算出f(0)、f(1)、f(2)……每一步都有前一步支撑，逻辑清晰，不容易出错。

实操心得：遇到递归题，先找“最小的那个参数值对应的返回值”，再逐步往上加。这其实就是动态规划里“边界+转移”的思想，四级考递归，本质也是在为后面的动态规划做铺垫。

延伸一下：这个递归的时间复杂度是O(2^n)，因为每次调用会分裂成两个子调用。如果你在代码里f(40)都要跑半天，那就是典型的指数爆炸。优化方案是记忆化：开一个数组存算过的值，递归前先查表。GESP四级虽然不直接考记忆化代码，但选择题经常用递归复杂度做文章。

2.3 第3题：vector与list，谁在中间插入更慢

题目还原（考生回忆版）：

关于STL中的vector，下列说法错误的是：

A.push_back()在尾部添加元素的均摊时间复杂度是O(1)
B.vector支持通过下标随机访问，时间复杂度是O(1)
C. 在vector中间位置插入一个元素是非常高效的
D.vector的容量不足时会自动扩容，扩容通常涉及重新分配内存和拷贝元素

正确答案：C

vector的本质是“动态连续数组”。因为元素在内存中连续存储，所以它天然支持下标随机访问，v[i]的时间复杂度是O(1)，这也是vector最大的优势。但连续存储也意味着，如果你在中间插入元素，需要把插入位置后面的所有元素逐个往后搬移，腾出一个空位，这个操作的时间复杂度是O(n)。元素越多，插入越慢，所以C说“非常高效”明显错误。

A选项的“均摊O(1)”值得单独解释一下。vector扩容策略通常是成倍增长（如容量1变2、2变4、4变8），每次扩容需要把旧数据拷贝到新内存。虽然某一次push_back可能触发昂贵的扩容，但把多次push_back的总代价摊到每一次操作上，平均确实是常数级别，也就是“均摊O(1)”。这股“均摊”概念在四级里越来越常考，需要理解而不是死记。

跟vector对比的是list（双向链表）。list的每个节点在内存中分散存储，中间插入只需要修改前后节点的指针，时间复杂度O(1)，但它不支持下标随机访问，你必须从头遍历才能找到第k个元素。所以在需要频繁中间插入的场景用list，在需要随机访问的场景用vector。这道题表面上考“vector哪个说法错”，实际是在考察你有没有理解两种容器的底层结构差异。

注意：vector的insert操作不仅会搬移元素，还可能导致迭代器失效。因为扩容后内存地址变了，原来保存的迭代器、指针、引用统统作废。这是四级选择题很喜欢用来做干扰项的“隐藏考点”，看到选项里说“迭代器依然有效”之类的表述，基本可以直接排除。

顺带说一句，很多同学问“那deque呢？”。deque是双端队列，支持头尾快速插入，也支持下标访问，但它的下标访问不如vector快，底层是分段连续存储。四级一般不会考得这么细，但如果你把这三个容器对比着学，选择题抽象度立刻上一个台阶。

2.4 第4题：排序稳定性，冒泡永远的神

题目还原（考生回忆版）：

下列排序算法中，稳定的是：

A. 快速排序 B. 堆排序 C. 冒泡排序 D. 选择排序

正确答案：C（冒泡排序）

排序的“稳定性”指的是：如果两个元素的关键字相等，排序后它们的相对先后顺序保持不变。冒泡排序只有相邻元素逆序时才交换，相等元素永远不会交换位置，所以它稳定。快速排序和堆排序因为存在跨越较远距离的交换，很容易打破相等元素的原始顺序。选择排序看似温和，实则不稳定——它在每一轮选出最小值时，可能会把后面的相等元素交换到前面来。

举一个具体的反例：数组[5a, 5b, 3]，其中5a和5b都等于5，但5a原本在5b前面。选择排序第一轮会找到最小值3，把3与第一个位置的5a交换，得到[3, 5b, 5a]，此时5a跑到了5b后面，相对顺序变了，所以不稳定。

这个表建议背熟。考试里最常出现的组合是“快排不稳定 + 归并稳定 + 冒泡/插入稳定 + 选择不稳定”，记住中间那组对比基本就能应对。

为什么实际开发中会关心稳定性？举个例子：先按总分给学生排序，再按班级排序。如果排序算法不稳定，同一个班级里的学生总分顺序就可能被打乱；如果稳定，第二次排序后班级内部依然保持总分从高到低。这种场景在真实业务里很常见，四级考排序稳定性，不只是考概念，也是在考你有没有工程思维。

实操心得：快速排序的“不稳定”不是它的bug，而是partition过程中普遍存在的跨越交换导致的。学习排序时，建议把每个排序算法的代码亲自跑一遍，打印每一轮交换后的数组，亲眼看看相等元素的相对位置如何变化。光看教科书上的结论，转头就忘。

3. 第5-8题精解：从遍历到复杂度，算法思维的主战场

如果说前4题是在考“C++语言本身”，后4题就开始进入“算法思维”的领域了。这部分题目需要你不仅会写代码，还能在脑子里“运行”算法过程。

3.1 第5题：二叉树遍历，给前中求后

题目还原（考生回忆版）：

一棵二叉树的前序遍历结果为ABDCE，中序遍历结果为DBAEC，则它的后序遍历结果是：

A.DEBCAB.DBEACC.DBECAD.DECBA

正确答案：A（DEBCA）

这道题的核心是掌握“前序找根、中序分左右”的还原方法。

前序遍历的顺序是“根、左子树、右子树”，所以前序序列的第一个字符就是整棵树的根，这里根是A。在中序序列DBAEC中找到A，A左边是DB，这就是左子树的中序序列；A右边是EC，这是右子树的中序序列。

接着看左子树。前序序列中，根A后面的BD对应左子树的前序序列（因为左子树先遍历）。左子树中序是DB，前序是BD。前序BD的第一个字符B是左子树的根，而中序DB中B在D的右侧，说明D是B的左孩子（注意：中序顺序是左、根、右，DB说明D在B左边，所以D是B的左子树）。

右子树同理。前序中CE对应右子树，根是C，中序EC中E在C左侧，所以E是C的左孩子。

还原出来的树结构是：

A / \ B C / / D E

后序遍历顺序是“左、右、根”，对每棵子树递归处理：左子树D-B的后序是DB，右子树E-C的后序是EC，最后根A。拼起来就是DEBCA。

注意：如果题目改成“已知前序和后序，能否唯一确定二叉树？”，答案是否定的。当某个节点只有左子树或只有右子树时，前序和后序无法区分它是左孩子还是右孩子。GESP四级偶尔会用判断题形式来考这个点，需要特别留意。

这道题还有一个高频变体：已知中序和后序求前序，方法类似，只是根从后序序列末尾找。考生如果只背“前中求后”的口诀而不理解递归划分过程，遇到变体就容易卡壳。我的建议是把这个过程画成一棵递归树，每层标注“当前子树的根是谁、左子树有哪些节点、右子树有哪些节点”，比空想靠谱得多。

3.2 第6题：二分查找，比较次数怎么数

题目还原（考生回忆版）：

在有序数组{1, 3, 5, 7, 9, 11, 13}中，使用二分查找查找元素9，需要与数组元素比较的次数是：

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

正确答案：C（3次）

数组长度为7，初始查找区间是整个数组，left = 0, right = 6。

• 第1次：mid = (0 + 6) / 2 = 3，对应元素7。9 > 7，所以目标在右半区间，更新left = 4。
• 第2次：区间变成[4, 6]，mid = (4 + 6) / 2 = 5，对应元素11。9 < 11，所以目标在左半区间，更新right = 4。
• 第3次：区间变成[4, 4]，mid = 4，对应元素9，查找成功。

总共比较3次。

这道题的失分点主要在两个地方。一是把“mid的计算过程”也当成一次比较，比如有人会认为第1次“算出mid=3”也算一次，导致多算；实际上考试里说的比较次数通常指“与数组元素比较”，不包括mid下标计算。二是边界条件搞混，比如用left < right还是left <= right，会影响最后一步是否还需要额外比较。

从复杂度角度看，二分查找每轮把区间缩小一半，所以对于长度为n的数组，最多需要log2(n) + 1次比较（向上取整）。7个元素，log2(7)约等于2.8，取整加1就是3次。这个“对数级”的特性也是后面第8题的重要铺垫。

实操心得：二分查找的边界处理是公认的易错点。你可以记住一个固定写法：while (left <= right)，left = mid + 1，right = mid - 1。这套搭配下，循环结束后left是第一个大于等于目标的插入点，非常规整。但如果你用left < right，则要注意初始区间和更新规则的区别，别两套混用。

3.3 第7题：爬楼梯，递推就是动态规划的雏形

题目还原（考生回忆版）：

有一段10级的楼梯，每次只能向上走1级或2级，那么走完这10级楼梯共有多少种不同的走法？

A. 55 B. 89 C. 144 D. 233

正确答案：B（89）

设f(n)表示爬到第n级楼梯的走法数。要到达第n级，最后一步可能来自第n-1级（走1级），也可能来自第n-2级（走2级），所以：

f(n) = f(n-1) + f(n-2)

边界条件是f(1) = 1（只能走1步），f(2) = 2（1+1或直接2步）。逐项递推：

• f(1) = 1
• f(2) = 2
• f(3) = f(2) + f(1) = 2 + 1 = 3
• f(4) = f(3) + f(2) = 3 + 2 = 5
• f(5) = f(4) + f(3) = 5 + 3 = 8
• f(6) = 8 + 5 = 13
• f(7) = 13 + 8 = 21
• f(8) = 21 + 13 = 34
• f(9) = 34 + 21 = 55
• f(10) = 55 + 34 = 89

所以答案是89。

这道题背后就是动态规划的雏形。你其实已经用上了动态规划的三要素：状态（f(n)）、转移方程（f(n) = f(n-1) + f(n-2)）、边界条件（f(1)、f(2)）。GESP四级对动态规划的要求就是“简单递推”，而爬楼梯是其中最经典的模型，几乎每年都以不同形式出现，比如换成一维数组路径计数或者数字三角形。

提示：注意如果边界定义为f(0) = 1, f(1) = 1，那么f(2) = 2依然成立，结果一致。考试中不要看到边界条件跟教材不一样就慌，先算前几项验证规律。

这道题的干扰项设置也很有意思：选项里有55（f(9)），有144（f(11)），有233（f(12)）。如果你递推过程数错一位，很可能正好选中干扰项。这也提醒我们，遇到递推数列题目，算完之后可以做个快速检查：f(10)是89，f(9)是55，两者比值已经接近黄金比例1.618，这是斐波那契数列的天然特征，看到选项里有没有“相邻项”关系可以反推验证。

3.4 第8题：时间复杂度，O(log n)长什么样

题目还原（考生回忆版）：

下列算法中，时间复杂度为O(log n)的是：

A. 冒泡排序 B. 二分查找 C. 遍历数组 D. 选择排序

正确答案：B（二分查找）

时间复杂度描述的是算法运行时间随输入规模n增长的趋势。二分查找每轮把查找区间缩小一半，所以执行轮数约等于log2(n)，时间复杂度是O(log n)。数组遍历需要对每个元素访问一次，O(n)；冒泡排序和选择排序都需要双重循环，O(n^2)。

这道题本身不难，但它背后的“复杂度体系”很值得展开。四级选择题经常让考生比较常见复杂度的大小关系：

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

一个直观的类比是：O(1)就是“翻门牌”——看一眼就知道；O(log n)就像“对半查找一本字典”——每次翻一半；O(n)是“从头扫到尾”；O(n log n)是“先分再合地整理”；O(n^2)是“两两比较”；O(2^n)是“列举所有子集”，稍微大点的输入就爆炸。

了解这个体系后，你看到算法的第一反应应该是“它属于哪一档”，而不是死记每个算法的具体复杂度。比如快速幂算法，因为每轮把指数减半，所以是O(log n)；单调栈算法，虽然外层循环套while，但每个元素最多入栈出栈一次，所以整体是O(n)。这些进阶算法虽然GESP四级不直接要求，但七级八级会大量出现，从四级开始建立复杂度直觉，后面会轻松很多。

注意：严格来说，二分查找需要数组有序，所以“二分查找本身O(log n)”的前提是“数据已排序”。考试中选项往往默认排序已完成，不用纠结。

4. 从这8题反推四级备考重点与答题节奏

做完这8道题，你会发现它们不是孤立的。每一道题背后都连着一条知识树，而这条知识树就是四级备考的主干。

4.1 四个必须拿分的知识模块

第一个模块是指针与内存模型。第1题只是热身，真正危险的变形题是“指针与二维数组”“指针数组与数组指针”“函数参数传递中的值传递、指针传递、引用传递”。我建议你至少花一周时间专门攻克指针，把int*、int**、int(*)[n]、int*[n]这几种声明全部写一遍、跑一遍。

第二个模块是递归与递推。第2题和第7题都归入这一类。递归的关键是“信任函数已经算好了子问题”，递推的关键是“找到状态转移关系”。你要能熟练写出斐波那契、汉诺塔、全排列、子集枚举这类代码，并且能手算小规模输入的结果。

第三个模块是STL与数据结构。第3题考vector，但list、stack、queue、map、set都是四级选择题的常客。你要清楚每个容器的底层结构、查找/插入/删除的时间复杂度、迭代器失效的条件。最强的方法是列一张对比表，把容器名称、底层结构、随机访问、头尾插入、中间插入、何时失效全部写上去，每天过一遍。

第四个模块是排序与查找算法。第4题和第6题只是抽样，实际上冒泡、选择、插入、归并、快排、堆排的原理、稳定性、时间复杂度，以及二分查找的边界写法，都是必考内容。建议把每个排序算法用代码实现一遍，再口头讲一遍“为什么这个算法是稳定的/不稳定的”，能讲清楚才算真会。

4.2 选择题的答题节奏：先秒杀基础，再死磕计算

GESP四级考试的时间比较紧张，尤其是后面还有编程题。我给学生的建议是：选择题部分不要恋战，25道题控制在合理时间内完成。遇到一眼能看出的题直接选，遇到需要手算的题（比如第2题的递归、第7题的递推）就在草稿纸上按“列步骤”的方式快速算，遇到完全没思路的先标记跳过，等编程题做完再回头想。

手算递归和递推时，强烈建议用“表格法”而不是“展开树法”。比如第7题，直接画一行表格，写上n=1到10，下面依次填走法数，一眼就能看到89。这样既快又不容易漏项。

注意：GESP四级的编程题往往难度更高，如果你在选择题上耗时太久，编程题很容易时间不够。选择题的目标是“60分钟内稳定拿基础分”，而不是每道题都钻研透彻。

5. 考场实战经验与常见错误复盘

作为一个带过不少四级考生的“过来人”，我想把这些年大家在选择题上踩过的坑集中整理一下，每条都对应真实的丢分案例。

5.1 基础概念题的三大高频坑

第一个坑是指针相关概念混用。不少考生把“取地址运算符&”和“引用&”搞混，看到int &r = a;就以为r是a的地址。还有考生把p++和(*p)++混为一谈，前者是指针偏移，后者才是值自增。建议在考前一天把指针的常用写法全部抄一遍，光看不动手特别容易在考场上犯迷糊。

第二个坑是递归边界条件漏看。第2题的n <= 1返回1，如果把条件看成n == 1，那f(0)就没定义，整个数列就乱了。考试时把函数签名和边界条件用笔圈出来，逐字阅读，不要凭“这个题我见过”的印象答题。

第三个坑是STL复杂度记反。vector随机访问O(1)，list随机访问O(n)，list中间插入O(1)，vector中间插入O(n)。这些结论一定要建立在“连续内存”和“节点分散”这两个底层原因之上，而不是孤立背诵。我见过太多考生把list的查找复杂度写成O(1)，就是因为没理解“链表只能从头遍历”。

5.2 快速验证答案的三种方法

选择题不像编程题能当场跑代码，但你可以在草稿纸上做“逻辑验证”。

第一种是代入验证法。把选项值代回原条件，看是否满足。比如第2题，你可以从f(0)开始逐项算到f(5)，每算一项就标记一次，发现规律不对立刻停下重新检查边界条件。

第二种是极端值法。用n=0、n=1这种最小输入去验证你对边界条件的理解。比如第7题，先算f(1)=1、f(2)=2，如果这两个数跟你用递推公式推出来的不一致，说明要么公式记错，要么边界理解偏了。

第三种是排除法结合复杂度量级。比如第8题，看到“O(log n)”你马上应该联想到“每次规模减半”的操作，而四个选项中只有二分查找符合这个特征。其他选项的复杂度要么O(n)要么O(n^2)，一眼排除。

5.3 平时怎么练选择题：把每道题变成一个小程序

这也是我最想强调的一点：选择题的复盘方式，不是“看一遍解析”，而是“把题目改成代码跑一遍”。比如第2题的递归，你可以在自己的编译环境里跑一下，输出f(5)看是不是8；第3题的vector，你可以写一段代码在中间插入元素，尝试访问迭代器，亲眼看到它失效；第5题的二叉树，你可以手动建树，再写三种遍历函数打印结果。你在电脑上亲手验证过的东西，考场上才会真正相信。

我个人的习惯是每做完一套真题，就把所有错题对应的知识点整理成一张“概念卡”。卡片一面写概念，一面写一个手写代码片段。考前复习只看卡片，不翻厚书。这样既高效又能快速定位自己的薄弱点。

最后再分享一个小技巧：GESP四级的选择题虽然基础，但错误选项往往设计得非常“聪明”。如果你对某个选项犹豫不决，不妨问问自己“出题人为什么写这个选项”——它一定对应一个常见的认知偏差。当你意识到这一点，你其实已经在用出题者的视角审视题目，正确率自然会上去。

如果你这次考试时间还充裕，建议把第7题爬楼梯和第2题斐波那契放在一起对比学习，你能看到“递推”和“递归”原来是一体两面。这不仅是四级考点，更是后续学习动态规划的第一块基石。祝各位这次四级一次通过。