CSP-J模拟题1（Lugu）

:1、请在进入答题前，确保设备性能和系统条件符合线上考试要求2、做题中请勿使用F功能键或查看源代码，如使用系统会记录下来3、诚信考试，请勿上网搜索答案，与其他考生交流，求助外援等4、做题中途遇到问题被退出，在有效期内仍可进入再次进行答题

Q1:姓名

:分割线

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

Q2:（1）(1047)8 = ( )。

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

Q4:小恺编写了如下函数，希望计算斐波那契数列f(n)第n项对10000取余数的值：[图片]在运行空间限制128MB、栈空间不超过空间限制、运行时限1秒的情况下，在主函数中运行函数f(12345)，则最有可能首先发生什么问题？

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

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

Q7:下图是一棵二叉树，它的后序遍历是 （ ）。[图片]

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

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

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

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

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

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

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

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

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

:二、阅读程序（程序输入不超过数组或字符串定义的范围 判断题正确填错误填 × 除特殊说明外，判断题 2 分，选择题 3 分，共计 40 分）1.[图片1][图片2]已知， 𝟏≤𝒏≤𝟏𝟎^𝟔,𝟏≤𝒂𝒊≤𝟏𝟎^𝟔。 完成下面的判断题和单选题：

:* 判断题

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

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

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

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

:* 单选题

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

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

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

:* 判断题

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

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

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

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

:* 单选题

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

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

:3.[图片1][图片2][图片3]以下程序的输入数据的绝对值均不超过𝟏𝟎^𝟑。完成下面的判断题和单选题：

:* 判断题

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

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

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

:* 单选题

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

Q33:5）（2 分） 对于以下的输入数据，输出结果为 。5 52 8 15 1 105 19 19 3 56 6 2 8 212 16 3 8 1712 5 3 14 131 1 1 1 1 1

Q34:6） 2 分） 对于以下的输入数据，输出结果为 。2 52 8 15 3 105 19 19 3 51 2 3 4 5 6

:分割线

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

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

Q35:1) ①处应填()

Q36:1) ②处应填()

Q37:③处应填( )。

Q38:④处应填( )。

Q39:④处应填( )。

Q40:⑤ 处应填（ ）。

: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][图片2]

Q41:1） ① 处应填 。

Q42:1） ① 处应填 。

Q43:2） ② 处应填 。

Q44:3） ③ 处应填 。

Q45:4） ④ 处应填 。

Q46:4） ⑤处应填 。