1. 在外部设备中，扫描仪属于（）。
A. 输入设备
B. 输出设备
C. 辅（外）存储器
D. 主（内）存储器
2. 现有 幅分辨率为 像素的 位真彩色图像，如果将这些图像保存在 CD 光盘上（一张 CD 光盘的容量按 计算），大约需要（）张 CD 光盘。
A.
B.
C.
D.
3. 计算 的结果，并选择答案的二进制：（）
A.
B.
C.
D.
4.每个操作数都只有一位，前缀表达式 -8/+693 的运算结果为 （）。
A.
B.
C.
D.
5. 以下（）组操作不能完成在双向循环链表的节点 p 后插入节点 x 的效果（其中，next 域为节点的直接后继，prev 域为节点的直接前驱）。
① p->next->prev = x;
② x->next = p->next;
③ x->prev = p;
④ p->next = x;
A. ①②③④
B. ①②④③
C. ①④③②
D. ②①④③
6. 给定一个入栈序列 ，问有（）种合法的出栈序列使得最后一个出栈的元素为 。
A.
B.
C.
D.
7. 二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行按位异或运算的结果是（）。
A. 00 1101 0111 1100
B. 10 1101 0111 1100
C. 10 1101 0011 1100
D. 10 1101 0111 1101
8. 根节点的高度为 ，一棵拥有 个节点的二叉树，其高度的最小值和最大值分别为（）。
A.
B.
C.
D.
9. 若有如下程序，其中 已定义为整数类型，且已赋值为一个正整数。
1 for (int i = 1; i <= n; i++) {
2 int cnt = 0;
3 for (int j = i; j <= n; j += i) {
4 cnt++;
5 }
6 cout << i << " " << cnt << endl;
7 }
则与上述代码段中第 行功能等价的赋值语句是（）。
A. int cnt = n / i;
B. int cnt = (n + i - 1) / i;
C. int cnt = n / i + (n % i != 0);
D. int cnt = n / i + (n % i == 0);
10. 使用以下程序段对 的序列 进行排序，第 行会执行（）次。
01 //对 a 数组 1~n 下标范围内的数据进行冒泡排序
02 void BubbleSort(int a[], int n) {
03 bool flag = true;
04 while (flag) {
05 flag = false;
06 for (int i = 1; i < n; i++) {
07 if (a[i] > a[i + 1]) {
08 swap(a[i], a[i + 1]);
09 flag = true;
10 }
11 }
12 }
13 }
A.
B.
C.
D.
11. 以下有向图的拓扑排序不合法的为（）。
A. ABCDEF
B. ACBEDF
C. BCADEF
D. BACDEF
12. 个相同的小球分成 组，要求第 组到第 组的球数分别要大于 个、 个、 个、 个，问有（）种不同的方案。（对于任意某一组，球数不同，就属于不同的方案）
A.
B.
C.
D.
13. 若一个整数序列 满足 是 的倍数，则称该序列为可比数列，问序列每项取值均为 且 的可比数列有（）种。
A.
B.
C.
D.
14. 以下对数据结构的表述不恰当的一项为（）。
A. 栈的访问原则后进先出，队列的访问原则是先进先出
B. 图的深度优先遍历算法常使用的数据结构为栈
C. 栈和队列的本质相同，都是线性容器
D. 栈常常被用于广度优先搜索算法
15. 以下无向加权图中，节点 A 到节点 F 的最短路数量有（）。
A.
B.
C.
D.
01 #include <iostream>
02 using namespace std;
03
04 int f1(int a, int b) {
05 int cnt = 0;
06 for (int i = 0; i < 10; i++) {
07 if ((a & 1) != (b & 1)) cnt++;
08 a >>= 1;
09 b >>= 1;
10 }
11 return cnt;
12 }
13
14 int f2(int a, int b) {
15 int t = a ^ b, sum = 0;
16 while (t) {
17 sum++;
18 t -= t & -t;
19 }
20 return sum;
21 }
22
23 int main() {
24 int x, y;
25 cin >> x >> y;
26 cout << f1(x, y) << " " << f2(x, y) << endl;
27 return 0;
28 }
输入的数为不超过 的正整数，完成下面的判断题和单选题。
当输入为 9 7 时，程序的输出为 3 3。（ ）
当输入为 128 32 时，程序的输出为 7 5。（ ）
（2 分）如果输入的两个数超过了 ，那么程序输出的两个数一定不相等。（ ）
（4 分）当输入为 127 10 时，程序的输出为（ ）。
A. 5 2
B. 5 5
C. 2 5
D. 2 2
下面哪一项修改不会影响原程序的输出（ ）。
A. 将第 行 int f1(int a, int b) 修改为 int f1(int &a, int &b)
B. 将第 行 if ((a & 1) != (b & 1)) 修改为 if (a & 1 != b & 1)
C. 将第 行 for (int i = 0; i < 10; i++) 修改为 for (int i = 0; i < 5; i++)
D. 将第 行 t -= t & -t 修改为 t = t & (t - 1)
01 #include <iostream>
02 #include <vector>
03 using namespace std;
04
05 int main() {
06 int n;
07 cin >> n;
08 vector<int> a(n), dp(n);
09 for (int i = 0; i < n; i++) cin >> a[i];
10 dp[0] = a[0];
11 for (int i = 1; i < n; i++) {
12 dp[i] = a[i];
13 for (int j = 0; j < i; j++) {
14 if (a[i] < a[j]) dp[i] = max(dp[i], dp[j] + a[i]);
15 }
16 }
17 int ans = 0;
18 for (int i = 0; i < n; i++) {
19 ans = max(ans, dp[i]);
20 }
21 cout << ans << endl;
22 return 0;
23 }
输入的数为不超过 的正整数，完成下面的判断题和单选题。
当输入的 a 数组为 ，程序的输出为 （ ）
（2分）如果 a[n - 1] 大于数组 a 中其余所有元素的总和，则 a[n - 1] 一定是最后的输出结果（ ）
（2分）如果 a[n - 1] 不大于数组 a 中其余所有元素的总和，则 a[n - 1] 不可能是最后的输出结果（ ）
程序的时间复杂度为 （ ）
当输入的 a 数组为 ，程序的输出结果为（ ）。
A.
B.
C.
D.
当输入的 a 数组为（ ），得到的输出结果最大。
A.
B.
C.
D.
01 #include <iostream>
02 #include <set>
03 using namespace std;
04
05 const int N = 1e5 + 10;
06
07 struct Node {
08 int D, P;
09 bool operator<(const Node &n) const { return P >= n.P; }
10 } a[N], b[N];
11
12 void merge(Node *l1, Node *r1, Node *l2, Node *r2, Node *st) {
13 Node *ed = st + (r1 - l1) + (r2 - l2);
14 while (st != ed)
15 *st++ = (l1 != r1 && (l2 == r2 || *l1 < *l2)) ? *l1++ : *l2++;
16 }
17
18 void prioritize(Node *a, int n) {
19 for (int seg = 1; seg < n; seg <<= 1) {
20 for (int l1 = 1; l1 <= n - seg; l1 += seg + seg) {
21 int r1 = l1 + seg;
22 int l2 = r1, r2 = min(l2 + seg, n + 1);
23 merge(a + l1, a + r1, a + l2, a + r2, b + l1);
24 memcpy(a + l1, b + l1, sizeof(Node) * (r2 - l1));
25 }
26 }
27 }
28
29 int main() {
30 int n;
31 long long res = 0;
32 set<int> st;
33
34 cin >> n;
35 st.insert(0);
36 for (int i = 1; i <= n; ++i) {
37 cin >> a[i].D >> a[i].P;
38 st.insert(i);
39 if (a[i].D > n) res += a[i].P;
40 }
41
42 prioritize(a, n);
43 for (int i = 1; i <= n; ++i) {
44 if (a[i].D > n) continue;
45 int pos = *--st.upper_bound(a[i].D);
46 if (pos) res += a[i].P, st.erase(pos);
47 }
48
49 cout << res << "\n";
50 return 0;
51 }
第一行输入一个整数 ；接下来 行每行输入两个整数，其中第 行的输入记为 ，完成下面的判断题和单选题。
（2 分）若程序输入的 满足严格递增，且 满足严格递减，则程序输出为所有 的和。（ ）
（2 分）prioritize 函数实现了基于归并排序思想的排序算法。（ ）
（2 分）第 23 行单次 merge 操作时间复杂度与当前的 seg 变量相关，为 ，且程序总时间复杂度为 。（ ）
第 45 中，变量 pos 被赋值后表示（ ）。
A. st 中第一个大于 a[i].D 的元素
B. st 中最后一个小于 a[i].D 的元素
C. st 中第一个大于等于 a[i].D 的元素
D. st 中最后一个小于等于 a[i].D 的元素
以下四项修改操作中，程序的运行结果一定不变的是（ ）。
A. 第 24 行，将 r2 - l1 修改为 seg + seg
B. 第 39、44 行，将两行中的 a[i].D > n 同时修改为 a[i].D >= n
C. 第 42 行，将 prioritize(a, n) 修改为 sort(a + 1, a + 1 + n)
D. 第 44 行，将 continue 修改为 break
若程序输入为 5\n 5 10\n 3 7\n 3 10\n 2 6\n 1 5\n（其中 \n 表示换行），则程序输出为（ ）。
A. 28
B. 31
C. 33
D. 38
回答多次询问，每次输入一个整数 ，求方程 在 内的正整数解。
数据范围满足 ， 。
试补全程序。
01 #include <iostream>
02 using namespace std;
03
04 long long f(int x) {
05 return /*____1____*/;
06 }
07
08 int binary_search(long long Y) {
09 int L = 1, R = 10000;
10 while (L <= R) {
11 int mid = (L + R) / 2;
12 if (/*____2____*/) {
13 /*____3____*/;
14 } else {
15 L = mid + 1;
16 }
17 }
18 return /*____4____*/;
19 }
20
21 int main() {
22 int q;
23 cin >> q;
24 for (int i = 0; i < q; i++) {
25 long long y;
26 cin >> y;
27 int x = binary_search(y);
28 if (/*____5____*/) {
29 cout << "No solution" << endl;
30 } else {
31 cout << "x = " << x << endl;
32 }
33 }
34 return 0;
35 }
/*____1____*/ 处应填（ ）
A. 2025 * x * x * x - 9 * x * x + 20 * x
B. 2025LL * x * x * x - 9 * x * x + 20 * x;
C. (long long)(2025 * x * x * x - 9 * x * x + 20 * x)
D. 2025 * x * x * x * 1.0 - 9 * x * x + 20 * x
/*____2____*/ 处应填（ ）
A. f(mid) == y
B. f(mid) >= y
C. f(mid) < y
D. f(mid) <= y
/*____3____*/ 处应填（ ）
A. R = mid - 1
B. R = mid
C. L = mid - 1
D. L = mid
/*____4____*/ 处应填（ ）
A. L
B. R
C. L + 1
D. R - 1
/*____5____*/ 处应填（ ）
A. x == 0
B. x == 1 || x == 10001
C. x > 10000 || f(x) != y
D. x < 1 || f(x) != y
给定 个顶点、 条边的有向图和一个序列 ，每次沿一条有向边移动需要花费 单位时间，限制到达顶点 的最早时间是 （即使能更早移动到顶点 处，也需等待至 才算到达，到达后才能进行下一步移动）。对于每个顶点 ，要回答一个独立的询问：在时刻 从顶点 出发，到达顶点 的最早时间是多少，无法到达则输出 。
数据范围满足 ，， 。
试补全程序。
01 #include <iostream>
02 #include <algorithm>
03 #include <queue>
04 #include <cstring>
05 using namespace std;
06
07 const int N = 100010, MAX = 200010;
08
09 int a[N], d[N];
10 queue<int> q[MAX];
11 /*____1____*/;
12
13 void solve() {
14 memset(d, -1, sizeof(d));
15 d[1] = 0;
16 q[0].push(1);
17 for (int i = 0; i < MAX; i++) {
18 while (/*____2____*/) {
19 int u = q[i].front();
20 q[i].pop();
21 for (int v : adj[u]) {
22 if (/*____3____*/) continue;
23 d[v] = /*____4____*/;
24 /*____5____*/;
25 }
26 }
27 }
28 }
29
30 int main() {
31 int n, m;
32 cin >> n >> m;
33 for (int i = 1; i <= n; i++) {
34 cin >> a[i];
35 }
36 for (int i = 1; i <= m; i++) {
37 int u, v;
38 cin >> u >> v;
39 adj[u].push_back(v);
40 }
41 solve();
42 for (int i = 1; i <= n; i++) {
43 cout << d[i] << ' ';
44 }
45 return 0;
46 }
/*____1____*/ 处应填（ ）
A. vector<int> adj[N]
B. vector<int> adj(N)
C. vector<vector<int>> adj
D. vector<pair<int, int>> adj
/*____2____*/ 处应填（ ）
A. !q.empty()
B. !q[i].empty()
C. !q[a[i]].empty()
D. !q[i].size()
/*____3____*/ 处应填（ ）
A. d[u] != -1
B. d[v] != -1
C. !q[v].empty()
D. !q[d[v]].empty()
/*____4____*/ 处应填（ ）
A. max(i + 1, a[v])
B. max(u + 1, a[v])
C. min(d[v], d[u] + 1)
D. min(d[v], d[u] + a[v])
/*____5____*/ 处应填（ ）
A. q.push(v)
B. q[u].push(v)
C. q[v].push(d[v])
D. q[d[v]].push(v)