附上汇总帖GESP认证C编程真题解析 | 汇总单选题第1题一间的机房要安排6名同学进行上机考试座位共2行3列。考虑到在座位上很容易看到同一行的左右两侧的 屏幕安排中间一列的同学做A卷左右两列的同学做B卷。请问共有多少种排座位的方案 。A. 720B. 90C. 48D. 15【答案】A【解析】6个同学是不同的个体因此将他们以全排列的方式分配到6个座位上即可。即6! 6 * 5 * 4 * 3 * 2 * 1 720。第2题又到了毕业季学长学姐们都在开心地拍毕业照。现在有3位学长、3位学姐希望排成一排拍照要求男生不 相邻、女生不相邻。请问共有多少种拍照方案 。A. 720B. 72C. 36D. 2【答案】B【解析】男女交替排列有两种情况①男女男…②女男女…。对于任何一种情况男女3人内部可以进行全排列即3! 3 * 2 * 1 6种方式。那么对于其中一种情况有6 * 6 36种方法两种情况的方法总数就是2 * 36 72种。第3题下列关于C类和对象的说法错误的是 。A.通过语句 const int x 5; 定义了一个对象 x 。B.通过语句 std::string t “12345”; 定义了一个对象 t 。C.通过语句 void (*fp)() NULL; 定义了一个对象 fp 。D.通过语句 class MyClass; 定义了一个类 MyClass 。【答案】D【解析】混淆了声明和定义class MyClass只是声明了一个类而非定义了一个类。第4题关于生成树的说法错误的是 。A. 一个无向连通图一定有生成树。B. n 个顶点的无向图其生成树要么不存在要么一定包含 n-1 条边。C. n 个顶点、n-1 条边的无向图不可能有多颗生成树。D. n 个顶点、n-1 条边的无向图它本身就是自己的生成树。【答案】D【解析】一个无向图拥有生成树的一个必要条件是连通D选项并没有说明图是连通的因此不一定存在生成树。第5题一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下两个孩子时实现儿女双全的概 率是多少 。A.2 3 \frac{2}{3}32B.1 3 \frac{1}{3}31C.1 2 \frac{1}{2}21D.1 4 \frac{1}{4}41【答案】C【解析】共有4种情况①男女②女男③男男④女女。其中儿女双全的情况占一半因此答案是1/2。第6题已定义变量 double a, b; 下列哪个表达式可以用来判断一元二次方程x 2 a x b 0 x^2axb0x2axb0是否有实根 。A. 4 * b - a * a 0B. 4 * b a * aC. a * a - 4 * bD. b * 4 - a * a【答案】B【解析】方程的判别式为 △ a * a - 4b当它0时说明有实根。第7题n 个结点的二叉树执行广度优先搜索的平均时间复杂度是 。A.O ( l o g n ) O(log n)O(logn)B.O ( n l o g n ) O(nlogn)O(nlogn)C.O ( n ) O(n)O(n)D.O ( 2 n ) O(2^n)O(2n)【答案】C【解析】广度优先搜索会将二叉树的n个结点恰好遍历一次因此时间复杂度是O ( n ) O(n)O(n)。第8题以下关于动态规划的说法中错误的是 。A. 动态规划方法通常能够列出递推公式。B. 动态规划方法的时间复杂度通常为状态的个数。C. 动态规划方法有递推和递归两种实现形式。D. 对很多问题递推实现和递归实现动态规划方法的时间复杂度相当。【答案】B【解析】动态规划的时间复杂度通常由状态数量和每个状态的转移复杂度共同决定。例如O ( n 2 ) O(n^2)O(n2)时间复杂度做法的最长上升子序列状态数只有O ( n ) O(n)O(n)种。第9题下面的 sum_digit 函数试图求出从 1 到 n 包含 1 和 n 的数中包含数字 d 的个数。该函数的时间复杂度为 。#includestringintcount_digit(intn,chard){intcnt0;std::string sstd::to_string(n);for(inti0;is.length();i)if(s[i]d)cnt;returncnt;}intsum_digit(intn,chard){intsum0;for(inti1;in;i)sumcount_digit(i,d);returnsum;}A.O ( n l o g n ) O(nlogn)O(nlogn)B.O ( n ) O(n)O(n)C.O ( l o g n ) O(logn)O(logn)D.O ( n 2 ) O(n^2)O(n2)【答案】A【解析】count_digit(函数中将整数n转换为字符串并枚举每一位时间复杂度与n的位数有关是O(logn)。sum_digit(函数中枚举1~n的每个数字去调用count_digit(函数因此时间复杂度是O(log(1)log(2)…log(n))O(log(n!))近似于 O(nlogn)。第10题下面程序的输出为 。#includeiostreamconstintN10;intch[N][N][N];intmain(){for(intx0;xN;x)for(inty0;yN;y)for(intz0;zN;z)if(x0y0z0)ch[x][y][z]1;else{if(x0)ch[x][y][z]ch[x-1][y][z];if(y0)ch[x][y][z]ch[x][y-1][z];if(z0)ch[x][y][z]ch[x][y][z-1];}std::coutch[1][2][3]std::endl;return0;}A. 60B. 20C. 15D. 10【答案】A【解析】递推式ch[x][y][z]ch[x-1][y][z]ch[x][y-1][z]ch[x][y][z-1]本质上是在计算从坐标000到达坐标xyz有多少种不同的方式。到达123一共需要6次移动分别需要在xyz的方向上走123步移动方式有C(6,1) * C(5,2) * C(3,3)6 * 10 * 1 种方式。其中C(5,2表示从5个里面选出2个的组合数。第11题下面 count_triple 函数的时间复杂度为 。intgcd(inta,intb){if(a0)returnb;returngcd(b%a,a);}intcount_triple(intn){intcnt0;for(intv1;v*v*4n;v)for(intuv1;u*(uv)*2n;u2)if(gcd(u,v)1){intau*u-v*v;intbu*v*2;intcu*uv*v;cntn/(abc);}returncnt;}A.O ( n ) O(n)O(n)B.O ( n 2 ) O(n^2)O(n2)C.O ( n l o g n ) O(nlogn)O(nlogn)D.O ( n 2 l o g n ) O(n^2logn)O(n2logn)【答案】C【解析】第1层循环v的增量是常数且vvn保证了循环次数是O(sqrt(n))第2层循环u与v同数量级增量也是常数u(uv)n的条件也保证了循环次数是 O(sqrt(n))。循环内部每次调用复杂度为 O(logn的最大公约数函数因此总时间复杂度为 O(sqrt(n) * sqrt(n) * logn)O(nlogn)。第12题下面 quick_sort 函数试图实现快速排序算法两处横线处分别应该填入的是 。voidswap(inta,intb){inttempa;ab;btemp;}intpartition(inta[],intl,intr){intpivota[l],il1,jr;while(ij){while(ija[j]pivot)j--;while(ija[i]pivot)i;if(ij)swap(a[i],a[j]);}________;// 在此处填入选项return________;// 在此处填入选项}voidquick_sort(inta[],intl,intr){if(lr){intpivotpartition(a,l,r);quick_sort(a,l,pivot-1);quick_sort(a,pivot1,r);}}A.swap(a[l],a[i])iB.swap(a[l],a[j])iC.swap(a[l],a[i])jD.swap(a[l],a[j])j【答案】D【解析】考察快速排序中的划分区间时的细节。可以发现区间[l, r]会递归到[l, pivot-1]和[pivot1, r]而在 partition 函数中通过 while(ij我们可以知道循环结束后必然存在 ij。考虑最坏情况 jr 自始至终没有变化过那么最终 i r 1如果我们返回 i那么区间 [l, r] 会递归到 [1, (r1)-1]造成无限递归因此排除AB选项。接下来考虑CD该如何选择可以发现 partition 函数最终返回的应当是基准值的下标如果要返回 j那么就需要将基准值 a[l] 与a[j]交换因此选D。第13题下面 LIS 函数试图求出最长上升子序列的长度横线处应该填入的是 。intmax(inta,intb){return(ab)?a:b;}intLIS(vectorintnums){intnnums.size();if(n0)return0;vectorintdp(n,1);intmaxLen1;for(inti1;in;i){for(intj0;ji;j)if(nums[j]nums[i])________;// 在此处填入选项maxLenmax(maxLen,dp[i]);}returnmaxLen;}A. dp[j] max(dp[j] 1, dp[i])B. dp[j] max(dp[j], dp[i] 1)C. dp[i] max(dp[i] 1, dp[j])D. dp[i] max(dp[i], dp[j] 1)【答案】D【解析】dp[i]表示以位置i结尾的最长上升子序列长度枚举上一个结尾位置是j那么转移方程就是 dp[i]max(dp[i], dp[j]1)。第14题下面 LIS 函数试图求出最长上升子序列的长度其时间复杂度为 。#defineINT_MIN(-1000)intLIS(vectorintnums){intnnums.size();vectorinttail;tail.push_back(INT_MIN);for(inti0;in;i){intxnums[i],l0,rtail.size();while(lr){intmid(lr)/2;if(tail[mid]x)lmid1;elsermid;}if(rtail.size())tail.push_back(x);elsetail[r]x;}returntail.size()-1;}A.O ( l o g n ) O(logn)O(logn)B.O ( n ) O(n)O(n)C.O ( n l o g n ) O(nlogn)O(nlogn)D.O ( n 2 ) O(n^2)O(n2)【答案】C【解析】循环执行了n次每次都进行了时间复杂度为 O(logn的二分因此总的时间复杂度为O(nlogn)。第15题下面的程序使用邻接矩阵表达的带权无向图则从顶点0到顶点3的最短距离为 。intweight[4][4]{{0,5,8,10},{5,0,1,7},{8,1,0,3},{10,7,3,0}};A. 9B. 10C. 11D. 12【答案】A【解析】计算从起点 0 到终点 3 的最短路可以使用 dijkstra 或者是 floyd 算法。但由于起点和终点已经确定因此中间经过的点数至多只有 2 个完全可以直接暴力搜索去枚举所有情况去计算答案。一共只有以下 5 种情况0-3距离为100-1-3距离为57120-2-3距离为83110-1-2-3距离为51390-2-1-3距离为81716其中最短的距离为9。判断题第1题C语言中表达式 9 | 12 的结果类型为 int 、值为 13。A. 正确B. 错误【答案】A【解析】9的二进制为100112的二进制为1100进行按位或计算之后结果为1101值为13。第2题C语言中访问数据发生下标越界时总是会产生运行时错误从而使程序异常退出。A. 正确B. 错误【答案】B【解析】C标准明确指出数组下标越界是未定义行为而未定义行为≠运行时错误。编译器或系统可能不强制检查越界因此程序可能不会立即崩溃而是继续运行并产生错误结果。常见的未定义行为有数组边界外的内存访问、有符号整数溢出、空指针解引用、通过不同类型的指针访问对象等等。第3题对 n 个元素的数组进行归并排序最差情况的时间复杂度为O ( n l o g n ) O(nlogn)O(nlogn)。A. 正确B. 错误【答案】A【解析】归并排序每次将要排序的区间进行分半递归n个元素至多进行 logn 层分半每一层都会将n 个元素都遍历一次因此最坏时间复杂度为 O(nlogn)。第4题5个相同的红球和4个相同的蓝球排成一排要求每个蓝球的两侧都必须至少有一个红球则一共有15种排列 方案。A. 正确B. 错误【答案】B【解析】相当于蓝球不能出现3个连在一起的情况那么考虑将蓝球按个数进行分组有如下几种情况[1111][211][121][112][22]即3332组这几种情况。对于每一种情况要把所有组放入到5个红球形成的6个部分中(每部分可以为空)。可以得到有C(64)3 * C(63)C(62)种排列方式显然不等于15。第5题使用 math.h 或 cmath 头文件中的函数表达式 log(8的结果类型为 double 、值约为 3。A. 正确B. 错误【答案】B【解析】log函数是以e为底的计算的是一个数的自然对数。log(8的值为2.079而log2(8的值才约为3。第6题C是一种面向对象编程语言C则不是。继承是面向对象三大特性之一因此使用C语言无法实现继承。A. 正确B. 错误【答案】B【解析】c语言确实没有直接实现继承的语法但是可以通过结构体嵌套的方式来模拟继承的效果。第7题n 个顶点的无向完全图有n n − 2 n^{n-2}nn−2棵生成树。A. 正确B. 错误【答案】A【解析】根据Cayley(凯莱)公式可以知道n个点的生成树个数为n n − 2 n^{n-2}nn−2第8题已知三个 double 类型的变量 a 、 b 和 theta 分别表示一个三角形的两条边长及二者的夹角弧度则三角形的周长可以通过表达式 sqrt(a * a b * b - 2 * a * b * cos(theta)求得。A. 正确B. 错误【答案】B【解析】题目的式子是根据两边长以及夹角通过余弦定理来计算第三边c的长度而非三角形的周长。若要计算周长还需要加上a和b。第9题有 V 个顶点、E 条边的图的深度优先搜索遍历时间复杂度为O ( V E ) O(VE)O(VE)。A. 正确B. 错误【答案】A【解析】在深度优先遍历的过程中对于当前点u我们会枚举它的出边来到达它的相邻点那么最终每个点都会被遍历并且每条边都会被枚举到因此时间复杂度是 O(V E)即点数边数。第10题从32名学生中选出4人分别担任班长、副班长、学习委员和组织委员老师要求班级综合成绩排名最后的4 名学生不得参选班长或学习委员仍可以参选副班长和组织委员则共有 P(30,4种不同的选法。A. 正确B. 错误【答案】A【解析】先考虑从剩余的28人中选出班长和学习委员那么有28 * 27种选法。还剩下26人接下来要选副班长和组织委员。此时原本被排除的4人可以参与选举了因此有30人那么有30 * 29种方法选出副班长和组织委员。一共有30 * 29 * 29 * 27 种选择方式即P(304)。编程题