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

1. 在计算机中,所有信息都是以( )形式存储和运算的。

{{ select(1) }}

• 十进制数
• 二进制数
• 八进制数
• 十六进制数

2. 八进制数 $(765)_8$ 转换成十六进制是( )。

{{ select(2) }}

• $(1F5)_{16}$
• $(1F4)_{16}$
• $(1E5)_{16}$
• $(2F5)_{16}$

3. 已知整型变量 $x=7$,表达式 (x >> 1) + (x & 1) 的值是( )。

{{ select(3) }}

• $3$
• $4$
• $7$
• $8$

4. 栈是后进先出的数据结构。若入栈序列为 $1,2,3,4$,下列哪个不可能是合法出栈序列?( )

{{ select(4) }}

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

5. 下列排序算法在最坏情况下时间复杂度仍为 $O(n\log n)$ 的是( )。

{{ select(5) }}

• 冒泡排序
• 快速排序
• 插入排序
• 归并排序

6. 十进制 $-25$ 的 $8$ 位二进制补码是( )。

{{ select(6) }}

• $11100111$
• $11100110$
• $11100101$
• $10011001$

7. $5$ 个顶点的无向完全图有( )条边。

{{ select(7) }}

• $5$
• $8$
• $10$
• $15$

8. 若某算法的递推式为 $T(n)=2T(n/2)+O(n)$,则该算法的时间复杂度是( )。

{{ select(8) }}

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

9. 从 $5$ 名男生和 $4$ 名女生中选 $3$ 人组成委员会,要求至少含 $1$ 名女生,有( )种选法。

{{ select(9) }}

• $60$
• $74$
• $80$
• $84$

10. 下列哪一项不是 TCP/IP 模型中的层次?( )

{{ select(10) }}

• 应用层
• 传输层
• 会话层
• 网络接口层

11. IP 地址 192.168.1.1 属于哪一类 IP 地址?( )

{{ select(11) }}

• A 类
• B 类
• C 类
• D 类

12. 在 C++ 中,要定义一个不能被继承的类,应使用关键字( )。

{{ select(12) }}

• final
• virtual
• static
• const

13. 将中缀表达式 $(a+b)\times c-(d+e)/f$ 转换为后缀表达式为( )。

{{ select(13) }}

• a b + c × d e + f - /
• a b c × + d e + f / -
• a b + c d × e + f / -
• a b + c × d e + f / -

14. 对一组数据 $\{5,3,8,6,2\}$ 进行第一趟冒泡排序(从小到大)后的结果是( )。

{{ select(14) }}

• $3,5,6,2,8$
• $3,5,2,6,8$
• $3,2,5,6,8$
• $2,3,5,6,8$

15. 某二叉树有 $10$ 个度为 $1$ 的结点,$5$ 个度为 $2$ 的结点,则其叶子结点数为( )。

{{ select(15) }}

• $4$
• $6$
• $5$
• $15$

程序输入不超过数组或字符串定义的范围。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。其中第 $24$ 题、$31$ 题每题 $2$ 分。判断题正确填「正确」,错误填「错误」。

阅读程序(一)

#include <bits/stdc++.h>
using namespace std;
int main() {
    string A, B;
    cin >> A >> B;
    int lenA = A.length(), lenB = B.length();
    vector<vector<int>> dp(lenA + 1, vector<int>(lenB + 1, 0));
    for (int i = 0; i <= lenA; ++i) dp[i][0] = i;
    for (int j = 0; j <= lenB; ++j) dp[0][j] = j;
    for (int i = 1; i <= lenA; ++i) {
        for (int j = 1; j <= lenB; ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
            }
        }
    }
    cout << dp[lenA][lenB] << endl;
    return 0;
}

(1) 程序的空间复杂度为 $O(\mathrm{lenA}+\mathrm{lenB})$。

{{ select(16) }}

• 正确
• 错误

(2) 如果 $A=\texttt{"abc"}$, $B=\texttt{"abcd"}$,程序输出 $1$。

{{ select(17) }}

• 正确
• 错误

(3) 对于输入 "abc" 和 "def",输出一定是 $3$。

{{ select(18) }}

• 正确
• 错误

(4) 若输入 $A=\texttt{"kitten"}$, $B=\texttt{"sitting"}$,程序的输出是?

{{ select(19) }}

• $2$
• $3$
• $4$
• $5$

(5) 以下哪个输入会导致程序输出为 $2$?

{{ select(20) }}

• $A=\texttt{"ab"}$, $B=\texttt{"ac"}$
• $A=\texttt{"ab"}$, $B=\texttt{"a"}$
• $A=\texttt{"ab"}$, $B=\texttt{"abc"}$
• $A=\texttt{"ab"}$, $B=\texttt{"ba"}$

(6) 该算法属于哪种算法思想?

{{ select(21) }}

• 贪心
• 分治
• 动态规划
• 回溯

阅读程序(二)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> f(n + 1, vector<int>(k + 1, 0));
    for (int i = 1; i <= n; i++) f[i][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= k && j <= i; j++) {
            f[i][j] = f[i - 1][j - 1] + f[i - j][j];
        }
    }
    cout << f[n][k] << endl;
    return 0;
}

(1) 当输入为 5 2 时,输出为 $2$。

{{ select(22) }}

• 正确
• 错误

(2) 该程序的时间复杂度为 $O(nk)$。

{{ select(23) }}

• 正确
• 错误

(3) 当输入为 6 3 时,输出为 $4$。

{{ select(24) }}

• 正确
• 错误

(4) 输入 10 3 时,输出为?

{{ select(25) }}

• $8$
• $6$
• $9$
• $7$

(5) 该程序解决的是哪个经典问题?

{{ select(26) }}

• 背包问题
• 最长公共子序列
• 整数划分
• 最短路径

(6) 输入 8 4 时,$f[8][4]$ 的值为?

{{ select(27) }}

• $3$
• $5$
• $4$
• $6$

阅读程序(三)

#include <bits/stdc++.h>
using namespace std;
int n, a[1024][1024];
void dfs(int x, int y, int n) {
    if (n == 1) {
        a[x][y + 1] = a[x + 1][y] = a[x + 1][y + 1] = 1;
        return;
    }
    int midx = x + (1 << n - 1), midy = y + (1 << n - 1);
    dfs(x, midy, n - 1);
    dfs(midx, y, n - 1);
    dfs(midx, midy, n - 1);
}
int main() {
    scanf("%d", &n);
    dfs(0, 0, n);
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

(1) 该程序递归的最大深度为 $n$。

{{ select(28) }}

• 正确
• 错误

(2) 该程序使用了二分递归,每次将问题分为 $4$ 个子问题。

{{ select(29) }}

• 正确
• 错误

(3) 程序中的 1 << n - 1 等同于 (1 << n) - 1。

{{ select(30) }}

• 正确
• 错误

(4) 该程序的时间复杂度为 $O(3^n)$。

{{ select(31) }}

• 正确
• 错误

(5) 输入 $n=2$ 时,矩阵中数字 $1$ 的个数为?

{{ select(32) }}

• $3$
• $6$
• $9$
• $12$

(6) 该程序在 $n=3$ 时,共进行了多少次递归调用(包括初始调用)?

{{ select(33) }}

• $27$
• $40$
• $9$
• $13$

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

完善程序(一)

P1177 【模板】排序

将读入的 $N$ 个数从小到大排序后输出。

第一行一个正整数 $N$。第二行包含 $N$ 个空格隔开的正整数 $a_i$。将这 $N$ 个数从小到大输出,数之间空格隔开。

样例:

5
4 2 4 5 1

1 2 4 4 5

下面程序使用归并排序,请补全。

#include <iostream>
using namespace std;
const int MAXN = 100005;
int n, a[MAXN], temp[MAXN];

void merge(int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            ①;
        }
    }
    while (i <= mid) ②;
    while (j <= right) temp[k++] = a[j++];
    for (int i = left; i <= right; i++) ③;
}

void mergeSort(int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(left, mid);
    ④;
    merge(left, mid, right);
}

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

(1) ① 处应填( )

{{ select(34) }}

• temp[i++] = a[k++]
• temp[i++] = a[j++]
• temp[k++] = a[j++]
• temp[j++] = a[i++]

(2) ② 处应填( )

{{ select(35) }}

• temp[j++] = a[k++]
• temp[i++] = a[j++]
• temp[k++] = a[i++]
• temp[k++] = a[j++]

(3) ③ 处应填( )

{{ select(36) }}

• temp[i] = a[i]
• a[i] = temp[i]
• a[i] = temp[k++]
• temp[i] = a[k++]

(4) ④ 处应填( )

{{ select(37) }}

• mergeSort(mid + 1, right)
• mergeSort(mid, left)
• mergeSort(mid, right)
• mergeSort(mid + 1, left)

(5) ⑤ 处应填( )

{{ select(38) }}

• merge(0, n / 2, n - 1)
• merge(0, n / 2, n)
• mergeSort(0, n)
• mergeSort(0, n - 1)

完善程序(二)

P1092 [NOIP 2004 提高组] 虫食算

所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要根据剩下的数字判定被啃掉的数字。来看一个简单的例子:

$$\begin{array}{cr} & 43\$9865\$045 \\ + & 8468\$6633 \\ \hline & 44445509678 \end{array}$$

其中 $\$$ 代表被虫子啃掉的数字。根据算式容易判断:第一行的两个数字分别是 $5$ 和 $3$,第二行的数字是 $5$。

现在对问题做两个限制:

1. 只考虑加法。这里的加法是 $n$ 进制加法,算式中三个数都有 $n$ 位,允许有前导 $0$。
2. 虫子把所有的数都啃光了,相同的数字用相同的字母表示,不同的数字用不同的字母。若是 $n$ 进制,则取英文字母表前 $n$ 个大写字母表示 $0\sim n-1$(不一定按顺序对应)。上面的数据用这种方法表示就是:

$$\begin{array}{cr} & \mathrm{BADC} \\ + & \mathrm{CBDA} \\ \hline & \mathrm{DCCC} \end{array}$$

这是一个 $4$ 进制算式。若令 $A,B,C,D$ 分别代表 $0,1,2,3$,则算式成立。

对于给定的 $n$ 进制加法算式,求出 $n$ 个不同字母分别代表的数字。保证有且仅有一组解。

输入第一行整数 $n$。随后三行各一个长度为 $n$ 的大写字母串,分别为两个加数与和(高位在左,允许前导零)。输出一行 $n$ 个空格隔开的整数,依次表示 $A,B,\ldots$ 对应的数字。

样例:

5
ABCED
BDACE
EBBAA

1 0 3 4 2

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
int n;
string a, b, c;
int num[26];
bool used[26];
vector<int> order;
bool found = false;

bool check() {
    for (int i = n - 1; i >= 0; i--) {
        int x = num[a[i] - 'A'], y = num[b[i] - 'A'], z = num[c[i] - 'A'];
        if (x == -1 || y == -1 || z == -1) continue;
        bool ok = false;
        for (int car = 0; car <= 1; car++) {
            if (①) ok = true;
        }
        if (!ok) return false;
    }
    return true;
}

void dfs(int pos) {
    if (found) return;
    if (pos == order.size()) {
        int carry = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = num[a[i] - 'A'], y = num[b[i] - 'A'], z = num[c[i] - 'A'];
            int sum = ②;
            if (sum % n != z) return;
            ③;
        }
        if (carry == 0) found = true;
        return;
    }
    int ch = ④;
    for (int d = n - 1; d >= 0; d--) {
        if (used[d]) continue;
        ⑤, used[d] = true;
        if (check()) dfs(pos + 1);
        if (found) return;
        num[ch] = -1, used[d] = false;
    }
}

int main() {
    cin >> n;
    cin >> a >> b >> c;
    for (int i = 0; i < 26; i++) num[i] = -1;
    bool appear[26] = {false};
    for (int i = 0; i < n; i++) {
        appear[a[i] - 'A'] = true;
        appear[b[i] - 'A'] = true;
        appear[c[i] - 'A'] = true;
    }
    for (int i = n - 1; i >= 0; i--) {
        int ch1 = a[i] - 'A', ch2 = b[i] - 'A', ch3 = c[i] - 'A';
        if (appear[ch1] && num[ch1] == -1) {
            order.push_back(ch1);
            num[ch1] = -2;
        }
        if (appear[ch2] && num[ch2] == -1) {
            order.push_back(ch2);
            num[ch2] = -2;
        }
        if (appear[ch3] && num[ch3] == -1) {
            order.push_back(ch3);
            num[ch3] = -2;
        }
    }
    for (int i = 0; i < 26; i++) if (num[i] == -2) num[i] = -1;
    dfs(0);
    for (int i = 0; i < n; i++) cout << num[i] << " ";
    return 0;
}

(1) ① 处应填( )

{{ select(39) }}

• (x + y + car) % n == z
• (x + car) % y == z
• (y + car) % x == z
• (x + y + z) % n == 0

(2) ② 处应填( )

{{ select(40) }}

• x + y
• x + y + z
• x + y + carry
• x + y + z + carry

(3) ③ 处应填( )

{{ select(41) }}

• carry = sum / x
• carry = sum / y
• carry = sum / z
• carry = sum / n

(4) ④ 处应填( )

{{ select(42) }}

• num[pos - 1]
• num[pos]
• order[pos - 1]
• order[pos]

(5) ⑤ 处应填( )

{{ select(43) }}

• order[ch] = d
• num[ch] = d
• order[pos] = d
• num[pos] = d