2021年CSP-J入门级第一轮试题及答案解析

1、2021年 CSP-J 入 门轮试题和答案解析2021 CCF非专业级别软件能力认证第一轮(CSP-31)提高级C+语言试题认证时间：2021年9月19日14:30-16:30考生注意事项工 演题纸共有12页，答题纸佚有1页，泗分分匚请在答题纸H1者.可在试题纸上的 一律无效.不得使用任何电亚备(切计双器，手机、电广词联等)或查阅任何书籍资科一、单项选押题(共15JH.每题7分,共计算分I每剧有且仅有1个正确选项)1 .以卜不属F面向对象程序设计谓彳的是().4. C+B. PythonC* JavaD. Ct答案】D【解枷】C语言是面向过程的编译性语言“，以下奖项与H我机题域最相关的是().

2、R.奥斯夕奖口.图足代C.诺贝尔奖D.普利第奖【答案】B【钝杆】图灵奖是计算机领域的闰际最高奖项。m.目前主流的计算机储存数据点终都是转换或()数据进，储存.A.二进制B.卜进制C.八进制D. F六进朝【答案】AI解析】计算机中以二进制方式进行存储数据。4.以比较作为基本运算,在N个数中找出最大数,最坏情况下所需要的最少的比较次数为A. N2BNC. N-1D N+1【答案】C【解析】以第一个数作为初始值，从笫二个数开始比较，最坏情况下需要比较到序列末尾才 能得到最大值，即比较N-1。5 .对于入栈顺序为a, b, c, % e的序列,卜列()不是合法的出极序列。A. a, b, c, d,

3、eB. e, d, a b, aC. b, a, c, 6, eD. c, d, a, e, b【答案】D【解析】D选项中c和d出栈后，从栈顶到栈底至少有b a,其中b还没有出栈，a无法 先出栈。6 .对于有n个顶点、m釜边的无向连通图(m>n),需要删掉()条边才能使其成为一棵树.A. n-1B. m-nC. m-n-1D m-n+1【答案】D【解析】n个节点的树有n-1条边，则需要留下n-1条边，即福要删除m-(n-1)条边。7 .二进制数101.11对应的卜进制数是()。A. 6.5B. 5.5C. 5.75D. 5.25【答案】C【解析】其他进制转十进制：按权展开求和。整数部分，

4、1*22 + 0*2】+ 1*20 = 5,小数部分1 1*2-1+ 1*2-2= 0.75,结果为5.75。8.如果 棵二叉树只行根结点,那么这棵二叉树高度为1请问高度为5的完全二叉树行()种不同的形态？A. 16B. 15C. 17D. 32【答案】A【解析】完全二叉树第5层最多有2，= 16个节点，那么从左到右依次可以有连续k( 14Hl6) 个节点，一共有16种情况.9,表达式a*(b+c)*d的后级表达式为(),其中和是运总符.A. *a+bcdB. abc+*d*C. abc+d*D. *a*+bcd【答案】B【弊析】a* (b+c) *d的后缀表示为abc+*d*。10.6个人,

5、两个人组一队，总共组成三队,不区分队伍的编号。不同的组队情况才()也A. 10B. 15C. 30D. 20【答案】B【解析】第一组有或第二组有Cj第三组有一共有：C"c：*c狂 15*6=90但是没有区分组别，所以还要除以房=6最终有：90/6-15种情况.11 .希数据压缩编码中的哈夫亚编码方法，在本质上是一种()的策略.A.枚举B.贪心C.递白D.动态规划【答案】B【解析】哈夫曼编码每次把频率最低的两个节点(字符)合并产生新的节点，将新的节点放 到集合中，删除用来合并的两个节点，重复上述过程直到剩下一个节点为止。每次选择频率 最小的两个节点就是贪心的思想。12 . It 1.

6、1. 2. 2, 3这五个数字ffl成不同的三位数有()种.A. 18B. 15C. 12D. 24【答案】A【解析】以1,1开头的三位数有2种；以1,2开头的三位数有3种；以1,3开头的三位数有2种以2,1开头的三位数有3种；以2,2开头的三位数有2种；以2,3开头的三位数有2种；以3开头的三位数有4种：一共有 2+3+2+3+2+2+4=18 种。13 .考虑如下递下算法solve(n)if n<=l return 1else if n>=5 return ntsolve(n-2)else return n*solve(n-l)则调用solve(7)得到的返网结果为()A. 1

7、05B 840C. 210D. 420【答案】c解卜solve (7) = 7 * solve (7 - 2)solve(5) =5*solve(5-2)solve(3) =3*solve(3-1)solve(2) =2solve(2-1)solve(1) = 1那么 solv(7)=7*5*3*2*1 = 210o14 .以a为起点,对仃边的无向图进行深度优先遍为，则b、c、d、e四个点中有可能作为及后一个遍历到的点的个数为()A. 1B. 2C. 3D. 4【答案】B【解析】从a向b的方向开始搜索的终点是e (a-b-d-c-e),从a向c的方向开始搜索 的终点是b (a-c-e-d-b)

8、或c (a-c-d-b-e)»则最多有两个终点分为b和15 .行四个人要从A点坐一条船过河到B点,船开始在从点,该船一次最多可坐两个人.己知这四个人中每个人独自坐船的过河时间分别为1, 2, 4, 8,且两个人坐船的过河时 间为两人独白过河时间的较大者.则最短()时间可以让四个人都过河到B点(包括从 B点把船开回A点的时间).A. 14B. 15C. 16D. 17【答案】B【解析】1和2从A到B, 1从B到A,此时A点有1、4、8, B点有2,所用时间为2+1=3;4和8从A到B, 2从B到A,此时A点有1、2, B点有4、8,所用时间为8+2=10；1和2从A到B,所用时间为2：

9、总时间为3+10+2=15.二、阅读程序(程序输入不超过数组或字符串定义的范围I判断题正确填错误填X,除特 殊说明外，判断题1.5分，选算题3分，共计40分)(1)01 include <iostream>02 using namespace std;0304 int n;05 int a1000;0607 int f(int x)08 09int ret = 0;10 for (; x; x &= x - 1) ret+;11 return ret;12 )1314 int g(int x)15 16 return x & -x;17 )1819 int main

10、()20 21 cin >> n22 for (int i = 0; i < n; i+) cin >> ai;23 for (int i = 0; i < n; i+)24 cout << f(ai) + g(ai) << *25 cout << endl;26 return 0;27 程序解读如下：x &= x-1的功能是将x二进制表示中最低位的1变为0,例如 x=00110100,贝！J x-l=0011001100110100(x)£ 00110011(x-1)=00110000因此，£

11、(公返回x二进制表示中1的个数X & (-X)的功能是仅保留X二进制表示中最低位的1,例如 x=00110100,则-x=1100110000110100(x)S 11001100(-x)=00000100因比，g(x)返回*二进制最低位的1对应的数判断麹16 .输入的n等丁 1001时，程序不会发生下标越界。()【答案】X【解析】数组int a1000没有1001个位置17 .输入的ai必须全为止整数，否则程序将陷入死循环()【答案】X【解析】ai为负数也行，“去掉最低位的1”的操作对负数也有效，最终仍会去掉所有1, 得到018 .当输入为“5 2 11 9 16 10”时，输出为“

12、3 4 3 17 5”.()【答案】X【解析】应为 3 4 3 17 4, 10=1010,f (10)+g(10)=2+2=419 .当输入为“1 511998”时，输出为“18”.()【答案】J【解析】511998=1111100111111111110, f (511998)+g(511998) =16+2=1820 .将源代码中g函数的定义(1417行)移到main函数的后面，程序可以正常编译运 行。()【答案】X【解析】主函数前g不声明不定义，无法在主函数中使用单选题21.当输入为“2 -65536 2147483647"时，输出力().A. "65532 33-

13、 B. ,65552 32- C. ”65535 34”I).”65554 33”【答案】B【解析】-65536=11111111111111110000000000000000,f (-65536)+g(-65536)=16+65536=655522147483647=01111111111111111111111111111111,f (2147483647)+g(2147483647)=31+1=32(2)01 #include <iostream>02 #include <string>03 using namespace std;0405 char base6

14、4;06 char table256;0708 void init()09 (10for(inti«0;i<26;i+)baseiA*+ i;11for(inti=0;i<26;ii)base26+i=9a9+i;12for(inti»0;i<10;i+)base52i*0*+i;13base62=*+*,base63=1415 for (int i - 0; i < 256; i+*) tablei - 0xff;16 for (int i = 0; i < 64; tablebasei = i;17 table'=' = 0

15、;18 1920 string decode(string str)21 22string ret;23int i;24 for (i « 0; i < str.size(); i +« 4) 25ret += tablestri << 2 | tablestri + 1 >> 4;26if (stri + 2 !« )27ret = (tablestri + 1 & 0x0f) << 4 | tablestri +2 » 2；28if(stri 3!«29ret = tablestri 2 &

16、lt;< 6 | tablestri 3;30)31returnret;32 13334 int main()35 (36init();37cout << int(table0) << endl;3839stringstr;40cin >>str;41cout << decode(str) << endl;42return0;43 )程序解读如下，base数组的卜标-值对应为063分别对应字符（ASCII码）AZ, az, 09, +, / table数组的下标-值对应为字符（ASCII码）AZ,.z,09, * ,/对应063

17、,字符（ASC工工码）=也对应0判断尊22 .输出的第二行一定是由小写字母、大写字母、数字和“ + ”、“/"、“ = ”构成的 字符中.（）【答案】X【解析】没有消息表明输入会保证这一点23 .可能存在输入不同，但输出的第二行相同的情形.（）【答案】J【解析】例如、'aO=和''al=均输出、k”24 .输出的第一行为“-1”.（）【答案】V【解析】tableO=Oxff= （11111111）2,按 int解释为-1单选题25 .设输入字符串长度为n. decode函数的时间杂度为（）儿。（夕i）R 6（n）C. 0（n logn）D. 0（n2）【答案】

18、B【解析】函数包含对字符串中字符的遍历，每个字符常数次操作，故复杂度为。（字符串长 度）26 .当输入为“Y3NX”时.输出的第二行为（）A. "cspwB. “esq”C. “CSP”D. “Csp”【答案】B【解析】可以按table数组的下标、值对应关系模拟，但需耍记忆ascii码。更合适的 方法是最后两个字符相差-2,故选B,这样不需要记忆记忆ascii码27 . （3.5分）当输入为“Y2NmIDIwMjEB八输出的第二行为（）A. ,ccf2021- B. -ccf2022w C. Mccf 2021w D. “ccf 2022”【答案】C【解析】同可以记忆ascii码模拟

19、.更合适的方法是排除法，确定位数为8且最后两个字 符不同，故选C010203040506070809101112131415161718192021222324252627 ?«2930313233343536373839404142434445464748(3)#include <iostream>using namespace std;const int n = 100000;const int N = n + 1;int m;int aN, bN, cN, dN;int fN, gNjvoid init() (fl = gl = 1;for (int i «

20、; 2; i <« n; i+) 讦bm+ » i;ci = 1, fi = 2;di » gi « i + 1； )for (int j = 0; j < m && bj * i <= n; j+) int k = bj;ai * k = 1;if (i % k = 0) ci * k = ci + 1;fi * k = fi / ci * k * (ci k + 1); di * k = di;gi * k = gi * k di;hrpak;else ci k = 1;fi k - 2 fi;di * k = gi

21、;gi * k工 gi * (k + 1);)int main()(init();int x;cin >> x;cout << fx <<,<< gx << endl;return 0;)程序解读如下，int aN;质数标记.。为蚊教，int bN;第i个质数int cN;最小质因子的个数int dN ;/ (p3+pa+. . .pnu") p 为最大质因子,num 为 p 的个数.int £N;约数个数int gN;约数和这是一个线性简全家套餐(筛法求质数+约数个数+约数和)，基础知识可以提供一个网站学 习：h

22、ttps:/blog. csdn. net/ControlBear/article/details/77527115假设输入的x是不超过工。ee的自然效，完成下面的判断咫和单选后，判断题28. 若输入不为“1” ,把第13行删去不会影响输出的结果.()r答案】j【解析】发现21行k的取值不会是1,那么14行包含的所有的下标都不会是1,后续计 算不会受影响29. (2分)第25行的“fi / ci * k"可能存在无法整除而向卜取整的情况.()【答案】X【解析】f i = (14-num_l) (l+num_2) . . . (l+num_m)» 所以 fi一定包含 ci *

23、 k=ci + 1 = num_l + 1,能够整除。30. (2分)在执行完后，f数组不是单调递增的.但8数组是单调递增的。()【答案】X【解析】举个例子即可，q8 = 1+2+4+8, g9 = 1+3+9单选题31.1 nit函数的时间复杂度为()。A. 6(n)B. 9(n logn)C. 而)I). 6(n2)【答案】A【解析】线性筛全家桶套餐，整体也是线性的。32 .在执行完 irdt()后，fl, f2, f3 _ 中有()个等于 2A. 23B. 24C. 25I). 26【答案】C【解析】含有2个约数就是质数，数质数即可33 . (4分)当输入为“100。”时，输出为()A.

24、 "IS 1340" B. "15 2340" C. -16 2340" D. 0 16 1340”【答案】C【斡机】知道数组的概念后，直接死算得到结果。三、完善程序（单选题.每小题3分，共计30分）（1） （Josephus问题）仃n个人惘成一个圈，依次标号0至月一1从0号开始.依次0,1,0,1, 剩下人的编号. 交替报数,报到1的人会离开,在至明中只剩F一个人求以后:式补全模拟程序.#include <iostream>using namespace std;const int MAXN 10906。； int FMAXN;i

25、nt main() int n;cin >> n;int i « 0, p « 0, c « 0;while ()if (Fi « 0) 讦(®) F(i « 1； ) ；)int ans « -1;for (1 e 0; i < n; i”)if (Fi « 6) ans = 1; cout << ans << endl; return 0;0102030405060708091011121314151617181920212223242526272834 .处应埴()A

26、. 1 < nB. c < nC. i < n - 1 D. c < n - 1【答案】D【解析】需要搞明白c的含义，c是表示出幽的人数，那么如果c没有到n-1,即剩下一 个人,就继续循环。35 .处应埴()A. 1 % 2 «« 0 B. i X 2 «« 1 C. pD. !p【答案】C【解析】需要搞明Hp的含义，Fi = 1;明显提示是出置的情况，那么我们要知道P什 么时候出圈,这里明显p需要在。1之间反复横跳，旦最开始p为0,那么应该是p为工时 出虬36 .处应填()A. i-H. i = (1 > 1) X nC.

27、 CiD. p A» 1【答案】c【解析】出圈后自然想到的是出圈人数的更新e37 .处应填()A.i-M-Ki(1 1) % nC.ciD.p 1【答案】D【解析】每次找到没有出圈的人我们必定干什么？肯定是更新报数状态，这里可能有同学会 将其与3搞混.38 .处应填()A.B. i - (1 + 1) X nC. £0. p *- 1【答案】B【解析】僚环里面出圈这个操作已经有了，那么自然会想到还剩下一个必要操作是移动考虑 的位置，这里注意到是一个环，需要考虑出界问题.01 02 03 0405 06 07 0809 101112 1314 1516 1718 19 2&#

28、169;2122 232425 2627 2829 3。3132 3334 3536 3738 3940 4142 43 4445 4647(2)矩形计数)平面H n个关键点,求和多少个四条边都和x轴或My轴平行的矩 形，足四个顶点那是关键点.给出的关键点可能有审更,完全簟合的矩形只计一次.逮补个收卒立法.Itinclude <iostream> using namespace std; struct point int x, Vid; )； bool equals(point a> point b) return a.x = b-x && a.y = b.y

29、;bool cmp(point a, point b) return ；void sort(point Af int n)( for (int i « 0; i < n; i+) for (int j - 1; j < n; ) if (cmpCAfj, Aj - 1) ( point t « Aj;A(j - Aj 1； Aj - 1 « t； ) ) int unique(point AL int n) int t « 0; for (int i = 0; i < n; i+>) if (®) Ati = Ai; r

30、eturn t;bool binary_search(point A9 int n, int x, int y) point p;P-x « x; p-y = y; p.id « n; int a « 0, b - n 1; while (a < b) int mid » 3)； if (®) a = mid + 1; else b « mid;a = mid + 1;elseb - mid; return equals(Aa,p);"/二分仓找对应的坐标是否出现在数组中MAXN 1000struct point AM

31、AXN;int main() int n;scanf(n%dM,&n);for(int 1 = 0;i < n;i+) scanf(H%d %dwf&Ai.x,&Ai.y); Ai.id = i;坐标数组输入sort(A,n) ;/坐标数组排序n = unique (A,n);坐标数组去第 int ans = 0;for(int i = 0;i < n;i+)for(int j = 0;j < n;j+)if (Ai.x < Aj.x && Ai.y < A j.y && binary search(A,n,A(i.x,Aj.y) i6 binary_search(A,n,Aj.xrAi.y) ans+;”/穷举举行左卜角与右上角，然后查看另外网个角是否存在 printf (,f%dnw , ans);return 0;)问题理解不难,但代码一堆东西，很容易很吭住，但好的地方是函数命都比较炫范，至 少能看出是什么功能.从主代码入手，我们大概能知道基本的计算步骤1 .坐标数组输入2 .坐标数组排序3 .坐标数组去重4 .穷举两个坐标，找答案.5 .给出答案重点在于步骤4的实现