CSP-J模拟题1（Lugu）

1、请在进入答题前，确保设备性能和系统条件符合线上考试要求

2、做题中请勿使用F功能键或查看源代码，如使用系统会记录下来

3、诚信考试，请勿上网搜索答案，与其他考生交流，求助外援等

4、做题中途遇到问题被退出，在有效期内仍可进入再次进行答题

姓名

一、一、单项选择题 共 15 题，每题 2 分，共计 30 分 每题有且仅有一个正确选 项

（1）(1047)8 = (   )。

若逻辑变量A、C为真，B、D为假，以下逻辑表达式的值为假的是（ ） 。

小恺编写了如下函数，希望计算斐波那契数列f(n)第n项对10000取余数的值：

在运行空间限制128MB、栈空间不超过空间限制、运行时限1秒的情况下，在主函数中运行函数f(12345)，则最有可能首先发生什么问题？

表达式a+b*(c-d)/e-f的后缀表达式为（ ）。

某个 MV 是一段时长 4 分整的视频文件。它每秒播放 10 帧图像，每帧图像是一幅分辨率为 2048×1152 像素（长宽比 16:9）的 32 位真彩色图像，其画面没有被压缩。这个视频没有音频。这个视频文件大约需要占用多大的存储空间？

下图是一棵二叉树，它的后序遍历是 （ ）。

五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是 （ ）？

设元素 a,b,c,d,e,f 依次入栈，则下列不合法的出栈序列为（）?

同时扔出 3 枚完全相同的六面骰子，每个骰子上有 1 到 6 的数字。将得到的点数排序后，有（ ）种不同的结果？

在编程时（使用任一种高级语言，不一定是 C++），如果需要从磁盘文件中 输入一个很大的二维数组（例如 1000*1000 的 double 型数组），按行读 （即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输 入效率上 。

不考虑稳定性，下列排序方法中平均时间复杂度最大的是 。

将数组 12,23, -1,19,117, -103,79,602 中的元素按从大到小的顺序排 列，每次可以交换任意两个元素，最少需要交换（ ）次

13 名男生和 3 名女生围成一个圈，男生 和男生不相邻，女生和女生不相邻。 如果两个围成的圈经过旋转可以重合，则视为同一种方案。请问一共有几种 方案？

以下关于 C++ 字符串的说法，错误的是 （）。

中国计算机学会成立于（ ）年。

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

1.

已知， 𝟏≤𝒏≤𝟏𝟎^𝟔,𝟏≤𝒂𝒊≤𝟏𝟎^𝟔。 完成下面的判断题和单选题：

* 判断题

1) solve2 函数实现了选择排序。

2）solve1 函数的时间复杂度为 𝑂(𝑛+𝑉)，其中 𝑉 指的是 𝑎𝑖 的最大值。

3）当输入数据为： 7 2 3 5 7 1 4 6 时， solve2 函数中的变量 cnt 最终值为 9。

4）若将 solve2 函数中的双斜杠全部移除，不会影响输出结果。

* 单选题

5) 下列哪组数据，会使得 solve1 函数与 solve2 函数的输出结果 不 同 ）（假设已经输入了 𝑛=8 ）。

若要使得 solve1 和 solve2 函数的输出结果 相同 ，则应当修改程序中 的哪一处？

2.

输入保证 t 的长度不大于 s 的长度，且两字符串均只含有大小写字母， 不是空串， type = 1,2,3 ，完成下面的判断题和单选题

* 判断题

1） 将程序中所有的 比较运算符 小于号 (<) 改为不等于号 (!=)(!=)，则程序 对所有符合要求的输入的输出结果 不变 。

2）当输入为 1 xyz abcd 时，程序的输出为 xyzd 。

3） 程序在输入为 1 xyz abcd 时的输出与输入为 2 xyz abcd 的输出 相同。

4） 将程序第 25~28 行的 while 循环替换为 do while 循环（判断条件 和循环体不变），则程序对同一合法输入的输出结果 一定不变 。

* 单选题

5) 若将程序第 13 行改为 for (int i = 0; i < strlen(t); ++i) s[i] = t[ i];，且已知输入的 type 一定为 1 的情况下，用 𝑛 表示 𝑠 的长度， 𝑚 表示 𝑡 的长度，则程序的时间复杂度为 。 A . B. C . Θ(𝑛2+𝑚) D. Θ(𝑛2+m2)

6) 给程序分别输入选项 ( ) 的两组输入数据，得到的输出不同。

3. 

以下程序的输入数据的绝对值均不超过𝟏𝟎^𝟑。完成下面的判断题和单选题：

* 判断题

1）存在 一种合法的输入数据，使得运行程序时，某次 find_down 函数的 返回值是 −1 。 

2）该程序的时间复杂度为 Θ(𝑛^2𝑚^2)。 

3) 对于 任意 𝑢∈[0,6)，「先执行 front_rotate(u) u)，再执行 right_rotate(u) 」，与「先执行 right_rotate(u) u)，再执行 front_rotate(u) 」，最终 𝑢

* 单选题

4） 将 anchorX 、 anchorY 、 anchorZ 依次 更换为（ ）时，对于全部合法 数据，与改变之前的输出结果无异。

5）（2 分） 对于以下的输入数据，输出结果为 。

5 5

2 8 15 1 10

5 19 19 3 5

6 6 2 8 2

12 16 3 8 17

12 5 3 14 13

1 1 1 1 1 1

6） 2 分） 对于以下的输入数据，输出结果为 。

2 5

2 8 15 3 10

5 19 19 3 5

1 2 3 4 5 6

三 、 完善 程序（ 单选题，每小题 3 分，共计 3 0 分

1.（支付问题）有 n 种纸币，其中第 i 种纸币的面值为 a i 元。每种纸币只 有一张。求能支付多少种 金额 （不包括 0 元）。 数据范围满足n <= 200 ai的总和不超过 5000 。

1) ①处应填()

1) ②处应填()

③处应填(   )。

④处应填(   )。

④处应填(   )。

⑤ 处应填（ ）。

2.(凑出17)凑出 17 给定 𝑛(1≤𝑛≤20) 个互不相同的正整数 𝑎1,𝑎2,…𝑎𝑛(1≤𝑎𝑖≤109)，将之排成一行。你需要在每个 𝑎𝑖 前加上一个加号 或减号 ((--))，使 这 𝑛 个数字组成一个算式。请问是否存在一种添加符号的方案，使该算式 的值为 17？如果存在，请输出 Yes ，否则输出 No 。

例如，给定 𝑛=5,𝑎1=1,𝑎2=4,𝑎3=5,𝑎4=9,𝑎5=8，则 −𝑎1−𝑎2+𝑎3+𝑎4+𝑎5=17。

提示：使用穷举法解决这个问题。

试补全程序。

1） ① 处应填 。

1） ① 处应填 。

2） ② 处应填 。

3） ③ 处应填 。

4） ④ 处应填 。

4） ⑤处应填 。