2021年CSP

2021年CSP-J组入门级初赛真题一、单项选择题（共15题，共计30分）

1.以下不属于面向对象程序设计语言的是（D）。

A.C++

B.Python

C.Java

D.C

题目解析

正确答案： D，C语言是面向过程的编译性语言

---------------------------------------------------------------------------------------------------------------------------------

2.以下奖项与计算机领域最相关的是（B）。

A.奥斯卡奖

B.图灵奖

C.诺贝尔奖

D.普利策奖

题目解析

正确答案： B，图灵奖是计算机领域的国际最高奖项

---------------------------------------------------------------------------------------------------------------------------------

3.目前主流的计算机储存数据最终都是转换成（A）数据进行存储。

A.二进制

B.十进制

C.八进制

D.十六进制

题目解析

正确答案： A，计算机中以二进制方式存储数据

---------------------------------------------------------------------------------------------------------------------------------

4.以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少的比较次数为（C）。

A.N2

B.N

C.N-1

D.N+1

题目解析

正确答案： C, 最值问题，以第一个数作为初始值，从第二个数开始比较，最坏情况下要比较到序列末尾才能得到最大值，即比较 N−1 次

---------------------------------------------------------------------------------------------------------------------------------

5.对于入栈顺序为a,b,c,d,e的序列，下列（D）不是合法的出栈序列。

A.a,b,c,d,e

B.e,d,c,b,a

C.b,a,c,d,e

D.c,d,a,e,b

题目解析

正确答案： D, acb进栈，c出栈，d进栈出栈，之后从栈顶到栈底还有b,a没有出栈，a无法在b之前先出栈

---------------------------------------------------------------------------------------------------------------------------------

6.对于有n个顶点，m条边的无向连通图（m>n），需要删掉（D）条边才能使其称为一棵树。

A.n-1

B.m-n

C.m-n-1

D.m-n+1

题目解析

正确答案： D, n个顶点的树有n−1条边，需删除 m-(n-1)= m-n+1 条边

---------------------------------------------------------------------------------------------------------------------------------

7.二进制数101.11对应的十进制数是（C）。

A.6.5

B.5.5

C.5.75

D.5.25

9.表达式a*(b+c)*d的后缀表达式为（B），其中“*”和“+”是运算符。

A.**a+bcd

B.abc+*d*

C.abc+d**

D.*a*+bcd

题目解析

正确答案： B, 考察前后缀表达式。表示为( a [ bc +] * ) d *，后缀表达式为 abc+*d*

---------------------------------------------------------------------------------------------------------------------------------

11.在数据压缩编码种的哈夫曼编码方法，在本质是一种（B）的策略。

A.枚举

B.贪心

C.递归

D.动态规划

题目解析

正确答案： B, 哈夫曼编码每次把频率最低的两个节点合并，产生新的节点并放在集合中，删除用来合并的两个节点，重复这个过程直到剩下一个节点为止。每次选择频率最小的两个节点就是贪心的思想。

---------------------------------------------------------------------------------------------------------------------------------

12.由1，1，2，2，3这五个数字组成不同的三位数有（A）种。

A.18

B.15

C.12

D.24

题目解析

正确答案： A, 枚举法，不同的三位数有：321，322，311，312，211，212，213， 221， 223，231， 232， 112，113，121，122，123，131，132共十八种

---------------------------------------------------------------------------------------------------------------------------------

13.考虑如下递归算法

solve(n) if n=5 return n*solve(n-2) else return n*solve(n-1)

---------------------------------------------------------------------------------------------------------------------------------

14.以a为起点，对右边的无向图进行深度优先遍历，则b,c,d,e四个点中有可能作为最后一个遍历到的点的个数为（B）。

A.1

B.2

C.3

D.4

题目解析

正确答案： B，从a→b方向的遍历：a−b−d−c−e; 从a→c方向的遍历：a-c-e-d-b和a−c−d−b−e. 则最多有两个终点：e和b

---------------------------------------------------------------------------------------------------------------------------------

15.有四个人要从A点坐一条船过河到B点，船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1，2，4，8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（B）时间可以让四个人过河到B点（包括从B点把船开回A点的时间）。

A.14

B.15

C.16

D.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；总时间为3+10+2=15

---------------------------------------------------------------------------------------------------------------------------------

二、阅读程序（程序输入不超过数组或字符串定义的范围，共计40分）01 #include 02 03 int n;04 int a[1000];05 06 int f(int x)07 {08 int ret = 0;09 for(; x; x &= x - 1) ret ++;10 return ret;11 }12 13 int g(int x)14 {15 return x & - x;16 }17 18 int main()19 {20 scanf("%d", &n);21 for (int i = 0; i

云奕文章网

2021年CSP

相关推荐：