CSP-J 2021 第一轮试题

场次：2021年CSP-J第1轮
考试时长：120 分钟
满分：100 分
题目来源：第三方来源（社区转写，非官方，仅供参考）

单项选择题

本分区标题为平台补的结构性占位，原卷（来源件）未收录。

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

C++

Python

Java

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

奥斯卡奖

图灵奖

诺贝尔奖

普利策奖

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

二进制

十进制

八进制

十六进制

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

$N^{2}$

$N$

$N-1$

$N+1$

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

$a, b, c, d, e$

$e, d, c, b, a$

$b, a, c, d, e$

$c, d, a, e, b$

对于有 $n$ 个顶点、 $m$ 条边的无向连通图 $(m>n)$ ，需要删掉（）条边才能使其成为一棵树。

$n-1$

$m-n$

$m-n-1$

$m-n+1$

二进制数 $101.11$ 对应的十进制数是（）。

6.5

5.5

5.75

5.25

如果一棵二叉树只有根结点，那么这棵二叉树高度为 $1$ 。请问高度为 $5$ 的完全二叉树有（）种不同的形态？

表达式 $\texttt{a*(b+c)*d}$ 的后缀表达式为( )，其中 $\texttt{*}$ 和 $\texttt{ + }$ 是运算符。

$\texttt{**a+bcd}$

$\texttt{abc+*d*}$

$\texttt{abc+d**}$

$\texttt{*a*+bcd}$

$6$ 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（）种。

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

枚举

贪心

递归

动态规划

由 $1,1,2,2,3$ 这五个数字组成不同的三位数有（）种。

考虑如下递归算法

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

则调用 solve(7) 得到的返回结果为（）。

105

840

210

420

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

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 × ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

判断题正确填 √，错误填 ×

阅读程序共 10.5 分6 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/6

原卷作答说明：判断题正确填 √，错误填 ×

程序

#include <iostream>using namespace std;int n;int a[1000];int f(int x){ int ret = 0; for (; x; x &= x - 1) ret++; return ret;}int g(int x){ return x & -x;}int main(){ cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cout << f(a[i]) + g(a[i]) << ' '; cout << endl; return 0;}

16判断1.5 分
输入的 $n$ 等于 $1001$ 时，程序不会发生下标越界。（）
17判断1.5 分
输入的 $a[i]$ 必须全为正整数，否则程序将陷入死循环。（）
18判断1.5 分
当输入为 5 2 11 9 16 10 时，输出为 3 4 3 17 5。（）
19判断1.5 分
当输入为 1 511998 时，输出为 18。（）
20判断1.5 分
将源代码中 g 函数的定义（ $14\sim 17$ 行）移到 main 函数的后面，程序可以正常编译运行。（）
21单选3 分
单选题
1. 当输入为 2 -65536 2147483647 时，输出为（）。
A. 65532 33
B. 65552 32
C. 65535 34
D. 65554 33
A
65532 33

B
65552 32

C
65535 34

D
65554 33

CSP-J 2021 第一轮试题