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

1. 设布尔变量 $a=\mathrm{false}$, $b=\mathrm{true}$, $c=\mathrm{false}$,下列逻辑表达式结果为假的是( )

{{ select(1) }}

• $(a \lor b) \land \lnot c$
• $\lnot a \land (b \lor c)$
• $(a \land b) \lor (\lnot b \land c)$
• $\lnot(a \land c) \land b$

2. 一张分辨率为 $4096 \times 2048$ 的 $24$ 位真彩色位图图像,其存储大小约为( )

{{ select(2) }}

• $24\mathrm{MB}$
• $48\mathrm{MB}$
• $16\mathrm{MB}$
• $32\mathrm{MB}$

3. 某 UTF-8 编码的字符占用了 $3$ 字节,其二进制首字节最可能是( )

{{ select(3) }}

• 0xxxxxxx
• 110xxxxx
• 11110xxx
• 1110xxxx

4. 二进制数 $11010110$ 算术右移 $2$ 位(保留符号位)后,结果是( )

{{ select(4) }}

• $00110101$
• $11110101$
• $00110110$
• $11110110$

5. 一个栈的入栈序列为 $1,2,3,4,5$,下列不可能是其出栈序列的是( )

{{ select(5) }}

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

6. 哈希表长 $m=17$,哈希函数 $h(k)=k \bmod 17$,用线性探测解决冲突。依次插入关键字 $19,36,53,37$,则关键字 $37$ 的存储位置是( )

{{ select(6) }}

• $5$
• $6$
• $7$
• $8$

7. $n$ 个顶点的连通无向图,最少边数、最多边数分别为( )

{{ select(7) }}

• $n-1$、$n(n-1)/2$
• $n$、$n^2$
• $n-2$、$n(n+1)/2$
• $n$、$n(n-1)$

8. 将 $8$ 本相同的书分给 $5$ 名学生,每人至少一本,共有( )种分法。

{{ select(8) }}

• $56$
• $70$
• $35$
• $126$

9. 一棵二叉树的先序遍历为 $ABDECF$,中序遍历为 $DBEAFC$,其后序遍历为( )

{{ select(9) }}

• $DBEFCA$
• $DEBCFA$
• $DEBFCA$
• $DEBAFC$

10. 一棵度为 $3$ 的树,有 $41$ 个叶子结点,$10$ 个度为 $2$ 的结点,则度为 $3$ 的结点个数为( )

{{ select(10) }}

• $15$
• $16$
• $17$
• $18$

11. 下列算法中,属于贪心算法应用的是( )

{{ select(11) }}

• 二分查找
• 哈夫曼编码
• 归并排序
• 深度优先搜索

12. 快速排序的平均时间复杂度和空间复杂度分别为( )

{{ select(12) }}

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

13. 递归函数如下:

f(n):
    if n <= 1 return 1
    else return f(n-1) + f(n-2)

调用 $f(6)$ 的过程中,函数 $f$ 被调用的总次数是( )

{{ select(13) }}

• $15$
• $25$
• $21$
• $31$

14. 中缀表达式 $(m - n) * (p + q) / k$ 的前缀表达式为( )

{{ select(14) }}

• * / - m n + p q k
• - * m n / + p q k
• / * m n - + p q k
• / * - m n + p q k

15. 已知无向图有 $6$ 个顶点、$8$ 条边,其连通分量最少个数为( )

{{ select(15) }}

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

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

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。判断题正确填「正确」,错误填「错误」。

阅读程序(一)

#include <bits/stdc++.h>
using namespace std;

char getType(const string &s) {
    bool has0 = false, has1 = false;
    for (char c : s) {
        if (c == '0') has0 = true;
        if (c == '1') has1 = true;
    }
    if (has0 && has1) return 'C';
    if (has0) return 'S';
    return 'P';
}

void buildCSP(const string &s) {
    if (s.length() == 1) {
        cout << getType(s);
        return;
    }
    int mid = s.length() / 2;
    buildCSP(s.substr(0, mid));
    buildCSP(s.substr(mid, mid));
    cout << getType(s);
}

int main() {
    string s;
    cin >> s;
    buildCSP(s);
    return 0;
}

(1) 若输入字符串为 "11",程序输出为 "PP"。

{{ select(16) }}

• 正确
• 错误

(2) buildCSP 函数对于长度为 $4$ 的字符串,只会输出 $4$ 个字符。( $2$ 分)

{{ select(17) }}

• 正确
• 错误

(3) 若输入为 "0101",最后一个输出字符一定是 'C'。

{{ select(18) }}

• 正确
• 错误

(4) 对于长度为 $8$ 的输入,getType 会被调用 $15$ 次。( $2$ 分)

{{ select(19) }}

• 正确
• 错误

(5) 若输出为 "SPC",则输入是以下哪个?

{{ select(20) }}

• "101"
• "010"
• "110"
• "001"

(6) 对于输入 "0000111100001111",输出字符串长度为多少?

{{ select(21) }}

• $16$
• $32$
• $15$
• $31$

(7) 以下哪个输入会导致输出中 'C' 出现次数最多?

{{ select(22) }}

• "0000"
• "1111"
• "0101"
• "0011"

阅读程序(二)

#include <bits/stdc++.h>
using namespace std;
string s;
long long comb[27][27];
int main() {
    for (int i = 0; i <= 26; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
    cin >> s;
    int len = s.size();
    if (len > 6) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] < 'a' || s[i] > 'z') {
            cout << 0 << endl;
            return 0;
        }
        if (i > 0 && s[i] <= s[i - 1]) {
            cout << 0 << endl;
            return 0;
        }
    }
    long long ans = 0;
    for (int i = 1; i < len; i++) ans += comb[26][i];
    int prev = 0;
    for (int i = 0; i < len; i++) {
        int cur = s[i] - 'a' + 1;
        for (int ch = prev + 1; ch < cur; ch++) {
            ans += comb[26 - ch][len - i - 1];
        }
        prev = cur;
    }
    ans += 1;
    cout << ans << endl;
    return 0;
}

(1) 若输入 "abc",程序输出为 $352$。

{{ select(23) }}

• 正确
• 错误

(2) 输入 "xyz" 时,程序输出 $2950$。( $2$ 分)

{{ select(24) }}

• 正确
• 错误

(3) 若输入 "abcdef",程序输出一定大于 $100000$。( $2$ 分)

{{ select(25) }}

• 正确
• 错误

(4) 若输入合法且输出为 $10587$,则输入字符串的长度最可能是:

{{ select(26) }}

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

(5) 程序在计算组合数时,以下哪个值最大?

{{ select(27) }}

• comb[26][0]
• comb[26][13]
• comb[26][6]
• comb[26][26]

阅读程序(三)

#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0;
vector<int> g[105];
int indeg[105], outdeg[105], dp[105];
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        indeg[b]++, outdeg[a]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            dp[i] = 1;
            q.push(i);
        }
    }
    vector<int> res;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            indeg[v]--;
            if (indeg[v] == 0) q.push(v);
        }
    }
    for (int i = 0; i < res.size(); i++) {
        int u = res[i];
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j];
            dp[v] = dp[v] + dp[u];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (outdeg[i] == 0) ans = ans + dp[i];
    }
    cout << ans << "\n";
    return 0;
}

(1) 若某个结点入度为 $0$,则其 $dp$ 值一定为 $1$。

{{ select(28) }}

• 正确
• 错误

(2) 程序在最坏情况下的时间复杂度为 $O(n+m)$。( $2$ 分)

{{ select(29) }}

• 正确
• 错误

(3) 若输入为 $n=4$, $m=3$,边为 $1 \to 3$, $2 \to 3$, $3 \to 4$,程序输出为:

{{ select(30) }}

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

(4) 若输入为 $n=6$, $m=5$,边为 $1 \to 3$, $1 \to 4$, $2 \to 4$, $3 \to 5$, $4 \to 6$,则输出为:

{{ select(31) }}

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

(5) 若输入图为 $n=5$, $m=4$,边为 $1 \to 2$, $1 \to 3$, $2 \to 4$, $3 \to 4$,程序执行过程中,$dp[4]$ 的最终值为:

{{ select(32) }}

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

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

完善程序(一)

P2359 三素数数

如果一个数的所有连续三位数字都是大于 $100$ 的素数,则该数称为三素数数。比如 $113797$ 是一个 $6$ 位的三素数数,因为 $113$、$137$、$379$、$797$ 都是素数。

一个整数 $n$($3 \le n \le 10^4$),表示三素数数的位数。输出 $n$ 位三素数数的个数。由于这个数可能很大,需要输出答案除以 $10^9+9$ 的余数。

样例:

4

204

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 9;
int n;
bool vis[1000];
long long dp[10005][105];
int main() {
    cin >> n;
    for (int i = 0; i < 1000; i++) vis[i] = true;
    vis[0] = vis[1] = false;
    for (int i = 2; i < 1000; i++) {
        if (vis[i]) {
            for (int j = i * i; j < 1000; j += i)
                vis[j] = false;
        }
    }
    for (int i = 100; i < 1000; i++) {
        if (vis[i]) {
            int cur = ①;
            dp[3][cur] = (dp[3][cur] + 1) % MOD;
        }
    }
    for (int i = 3; i < n; i++) {
        for (int j = 0; j < 100; j++) {
            if (dp[i][j] == 0) continue;
            for (int k = 0; k <= 9; k++) {
                int num = ②;
                if (num >= 100 && vis[num]) {
                    int cur = ③;
                    ④;
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < 100; i++) {
        ⑤;
    }
    cout << ans << endl;
    return 0;
}

(1) ① 处应填( )

{{ select(33) }}

• i / 100
• i / 10
• i % 100
• i % 10

(2) ② 处应填( )

{{ select(34) }}

• j * 100 + k
• j * 10 + k
• j * 100
• j * 10

(3) ③ 处应填( )

{{ select(35) }}

• num % 100
• num % 10
• num / 100
• num / 10

(4) ④ 处应填( )

{{ select(36) }}

• dp[i + 1][cur] = (dp[i + 1][cur] + 1) % MOD
• dp[i + 1][cur + 1] = (dp[i + 1][cur + 1] + 1) % MOD
• dp[i + 1][cur] = (dp[i + 1][cur] + dp[i][j]) % MOD
• dp[i + 1][cur + 1] = (dp[i + 1][cur + 1] + dp[i][j]) % MOD

(5) ⑤ 处应填( )

{{ select(37) }}

• ans = (ans + dp[i][1]) % MOD
• ans = (ans + dp[i][n]) % MOD
• ans = (ans + dp[1][i]) % MOD
• ans = (ans + dp[n][i]) % MOD

完善程序(二)

P1248 加工生产调度

某工厂收到了 $n$ 个产品的订单,这 $n$ 个产品分别在 A、B 两个车间加工,并且必须先在 A 车间加工后才可以到 B 车间加工。一个车间在同一时刻只能加工一个产品。

某个产品 $i$ 在 A、B 两车间加工的时间分别为 $A_i,B_i$。怎样安排这 $n$ 个产品的加工顺序,才能使总的加工时间最短。这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间。

输入第一行一个整数 $n$。接下来一行 $n$ 个整数表示各产品在 A 车间的加工时间。最后一行 $n$ 个整数表示各产品在 B 车间的加工时间。

输出第一行一个整数,表示最少的加工时间。第二行是一种达到最少加工时间的加工顺序。

样例:

5
3 5 8 7 10
6 2 1 4 9

34
1 5 4 2 3

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
int n, a[1005], b[1005];
int minx[1005], posx[1005];
int dk[1005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        minx[i] = min(a[i], b[i]);
        posx[i] = i;
    }
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (minx[i] > minx[j]) {
                swap(minx[i], minx[j]);
                swap(posx[i], posx[j]);
            }
        }
    }
    int k = 0, t = n + 1;
    for (int i = 1; i <= n; i++) {
        if (①) {
            ②;
        } else {
            ③;
        }
    }
    k = 0, t = 0;
    for (int i = 1; i <= n; i++) {
        ④;
        if (t < k) t = k;
        ⑤;
    }
    cout << t << "\n";
    for (int i = 1; i <= n; i++) cout << dk[i] << " ";
    return 0;
}

(1) ① 处应填( )

{{ select(38) }}

• minx[posx[i]] == a[i]
• minx[i] == a[i]
• minx[posx[i]] == a[posx[i]]
• minx[i] == a[posx[i]]

(2) ② 处应填( )

{{ select(39) }}

• k--, dk[k] = a[posx[i]]
• k++, dk[k] = posx[i]
• k++, dk[k] = a[posx[i]]
• k--, dk[k] = posx[i]

(3) ③ 处应填( )

{{ select(40) }}

• t++, dk[t] = posx[i]
• t--, dk[t] = a[posx[i]]
• t--, dk[t] = posx[i]
• t++, dk[t] = a[posx[i]]

(4) ④ 处应填( )

{{ select(41) }}

• k += a[i]
• k += dk[i]
• k += a[dk[i]]
• k += dk[posx[i]]

(5) ⑤ 处应填( )

{{ select(42) }}

• t += b[i]
• t += dk[i]
• t += b[dk[i]]
• t += dk[posx[i]]