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

1. 网址 www.luogu.com.cn 当中，顶级域名是（ ）。

  A. www  B. cn  C. com.cn D. luogu

2. 以下物品可以携带进 CSP 第二轮测试考场的是（ ）。

  A. 可以发出巨大响声的发光机械键盘

  B. 写有 kkksc03 签名的《深入浅出程序设计竞赛 基础篇》的封皮

  C. 印有 dzd 照片（已设法获得其授权）的文化衫 T 恤

  D. 具有拍照功能的游标卡尺

3. 将元素 a,b,c,d,e,f 依次入栈，则以下选项中出栈序列不可能是（） 。

  A. b,d,c,f,e,a  B. f,e,d,c,b,a   C. d,c,e,b,f,a   D. d,c,f,b,e,a

4. 「流程结构」是编程中用于控制程序执行流程的一种方式．它包括顺序结构、分支结 构和循环结构．在一些诗歌作品中，也有对「流程结构」的体现．下列诗歌片段中体 现循环结构的是（ ）。

  A. 如果还能找到你，就让风儿告诉你。

  B. 只要我还能够行走，只要我还能够张望，只要我还能够呼吸，就一直走 向前方。

  C. 昔闻洞庭水，今上岳阳楼。

  D. 啊如果我在，战斗中牺牲，啊朋友再见吧，再见吧，再见吧！如果我 在，战斗中牺牲，你一定把我来埋葬。

5. 已知两个二进制整数 𝑎, 𝑏： 𝑎 = $1010001010_{(2)} ; 𝑏 = 1110100110_{(2)}$ 则表达式 (a&b)^(a|b) 的值为（ ）。

  A. $0011011010_{(2)}$  B. $0100101100_{(2)}$

  C.$0011010010_{(2)}$   D. $0100101000_{(2)}$

6. 一个有 10 个节点的有向图，要使得每一个满足 1 ≤ 𝑖,𝑗 ≤ 10, 𝑖 ≠ 𝑗 的点对 (𝑖,𝑗) 都 存在一条从 𝑖 到达 𝑗 的路径，至少需要连（ ）条有向边。

  A. 9   B. 10   C. 19   D. 20

7. 观察下列代码

int a[] = {5, 4, 3, 2, 1};
auto p = a + 3;
auto q = &p;
(*q) ++;
auto k = *p;

其中，𝑘 的类型以及 𝑘 的值分别为（）。

  A. int 类型，值为 1

  B. int 类型，值为 3

  C. int 指针类型，值为 𝑎 数组的下标为 3 的元素的地址

  D. int 指针类型，值为 𝑎 数组的下标为 4 的元素的地址

8. 中缀表达式 a+(b+c)-d*e/f 改写成后缀表达式为（ ）。

  A. a b + c + d e * f / -   B. a b c + + d e * f / -

  C. a b + c + d * e f / -   D. a b c + + d * e / f -

9. 一张大小为 6114 × 8192 的 24 位彩色图片，使用 .bmp 格式存储，占用的空间大小约为（ ）。

  A. 144 MiB   B. 288 MiB

  C. 1152 MiB   D. 48 MiB

10.中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。

  A.1983   B.1984   C.1985   D.1986

11. 十进制小数 0.3，转写成八进制为（ ）。

  A. 0.3   B. 0.2314631⋯   C. 0.2046204⋯   D. 0.3333333⋯

12. 依次抛出四个六面骰子，按照抛出顺序将骰子上的数值记为 𝑎, 𝑏, 𝑐, 𝑑。则 a < b; b > c; c < d 同时成立的概率为（ ）。

  A. 95/648   B. 4/27   C. 5/27   D. 1/6

13. 已知某种可用来维护序列的数据结构，支持$o(log 𝑛)$ 向某个位置后面插入元素、 $o(𝑛)$ 查询某个元素的排名，$o(𝑛 log 𝑛)$遍历整个序列，那么用上述三种操作实现插 入排序的时间复杂度最坏为（ ）。

  A. $o(𝑛^2 )$   B. $o(n^2 logn)$

  C. $o(n log n)$   D. $o(n log2 n)$

14.已知L是带头节点的单链表，节点P既不是头节点（第一个节点），也不是尾节点，删除P节点直接后继节点的语句序列是( )。

  A.P=P->next;   B.P->next=P;

  C.P->next=P->next->next;   D. P=P->next->next;

15.下列描述是面向对象编程的是（）。

  A.编写一个二分查找函数，用来查找升序序列数中的数。

  B.编写一个堆排序函数，实现对一维数组排序。

  C.创建一个飞机类，在游戏中实现移动、开火等动作。

  D.创建一个结构体student，包含学生的姓名、成绩、学号等成员。

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

(1)

01 #include <iostream>
02 #include <cstring>
03 using namespace std;
04 string s, t;
05 string a, b;
06 int main(){
07     getline(cin, s);
08     getline(cin, a);
09     getline(cin, b);
10     for(int i = 0;i < s.size();i ++){
11         bool flag = true;
12         if(i + a.size() <= s.size()){
13             for(int j = 0;j < a.size();j ++){
14                 char p = s[i + j], q = a[j];
15                 if('a' <= p && p <= 'z') p = p - 'a' + 'A';
16                 if('a' <= q && q <= 'z') q = q - 'a' + 'A';
17                 if(p != q)
18                     flag = false;
19             }
20         } else
21                 flag = false;
22
23         if(flag == true){
24             t += b;
25             i += a.size() - 1;
26         } else
27             t += s[i];
28     }
29     cout << t << endl;
30     return 0;
31 }

保证输入的三行字符串的长度均不超过 $𝟏𝟎^ 𝟑$，且每个字符串均由 ASCII 可视字符或 空格组成且非空。完成下面的判断题和单选题：

⚫判断题

16. 保持 s,b 的字母大小写不变，将 a 里的小写英文字母改写成大写、将大写英文字母改写成小写，输出结果不变。（ ）
17. 每次调用 s.size()的复杂度是 O(1) 的，但若是把 s.size()替换成s.length() 则调用的复杂度将会变成 O(l)，其中 l 是 s 当前的长度。这是因为s.length() 作为 strlen() 函数的 string 版本，会每次重新计算 s 最后一个元素的位置。（ ）
18. 当输入的字符串 s,a,b 均由小写字母 a 或 b 组成，记 s,a,b 的长度分别为n,m,k，则程序的时间复杂度最坏为 O(nm+nk)。（ ）
19. 当输入的字符串 s,a,b 均由小写字母 a 组成，记 s,a,b 的长度分别为 n,m,k且有n>m>k，那么上述程序的总复杂度为 O(n)。（ ）

⚫单选题

20. 针对下列输入数据，程序的输出为？。

National Olympiad in Informatics A154
A
C

  A. National Olympiad in Informatics C154

  B. NCtionCl OlympiCd in InformCtics C154

  C. National!

  D. Nctioncl Olympicd in Informctics C154

21. 针对下列输入数据，程序的输出为？。

abaabaaabaaaabaaaaabababab
aa
ab

  A. abABbABBbABBBbABBBBbababab

  B. ababbabbbabbbbabbbbbababab

  C. ababbababababbabababababab

  D. 程序陷入死循环/非正常退出，无法正常输出

(2)

01 #include<iostream>
02 using namespace std;
03 int a[100005], b[100005], n, m;
04 void very_quick_sort(int l, int r, int p, int q){
05 		if(l >= r || p > q){ // ①
06 		return;
07 }
08 int mid = (l + r) / 2;
09 int p0 = p - 1;
10 int q0 = q + 1;
11 for(int i = p;i <= q;i ++){
12 		if(a[i] > mid) b[++ p0] = a[i];
13 		else b[-- q0] = a[i];
14 }
15 for(int i = p;i <= q;i ++)
16 		a[i] = b[i];
17 very_quick_sort(mid + 1, r, p, p0);
18 very_quick_sort(l, mid, q0, q);
19 }
20 int main(){
21     cin >> n >> m;
22     for(int i = 1;i <= n;i ++)
23         cin >> a[i];
24     very_quick_sort(1, m, 1, n);
25 // ②
26     for(int i = 1;i <= n;i ++)
27         cout << a[i] << " ";
28     cout << endl;
29     return 0;
30 }

保证输入的 𝒏 不超过 𝟏𝟎𝟓，𝒎 不超过 𝟏𝟎𝟗，且 𝟏 ≤ 𝒂𝟏, 𝒂𝟐, ⋯ , 𝒂𝒏 ≤ 𝒎。完成下面的

判断题和单选题

⚫ 判断题

22. (1 分)上述代码实现了一种排序算法，可以将 a 数组按照从小到大的顺序排序。 （ ）
23. 如果在程序开始之前向 b 数组里写入数据（保证不会发生数组越界），则上述 代码的输出不会发生变化。 （ ）
24. 若 𝑛 = 𝑚，存在某种数据构造方式，使得上述代码运行的时间复杂度为 𝑂(𝑛 2 )，

这是因为算法本身是对快速排序的改进，但是这种改进不能避免由于对数组的划分不 够均等而在极端数据下导致复杂度发生退化。 （ ）

25. 如果将 ① 处的 l >= r 条件删除（同时删除 || 使得程序能正常编译运行，下 同），程序的时间复杂度不会发生变化；而将 p > q 条件删除，程序在某些数据下 的运行效率将会明显降低。 （ ）

⚫ 单选题

26. 不认为 𝑛, 𝑚 同阶，即可能出现 𝑛 远大于 𝑚 或者 𝑚 远大于 𝑛 的情况。则该 程序的最坏时间复杂度为（ ）。

A. $o(𝑛^2 + 𝑚^2 )$

B. $o(m log m)$

C. $o(m log n)$

D. $o(n log m)$

27. 若输入数据为：

10 10

10 4 5 2 2 3 1 5 8 3

那么在程序执行到 ② 位置时， b 数组 内的值为 （ ）。

  A. [10,8,3,5,1,3,2,2,5,4]

  B. [3,5,1,3,2,2,5,4,10,8]

  C. [10,8,5,5,4,3,3,2,2,1]

  D. [1,2,2,3,3,4,5,5,8,10]