一、单项选择题（1~15 题，每题 2 分，共 30 分）
- 以下哪种功能没有涉及 C++ 语言的面向对象特性支持（ ）。
{{ select(1) }}
- C++中调用 printf 函数
- C++中调用用户定义的类成员函数
- C++中构造一个 class 或 struct
- C++中构造来源于同一基类的多个派生类
- 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
{{ select(2) }}
- 5 4 3 6 1 2
- 4 5 3 1 2 6
- 3 4 6 5 2 1
- 2 3 4 1 5 6
- 运行以下代码片段的行为是（ ）。
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;
{{ select(3) }}
- 将 x 的值赋为 201
- 将 y 的值赋为 101
- 将 q 指向 x 的地址
- 将 p 指向 y 的地址
- 链表和数组的区别包括（ ）。
{{ select(4) }}
- 数组不能排序，链表可以
- 链表比数组能存储更多的信息
- 数组大小固定，链表大小可动态调整
- 以上均正确
- 假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。
{{ select(5) }}
- 对表达式 a+(b-c)d 的前缀表达式为（ ），其中 +、-、 是运算符。
{{ select(6) }}
- *+a-bcd
- +a*-bcd
- abc-d*+
- abc-+d
- 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%、15%、30%、16%、29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。
{{ select(7) }}
- 一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
{{ select(8) }}
- 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
{{ select(9) }}
- 以下对数据结构的表述不恰当的一项为（ ）。
{{ select(10) }}
- 图的深度优先遍历算法常使用的数据结构为栈。
- 栈的访问原则为后进先出，队列的访问原则是先进先出。
- 队列常常被用于广度优先搜索算法。
- 栈与队列存在本质不同，无法用栈实现队列。
- 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）（ ）。
{{ select(11) }}
- p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
- p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
- s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
- s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
- 以下排序算法的常见实现中，哪个选项的说法是错误的（ ）。
{{ select(12) }}
- 冒泡排序算法是稳定的
- 简单选择排序是稳定的
- 简单插入排序是稳定的
- 归并排序算法是稳定的
- 八进制数 32.1 对应的十进制数是（ ）。
{{ select(13) }}
- 24.125
- 24.250
- 26.125
- 26.250
- 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。
{{ select(14) }}
- 以下对递归方法的描述中，正确的是（ ）。
{{ select(15) }}
- 递归是允许使用多组参数调用函数的编程技术
- 递归是通过调用自身来求解问题的编程技术
- 递归是面向对象和数据而不是功能和逻辑的编程语言模型
- 递归是将用某种高级语言转换为机器代码的编程技术
二、阅读程序（判断题正确填 √、错误填 ×；判断题每题 1.5 分，选择题每题 3 分）
程序 1
1 | #include <iostream>
2 | using namespace std;
3 | int main() {
4 | unsigned short x, y;
5 | cin >> x >> y;
6 | x = (x | x << 2) & 0x33;
7 | x = (x | x << 1) & 0x55;
8 | y = (y | y << 2) & 0x33;
9 | y = (y | y << 1) & 0x55;
10 | unsigned short z = x | y << 1;
11 | cout << z << endl;
12 | return 0;
13 | }
- 假设输入的 x、y 均是不超过 15 的自然数，删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）
{{ select(16) }}
- 假设输入的 x、y 均是不超过 15 的自然数，将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）
{{ select(17) }}
- 假设输入的 x、y 均是不超过 15 的自然数，程序总是输出一个整数“0”。（ ）
{{ select(18) }}
- 假设输入的 x、y 均是不超过 15 的自然数，当输入为“2 2”时，输出为“10”。（ ）
{{ select(19) }}
- 假设输入的 x、y 均是不超过 15 的自然数，当输入为“2 2”时，输出为“59”。（ ）
{{ select(20) }}
- 假设输入的 x、y 均是不超过 15 的自然数，当输入为“13 8”时，输出为（ ）。
{{ select(21) }}
程序 2
1 | #include <algorithm>
2 | #include <iostream>
3 | #include <limits>
4 | using namespace std;
5 | const int MAXN = 105;
6 | const int MAXK = 105;
7 | int h[MAXN][MAXK];
8 | int f(int n, int m) {
9 | if (m == 1) return n;
10 | if (n == 0) return 0;
11 | int ret = numeric_limits<int>::max();
12 | for (int i = 1; i <= n; i++)
13 | ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
14 | return ret;
15 | }
16 | int g(int n, int m) {
17 | for (int i = 1; i <= n; i++)
18 | h[i][1] = i;
19 | for (int j = 1; j <= m; j++)
20 | h[0][j] = 0;
21 | for (int i = 1; i <= n; i++) {
22 | for (int j = 2; j <= m; j++) {
23 | h[i][j] = numeric_limits<int>::max();
24 | for (int k = 1; k <= i; k++)
25 | h[i][j] = min(h[i][j],
26 | max(h[i - k][j], h[k - 1][j - 1]) + 1);
27 | }
28 | }
29 | return h[n][m];
30 | }
31 | int main() {
32 | int n, m;
33 | cin >> n >> m;
34 | cout << f(n, m) << endl << g(n, m) << endl;
35 | return 0;
36 | }
- 假设输入的 n、m 均是不超过 100 的正整数，当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
{{ select(22) }}
- 假设输入的 n、m 均是不超过 100 的正整数，输出的两行整数总是相同的。（ ）
{{ select(23) }}
- 假设输入的 n、m 均是不超过 100 的正整数，当 m 为 1 时，输出的第一行总为 n。（ ）
{{ select(24) }}
- 假设输入的 n、m 均是不超过 100 的正整数，算法 g(n, m) 最为准确的时间复杂度分析结果为（ ）。
{{ select(25) }}
- O(n^(3/2) * m)
- O(nm)
- O(n²m)
- O(nm²)
- 假设输入的 n、m 均是不超过 100 的正整数，当输入为“20 2”时，输出的第一行为（ ）。
{{ select(26) }}
- 假设输入的 n、m 均是不超过 100 的正整数，当输入为“100 100”时，输出的第一行为（ ）。
{{ select(27) }}
程序 3
1 | #include <iostream>
2 | using namespace std;
3 | int n, k;
4 | int solve1() {
5 | int l = 0, r = n;
6 | while (l <= r) {
7 | int mid = (l + r) / 2;
8 | if (mid * mid <= n) l = mid + 1;
9 | else r = mid - 1;
10 | }
11 | return l - 1;
12 | }
13 | double solve2(double x) {
14 | if (x == 0) return x;
15 | for (int i = 0; i < k; i++)
16 | x = (x + n / x) / 2;
17 | return x;
18 | }
19 | int main() {
20 | cin >> n >> k;
21 | double ans = solve2(solve1());
22 | cout << ans << ' ' << (ans * ans == n) << endl;
23 | return 0;
24 | }
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，该算法最准确的时间复杂度分析结果为 O(log n + k)。（ ）
{{ select(28) }}
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“9801 1”时，输出的第一个数为“99”。（ ）
{{ select(29) }}
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）
{{ select(30) }}
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）
{{ select(31) }}
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“2 1”时，输出的第一个数最接近（ ）。
{{ select(32) }}
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“3 10”时，输出的第一个数最接近（ ）。
{{ select(33) }}
- 假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，当输入为“256 11”时，输出的第一个数（ ）。
{{ select(34) }}
- 等于 16
- 接近但小于 16
- 接近但大于 16
- 前三种情况都有可能
三、完善程序（每题 3 分）
程序 1
1 | #include <cmath>
2 | #include <iostream>
3 | #include <vector>
4 | using namespace std;
5 | int main() {
6 | int n;
7 | cin >> n;
8 | vector<int> fac;
9 | fac.reserve((int)ceil(sqrt(n)));
10 | int i;
11 | for (i = 1; i * i < n; ++i) {
12 | if (①) {
13 | fac.push_back(i);
14 | }
15 | }
16 | for (int k = 0; k < (int)fac.size(); ++k) {
17 | cout << ② << " ";
18 | }
19 | if (③) {
20 | cout << ④ << " ";
21 | }
22 | for (int k = fac.size() - 1; k >= 0; --k) {
23 | cout << ⑤ << " ";
24 | }
25 | return 0;
26 | }
- （1）处应填（ ）。
{{ select(35) }}
- n % i == 0
- n % i == 1
- n % (i-1) == 0
- n % (i-1) == 1
- （2）处应填（ ）。
{{ select(36) }}
- n / fac[k]
- fac[k]
- fac[k]-1
- n / (fac[k]-1)
- （3）处应填（ ）。
{{ select(37) }}
- (i-1)*(i-1)==n
- (i-1)*i==n
- i*i==n
- i*(i-1)==n
- （4）处应填（ ）。
{{ select(38) }}
- （5）处应填（ ）。
{{ select(39) }}
- n / fac[k]
- fac[k]
- fac[k]-1
- n / (fac[k]-1)
程序 2
1 | #include <iostream>
2 | #include <queue>
3 | using namespace std;
4 | const int ROWS = 8;
5 | const int COLS = 8;
6 | struct Point {
7 | int r, c;
8 | Point(int r, int c): r(r), c(c) {}
9 | };
10 | bool is_valid(char image[ROWS][COLS], Point pt,
11 | int prev_color, int new_color) {
12 | int r = pt.r;
13 | int c = pt.c;
14 | return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
15 | ① && image[r][c] != new_color);
16 | }
17 | void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
18 | queue<Point> queue;
19 | queue.push(cur);
20 | int prev_color = image[cur.r][cur.c];
21 | ②
22 | while (!queue.empty()) {
23 | Point pt = queue.front();
24 | queue.pop();
25 | Point points[4] = {③, Point(pt.r - 1, pt.c),
26 | Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
27 | for (auto p : points) {
28 | if (is_valid(image, p, prev_color, new_color)) {
29 | ④
30 | ⑤
31 | }
32 | }
33 | }
34 | }
35 | int main() {
36 | char image[ROWS][COLS] = {{'g','g','g','g','g','g','g','g'},
37 | {'g','g','g','g','g','g','r','r'},
38 | {'g','r','r','g','g','r','g','g'},
39 | {'g','b','b','b','b','r','g','r'},
40 | {'g','g','g','b','b','r','g','r'},
41 | {'g','g','g','b','b','b','b','r'},
42 | {'g','g','g','g','g','b','g','g'},
43 | {'g','g','g','g','g','b','b','g'}};
44 | Point cur(4, 4);
45 | char new_color = 'y';
46 | flood_fill(image, cur, new_color);
47 | for (int r = 0; r < ROWS; r++) {
48 | for (int c = 0; c < COLS; c++) {
49 | cout << image[r][c] << ' ';
50 | }
51 | cout << endl;
52 | }
53 | return 0;
54 | }
- （1）处应填（ ）。
{{ select(40) }}
- image[r][c] == prev_color
- image[r][c] != prev_color
- image[r][c] == new_color
- image[r][c] != new_color
- （2）处应填（ ）。
{{ select(41) }}
- image[cur.r+1][cur.c] = new_color
- image[cur.r][cur.c] = new_color
- image[cur.r][cur.c+1] = new_color
- image[cur.r][cur.c] = prev_color
- （3）处应填（ ）。
{{ select(42) }}
- Point(pt.r, pt.c)
- Point(pt.r, pt.c+1)
- Point(pt.r+1, pt.c)
- Point(pt.r+1, pt.c+1)
- （4）处应填（ ）。
{{ select(43) }}
- prev_color = image[p.r][p.c]
- new_color = image[p.r][p.c]
- image[p.r][p.c] = prev_color
- image[p.r][p.c] = new_color
- （5）处应填（ ）。
{{ select(44) }}
- queue.push(p)
- queue.push(pt)
- queue.push(cur)
- queue.push(Point(ROWS,COLS))
