CSP-J初赛模拟训练（3）

一、单项选择题 （共15题，每题2分，共计30分；每题有且仅有一个正确选项）
*
您的姓名：
*
1) 不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢排列的是（）
A.快存/辅存/主存
B.外存/主存/辅存
C.快存/主存/辅存
D.主存/辅存/外存
*
2) RAM中的信息是（）
A.生产厂家预先写入的
B.计算机工作时随机写入的
C.防止计算机病毒侵入所使用的
D.专门用于计算机开机时自检用的
*
3) 在24*24 点阵的字库中，汉字“一”与“编”的字模占用字节数分别是（）
A.72、72
B.32、32
C.32、72
D.72、32
*
4) 计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知64位的奔腾处理器一次能处理 64个信息，相当于（）字节
A.8个
B.1个
C.16个
D.2个
*
5) 在计算机领域中，通常用英文单词“BYTE”来表示（）
A.字
B.字长
C.二进制位
D.字节
*
6) GB2312-80规定了- -级汉字3755 个，二级汉字3008 个，其中二级汉字字库中的汉字是以（）为序排列的。
A.以笔划的多少
B.以部首
C.以ASCII码
D.以机内码
*
7) 设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4, 5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈):进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是（）
A.{5，4，3，2，1}
B.{2，1}
C.{2，3}
D.{3，4}
*
8) 设循环队列中数组的下标范围是n,其中头尾指针分别是f和r，则其元素个数是（）
A.r-f
B.r-f+1
C.(r-f) MOD n+1
D.(r-f+n) MOD n
*
9) 电线上停着两种鸟(A, B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类: 一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知:电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）
A.奇数
B.偶数
C.可奇可偶
D.数目固定
*
10) 从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为（）
A.插入排序
B.归并排序
C.选择排序
D.快速排序
*
11) 计算机中的数值信息分为整数和实数(浮点数)。实数之所以能够表示很大或者很小的数,是由于使用了（）。
A.阶码
B.补码
C.反码
D.较长的尾数
*
12) 下列哪个软件不是操作系统软件的名字（）。
A.WindowsXP
B.Arch/Info
C.Linux
D.OS/2
*
13) 下列哪个不是个人计算机的硬件组成部分（）。
A.主板
B.虚拟内存
C.总线
D.硬盘
*
14) 已知元素(8，25，14，87，51, 90，6，19， 20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足:8在51前面:90在87的后面;20在14的后面:25在6的前面；19在90的后面。（）
A.20，6，8，51，90，25，14，19，87
B.51，6，19，20，14，8，87，90，25
C.19，20，90，7，6，25，51，14，87
D.6，25，51，8，20，19，90，87，14
*
15) 假设我们用d=(a1,a2....,a5), 表示无向图G的5个顶点的度数，下面给出的哪组值合理（）。
{2，2，2，2，2}
{1，2，2，1，1}
{3，3，3，2，2}
{5，4，3，2，1}
*
二、阅读程序 （程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题4分，共计40分）


16) (1分)第19行输入97时，输出为“NO” (不含引号)。（）
A对
B错
*
17) (1分)第19行输入119时，输出为“YES” (不含引号)。（）
A对
B错
*
18) 若将第7行的“<=”改成“<”，程序输出的结果一定不会改变。（）
A对
B错
*
19) 当程序执行第14行时，i 值为 sqrt(num) 。（）
A对
B错
*
20) （3分）最坏情况下，此程序的时间复杂度是（）。
A.O(num)
B.O(num^2)
C.O(sqrt(num))
D.O(lognum)
*
21) 若输入的 num 为 20 以内的正整数，则输出为 “YES” 的概率是 （） 。
A.0.45
B.0.4
C.0.5
D.0.35
*

22) (1分)将第9行和第11行的括号去掉，程序输出结果一定不变。（）
A对
B错
*
23) (1分)将第12行的“mi>>=1”改为“mi*=0.5”，程序输出结果一定不变。（）
A对
B错
*
24) 若输入为“4 4”，则输出为“78”。（）
A对
B错
*
25) 此程序的时间复杂度为O(logn )。（）
A对
B错
*
26) 若输入为“3 4”，则输出为（）。
A.8
B.12
C.18
D.19
*
27) kasumi (2046,13)的返回值为（）。
A.0
B.2022
C.2
D.2024
*

28) (1分)程序结束时，对任意1≤i≤n， mark[i]=0。（）
A对
B错
*
29) (2分)若n<r，则程序无输出
A对
B错
*
30) (2分)若输入为“4 3”，则输出中数字1和2的个数不同。（）
A对
B错
*
31) (2分)此程序的时间复杂度为O(n)。（）
A对
B错
*
32) 若输入为“6 3”，则函数print的执行次数为（）。
A.60
B.120
C.6
D.720
*
33) 若输入为“7 4”，则输出的最后一行为（）。
A.4 5 6 7
B.7 6 5 4
C.4 3 2 1
D.1 2 3 4
三、完善程序 （单选题，每题3分，共计30分）
克鲁斯卡尔求最小生成树思想:首先将n个点看做n个独立的集合，将所有边快排(从小到大)。然后，按排好的顺序枚举每一条边， 判断这条边连接的两个点是否属于一个集合。若是，则将这条边加入最小生成树，并将两个点所在的集合合并为一个集合。若否，则跳过。直到找到n-1条边为止。

*
34) ①处应填（）
A.a.v ＜ b.v
B.a.v > b.v
C..a.v >= b.v
D.a.v ＜=b.v
*
35) ②处应填（）
A.father(x)
B.father(fat[x])
C.fat[father(x)]
D.father(father(x))
*
36) ③处应填（）
A.algorithm
B.point
C.cmp
D.sizeof(a)
*
37) ④处应填（）
A.a[i].y
B.father(a[i].y)
C.fat[a[i].y]
D.a[i].x
*
38) ⑤处应填（）
A.cnt > 0
B.i == 1
C.ans == n-1
D.cnt == n-1
*
(最小区间覆盖)给出n个区间，第i个区间的左右端点是$[a_i, b_i]$。现在要在这些区间中选出若干个，使得区间[0, m]被所选区间的并覆盖(即每一个$0≤i≤m$都在某个所选的区间中)。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数$n$和$ m (1≤n≤5000, 1≤m≤10^9)$。
接下来n行，每行两个整数$a_i, b_i (0≤ai, bi≤m)$。
提示:使用贪心法解决这个问题。先用$θ(n^2)$的时间复杂度排序，然后贪心选择这些区间。
试补全程序。

39) ①处应填（）
A.A[j].b ＜ A[j-1].b
B.A[j].a ＜ A[j-1].a
C. A[j].a > A[j-1].a
D.A[j].b > A[j-1].b
*
40) ②处应填（）
A. A[j+1]=A[j]; A[j]=t;
B.A[j-1]=A[j]; A[j]=t;
C.A[j]=A[j+1];A[j+1]=t;
D.A[j]=A[j-1];A[j-1]=t;
*
41) ③处应填（）
A. A[i].b > A[p-1].b
B.A[i].b < A[i-1].b
C. A[i].b > A[i-1].b
D.A[i].b < A[p-1].b
*
42) ④处应填（）
A. q+1
B.q+1
C.q
D.q
*
43) ⑤处应填（）
A. r = max(r, A[q+1].b)
B.r = max(r, A[q].b)
C.r = max(r, A[q+1].a)
D.q++
问卷星提供技术支持
举报