一、单项选择题

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

【第 1 题】

关于图灵机下面的说法哪个是正确的（ ）。 {{ select(1) }}

• 图灵机是世界上最早的电子计算机
• 由于大量使用磁带操作，图灵机运行速度很慢
• 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用
• 图灵机只是一个理论上的计算模型

【第 2 题】

关于计算机内存下面的说法哪个是正确的（ ）。 {{ select(2) }}

• 随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的
• 1MB 内存通常是指 1024×1024 字节大小的内存
• 计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分
• 一般内存中的数据即使在断电的情况下也能保留 2 个小时以上

【第 3 题】

关于 BIOS 下面说法哪个是正确的（ ）。

{{ select(3) }}

• BIOS 是计算机基本输入输出系统软件的简称
• BIOS 里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序
• BIOS 一般由操作系统厂商来开发完成
• BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能

【第 4 题】

以下哪一种设备属于输出设备（ ）。 {{ select(4) }}

• 扫描仪
• 键盘
• 鼠标
• 打印机

【第 5 题】

1 MB 等于（ ）。 {{ select(5) }}

• 1000 字节
• 1024 字节
• 1000 ×1000 字节
• 1024 × 1024 字节

【第 6 题】

中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。 {{ select(6) }}

• 1983
• 1984
• 1985
• 1986

【第 7 题】

如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、 字母键 A、字母键 S、字母键 D、字母键 F 的顺序循环按键，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第 81 个字符是字母（ ）。 {{ select(7) }}

• A
• S
• D
• a

【第 8 题】

根节点深度为 0，一棵深度为 h 的满 k(k>1) 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ ）个结点。 {{ select(8) }}

• $\frac{k^{h+1}-1}{k-1}$
• $k^{h-1}$
• $k^h$
• $\frac{k^{h-1}}{k-1}$

【第 9 题】

给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的 数，至少需要 N−1 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（ ）次比较操作。 （⌈⌉ 表示向上取整，⌊⌋ 表示向下取整）（ ）。 {{ select(9) }}

• $⌈\frac{3N}{2}⌉-2$
• $⌊\frac{3N}{2}⌋-2$
• $2N-2$
• $2N-4$

【第 10 题】

为了统计一个非负整数的二进制形式中 1 的个数，代码如下：

int CountBit(int x) {
    int ret = 0;
    while (x) {
        ret++;
        ___________;
    }
    return ret;
}

则空格内要填入的语句是（ ）。

{{ select(10) }}

• x >>= 1
• x &= x - 1
• x |= x >> 1
• x <<= 1

【第 11 题】

下列协议中与电子邮件无关的是（ ）。 {{ select(11) }}

• POP3
• SMTP
• WTO
• IMAP

【第 12 题】

分辨率为 800×600、16 位色的位图，存储图像信息所需的空间为（ ）。

{{ select(12) }}

• 937.5 KB
• 4218.75 KB
• 4230 KB
• 2880 KB

【第 13 题】

计算机应用的最早领域是（ ）。

{{ select(13) }}

• 数值计算
• 人工智能
• 机器人
• 过程控制

【第 14 题】

NOI 的中文意思是（ ）。

{{ select(14) }}

• 中国信息学联赛
• 全国青少年信息学奥林匹克竞赛
• 中国青少年信息学奥林匹克竞赛
• 中国计算机协会

【第 15 题】

阅读如下程序：

#include <cstdio>
char st[100];

int main() {
	scanf("%s", st);
	for (int i = 0; st[i]; ++i) {
		if ('A' <= st[i] && st[i] <= 'Z')
		st[i] += 1;
	}
	printf("%s\n", st);
	return 0;
}

输入：QuanGuoLianSai

输出为？（ ）

{{ select(15) }}

• RUANHUOMIANTAI
• quanguoliansai
• RuanHuoMianTai
• ruanhuomiantai

二、阅读程序

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

阅读程序（一）

1. #include <iostream>
2. using namespace std;
3.
4. int main() {
5.      int a, b, u, i, num;
6.      cin >> a >> b >> u;
7.      num = 0;
8.      for (i = a; i <= b; i++)
9.         if ((i % u) == 0)
10.             num++;
11.     cout << num << endl;
12.     return 0;
13. }

判断题

16. u 可以为 0。 {{ select(16) }}

• 正确
• 错误

17. b-a 一定不小于 num。 {{ select(17) }}

• 正确
• 错误

18. 输入1 9 2，输出 4。 {{ select(18) }}

• 正确
• 错误

19. 该程序复杂度与 u 有关。 {{ select(19) }}

• 正确
• 错误

20. 输出结果为 10，输入数据可能为（ ）。 {{ select(20) }}

• 10 27 2
• 20 30 10
• 5 99 3
• 41 83 4

21. 输入151 981 7，输出结果为（ ）。 {{ select(21) }}

• 117
• 118
• 119
• 120

阅读程序（二）

1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. const int N = 1e6 + 10;
5.
6. int n, m;
7. int w[N], c[N]; 
8.
9. int f(int m, int n){
10.	   if(n == 0)
11.		  return 0;
12.	   int x = f(m, n - 1);
13.	   int y = 0;
14.	   if(m - w[n] >= 0) 
15.		  y = f(m - w[n], n - 1) + c[n];
16.	   return max(x, y);
17. }
18.
19. int main() {
20.
21. 	cin >> m >> n;
22. 	for(int i = 1; i <= n; i++)
23. 		cin >> w[i] >> c[i];
24.		
25.	    cout << f(m, n);
26.
27.     return 0;
28. }

假设输入的 n 是不超过 200 的正整数，m 是不超过 30 的正整数，w[i]、c[i] 都是不超过 5000 的正整数，完成下面的判断题和单选题：

判断题

22. main 函数里的 m 和 n 变量，与 f 函数里面的 m 和 n 变量，占用内存中的不同空间。 {{ select(22) }}

• 正确
• 错误

23. 输入 m 为 0，此程序可能会死循环或发生运行错误。 {{ select(23) }}

• 正确
• 错误

选择题

24. 若输入 2 2 1 2 3 4 则输出为（ ）。 {{ select(24) }}

• 0
• 2
• 6
• 10

25. 若输入 10 2 1 2 3 4 则输出为（ ）。 {{ select(25) }}

• 0
• 2
• 6
• 10

26. 若输入 10 4 2 1 3 3 4 5 7 9 则输出为（ ）。 {{ select(26) }}

• 8
• 10
• 12
• 14

27. 若输入 20 10，接下来的输入是 1 到 20，则输出为（ ）。 {{ select(27) }}

• 100
• 110
• 20
• 24

阅读程序（三）

1. #include <bits/stdc++.h>
2. using namespace std;
3. long long a[100010], b[100010], ans;
4.
5. void f(int L, int R){
6.	   if(L == R) return;
7.	   int mid = (L + R) >> 1;
8.	
9.	   f(L, mid);
10.	   f(mid + 1, R);
11.	   int i = L, j = mid + 1, k = L;
12.	   while(i <= mid && j <= R){
13.		  if(a[i] > a[j]){
14.			 ans += j - k;
15.			 b[k++] = a[j++];
16.		  }
17.		  else
18.			 b[k++] = a[i++];
19.	   }
20.	
21.	   while(i <= mid) b[k++] = a[i++];
22.	   while(j <= R) b[k++] = a[j++];
23.	   for(int i = L; i <= R; i++) a[i] = b[i];
24. }
25.
26. int main() {
27.	
28.	   int n;
29.	   cin >> n;
30.	   for(int i = 1; i <= n; i++)
31.		  cin >> a[i];
32.	   f(1, n);
33.	   cout << ans << endl;
34.
35.    return 0;
36. }

判断题

28. 去掉第 6 行，程序运行结果相同。 {{ select(28) }}

• 正确
• 错误

29. 第 21 行与第 22 行交换一下，程序运行结果相同。 {{ select(29) }}

• 正确
• 错误

30. 第 7 行改为 int mid=(L+R)/2，程序运行结果相同。 {{ select(30) }}

• 正确
• 错误

31. 该算法的原理是归并排序。

{{ select(31) }}

• 正确
• 错误

单选题

32. 该程序的时间复杂度为（ ）。 {{ select(32) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• $O(n\sqrt{n})$

33. 程序输入 4 3 2 3 2，则输出为（ ）。 {{ select(33) }}

• 2
• 3
• 4
• 5

34. 程序输入 4 6 5 2 4，则执行到 33 行时，数组 a 的数据为（ ）。 {{ select(34) }}

• 6 5 2 4
• 6 5 4 2
• 2 4 6 5
• 2 4 5 6

三、完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序（一）

（找位置） 对于一个 1 到 n 的排列 P（即 1 到 n 中每一个数在 P 中出现了恰好一次），令 q[i] 为第 i 个位置之后第一个比 P[i] 值更大的位置，如果不存在这样的位置，则 q[i] = n + 1。举例来说，如果 n = 5 且 P 为 1 5 4 2 3 ，则 q 为 2 6 6 5 6。

下列程序读入了排列 P ，使用双向链表求解了答案。试补全程序。

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int L[N], R[N], a[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ① ;
    }

    for (int i = 1; i <= n; ++i) {
        R[i] = ② ;
        L[i] = i - 1;
    }

    for (int i = 1; i <= n; ++i) {
        L[ ③ ] = L[a[i]];
        R[L[a[i]]] = R[ ④ ];
    }

    for (int i = 1; i <= n; ++i) {
        cout << ⑤ << " ";
    }

    cout << endl;
    return 0;
}

35. ① 处应填（ ）。

{{ select(35) }}

• a[i] = x
• a[x] = i
• a[x] = i+1
• a[i] = x+1

36. ② 处应填（ ）。

{{ select(36) }}

• i
• i-1
• i+1
• i+2

37. ③ 处应填（ ）。

{{ select(37) }}

• L[a[i]]
• R[a[i]]
• a[i]
• R[i]

38. ④ 处应填（ ）。

{{ select(38) }}

• a[i]
• L[a[i]]
• R[a[i]]
• i

39. ⑤ 处应填（ ）。

{{ select(39) }}

• a[i]
• R[a[i]]
• L[i]
• R[i]

完善程序（二）

（切割绳子） 有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。 输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 $10^6$ 的正整数，表示每条绳子的长度，第三行是一个不超过 $10^8$ 的正整数 m。 输出：绳段的最大长度，若无法切割，输出 Failed。

#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100];  // 绳子长度
int main() {
    cin >> n;
    count = 0;
    for (i = 0; i < n; i++) {
        cin >> len[i];
        ①;
    }
    cin >> m;
    if (②) {
        cout << "Failed" << endl;
        return 0;
    }
    lbound = 1;
    ubound = 1000000;
    while (③) {
        mid = ④;
        count = 0;
        for (i = 0; i < n; i++)
            ⑤;
        if (count < m)
            ubound = mid - 1;
        else
            lbound = mid;
    }
    cout << lbound << endl;
    return 0;
}

40. ① 处应填（ ）。

{{ select(40) }}

• count+=len[i]
• count=len[i]
• count++
• len[i]++

41. ② 处应填（ ）。

{{ select(41) }}

• count<=m
• count=m
• count<m
• count>m

42. ③ 处应填（ ）。

{{ select(42) }}

• lbound<ubound
• lbound<=ubound
• lbound<=ubound+1
• lbound+1<ubound

43. ④ 处应填（ ）。

{{ select(43) }}

• (lbound+ubound)/2
• (lbound+ubound+1)/2+1
• (lbound+ubound)>>1
• lbound+ubound+1>>1

44. ⑤ 处应填（ ）。

{{ select(44) }}

• count+=len[i]
• count=len[i]
• count+=len[i]/mid
• count+=mid