附上汇总帖历年CSP-J初赛真题解析 | 汇总单项选择第1题32位int类型的存储范围是 A.-2147483647 ~ 2147483647B.-2147483647 ~ 2147483648C.-2147483648 ~ 2147483647D.-2147483638 ~ 2147483648【答案】C【解析】int的范围为− 2 31 ∼ 2 31 − 1 -2^{31}\sim 2^{31}-1−231∼231−1即-2147483648 ~ 2147483647第2题计算( 14 8 − 1010 2 ) ∗ D 16 − 1101 2 (14_8-1010_2)*D_{16}-1101_2(148​−10102​)∗D16​−11012​的结果并选择答案的十进制值 A.13B.14C.15D.16【答案】A【解析】统一换算为10进制计算(12 - 10) * 13 - 13 13第3题某公司有 10 名员工分为 3 个部门A 部门有 4 名员工B 部门有 3 名员工、C 部门有3 名员工。现需要从这 10 名员工中选出 4 名组成一个工作组且每个部门至少要有 1 人。问有多少种选择方式 A.120B.126C.132D.238【答案】B【解析】A选2人BC各选1人C 4 2 ∗ C 3 1 ∗ C 3 1 54 C_4^2 * C_3^1 * C_3^1 54C42​∗C31​∗C31​54B选2人AC各选1人C 4 1 ∗ C 3 2 ∗ C 3 1 36 C_4^1 * C_3^2 * C_3^1 36C41​∗C32​∗C31​36C选2人AB各选1人C 4 1 ∗ C 3 1 ∗ C 3 2 36 C_4^1 * C_3^1 * C_3^2 36C41​∗C31​∗C32​36合计54 36 36 126第4题以下哪个序列对应数组 0 至 8 的 4 位二进制格雷码Gray code A.00000001001100100110011101011000B.00000001001100100110011101000101C.00000001001100100100010101110110D.00000001001100100110011101010100【答案】D【解析】格雷码Gray code是一个数列集合其中任意两个相邻的数值仅有一个二进制位不同。4位格雷码的生成过程从0000开始每次改变一个位使得新的数字与前一个数字只相差一位确保所有16个4位二进制数都被使用一次选项D正确地表示了0到7的4位格雷码序列。可以验证每对相邻的数只有一位不同。第5题记 1Kb 位 1024 字节byte1MB 位 1024KB那么 1MB 是多少二进制位bit? A.1000000B.1048576C.8000000D.8388608【答案】D【解析】1MB 1024 * 1024 * 8 8388608 bit第6题以下哪个不是 C中的基本数据类型 A. intB. floatC. structD. char【答案】C【解析】int, float, 和char都是C的基本数据类型struct是用户自定义的复合数据类型,不是基本数据类型第7题以下哪个不是 C中的循环语句 A. forB. whileC. do-whileD. repeat-untill【答案】D【解析】C中没有repeat-until是Pascal语言中的循环语句第8题在 C/C中(char)(‘a’13)与下面的哪一个值相等 A.‘m’B.‘n’C.‘z’D.‘3’【答案】B【解析】在’a’字符位置增加13对应’n’第9题假设有序表中有 1000 个元素则用二分法查找元素 x 最多需要比较 次A.25B.10C.7D.1【答案】B【解析】二分查找每次将搜索范围减半需要找到最小的n,使得2 n 1000 2^n 10002n1000n为10第10题下面哪一个不是操作系统名字 A.NotepadB.LinuxC.WindowsD.macOS【答案】A【解析】A是记事本其他都是操作系统第11题在无向图中所有顶点的度数之和等于 A. 图的边数B. 图的边数的两倍C. 图的定点数D. 图的定点数的两倍【答案】B【解析】每条边连接2个顶点即每条边对两个顶点的度数都贡献1。因此所有顶点的度数之和等于边数的两倍第12题已知二叉树的前序遍历为[A,B,D,E,C,F,G],中序遍历为[D,B,E,A,F,C,G],求二叉树的后序遍历的结果是 A.[D,E,B,F,G,C,A]B.[D,E,B,F,G,A,C]C.[D,B,E,F,G,C,A]D.[D,B,E,F,G,A,C]【答案】A【解析】根据前序遍历和中序遍历画出二叉树后序遍历结果为A第13题给定一个空栈支持入栈和出栈操作。若入栈操作的元素依次是 1 2 3 4 5 6,其中 1 最先入栈6 最后入栈下面哪种出栈顺序是不可能的 A.6 5 4 3 2 1B.1 6 5 4 3 2C.2 4 6 5 3 1D.1 3 5 2 4 6【答案】D【解析】D不可能因为2必须在1之后入栈所以2不可能在5之后出栈第14题有 5 个男生和 3 个女生站成一排规定 3 个女生必须相邻问有多少种不同的排列方式A.4320 种B.5040 种C.3600 种D.2880 种【答案】A【解析】将3个女生看作一个整体那么就变成了6个元素的排列6个元素的排列方式有6! 720种3个女生之间还可以互相调换位置,有3! 6种。所以总的排列方式 720 * 6 4320种第15题编译器的主要作用是什么 A.直接执行源代码B.将源代码转换为机器代码C.进行代码调试D.管理程序运行时的内存【答案】B【解析】编译器的主要作用是将高级编程语言编写的源代码转换为机器可以直接执行的机器代码阅读程序#includeiostreamusingnamespacestd;boolisPrime(intn){if(n1){returnfalse;}for(inti2;i*in;i){if(n%i0){returnfalse;}}returntrue;}intcountPrimes(intn){intcount0;for(inti2;in;i){if(isPrime(i)){count;}}returncount;}intsumPrimes(intn){intsum0;for(inti2;in;i){if(isPrime(i)){sumi;}}returnsum;}intmain(){intx;cinx;coutcountPrimes(x) sumPrimes(x)endl;return0;}第16题当输入为“10”时程序的第一个输出为“4”第二个输出为“17”。 A.正确B.错误【答案】A【解析】2~10中的质数有2357那么质数个数为4所有质数的和为17第17题若将 isPrime(i)函数中的条件改为 in/2,输入“20”时countPrimes(20)的输出将变为“6”。 A.正确B.错误【答案】B【解析】首先将条件修改为 in/2 是不会引起程序错误只会降低程序的运行效率。那么countPrimes(20)本质上还是计算2~20中的质数个数2,3,5,7,11,13,17,19共8个质数。第18题sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和 A.正确B.错误【答案】A【解析】sumPrime函数是枚举2~n之间每个整数i每次判断i如果是质数则会把i累加到sum中最终sum中存储的值就是 2~n之间所有的质数之和。第19题当输入为“50”时sumPrimes(50)的输出为 A.1060B.328C.381D.275【答案】B【解析】2~50之间的质数有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47其和值为 328。第20题如果将for(int i2;i*in;i)改为for(int i2;in;i),输入“10”时程序的输出 A.将不能正确计算 10 以内素数个数及其和B.仍然输出“4”和“17”C.输出“3”和 10D.输出结果不变但运算时间更短【答案】A【解析】修改为in则每次枚举都会枚举到nn的约数一定有自己所以导致无法正确判断质数从而也无法统计质数的个数与质数和。#includeiostream#includevectorusingnamespacestd;intcompute(vectorintcost){intncost.size();vectorintdp(n1,0);dp[1]cost[0];for(inti2;in;i){dp[i]min(dp[i-1],dp[i-2])cost[i-1];}returnmin(dp[n],dp[n-1]);}intmain(){intn;cinn;vectorintcost(n);for(inti0;in;i){cincost[i];}coutcompute(cost)endl;return0;}第21题当输入的 cost 数组为{101520}时程序的输出为 15 A.正确B.错误【答案】A【解析】从最底层先跨两步走到第2层然后从第2层再跨两步直接走到最顶层因此最少的花费应该是 15只走了第2层台阶。第22题如果将 dp[i-1]改为 dp[i-3]程序可能会产生编译错误 A.正确B.错误【答案】B【解析】不会产生编译错误只会修改了题目的逻辑同时在运行的过程中会产生运行错误因为dp[i - 3] 在i 2时会导致下标为负数。第23题程序总是输出 cost 数组中的最小的元素 A.正确B.错误【答案】B【解析】程序输出的是从最底层走到最顶层过程中走过的台阶的花费总和的最小值。第24题当输入的 cost 数组为1,100,1,1,1,100,1,1,100,1时程序的输出为 。A.“6”B.“7”C.“8”D.“9”【答案】A【解析】从最底层到最顶层的最优路线应该是最底层-第1层-第3层-第5层-第7层-第8层-第10层-最顶层。走过的台阶花费之和为第1层花费第3层花费第5层花费第7层花费第8层花费第10层花费 1 1 1 1 1 1 6。第25题如果输入的 cost 数组为10,15,30,5,5,10,20程序的输出为 。A.“25”B.“30”C.“35”D.“40”【答案】B【解析】从最底层到最顶层的最优路线应该是最底层-第2层-第4层-第6层-最顶层。走过的台阶花费之和为第2层花费第4层花费第6层花费 15 5 10 30。第26题若将代码中的 min(dp[i-1],dp[i-2])cost[i-1]修改为 dp[i-1]cost[i-2]输入 cost 数组为{5,10,15}时程序的输出为 。A.“10”B.“15”C.“20”D.“25”【答案】A【解析】将min(dp[i - 1], dp[i - 2]) cost[i - 1] 修改为 dp[i - 1] cost[i - 2] 之后那么计算的逻辑会发生变化这种修改意味着每一步只能从前一个台阶跳跃过来并且要加上前一个台阶的费用而不是当前台阶的费用。dp[1] cost[0] 5dp[2] dp[1] cost[0] 5 5 10dp[3] dp[2] cost[1] 10 10 20最终返回的结果为min(dp[n], dp[n - 1]) min(20, 10) 10因此结果为10。#includeiostream#includecmathusingnamespacestd;intcustomFunction(inta,intb){if(b0){returna;}returnacustomFunction(a,b-1);}intmain(){intx,y;cinxy;intresultcustomFunction(x,y);coutpow(result,2)endl;return0;}第27题当输入为“2 3”时customFunction(2,3)的返回值为“64”。 A.正确B.错误【答案】B【解析】customFunction(2,3)是返回2 * (31) 的结果 8。注意是customFunction的返回值而非最终输出的结果。第28题当 b 为负数时customFunction(a,b) 会陷入无限递归。 A.正确B.错误【答案】A【解析】因为递归出口是 b 0当b为负数时该条件不会成立会继续执行return a customFunction(a, b - 1); b的值越来越小从而导致b 0 的条件是无法成立因此会陷入无限递归。第29题当 b 的值越大程序的运行时间越长。 A.正确B.错误【答案】A【解析】整个程序的效率由customFunction函数决定而customFunction函数的时间复杂度为 O(b)所以b越大程序运行的时间越长。第30题当输入为“5 4”时customFunction(5,4) 的返回值为 。A.5B.25C.250D.625【答案】B【解析】customFunction(5,4)是返回5 * (41) 的结果 25。注意是customFunction的返回值而非最终输出的结果。第31题如果输入 x 3 和 y 3则程序的最终输出为 A.“27”B.“81”C.144“D.256”【答案】C【解析】首先customFunction(5,4)是返回3 * (31) 的结果 12即result 12输出 result的平方后的结果为 144。第32题若将 customFunction 函数改为“return a customFunction(a-1,b-1);” 并输入“3 3”则程序的最终输出为 。A.9B.16C.25D.36【答案】D【解析】修改之后的customFunction功能是计算 a (a-1) (a-2) … (a-b) 的结果因此如数 3 3 customFunction返回 3 2 1 0 6即result 6输出 result的平方后的结果为 36。完善程序判断平方数问题给定一个正整数 n判断这个数 是不是完全平方数即存在一个正整数 x 使得 x 的平方等于 n。试补全程序#includeiostream#includevectorusingnamespacestd;boolisSquare(intnum){inti__1__;intbound__2__;for(;ibound;i){if(__3__){return(__4__);}}return(__5__);}intmain(){intn;cinn;if(isSquare(n)){coutn is a Square numberendl;}else{coutn is not a Square numberendl;}第33题1处应填 A.1B.2C.3D.4【答案】A【解析】函数要判断 n 是否为 i 的平方在只保证 n 为正整数的情况下要考虑到 n 可能为 1、2 这类极小的正整数因此枚举范围要包括这些较小正整数的平方根应从 1 开始故选择 A 选项。第34题2处应填 A.(int)floor(sqrt(num)-1)B.(int)floor(sqrt(num))C.floor(sqrt(num/2))-1D.floor(sqrt(num/2))【答案】B【解析】函数 floor(x) 为 C 中的向下取整函数其返回 x 的向下取整结果但入参和返回值都为 double 类型。实际上在将 double 类型的值赋值给 int 类型时会自动完成隐式类型转换转换因此 A、B 选项的显式类型转换 (int) 实际不影响结果可以去掉只需关注取整前的结果即可。对正整数 num若其平方根存在则为不超过n u m \sqrt {num}num​的最大整数。由向下取整函数的含义可知应选择 B 选项。第35题3处应填 A.num2*iB.num 2*iC.numi*iD.numi*i【答案】D【解析】由 34 题 bound 指定的枚举范围可知函数的实现方式是枚举可能成为 num 平方根的整数 i并判断 i 是否确实为 num 的平方根这要求 i * i num。注意 C 语言中 为赋值运算符 为判断相等的关系运算符应选择 D 选项。第36题4处应填 A.num 2*iB.num2*iC.trueD.false【答案】C【解析】由 35 题的判定条件可知其对应找到了 num 的正整数平方根的情形此时 num 应为完全平方数根据程序主函数中输出的条件isSquare 函数应返回为真故选择 C 选项。第37题5处应填 A. num i*iB. num!2*iC. trueD. false【答案】D【解析】若 num 为完全平方数则应在循环过程中找到 num 的正整数平方根并结束函数调用。若函数执行至5则说明 num 不存在正整数平方根即 num 不是完全平方数故选择 D 选项。汉诺塔问题给定三根柱子分别标记为 A、B 和 C。初始状态下柱子 A 上有若干个圆盘这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 c 上且必须保持原有顺序不变。在移动过程中需要遵守以不规则只能从一根柱子的顶部取出圆盘并将其放入另一根柱子的顶部。每次只能移动一个圆盘小圆盘必须始终在大圆盘之上。#includebits/stdc.husingnamespacestd;voidmove(charsrc,chartgt){cout从柱子src挪到柱子上tgtendl;}voiddfs(inti,charsrc,chartmp,chartgt){if(i__1__){move(__2__);return;}dfs(i-1,__3__);move(src,tgt);dfs(__5__,__4__);}intmain(){intn;cinn;dfs(n,A,B,C);}第38题1处应填 A.0B.1C.2D.3【答案】B【解析】可以参考之前学习的代码voidhanoi(intn,chara,charb,charc){if(n0){hanoi(n-1,a,c,b);couta -- c;hanoi(n-1,b,a,c);}}这是递归的终止条件。当只剩1个圆盘时,直接从源柱移到目标柱即可,不需要再递归。所以当i1时,执行move操作并返回。第39题2处应填 A.src,tmpB.src,tgtC.tmp,tgtD.tgt,tmp【答案】B【解析】在递归终止条件下,需要将唯一的圆盘从源柱(src)移动到目标柱(tgt)。第40题3处应填 A.src,tmp,tgtB.src, tgt, tmpC.tgt, tmp, srcD.tgt, src, tmp【答案】A【解析】先把i-1层盘子从src移动到tgttmp用做中转对应代码第13行是dfs(i-1, src, tgt, tmp)第41题4处应填 A.src, tmp, tgtB.tmp,src, tgtC.src, tgt,tmpD.tgt,src,tmp【答案】B【解析】最后把i-1层盘子从tmp移动到tgtsrc用做中转对应代码第15行是dfs(i-1tmp, src, tgt)。所以第4空选B第5空选C。第42题5处应填 A. 0B. 1C. i-1D. i【答案】C【解析】最后把i-1层盘子从tmp移动到tgtsrc用做中转对应代码第15行是dfs(i-1tmp, src, tgt)。所以第4空选B第5空选C。