2021年CSP-S 初赛试题

ID: 4935

客观题

尝试: 2

已通过: 1

难度: 10

上传者:

shijingyao

标签>

2021

CSP-S

初赛

一、单选题（共15题，每题2分，共计30分；每题有且只有一个正确选项。）

在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（）。 {{ select(1) }}

二进制数 $00101010_{2}$ 和 $00010110_{2}$ 的和为（）。 {{ select(2) }}

$00111100_{2}$
$01000000_{2}$
$00111100_{2}$
$01000010_{2}$

在程序运行过程中，如果递归调用的层数过多，可能会由于（）引发错误。 {{ select(3) }}

系统分配的栈空间溢出
系统分配的队列空间溢出
系统分配的链表空间溢出
系统分配的堆空间溢出

以下排序方法中，（）是不稳定的。 {{ select(4) }}

插入排序
冒泡排序
堆排序
归并排序

以比较为基本运算，对于 $2n$ 个数，同时找到最大值和最小值，最坏情况下需要的最小的比较次数为（）。 {{ select(5) }}

$4n-2$
$3n+1$
$3n-2$
$2n+1$

现有一个地址区间为 $0\sim 10$ 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到 $10$ 冲突了就从 $0$ 开始往后），现在要依次存储 $(0,1,2，3,4,5,6,7)$ ，哈希函数为 $h(x)=x^{2} \bmod {11}$ 。请问 $7$ 存储在哈希表哪个地址中（）。 {{ select(6) }}

G 是一个非连通简单无向图（没有自环和重边），共有 $36$ 条边，则该图至少有（）个点。 {{ select(7) }}

令根结点的高度为 $1$ ，则一棵含有 $2021$ 个结点的二叉树的高度至少为（）。 {{ select(8) }}

10
11
12
2021

前序遍历和中序遍历相同的二叉树为且仅为（）。 {{ select(9) }}

只有 1 个点的二叉树
根结点没有左子树的二叉树
非叶子结点只有左子树的二叉树
非叶子结点只有右子树的二叉树

定义一种字符串操作为交换相邻两个字符。将 $\texttt{DACFEB}$ 变为 $\texttt{ABCDEF}$ 最少需要 ( ) 次上述操作。 {{ select(10) }}

有如下递归代码

solve(t, n):
 if t=1 return 1
 else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为（）。 {{ select(11) }}

斐波那契数列的定义为： $F_{1}==1，F_{2}=1，F_{n}=F_{n-1}+F_{n-2}$ $(n\geq 3)$ 。现在用如下程序来计算斐波那契数列的第 $n$ 项，其时间复杂度为（）。

F(n):
  if n<=2 return 1
  else return F(n-1) + F(n-2)

$O(n)$
$O(n^{2})$
$O(2^{n})$
$O(n\ log\ n)$ O

有 8 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（）种方案。 {{ select(13) }}

设一个三位数 $n= \overline{abc}$ ， $a,b,c$ 均为 $1\sim 9$ 之间的整数，若以 $a$ 、 $b$ 、 $c$ 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 $n$ 有（）个。 {{ select(14) }}

有如下的有向图，节点为 $A ,B , \cdots , J$ , 其中每条边的长度都标在图中。则节点 A 到节点 J 的最短路径长度为（）。 {{ select(15) }}

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

假设输入的所有数的绝对值都不超过 $1000$ ，完成下面的判断题和单选题：

·判断题

1）将第 21 行中 t 的类型声明从 int 改为 double，不会影响程序运行的结果。（） {{ select(16) }}

正确
错误

2）将第 26、27 行中的 / sqrt(t) / 2替换为/ 2 / sqrt(t)，不会影响程序运行的结果。（） {{ select(17) }}

正确
错误

3）将第 28 行中的 x * x 改成 sq(x)、y * y 改成 sq(y)，不会影响程序运行的结果。（） {{ select(18) }}

正确
错误

4）（2 分）当输入为 0 0 0 1 1 0 0 1 时，输出为 1.3090 ( ) {{ select(19) }}

正确
错误

·单选题

5）当输入为 1 1 1 1 1 1 1 2 时，输出为（）。 {{ select(20) }}

3.1416
6.2832
4.7124
4.1888

6）（2.5 分）这段代码的含义为（）。 {{ select(21) }}

求圆的面积并
求球的体积并
求球的体积交
求椭球的体积并

假设输入的所有数的绝对值都不超过 1000 ，完成下面的判断题和单选题：

·判断题

1）程序总是会正常执行并输出两行两个相等的数。（） {{ select(22) }}

正确
错误

2）第 28 行与第 38 行分别有可能执行两次及以上。（） {{ select(23) }}

正确
错误

3）当输入为 5 -10 11 -9 5 -7 时，输出的第二行为 7。( ) {{ select(24) }}

正确
错误

·单选题

4）solve1(1, n) 的时间复杂度为（）。 {{ select(25) }}

$O(\log n)$
$O(n)$
$O(n \log n)$
$O(n^{2})$

5）solve2(1, n) 的时间复杂度为（）。 {{ select(26) }}

$O(\log n)$
$O(n)$
$O(n \log n)$
$O(n^{2})$

6）当输入为 10 -3 2 10 0 -8 9 -4 -5 9 4 时，输出的第一行为（）。 {{ select(27) }}

假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题：

·判断题

1）程序总是先输出一行一个整数，再输出一行一个字符串。（） {{ select(28) }}

正确
错误

2）对于任意不含空白字符的字符串 str1，先执行程序输入0 str1，得到输出的第二行记为 str2 再执行程序输入1 str2，输出的第二行必为 str1。（） {{ select(29) }}

正确
错误

3）当输入为1 SGVsbG93b3JsZA==时，输出的第二行为HelloWorld。( ) {{ select(30) }}

正确
错误

·单选题

4）设输入字符串长度为 $n$ ，encode 函数的时间复杂度为（）。 {{ select(31) }}

$O( \sqrt{n})$
$O(n)$
$O(n\log n)$
$O(n^2)$

5）输出的第一行为（）。 {{ select(32) }}

0xff
255
0xFF
-1

6）（4 分）当输入为 0 CSP2021csp 时，输出的第二行为（）。 {{ select(33) }}

Q1NQMjAyMWNzcAv=
Q1NQMjAyMGNzcA==
Q1NQMjAyMGNzcAv=
Q1NQMjAyMWNzcA==

三、完善程序（单选题，每小题 3 分，共计 30 分） (1) （魔法数字）小 H 的魔法数字是 4。给定 $n$ ，他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$ 。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$ 。