GESP2026年6月认证C++八级( 第一部分选择题（8-15））精讲

第8题 判断点是否在圆内答案A1、题目判断点是否在圆心为原点半径为5的圆内包括圆上。2、第一方法求距离然后判断sqrt(x*xy*y)53、第二方法两边同时平方。1原来2平方以后3因此直接写x*xy*y25答案就是A4、为什么程序员喜欢这样写1因为开平方sqrt(...)属于浮点运算。2而x*xy*y全部整数运算更快更准确不会有误差比赛可以这么写。第9题 最小生成树MST答案D101、这一题考的是Kruskal算法2、什么叫最小生成树假设有很多城市。修路要求所有城市都能互相到达总花费最小这就是最小生成树Minimum Spanning Tree3、Kruskal口诀只有四步① 所有边按权值排序↓② 从最小开始选↓③ 不形成环↓④ 一直选到n-1条边结束。4、这道题按照边权从小到大加入遇到形成环的边跳过最终得到总代价10所以答案D5、Kruskal模板先写sort(edge.begin(),edge.end());然后并查集判断是否连通。这这是Kruskal模板。第10题 Dijkstra最短路答案A1、本题考察Dijkstra算法2、很多同学容易和BFS混。区别非常简单算法适用情况BFS边权全部相同Dijkstra边权不同且非负3、Dijkstra思想1可以把它理解成石头掉进水里。2起点距离03最短距离一点点向外扩散。每一步选择当前距离最小那个点。更新邻居。不断重复。4最后到4号点距离最短。答案A4、Dijkstra三件事① priority_queue② dist[]③ vis[]这是考试的重要模板之一。第11题 时间复杂度1、程序for(i1;in;i) { for(j1;j*jn;j) { ... } }答案C2、为什么1第一层n2第二层注意不是jn而是j*jn所以j√n3因此第二层循环执行次。4总代价即3、所以答案C4、考试技巧1看到i*in2立即想到√n3以后约数质因数分解都会这样写。第12题 二分答案答案B1、题目说check(x)一次复杂度O(f(n))需要寻找最小答案。2、二分答案模板1不是二分数组。而是二分答案。2例如最长木棍最大最小值最小最大值都是。3每次mid调用一次check(mid)一共调用多少次3、答案范围l~m所以二分次数4、每次5、所以总代价答案B6、记忆口诀二分答案枚举答案× 检查可不可行√第13题 线性筛答案B1、有的同学不理解代码if(i%p0) break;为什么要break2、举个例子1假设i12质数2 3 5 ...先乘12×2得到24。2这时候因为2已经是最小质因子。3于是break;直接结束。3、需要保证每个合数只会被筛一次。这就是线性筛。4、所以答案B5、线性筛时间复杂度每个合数只会被筛一次。于是复杂度第14题 C继承答案C1、题目问关于继承正确的是2、我们逐个选项看。1A选项private成员子类不能直接访问。所以错误。2B选项private继承以后protected不会变成public。错误。3C选项创建对象一定先构造父类。再构造子类。例如class Animal↓class Dog:public Animal创建Dog先Animal()后Dog()这是正确。4D选项析构正好反过来。不是父↓子而是子↓父所以错误。3、记忆口诀构造父→子析构子→父考试特别喜欢考这类问题。第15题 栈的出栈序列答案D1、这是经典栈模拟2、入栈固定例如1 2 3 4 5依次进入。但是什么时候出栈可以自由决定。3、判断方法1最好的办法模拟。2准备stackint3边入栈。如果栈顶目标数字立即出栈。4最后全部成功。说明合法。否则非法。4、为什么D非法1模拟以后3出栈后栈顶是2不是12因此无法完成。3所以D5、八级重点模板1判断栈序列是否合法for(每个入栈元素) { 入栈; while(栈顶目标) { 出栈; } }2最后栈空就是合法。否则非法。这是所有栈序列问题的标准模板。第一部分8~15题知识总结题号考点必须掌握的知识8圆内点判断比较平方避免sqrt()9最小生成树Kruskal 并查集10最短路径Dijkstra 优先队列11时间复杂度j*jn推出O(n√n)12二分答案check()单调性 O(f(n)logn)13线性筛每个合数仅由最小质因子筛去一次14C继承构造父→子析构子→父15栈入栈固定、模拟判断出栈序列这8道题覆盖了八级算法竞赛中的核心基础图论最小生成树、最短路、复杂度分析、二分答案、线性筛、面向对象和数据结构栈。其中第9、10、12、13、15题尤其重要它们不仅是选择题高频考点也是编程题中经常直接应用的算法模板。