2024CSPJ初赛模拟题(三)
一、单项选择（共 15 题，每题 2 分，共计 30 分）
1、信息论的奠基者是( )
{{ select(1) }}
- 冯.诺伊曼
- 艾伦 ·麦席森 · 图灵
- 克劳德 ·艾尔伍德 ·香农
- 姚期智
2、下列不同的进制数中,与其他三项不同的是( )
{{ select(2) }}
- (1000011)2
- (67)10
- (103)8
- (45)16
3、采用八位二进补码表示十进制整数-128，则其表示形式为？ ()
{{ select(3) }}
- 00000000
- 00000001
- 10000000
- 11111111
4、表 达 式 a*b+c*d 的后缀形式是()。
{{ select(4) }}
- ab*cd*+
- abc+*d*
- a*bc*d+
- b+c*a*d
5、基于比较的排序算法最优的时间复杂度为（）。
{{ select(5) }}
- O(n)
- O(1)
-
-
6、已知一个程序的时间复杂度满足 T(1)=1,T(n)=2T(n/2)+n,问该程序的时间复 杂度为（）。 {{ select(6) }}
- O(n)
- O(2n)
-
-
7、分辨率为 1920×1080、64 位色的位图 ， 存储图像信息所需的空间约为（ ） {{ select(7) }}
- 8MB
- 16MB
- 32MB
- 64MB
8、以下二叉树的中序遍历为 （）
{{ select(8) }}
- ABCDEFG
- CBDAEFG
- CDBGFEA
- CBDEFGA
9、对于入栈顺序为 a,b,c,d,e,f,g 的序列,出栈顺序为 d,f,e,g,c,b,a,则栈 的深度至少为()
{{ select(9) }}
- 4
- 5
- 6
- 7
10、 现要在双向链表中的指针 p 后插入一个由指针 s 指向的结点,下列代码正 确的是( )
{{ select(10) }}
- p->next=s; s->prev=p;s->next=p->next; p->next->prev=s;
- s->prev=p;p->next=s; s->next=p->next; p->next->prev=s;
- s->prev=p; s->next=p->next; p->next->prev=s; p->next=s;
- s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
11、1582 年以来公历的置闰规则： 普通闰年：公历年份是 4 的倍数，且不是 100 的倍数的，为闰年（如 2004 年、 2020 年等就是闰年）。 世纪闰年：公历年份是整百数的，必须是 400 的倍数才是闰年（如 1900 年不是 闰年，2000 年是闰年）。已知年份 x>1582,以下哪一个逻辑表达式可以正确判定闰年( )。
{{ select(11) }}
- x%4==0&&x%100!=0
- x%4==0|| (x%400==0&&x%100!=0)
- x%4==0&&(x%100!=0||x%400==0)
- x%4==0&&x%400==0&&x%100!=0
12、考虑如下递归算法，问调用 solve(24,64)的返回值 ( )
solve(n,m)
if m==0 return n
else return solve(m, n%m)
{{ select(12) }}
- 4
- 8
- 12
- 16
13、有 6 个人排成一排，其中有两个人撞衫了，不能站在相邻的位置，问有多少 种排队方式 ( )
{{ select(13) }}
- 720
- 600
- 480
- 320
14、数位之和为 10 的四位数有( )种
{{ select(14) }}
- 218
- 219
- 220
- 240
15、有 5 名同学，每个同学有一个座位，现在每个同学都不想坐在自己的座位上， 问一共有多少种坐法（ ）
{{ select(15) }}
- 120
- 72
- 60
- 44
二、阅读程序（除特殊说明外，判断题 1.5 分，选择题 4 分，共计 40 分）
1、
保证输入的 n 和 m 为不超过 1,000,000 的正整数
16、 第 7 行，a&1 改成 a%2,程序结果不变( ) {{ select(16) }}
- 正确
- 错误
17、 第 6 行,条件改成仅为 a&1,程序结果不变( ) {{ select(17) }}
- 正确
- 错误
18、 第 6 行,条件改成仅为 b&1,程序结果不变() {{ select(18) }}
- 正确
- 错误
19、 输出结果不可能为 0( ) {{ select(19) }}
- 正确
- 错误
20、 该算法的时间复杂度为( ) (3 ’)
{{ select(20) }}
- O(n)
- O(logn)
- O(nlogn)
21、 输入 192 80 ,输出结果为( ) (3 ’)
{{ select(21) }}
- 40
- 80
- 16
- 8
2、
输入的 n 为不超过1000000的正整数，接下来 n 个数为 1000000 范围内的正整数。
22、 solve2()实现了选择排序。 ( )
{{ select(22) }}
- 正确
- 错误
23、 solve1()函数的时间复杂度为 O(n+V)，其中 V 指的是 ai 的最大值。 ( )
{{ select(23) }}
- 正确
- 错误
24、 当输入数据为 7 2 3 5 7 1 4 6, solve2 函数内的 cnt 最终为 9。 ( )
{{ select(24) }}
- 正确
- 错误
25、若将第 24 行的双斜杠删除，不会影响输出结果。 ( )
{{ select(25) }}
- 正确
- 错误
26、下列哪组数据，solve1 和 solve2 的输出结果不同 ( )。
{{ select(26) }}
- 5 1 2 3 4 5
- 6 111 222 3 4 6 7
- 7 123 456 432 243 213 342 343
- 8 111 222 333 444 555 666 333 111
27、将第 9 行改为( )，可以使 solve1 和 solve2 的输出保持一致。
{{ select(27) }}
- while(b[i])
- while(--b[i])
- while(b[i]--)
- if(b[i]>1)
3、
输入：第一行两个正整数n,m, 接下来输入 n*m 的字符矩阵，由 F 或 X 组成。 (1<=n,m<=1000)
28、 若删除第 17 行， 程序结果不变。 ( )
{{ select(28) }}
- 正确
- 错误
29、 若删除第 19 行， 程序结果不变。 ( )
{{ select(29) }}
- 正确
- 错误
30、 若将第 7 行改为 int maxx=-1； 程序结果可能会产生错误。 ( )
{{ select(30) }}
- 正确
- 错误
31、单次 ask 函数的时间复杂度是 O(m)。 ( )
{{ select(31) }}
- 正确
- 错误
32、 若输入为：
3 4
FXFX
FFFX
XFFX
输出为 ( )。
{{ select(32) }}
- 3
- 4
- 5
- 7
33、 若输入为：
3 4
FXFX
FFFF
XFFF
maxx 变化了 ( )次。
{{ select(33) }}
- 3
- 4
- 5
- 6
三、完善程序（单选题，每小题 3 分，共计 30 分）
1、（链表反转）单向链表反转是一道经典算法问题，比如有一个链表是这样的， 1->2->3->4->5，反转后成为 5->4->3->2->1。现给定如下链表节点的定义：
struct LinkNode{
int value;
LinkNode* next;
};
非递归实现：
LinkNode* Reverse(LinkNode* header){
if (header == NULL || header->next == NULL){
return header;
}
LinkNode* pre = header, *cur = header->next;
pre->next = NULL; while(cur != NULL) {
LinkNode* next = 1 ;
2 = pre;
pre = cur;
cur = next;
}
return pre;
}
递归实现：
LinkNode * Reverse(LinkNode * head){
if (head == NULL || head->next == NULL){
return head;
}
LinkNode * newhead = 3 ;
4 = head;
head->next = 5 ;
return newhead;
}
34、上述程序 1 中应该填写（）
{{ select(34) }}
- pre-> next
- cur-> next
- header-> next
- NULL
35、上述程序 2 中应该填写（）
{{ select(35) }}
- pre-> next
- cur-> next
- header-> next
- NULL
36、上述程序 3 中应该填写（）
{{ select(36) }}
- Reverse(head)
- Reverse(pre)
- Reverse(cur)
- Reverse(head->next)
37、上述程序 4 中应该填写（）
{{ select(37) }}
- newhead->next
- head-> next
- head-> next->next
- NULL
38、上述程序 5 中应该填写（）
{{ select(38) }}
- newhead->next
- head-> next
- head-> next->next
- NULL
2、设备检测
有 n 个器件,要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先 级。优先级有 m 个为等级, 由高到低分别用 0~m-1 的整数表示。每个器件的送达时间各不 相同。已送达的器件按照各优先级通道分别排队,先到达先入队。设备每次检测都从当前各 非空队列中,选取优先级最高的队列的队首器件出队进行检测。(同一时刻出现入队和出队时, 先处理入队。)
输入 n 个器件的信息，输出任务的执行顺序
提示：
bool operator<(const Work a)const{
return t<a.t;
}
以上程序功能为默认结构体中的 t 按照从小到大的规则排序。
39、①处应填（ ）
{{ select(39) }}
- i<=n
- cnt
- i<=n && cnt
- i<=n || cnt
40、②处应填（）
{{ select(40) }}
- a[i].t>T
- !cnt
- !cnt && a[i].t>T
- !cnt || a[i].t>T
41、③处应填（）
{{ select(41) }}
- link[tail[a[i].rk]]=i;
- link[i]= tail[a[i].rk];
- head[tail[a[i].rk]]=i;
- head[i]= tail[a[i].rk];
42、 ④处应填（）
{{ select(42) }}
- ans[++now]=a[head[j]].id;
- ans[++now]=i;
- ans[++now]=head[j];
- ans[++now]=j;
43、 ⑤处应填（）
{{ select(43) }}
- T = a[head[j]].t;
- T = T+a[head[j]].len;
- T = a[tail[j]].t;
- T = a[tail[j]].t+a[tail[j]].len;