一、单项选择题(每题 2 分,共 30 分)

1. 在 C++ 中,若希望函数内的局部变量在多次函数调用之间保留上一次的值,应使用哪个关键字?

{{ select(1) }}

• const
• static
• extern
• register

2. 二进制数 $1 1 0 1 0 1_{2}$与十六进制数 $1 A_{1 6}$的和对应的十进制值是?

{{ select(2) }}

• $67$
• $75$
• $79$
• $83$

3. 已知 int x = 5;,下面哪一项可以正确声明一个引用变量 r,使其引用 x?

{{ select(3) }}

• int r = &x;
• int &r = x;
• int *r = x;
• int &&r = &x;

4. 一个空栈依次将 $1,2,3,4,5$ 入栈,下面哪个序列不可能作为出栈序列?

{{ select(4) }}

• $2$,$1$,$4$,$5$,$3$
• $3$,$2$,$1$,$5$,$4$
• $4$,$1$,$3$,$2$,$5$
• $1$,$2$,$3$,$4$,$5$

5. 一棵有 $31$ 个结点的满二叉树,其叶子结点个数为?

{{ select(5) }}

• $8$
• $12$
• $15$
• $16$

6. 已知一棵二叉树的前序遍历为 A B D E C F,中序遍历为 D B E A C F,则其后序遍历为?

{{ select(6) }}

• D E B F C A
• D B E F C A
• E D B F C A
• D E B C F A

7. 一个有 $8$ 个顶点、$10$ 条边的无向连通图,至少删除多少条边后可以变成一棵树?

{{ select(7) }}

• $1$
• $2$
• $3$
• $4$

8. 下列排序算法的常见实现中,通常不稳定的是?

{{ select(8) }}

• 冒泡排序
• 简单选择排序
• 直接插入排序
• 归并排序

9. 有 $4$ 名男生和 $3$ 名女生,从中选出 $3$ 人组成小组,要求至少有 $1$ 名女生,共有多少种选法?

{{ select(9) }}

• $21$
• $28$
• $31$
• $35$

10. 后缀表达式 $34+5\times 6-$ 对应的中缀表达式是?

{{ select(10) }}

• $3+4 \times 5-6$
• $(3+4) \times(5-6)$
• $(3+4) \times 5-6$
• $3+4 \times(5-6)$

11. 在 C++ 中,表达式 (char)('A' + 5) 的值是?

{{ select(11) }}

• 'E'
• 'F'
• 'G'
• '5'

12. 对含有 $2026$ 个元素的有序数组进行二分查找,最坏情况下最多需要比较多少次?

{{ select(12) }}

• $9$
• $10$
• $11$
• $12$

13. 一个不含自环的有向图有 $6$ 个顶点,若用邻接矩阵表示,矩阵中最多可能有多少个非零元素?

{{ select(13) }}

• $12$
• $18$
• $24$
• $30$

14. 有 $6$ 个字符,其出现频率分别为 $5$,$7$,$10$,$15$,$20$,$43$。若用哈夫曼编码,频率为 $7$ 的字符编码长度为?

{{ select(14) }}

• $1$
• $2$
• $3$
• $4$

15. 下面哪一个通常不是编译器?

{{ select(15) }}

• GCC
• Clang
• MSVC
• Chrome

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填“$\surd$”,错误填“$\times$”。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。其中第 $16\sim 18$ 题每题 $2$ 分,第 $32$ 题 $4$ 分。

阅读程序(一)

假设输入的 $n$ 是不超过 $1000000$ 的正整数。

#include <iostream>
using namespace std;

int f(int x) {
    int s = 0;
    while (x) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

int g(int x) {
    int r = 0;
    while (x) {
        r = r * 10 + x % 10;
        x /= 10;
    }
    return r;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << " " << g(n) << endl;
    return 0;
}

(程序 1,每题 2 分)

(1) 当输入为 $1203$ 时,程序输出为 $63021$。

{{ select(16) }}

• 正确
• 错误

(2) 对任意合法输入 $n$,都有 $g(g(n))=n$。

{{ select(17) }}

• 正确
• 错误

(3) 对任意合法输入 $n$,都有 $f(n)=f(g(n))$。

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 $100200$ 时,程序输出为?

{{ select(19) }}

• $3200100$
• $32001$
• $42001$
• $41002$

(5) 该程序的时间复杂度最准确地表示为?

{{ select(20) }}

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(n \log n)$

阅读程序(二)

假设输入字符串只包含 (、)、[、]、{、} 这 $6$ 种字符。

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool ck(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char t = st.top();
            st.pop();
            if (c == ')' && t != '(') return false;
            if (c == ']' && t != '[') return false;
            if (c == '}' && t != '{') return false;
        }
    }
    return st.empty();
}

int main() {
    string s;
    cin >> s;
    cout << ck(s) << endl;
    return 0;
}

(程序 2,每题 1.5 分)

(1) 当输入为 ([]{}) 时,程序输出为 $1$。

{{ select(21) }}

• 正确
• 错误

(2) 只要字符串中每种左括号和右括号数量分别相等,程序就一定输出 $1$。

{{ select(22) }}

• 正确
• 错误

(3) 若程序输出为 $1$ ,则输入字符串长度一定是偶数。

{{ select(23) }}

• 正确
• 错误

(4) 当输入为 ([]] 时,程序输出为?

{{ select(24) }}

• 0
• 1
• true
• false

(5) 当输入为 {[()][]} 时,程序输出为?

{{ select(25) }}

• 0
• 1
• 8
• false

(6) 设输入字符串长度为 $n$ ,该程序的时间复杂度为?

{{ select(26) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n^2)$

阅读程序(三)

假设 $1 \leq n,m \leq 8$,输入的 $a_{ij}$ 只可能为 $0$ 或 $1$。其中 $1$ 表示该格子可以经过,$0$ 表示该格子不能经过。

#include <iostream>
using namespace std;

int a[10][10], dp[10][10];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    if (a[1][1]) dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) {
                dp[i][j] = 0;
                continue;
            }
            if (i == 1 && j == 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

(程序 3,每题 1.5 分)

(1) 如果 $a_{11}=0$,程序一定输出 $0$。

{{ select(27) }}

• 正确
• 错误

(2) 程序中的 $dp_{ij}$ 表示从左上角走到位置 $(i,j)$ 的合法路径数量。

{{ select(28) }}

• 正确
• 错误

(3) 若将两层循环改为外层枚举 $j$,内层枚举 $i$,程序输出结果总是不变。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为: $3$ $3$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ 程序输出为?

{{ select(30) }}

• $3$
• $4$
• $6$
• $9$

(5) 若输入为: $3$ $4$ $1$ $1$ $1$ $1$ $0$ $1$ $0$ $1$ $1$ $1$ $1$ $1$ 程序输出为?

{{ select(31) }}

• $1$
• $2$
• $3$
• $4$

(6) 若 $n=m=4$,且所有 $a_{ij}$ 都为 $1$,程序输出为?

{{ select(32) }}

• $12$
• $16$
• $20$
• $24$

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

完善程序(一)

下面程序使用插入排序将数组从小到大排序,请补全程序。

#include <iostream>
using namespace std;

int a[1005];

void ins(int n) {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = ①;
        while (j >= 0 && ②) {
            a[j + 1] = ③;
            ④;
        }
        ⑤;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    ins(n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

(1) ① 处应填( )

{{ select(33) }}

• 0
• i
• i-1
• n-1

(2) ② 处应填( )

{{ select(34) }}

• a[j] < x
• a[j] > x
• a[i] > x
• j > x

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

• i++
• j++
• i--
• j--

(5) ⑤ 处应填( )

{{ select(37) }}

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

完善程序(二)

下面程序用数组模拟一个队列,支持三种操作:

• 1 x:将 $x$ 加入队尾;
• 2:若队列非空,弹出队首;
• 3:若队列非空,输出队首元素,否则输出 empty。

请补全程序。

假设操作次数不超过 $1000$,不会因为入队次数过多导致数组越界。

#include <iostream>
using namespace std;

int q[1005];
int hd = 0, tl = 0;

void ps(int x) {
    q[①] = x;
    ②;
}

void pp() {
    if (③) ④;
}

bool em() {
    return ⑤;
}

int main() {
    int m;
    cin >> m;
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            ps(x);
        } else if (op == 2) {
            pp();
        } else {
            if (em()) cout << "empty" << endl;
            else cout << q[hd] << endl;
        }
    }
    return 0;
}

(1) ① 处应填( )

{{ select(38) }}

• hd
• tl
• tl+1
• hd+1

(2) ② 处应填( )

{{ select(39) }}

• hd++
• tl++
• hd--
• tl--

(3) ③ 处应填( )

{{ select(40) }}

• hd < tl
• hd == tl
• hd > tl
• tl == 0

(4) ④ 处应填( )

{{ select(41) }}

• tl++
• hd++
• tl--
• hd--

(5) ⑤ 处应填( )

{{ select(42) }}

• hd < tl
• hd > tl
• hd == tl
• q[hd] == q[tl]