一、单项选择题（共 \(15\) 题，每题 \(2\) 分，共计 \(30\) 分。每题有且仅有一个正确选项。）
\(1.\) 在下列设备中，（）属于输入设备。
\(\qquad A. \text{显示器} \qquad B. \text{键盘} \qquad C. \text{打印机} \qquad D. \text{音箱}\)
\(2.\) 二进制数 \((00111001)_2\) 和 \((01010110)_2\) 的和为（）。
\(\qquad A.(10011111)_2\qquad \qquad \qquad B.(10001101)_2\)
\(\qquad C.(10001111)_2 \qquad \qquad \qquad D.(10000111)_2\)
\(3.\) 有一个栈 \(S\) 的进栈序列为 \(1, 2, 3\)，则出栈序列的方案数为（）。
\(\qquad A. 3\qquad \qquad B. 5\qquad \qquad C.7 \qquad \qquad D.9\)
\(4.\) 如下代码的时间复杂度为：
int num = 0;
for (int i = 2; i <= n; ++i) {
bool Z = true;
for (int j = 1; j * j <= i; ++j) {
if (i % j == 0) {
Z = false; break;
}
}
num += Z;
}
\(\qquad A. \Theta(n) \qquad \quad B. \Theta(n \log n) \qquad \quad C. \Theta(n \sqrt n) \qquad \quad D. \Theta(n ^ 2)\)
\(5.\) 将 \(n\) 个小球装入 \(m\) 个盒子中，每个小球相同，每个盒子不同，且一个盒子中可以没有小球，有（）种方案。
\(\qquad A. \dbinom{n}{m} \qquad B. \dbinom{n - 1}{m - 1} \qquad C. \dbinom{n + m - 1}{m - 1} \qquad D. m ^ n\)
\(6.\) 已知 \(A = B = \text{false}, C = \text{true}\)，则以下表达式结果为真的是（）。
\(\qquad A. (A \lor B) \land C \qquad \qquad B. (A \lor C) \land (\lnot B \land A)\)
\(\qquad C. \lnot C \lor \lnot A \land \lnot B \quad \qquad D. A \lor (B \lor \lnot C)\)
\(7.\) 如下代码的时间复杂度为（已知 \(x, y\) 均为 \(n\) 级别）：
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
\(\qquad A. \Theta(n) \qquad B. \Theta(\sqrt n) \qquad C. \Theta(\log n) \qquad D. \Theta(n \log n)\)
\(8.\) 已知有一棵满二叉树，从第一层开始，每一层都从左往右，依次给节点编号，则第 \(i\) 层从左往右数第 \(j\) 个节点的编号为（）。
\(\qquad A. 2 ^ {i - 1} + j - 1 \qquad B. 2 ^ i + j - 1 \qquad C. 2 ^ {i - 1} + j \qquad D. 2 ^ i + j\)
\(9.\) \(d + (a + b) \times c\) 的后缀表达式为（）。
\(\qquad A. ++\times\ b\ c\ a\ d \qquad B. \times\ c + +\ a\ b\ d\)
\(\qquad C. ++\times\ a\ c\ b\ d \qquad D. +\ d\times +\ a\ b\ c\)
\(10.\) 下列储存器中，存取速度最快的是（）。
\(\qquad A.\text{硬盘}\qquad B.\text{软盘}\qquad C.\text{光盘}\qquad D.\text{内存}\)
\(11.\) 如下程序运行时错误的原因为（）。
#include <bits/stdc++.h>
using namespace std;
int a[10];
int main() {
for (int i = 1; i <= 10; ++i) {
cin >> a[i];
}
int S = 0;
for (int i = 1; i <= 10; ++i) {
S += a[i];
}
cout << S << '\n';
return 0;
}
\(\qquad A. \text{死循环} \qquad B.\text{数组越界} \qquad C.\text{S 变量的值超出了 int 范围} \qquad D.\text{未知错误}\)
\(12.\) 如下程序的中 \(C\) 的值为（）。
int A = 3, B = 2, C = ceil(A / B);
\(\qquad A. 0 \qquad \qquad B. 1 \qquad \qquad C. 2 \qquad \qquad D. 3\)
\(13.\) 长度为 \(n\)，每个元素在 \(1 \sim m\) 之间，且相邻两个元素不能相同的数列的数量为（）。
\(\qquad A. m ^ n \qquad \quad B. m \times (m - 1) ^ n \qquad \quad C. \dbinom{n + m - 1}{m - 1} \qquad \quad D. n ^ m\)
\(14.\) 字符串 \(\texttt{ababc}\) 中本质不同非空子串数量为（）。
\(\qquad A.15 \qquad\qquad B.13 \qquad\qquad C.12 \qquad\qquad D.10\)
\(15.\) \(12345\) 的所有因数的和为（）。
\(\qquad A.19776 \quad\qquad B.19777 \quad\qquad C.19778 \quad\qquad D.19780\)
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 \(1.5\) 分，选择题 \(3\) 分，共计 \(40\) 分）
\(1.\)
#include <bits/stdc++.h>
using namespace std;
int n, a[1005];
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (a[i] > a[j]) swap(a[i], a[j]);
}
}
for (int i = 1; i <= n; ++i) {
cout << a[i] << " \n" [ i == n ];
}
return 0;
}
- 判断题
-
程序的时间复杂度为 \(\Theta(n ^ 2)\)。（）
-
如果输入的 \(n\) 在 \(1005\) 以内，程序就不会出现运行错误。（）
-
程序的作用是将一个无序的数组排序。（）
-
将
a[i] > a[j]改成a[i] >= a[j]，输出结果不变。（）
- 选择题
- 若输入为
5 4 3 5 2 1，则输出为（）。
\(\qquad A.\)1 4 2 3 5 \(\quad B.\)1 2 4 3 5\(\quad C.\)1 2 3 4 5 \(\quad D.\)5 4 3 2 1
- 若输入为
9 8 4 6 5 9 7 3 1 2，则程序中swap函数执行的次数为（）。
\(\qquad A. 25 \qquad \qquad B. 26 \qquad\qquad C. 27 \qquad\qquad D. 28\)
\(2.\)
#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
cin >> n;
int ans = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
ans = gcd(ans, a[i]);
}
cout << ans << '\n';
return 0;
}
保证输入的 \(a_i\) 的值域为 \(w\) 级别。
- 判断题
-
程序求的是 \(n\) 个数的最大公约数。（）
-
若存在 \(\gcd(a_i, a_j) = 1, 1 \le i, j \le n\)，则程序输出为 \(1\)。（）
-
输入的 \(n\) 可以为 \(100005\)。（）
- 选择题
- 程序的时间复杂度为（）。
\(\qquad A. \Theta(n \log w) \qquad B. \Theta(n + \log w) \qquad C. \Theta(n) \qquad D. \Theta(n + w)\)
- 若程序输入
5 6 18 24 9 3，输出为（）。
\(\qquad A. 2 \qquad \qquad B. 3 \qquad \qquad C. 4 \qquad \qquad D. 5\)
- （\(4\) 分）若程序输出 \(3\)，且 \(n = 5\)，保证每个 \(1 \le a_i \le 18\)，则这样的输入有（）种。
\(\qquad A. 7501 \qquad \qquad B. 7502 \qquad \qquad C. 7503 \qquad \qquad D. 7504\)
\(3.\)
#include <bits/stdc++.h>
using namespace std;
int n, A[ 1 << 15 ], B[ 1 << 15 ], C[ 1 << 15 ];
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 0; i < 1 << n; ++i) {
cin >> A[i];
}
for (int i = 0; i < 1 << n; ++i) {
cin >> B[i];
}
for (int i = 0; i < 1 << n; ++i) {
C[i] += A[0] * B[i];
for (int j = i; j; j = (j - 1) & 1) {
C[i] += A[j] * B[ i ^ j ];
}
}
for (int i = 0; i < 1 << n; ++i) {
cout << C[i] << " \n" [ i == (1 << n) - 1 ];
}
return 0;
}
- 判断题
-
\(n\) 可以等于 \(15\)。（）
-
若将循环中的
i < 1 << n改为i < (1 << n)，程序的运算结果会发生改变。（） -
若保证 \(n \ge 0\)，程序依然可能会死循环。（）
- 选择题
- 若输入为
2 5 9 4 6 8 1 3 7，则输出为（）。
\(\qquad A.\)40 76 110 83 \(\qquad B.\)40 77 110 83
\(\qquad C.\)40 77 110 82 \(\qquad D.\)40 77 111 83
- 程序的时间复杂度为（）。
\(\qquad A. \Theta(2 ^ n) \qquad \quad B. \Theta(3 ^ n) \qquad \quad C. \Theta(n \cdot 2 ^ n) \qquad \quad D. \Theta(n \cdot 3 ^ n)\)
- 若保证 \(0 \le A_i, B_i \le w\)，则输出中 \(C_i\) 可能的最大值为（）。
\(\qquad A. 2 ^ n \cdot w \qquad \quad B. 3 ^ n \cdot w \qquad \quad C. w ^ 2 \qquad \quad D. 2 ^ n \cdot w ^ 2\)
三．完善程序（单选题，每小题 \(3\) 分，共计 \(30\) 分）