GESP第13次认证真题解析|C++八级真题回顾

一、单选题（共15题，每题2分，共30分）

A.112

B.168

C.224

D.288

【答案】D

【考纲知识点】排列组合

【解析】总选法数为从14人中选3人：C(14,3)=364

减去全男生和全女生的情况：C(8,3)+C(6,3)=56+20=76

所以一共是:364-76=288种

【第2题】在杨辉三角中，从第0行开始计数，第10行的所有数之和为（ ）。

A.512

B.1024

C.2048

D.4096

【答案】B

【考纲知识点】杨辉三角

【解析】杨辉三角第n行所有数之和为2ⁿ 。因此第10行的和为：2¹⁰=1024

【第3题】下列代码实现了快速幂算法，其时间复杂度为（ ）。

A. O(log b)

B. O(log e)

C. O(log mod)

D. O(e)

【答案】B

【考纲知识点】快速幂

【解析】快速幂每次循环都把指数e 右移一位，因此循环次数是O(log e)。

【第4题】从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（ ）种。

A.60

B.74

C.80

D.84

【答案】C

【考纲知识点】排列组合

【解析】总选法为：C(9,3)=84

去掉3本全是物理书的情况：C(4,3)=4

所以答案为：84-4=80

【第5题】在二叉搜索树（BST）中，若中序遍历的序列为{1,2,3,4,5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（ ）。

A.该树一定是一棵完全二叉树

B.元素4 和5 不可能是兄弟节点

C.元素1 所在节点的深度可能大于3（根节点深度为1）

D.元素2一定是元素1 的父节点

【答案】B

【考纲知识点】

【解析】先序遍历的开头为根，因此根是3，右子树只包含4和5。在BST里，右子树的中序必须还是4 ,5 。这两个点只能形成一条链：要么4 是5 的父亲，要么5 是4 的父亲，不可能分居某个父节点的左右孩子，因此不可能是兄弟节点。

【第6题】在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（ ）。

A. O(V²)

B. O(V • E)

C. O((V + E)log V)

D. O(V²log V)

【答案】C

【考纲知识点】最短路dijkstra

【解析】堆优化后,每个logv的复杂度得到某个点的最短路，配合邻接表，点和边都遍历一遍,总复杂度为O((V + E)log V)。

【第7题】对于含n 个顶点（n > 2）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（ ）条边。

A.n

B.n-1

C.n+1D.无法确定，取决于图的具体边数

【答案】B

【考纲知识点】最短路-负环

【解析】无负环时，最短路为简单路径，每个点最多经过一次，最短路最多为n-1条边

【第8题】在使用Floyd算法求任意两点间最短路径时，时间复杂度为O(V³)。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist 数组。如果此时继续对该dist 数组执行一次完整的Floyd算法过程（无任何提前终止），执行完毕后dist 数组内的值（ ）。

A.会发生改变，因为Floyd又做了一次松弛

B.不会发生改变

C.可能变大，因为未针对已有最短路优化

D.可能在某些负权图中陷入死循环

【答案】B

【考纲知识点】最短路

【解析】Floyd的每一步只是在尝dist[i][j] > dist[i][k] + dist[k][j],是否成立；现在dist[i][j]已经求得最短路，值已经固定，所以Floyd整轮跑完以后dist数组不变。

【第9题】关于图论中的最短路径算法，下列说法中严格正确的是（ ）。

A. Dijkstra 算法能够高效处理包含负权边的有向图。

B. Floyd 算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环）。

C.单源最短路径算法无法用于无向图，无向图只能通过BFS求解。

D. Dijkstra 算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。

【答案】B

【考纲知识点】

【解析】Floyd可以处理负权边，只要图里没有负权环，因此B正确。

A错在Dijkstra不能直接处理负权边；

C错在单源最短路当然也能做无向图；

DDijkstra每次取的是当前距离最近的未确定点。

【第10题】有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（ ）种。

A. 120

B. 144

C. 192

D. 240

【答案】C

【考纲知识点】排列组合

【解析】第一处：需要将基准值放到正确位置，即交换a[l]和a[j]（因为j是最后一个小于基准值的位置）,第二处：返回基准值的最终位置j。先把甲乙看成一个整体，并考虑内部顺序，共有2 种。这样一共变成5 个对象，排列数为：2 × 5! =240再减去丙站在排头的情况。此时剩下5人，其中甲乙仍要相邻，排法数为：2 × 4! =48

所以一共是:240 -48=192

【第11题】下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（ ）。

A. dist[i][k] + dist[k][j] < dist[i][j]

B. dist[i][k] != INF && dist[k][j] != INF

C. dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]

D. dist[i][j] == INF

【答案】C

【考纲知识点】最短路Floys

【解析】只有当两段路径都存在，并且经过k 后更短时，才应更新dist[i][j]。

【第12题】用数字0、1、2、3、4 组成无重复数字的五位偶数，共有（ ）个。

A.48   

B.60   

C.72     

D.96

【答案】B

【考纲知识点】排列组合

【解析】1.末位为0：前四位用 1,2,3,4 排列，共4! = 24 种。

2.末位为2或4：共2 种选择。首位不能为0，从剩余4个数字中选首位有3 种，其余3位全排列有3! = 6 种，共2 × 3 × 6 = 36 种。

总数为：24 + 36 =60

【第13题】在一个无向带权图中，若使用Prim算法从顶点0 开始构造最小生成树（边权均为正整数，且graph[u][v] == θ 表示无边），下列代码中横线处应填入（ ）。

A. graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]

B. !inMST[v] && graph[u][v] < minEdge[v]

C. graph[u][v] > θ  && !inMST[v]

D. !inMST[v] && minEdge[v] > θ 

【答案】A

【考纲知识点】最小生成树

【解析】因为θ表示无边，所以必须先保证graph[u][v] 非零；同时v 不能已在生成树中，而且新边权要更小。

【第14题】已知三个点A(x₁,y₁),B(x₂,y₂),C(x₃,y₃)  在平面直角坐标系中的坐标。下列C++表达式中，在精度误差范围 1e-8 内能正确计算判断这三个点是三点共线的表达式是（ ）。

A. (x2-x1)/(y2-y1) == (x3-x1)/(y3-y1)

B. (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) == θ 

C. fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)) < 1e-8

D. fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1)) < 1e-8

【答案】C

【考纲知识点】

【解析】三点共线可通过二维叉积为0判断。考虑浮点误差，应使用绝对值小于某个容许误差的形式。A、D可能出现除零问题。

【第15题】在64位操作系统下（LP64 / LLP64 模型），下面代码的输出结果是（ ）。

A. 16 8 8 8 1 1

B. 16 8 16 8 1 1

C. 16 8 8 4 4 1

D. 16 8 8 8 4 1

【答案】A

【考纲知识点】指针,sizeof

【解析】a 是4个int，总大小为16 字节；p 和q 都是指针，64位下大小都为8 字节；sizeof(p+1)、sizeof(q+1) 依旧是指针大小8。指针相减得到跨过的元素个数，因此 (p+1)-p = 1，(q+1)-q = 1。

二、判断题（共10题，每题2分，共20分）

【第1题】在C++中，若结构体中包含一个 static 成员变量，则该变量的存储空间属于结构体对象的一部分（ ）

【答案】×

【考纲知识点】结构体,静态变量

【解析】static 成员变量属于类或结构体本身，不属于某个对象实例的内部存储空间。

【第2题】对于任意正整数n，二项式(a + b)ⁿ展开式中各项的二项式系数之和等于2ⁿ（ ）

【答案】√

【考纲知识点】二项式

【解析】令 a = 1, b = 1，则展开式系数和就是(1+1)ⁿ= 2ⁿ。

【第3题】在C++中，若函数参数类型为const int &，则该参数既可以绑定左值，也可以绑定右值。（ ）

【答案】√

【考纲知识点】C++引用

【解析】常量左值引用既能绑定普通左值，也能绑定右值或临时对象。

【第4题】若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。（ ）

【答案】×

【考纲知识点】最小生成树

【解析】边权有重复时，最小生成树仍可能唯一。比如本就是有相同边权的无向联通树。

【第5题】使用快速排序对n个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为O(nlogn）。

【答案】×

【考纲知识点】排序【解析】快速排序的时间复杂度通常情况下是O(nlogn)，最差情况下会退化成O(n²)

【第6题】若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。（ ）

【答案】×

【考纲知识点】欧拉回路

【解析】欧拉回路图必须是连通的。仅度数全为偶数不能保证联通(比如单独的点)。

【第7题】使用倍增法预处理区间最值问题时，预处理的时间复杂度为O(nlog n)，查询的时间复杂度为O(1)。（ ）

【答案】√

【考纲知识点】ST倍增

【解析】这是稀疏表（ST表）处理RMQ的经典复杂度。

【第8题】如果将一个连通无向图G₁中所有边的权值都统一增加同一个正整数常数C，形成图G₂。则G₁的最小生成树中每条边在G₂中对应的边组成的树，一定是G₂的最小生成树。（ ）

【答案】√

【考纲知识点】最小生成树

【解析】任意生成树都恰有n-1条边，统一加常数后每棵生成树总权值都增加相同的(n-1)c，相对大小不变，因此最小生成树保持不变。

【第9题】在图论算法中，Kruskal算法和Prim算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。（ ）

【答案】√

【考纲知识点】最小生成树

【解析】最小生成树不唯一，不同算法可能求出不同的最小生成数，但它们的总边权和必定相同，否则与最小生成树定义中的“最小”相矛盾。

【第10题】在动态规划问题中，“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。（ ）

【答案】×

【考纲知识点】动态规划

【解析】它们常常对应同一组状态，但复杂度可能存在区别（实现细节、访问状态范围、常数因素等都可能不同），特别是当状态转移方程中涉及的正反操作（例如：求倍数vs求因子）的时间复杂度不同的情况，时间复杂度可能差别巨大。

三、编程题（每题25分，共50分）

3.1编程题1

• 试题名称：消息查找

• 时间限制：1.0 s

• 内存限制：512.0 MB

3.1.1题目描述

小A的消息记录中有n条消息，依次以1，2，...,n编号。编号小的消息发送时间早于编号大的消息。

一条消息可以引用一条编号小于它的消息，也可以不引用消息。小A注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是：

【消息1】小A：有人做了今天的第一题吗？

【消息2】小A：我第一题WA了，可能是什么原因？

【消息3：引用消息1】小B：我我我

【消息4：引用消息2】小C：我也WA了

【消息5：引用消息2】小B：是不是没开long long ？

【消息6：引用消息5】小A：改了就AC了，太厉害了！

对于消息i（1≤i≤n），小A以r_i标记消息i是否有引用，以及所引用的消息编号。如果r_i>0，则消息i为引用了消息r_i；如果r_i=0，则消息没有引用消息。

消息记录里有非常多条消息。为了快速查找所需要的消息，小A准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息i（1<i≤n），那么接下来可以选择以下两种操作之一：

定位到消息i-1；

如果消息i引用了消息r_i，定位到消息r_i。

以上操作可以执行任意次（包括零次）。

小A有q次询问。在第k(1≤k≤q)次询问中，小A给出消息编号x_k,y_k(y_k<x_k)。小A想知道，如果当前消息查找工具位于x_k，至少需要多少次操作才能定位到消息y_k。

3.1.2输入格式

第一行，两个正整数n,q，分别表示消息条数与询问次数。

第二行，n个非负整数r₁,r₂,...,r_n，表示消息的引用关系，具体含义见题目描述。

接下来q行中的第k行(1≤k≤q)包含两个正整数x_k,y_k，表示一次询问。

保证至多只有1000条引用消息。

3.1.3输出格式

输出共q行，第行包含一个整数，表示将界面从消息x_k切换到消息y_k所需的最少操作次数。

3.1.4样例

3.1.4.1输入样例1

3.1.4.2输出样例1

3.1.4.3输入样例2

3.1.4.4输出样例2

3.1.5数据范围

对于40%的测试点，保证1≤n≤2000，1≤q≤2000。

对于所有测试点，保证1≤n≤10⁵,1≤q≤10⁵,0≤r_i≤i,1≤y_k≤x_k≤n,保证至多有1000条引用消息。

【思路解析】普通消息其实没什么可研究的，因为它只能老老实实往前走一步。真正会改变最短路的，只有两类消息：自己引用了别人，或者被别人引用过。只有走到这些位置，路径才有机会“抄近道”。题目保证这样的消息总数不多，所以参考程序先把它们全挑出来，当成关键点。后面真正预处理的，不是全部n 条消息之间的关系，而是这些关键点之间的最短代价。设全部关键点按编号从小到大排成p1<p2<......<pc,程序里的p[i] 就是这里的pi 。接下来做一个预处理动态规划。它的目标是：对于每个起点关键点 pi，求出走到更早关键点pj  的最少操作数。把状态记为di,j，表示“当前从关键点pi 出发，走到关键点pj 的最少操作数”，其中1≤j≤i≤C 。程序里的d[i][j] 对应的就是这个量。初始状态很：di,i=0从pi到自己不需要操作。接下来按 j=i,i-1,......2倒着转移。倒着枚举的原因是：操作只会让消息编号变小，所以从较大的关键点向前推，后继状态一定已经算过。对于当前状态di,j，只有两种决策。第一种决策：不用引用，直接一步一步往前退，直到前一个关键点pj-1。这中间没有别的关键点，所以必须走pj-pj-1步，转移方程是di,j-1=min(di,j-1,di,j+di,j+pj-pj-1)第二种决策：如果消息pj 本身引用了更早的消息，也就是rpi>0，那么可以直接用一次引用操作跳到消息rpi 。由于被引用的消息也被算作关键点，设它在关键点序列中的下标是k ，即pk=rpj，那么转移方程是：di,k=min(di,k,di,j+di,j+1)这两类转移已经包含了所有可能操作，因为题目允许的动作只有“退到上一条消息”和“沿引用跳转”两种。于是，一轮预处理结束后，任意两个关键点之间的最少操作数就都求出来了。回答询问时，再把路径拆成三段看：1.先从x 一步一步退到左边最近的关键点pre[x]；2.在关键点之间按预处理结果走到y 右边最近的关键点 suf[y]；3.最后再一步一步退到y。如果记a=pre[x] , b=suf[y],那么只要中间确实存在关键点可用，也就是a≥b，答案就是(x-a)+dpos(a),pos(b)+(b-y)

这里pos(a)表示关键点a 在关键点序列里的下标，程序里用pos[a] 保存。

如果中间根本碰不到关键点，那就直接走x-y 步，连预处理结果都用不上。

设关键点个数是C，那么预处理规模主要是关键点之间的转移，复杂度大约是O(C2) ；每次询问只需要代公式，时间是O(1) 。这也是这题能在大数据范围下通过的原因。

【参考程序】

3.2编程题2

• 试题名称：子图最短路

• 时间限制：1.0 s

• 内存限制：512.0 MB

3.2.1题目描述

给定包含n个结点m 条边的带权无向图G，结点依次以1，2...，n编号。第i（1≤i≤m）条边连接编号为u_i与v_i 的两个结点，权值为w_i。

对于指定的1≤l≤r≤n，按以下方式构造图G 的子图G(l,r)：保留G 中编号在区间[l,r] 中的结点。删去其它编号不在[l,r] 中的结点以及与之相连的边。剩余的结点和边构成子图G(l,r)。

对于G(l,r) 中的任意结点u,v应有l≤u,v≤r 。记u,v 在子图G(l,r) 上的最短距离为d(l,r,u,v)。特殊地，若u,v 在子图G(l,r) 上不连通，则认为d(l,r,u,v)=0。

你需要求出：

对10⁹取模的结果。

题目中的英文字母l使用了特殊写法l，以避免英文字母l 与数字1 混淆。

3.2.2输入格式

第一行，两个正整数n, m，表示结点数与边数。

接下来m 行，第i（1≤i≤m）行包含三个正整数u_i ,v_i ,w_i，表示一条连接结点u_i ,v_i的权值为w_i的边。

3.2.3输出格式

输出一行，一个整数，表示对10⁹取模的结果。

3.2.4样例

3.2.4.1输入样例1

3.2.4.2输出样例1

3.4.2.3输入样例2

3.4.2.4输出样例2

3.2.5数据范围

对于40%的测试点，保证2≤n≤20。

对于所有测试点，保证2≤n≤100,2≤m≤,i≤u_i,v_i≤,1≤w_i≤10⁶。图中可能存在重边。

【思路解析】

直接对每个区间 [l,r] 单独跑一遍最短路，肯定太慢。参考程序的想法是：把区间一点一点往右扩，每次只新加入一个点 ，这样最短路可以接着上一次的结果继续更新。

先用f[i][j] 记录原图里的最短直接边。如果有重边，就保留较小的那条；没有边就记成一个很大的数。

然后固定左端点l。当r=l,l+1,l+2,...... 逐步往右扩时，新加入的只有结点r 。这时只要做一轮g[i][j]=min(g[i][j],g[i][r]+g[r][j])就等于在Floyd里把结点r 当成新的中转点放进来。于是，处理完当前 r 以后，g[i][j] 就已经是子图[l,r] 内的最短路。

这样每扩展一次右端点，都可以立刻把当前区间内所有点对的最短路加进答案，不必重新从头算一遍。整个算法是两层区间枚举，再套一层Floyd式更新，复杂度是O(n⁴) 。这里n≤100，所以能过。代码里把10⁹同时拿来做取模和“无穷大”占位，是因为题目数据保证真实最短路不会碰到这个值，不会和无边状态混淆。

【参考代码】

1. GESP微信：关注“CCF GESP”公众号，点击“GESP小助手”即可交流。

2. GESP邮箱：gesp@ccf.org.cn

注：请在邮件中详细描述咨询的问题并留下考生的联系方式及姓名、身份证件号，以便及时有效处理。

3. GESP电话：0512-67656856

咨询时间：周一至周五(法定节假日除外）: 上午 8:30-12:00；下午 13:00-17:30

扫描下方二维码关注GESP公众号，了解更多资讯