2024CSP-J原创初赛模拟卷4

（认证时间：2023年9月16日 09:30~11:30）
*
基本信息：
姓名：
姓名：
班级：
班级：
学校:
学校:

一、单项选择题（每题只有一个正确选项，每题2分，共30分）

*
1．45和30的最小公倍数是（）
A.30
B.45
C.90
D.180
*
2．下列不同数制的数中，最大的一个数是（）。
A.十进制数220.1
B.二讲制数11011011
C.八进制数334.1
D.十六进制数DC.1
*
3．字母在计算机中是以编码形式表示的，通用的编码是 ASCII码，字母 “A”的 ASCII码 65 ，字母“E”的ASCII码是 （）。
A.05
B.52
C.69
D.68
*
4．计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知64位的奔腾处理器一次能处理 64个信息，相当于（）字节
A.8个
B.1个
C.16个
D.2个
*
5．在计算机领域中，通常用英文单词“BYTE”来表示（）。
A字
B.字长
C.二进制位
D.字节
*
6．一棵树T有 2 个度数为2 的结点、有1个度数为3的结点、有3个度数为4的结点，那么树T有（）个树叶。
A.14
B.6
C.18
D.7
*
7．在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A.1/2
B.1
C.2
D.4
*
8．下列IP地址中正确的是（）。
A.202.300.12.4
B.192.168.0.3
C.100:128:35:91
D.111-102-35-21
*
9．设有100个顶点，利用二分法查找时，最大比较次数是（） 。
A.50
B.10
C.25
D.7
*
10．一棵二叉树的中序遍历序列为:DGBAECHF，后序遍历序列为:GDBEHFCA，则前序遍历的序列是（）。
A.ABCDFGHE
B.ABDGCEFH
C.ACBGDHEF
D.ACEFHBGD
*
11．今年信息学进复赛的同学有6人，老师将他们排成一圈分发奖品，请问有几种排法（）。
A.60
B.120
C.180
D.240
*
12．甲箱中有200 个螺杆，其中有160 个A型螺杆:乙箱中有240 个螺母，其中有180个A型的。现从甲乙两箱中各任取一个，则能配成A型螺栓的概率为多少?（）
A.1/20
B.19/20
C.3/5
D.15/16
*
13．在数据结构中，链表是（）。
A.顺序存储的线性表结构
B.非顺序存储的线性表结构
C.非师序在储的非线性表结构
D.顺序存储的非线性表结构
*
14．C++ 程序运行时，是在哪个存储器上进行的?（）。
A.硬盘
B.RAM
C.ROM
D.CACHE
*
15．当 A>=B && B>=C 的取值为真时，表达式A>C||B==C的值（）。
A.为真
B.无法判定结果的真假
C.也有可能为假
D.只有当A、B、C都相等时才为真

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

1.

注：


● 判断题

*
16..函数C的作用是求。( )
对
错
*
17..第 24 行计算得到的 x 每次比上一次计算得到的大。（ ）
对
错
*
18..存在一组范围内的 a, b 使程序会陷入死循环。（ ）
对
错
*
19..若输入 n=3,m=2,a = 155, b = 229，程序各执行第 27,28 行八次。（ ）
对
错
*
20.假设不考虑上述代码中的n、m以及C函数，完成下列两题:
.设 N 为 max (a, b)，最优情况下，此程序的时间复杂度是（）。
A.O(1)
B.O(log N)
C.O(N)
D.O(N log N)
*
21.（4分）设 N 为 max (a, b)，最坏情况下，此程序的时间复杂度是（）。
A.O(1)
B.O(log N)
C.O(N)
D.O(N log N)
2.


● 判断题

*
22..a 数组为邻接表，是一种存储无向图的结构。（ ）
对
错
*
23..将第 4 行 inf 的取值改成 3e9 不影响程序运行结果。（ ）
对
错
*
24..函数 solve(int s, int res[])中的 res 是指针形参，在函数内对res 数组的修改会同时作用于作为实参的数组。( )
对
错
*
25..若输出大于等于 inf，则 0 号结点不与 1 号结点连通。（ ）
对
错
*
26..（4分）若图连通且边权全为 1，此时程序输出 6，n 最小为（）。
A.4
B.5
C.6
D.7
*
27..（4 分）忽略 m，最坏情况下，此程序的时间复杂度是（）。
A.O(n^2)
B.O(n^2 log n)
C.O(n^3)
D.O(n^n)
3.

● 判断题


*
28..对于 1 ≤ x ≤ n，若不存在 a[i] = x，则程序执行到第18 行时 last[x] 为 0。（ ）
对
错
*
29..若对 1 < i ≤ n 满足 a[i-1] <= a[i]，则输出为 。（ ）
对
错
*
30..存在一组输入使得输出为 2。（ ）
对
错
*
31..程序输出时，对 1 ≤ i ≤ n 一定满足 pre[i] >= suf[i]。（ ）
对
错
*
32.. 若 n = 10 且程序输出 18，输入的 a 数组从 1 到 n 可能是:（）。
A.1 6 2 5 3 4 8 10 9 7
B.1 6 2 5 3 4 8 9 10 7
C.1 6 2 5 8 3 4 10 9 7
D.1 6 2 5 8 3 4 9 10 7
*
33.. （4 分）以下哪项操作不会影响程序运行结果:(B
)
A.交换第 21 行和第 22 行的代码
B.将第 27 行的 ＜ 修改为 ＜=
C.将第 32 行的 <= 修改为 <
D.移除第 34 行的代码

1.云云有n个幸运数字 。此外，他定义正整数x是厄运的，当且仅当它不是任何一个幸运数字的倍数。他想知道有多少个小于等于k的正整数是厄运的。

输入第一行给定幸运数字的个数和上界。第二行有n个数，即幸运数字 。

输出合法正整数的个数。

提示：本题可以使用容斥原理，比如说我们有4个数字：2、5、11、13，那我们可以先求出<=k的有多少个他们的倍数，这里假设有a、b、c、d个，然后分别求有多少个数是10、22、26、55、65、143的倍数（这几个数字是2、5、11、13两两组合的最小公倍数），然后求<=k有多少个数是他们的倍数，假设是e、f、g、h、i、j，以此类推......那么最终的答案就是ans = n - (a+b+c+d) + (e+f+g+h+i+j) - ... + ...个。

试补全程序。


*
34.①处应填（）
A. get(x % y, y)
B. get(y % x, x)
C. get(y, x % y)
D. get(x, y % x)
*
35.②处应填（）
A. s * k / prod
B. s * k / get(prod, k)
C. k – s * k / prod
D. k – s * k / get(prod, k)
*
36.③处应填（）
A. -s
B. !s
C. get(prod, a[i]) != 1 ? 0 : s
D. get(prod, a[i]) != 1 ? s : -s
*
37.④处应填（）
A. prod * a[i]
B. prod * a[i] / get(prod, a[i])
C. prod * get(prod, a[i])
D. prod / get(prod, a[i]) * a[i]
*
38.⑤处应填（）
A. 0
B. -1
C. 1
D. n % 2 ? -1 : 1

2.一套牌由n张数字牌(从1到n)和n张空牌(用0标注)组成，其中n张牌在你手中，其余形成牌堆。一次操作可以将手中的任意一张牌置入牌堆底，并从牌堆顶摸入新的手牌。求最少多少次操作能让最终手牌均为空牌，且牌堆从上到下第i张牌恰好数值为i。

输入第一行给定数字牌个数第二行有n个数，分别表示初始你的每张手牌，空牌以0标注。第三行有n个数，第i个数表示初始从上到下第i张牌的数值，空牌以0标注。输出达到目标最少的操作数。

提示：可以采用贪心解决这个问题，最优策略一定是下面两种之一：

•存在x，依次从手牌中取出x张空牌，再依次取出数值牌1,2,…,n

•存在 x，依次从手牌中取出数值牌x,x+1,…, n

试补全程序。



*
39.①处应填（）
A.p[i] = b[i]
B.p[n + 1 – i] = b[i]
C.p[b[i]] = i
D.p[b[i]] = n + 1 – i
*
40.②处应填（）
A. p[i] + i - 1 + n
B.i – p[i] – 1 + n
C.i - p[i] + 1 + n
D.p[i] - i + 1 + n
*
41.③处应填（）
A.p[i] == p[1] + i - 1
B.p[i] == p[1] - i + 1
C.p[i] >= p[1] + i - 1
D.p[i] >= p[1] - i + 1
*
42.④处应填（）
A.p[j] == j – i
B.p[j] <= j – i
C.p[j] == p[1] - j + 1
D.p[j] >= p[1] + j - 1
*
43.⑤处应填（）
A.ans < t
B.ans > t
C.i <= n
D.i <= t
问卷星提供技术支持
举报