一、单项选择题（共 15 题，每题 2 分，共计 30 分）

1. {{ select(1) }} 操作系统的功能是（ ）。

• 负责外设与主机之间的信息交换
• 控制和管理计算机系统的各种硬件和软件资源的使用
• 负责诊断机器的故障
• 将源程序编译成目标程序

---

2. {{ select(2) }} 在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。

• 系统分配的栈空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出
• 系统分配的堆空间溢出

---

3. 计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++ 代码段表示的程序，将分别输出什么结果？（ ）

unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);

{{ select(3) }}

• EF、EF
• EF、DE
• DE、EF
• DE、DE

---

4. {{ select(4) }} 以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？（ ）

• g++ -o main main.cpp
• g++ -o main.cpp main
• g++ main -o main.cpp
• g++ main.cpp -o main.cpp

---

5. {{ select(5) }} 考虑一个自然数 n 以及一个模数 m，你需要计算 n 的逆元（即 n 在模 m 意义下的乘法逆元）。下列哪种算法最为适合？（ ）

• 使用暴力法依次尝试
• 使用扩展欧几里得算法
• 使用快速幂法
• 使用线性筛法

---

6. {{ select(6) }} 在 KMP 算法中，对于模式串 P=abacaba，其 next 数组（next[i] 定义为模式串 P[0..i] 最长公共前后缀的长度，且数组下标从 0 开始）的值是什么？

• {0,0,0,1,0,1,2,3}
• {0,1,2,3,4,5,6}
• {0,0,0,1,1,2,2,3}
• {0,0,0,0,0,1,2,3}

---

7. {{ select(7) }} 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（ ）条边。

• 144
• 100
• 48
• 122

---

8. {{ select(8) }} 定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要 ( ) 次上述操作。

• 7
• 8
• 9
• 6

---

9. {{ select(9) }} 考虑对 n 个数进行排序，以下最坏时间复杂度低于 O(n^2) 的排序方法是（ ）。

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

---

10. {{ select(10) }} 在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？（ ）

• 4 个结点的树
• 6 个结点的树
• 7 个结点的树
• 8 个结点的树

---

11. {{ select(11) }} 设有一个 10 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 4 的环？（ ）

• 120
• 210
• 630
• 5040

---

12. {{ select(12) }} 递归关系式 T(n)=2T(n/2)+O(n²) 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

• O(n)
• O(n log n)
• O(n²)
• O(n² log n)

---

13. {{ select(13) }} 表达式 a*(b+c)-d 的后缀表达形式为（ ）。

• abc*+d-
• -+*abcd
• abcd*+-
• abc+*d-

---

14. {{ select(14) }} 共有 8 人选修了程序设计课程，期末大作业要求由 2 人组成的团队完成。假设不区分每个团队内 2 人的角色和作用，请问共有多少种可能的组队方案。（ ）

• 28
• 32
• 56
• 64

---

15. {{ select(15) }} 将字符串 cat, car, cart, case, dog, do 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

• 8
• 9
• 10
• 11

---

二、阅读程序

程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分。

程序 1

#include <iostream>
using namespace std;
​
unsigned short f(unsigned short x) {
    x ^= x << 6;
    x ^= x >> 8;
    return x;
}
int main() {
    unsigned short x;
    cin >> x;
    unsigned short y = f(x);
    cout << y << endl;
    return 0;
}

假设输入的 x 是不超过 65535 的自然数，完成下面的判断题和单选题：

判断题

16. {{ select(16) }} 当输入非零时，输出一定不为零。（ ）

• √
• ×

17. {{ select(17) }} 将 f 函数的输入参数的类型改为 unsigned int，程序的输出不变。（ ）

• √
• ×

18. {{ select(18) }} 当输入为 65535 时，输出为 63。（ ）

• √
• ×

19. {{ select(19) }} 当输入为 1 时，输出为 64。（ ）

• √
• ×

选择题

20. {{ select(20) }} 当输入为 512 时，输出为（ ）。

• 33280
• 33410
• 33106
• 33346

21. {{ select(21) }} 当输入为 64 时，执行完第 5 行后 x 的值为（ ）。

• 8256
• 4130
• 4128
• 4160

---

程序 2

1  #include <iostream>
 2  #include <string>
 3  #include <vector>
 4
 5  using namespace std;
 6
 7  int f(const string &s, const string &t)
 8  {
 9      int n = s.length(), m = t.length();
10
11      vector<int> shift(128, m + 1);
12
13      int i, j;
14
15      for (j = 0; j < m; j++)
16          shift[t[j]] = m - j;
17
18      for (i = 0; i <= n - m; i += shift[s[i + m]]) {
19          j = 0;
20          while (j < m && s[i + j] == t[j]) j++;
21          if (j == m) return i;
22      }
23
24      return -1;
25  }
26
27  int main()
28  {
29      string a, b;
30      cin >> a >> b;
31      cout << f(a, b) << endl;
32      return 0;
33  }

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：

判断题

22. {{ select(22) }} 当输入为"abcde fg"时，输出为 -1。

• √ 正确
• × 错误

23. {{ select(23) }} 当输入为"abbababbbab abab"时，输出为 4。

• √ 正确
• × 错误

24. {{ select(24) }} 当输入为"GoodLuckCsp2022 22"时，第 20 行的"j++"语句执行次数为 2。

• √ 正确
• × 错误

选择题

25. {{ select(25) }} 该算法最坏情况下的时间复杂度为（ ）。

• O(n+m)
• O(n log m)
• O(m log n)
• O(nm)

26. {{ select(26) }} f(a, b) 与下列（ ）语句的功能最类似。

• a.find(b)
• a.rfind(b)
• a.substr(b)
• a.compare(b)

27. {{ select(27) }} 当输入为"baaabaaabaaabaaaa aaaa"，第 20 行的"j++"语句执行次数为（ ）。

• 9
• 10
• 11
• 12

---

程序 3

#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k - 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

判断题

28. {{ select(28) }} 当输入的 n=3 的时候，程序输出的答案为 3。

• √
• ×

29. {{ select(29) }} 在 dfs 函数运行过程中，k 的取值会满足 1≤k≤n+1。

• √
• ×

30. {{ select(30) }} 删除第 19 行的 flag[i]=false;，对答案不会产生影响。

• √
• ×

选择题

31. {{ select(31) }} 当输入的 n=4 的时候，程序输出的答案为（ ）。

• 11
• 12
• 24
• 9

32. {{ select(32) }} 如果因为某些问题，导致程序运行第 25 行的 dfs 函数之前，数组 p 的初值并不全为 0，则对程序的影响是（ ）。

• 输出的答案比原答案要小
• 无法确定输出的答案
• 程序可能陷入死循环
• 没有影响

33. {{ select(33) }} （4 分）假如删去第 14 行的 if(flag[i]) continue;，输入 3，得到的输出答案是（ ）。

• 27
• 3
• 16
• 12

---

三、完善程序（单选题，每小题 3 分，共计 30 分）

程序 1：分数背包

小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 w_i，体积是 v_i。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 a\;(0<a<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 a \times w，体积是 a \times v，另一块的价值是 (1-a) \times w，体积是 (1-a) \times v。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 n=3,\;B=8，三块蛋糕的价值分别是 4,4,2，体积分别是 5,3,2。那么最优的方案就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.6，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。

输入的数据范围为：1 \le n \le 1000，1 \le B \le 10^5，1 \le w_i,v_i \le 100。

提示：将所有的蛋糕按照性价比 \frac{w_i}{v_i} 从大到小排序后进行贪心选择。

试补全程序。

#include <cstdio>
using namespace std;
​
const int maxn = 1005;
​
int n, B, w[maxn], v[maxn];
​
int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}
​
void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n", w, v);
}
​
void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}
​
int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }
    for (int i = 2; i <= n; i++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

34. {{ select(34) }} ① 处应填（ ）。

• w[j] / v[j] < w[j+1] / v[j+1]
• w[j] / v[j] > w[j+1] / v[j+1]
• v[j] * w[j+1] < v[j+1] * w[j]
• w[j] * v[j+1] < w[j+1] * v[j]

35. {{ select(35) }} ② 处应填（ ）。

• w[1] <= B
• v[1] <= B
• w[1] >= B
• v[1] >= B

36. {{ select(36) }} ③ 处应填（ ）。

• print(v[1], w[1]); return 0;
• curV = 0; curW = 0;
• print(w[1], v[1]); return 0;
• curV = v[1]; curW = w[1];

37. {{ select(37) }} ④ 处应填（ ）。

• curW * v[i] + curV * w[i], v[i]
• (curW - w[i]) * v[i] + (B - curV) * w[i], v[i]
• curW + v[i], w[i]
• curW * v[i] + (B - curV) * w[i], v[i]

38. {{ select(38) }} ⑤ 处应填（ ）。

• curW, curV
• curW, 1
• curV, curW
• curV, 1

程序 2：次短路

已知一个有 n 个点 m 条边的有向图 G，并且给定图中的两个点 s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 −1。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
​
const int maxn = 2e5+10, maxm = 1e6+10, inf = 522133279;
​
int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn<<1], *dis2;
int pre[maxn<<1], *pre2;
bool vis[maxn<<1];
​
void add(int a, int b, int c) {
    ++tot;
    nxt[tot] = head[a];
    to[tot] = b;
    w[tot] = c;
    head[a] = tot;
}
​
bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
    if (d >= dis[b]) return false;
    if (b < n) ___①___;
    q.push(___②___);
    dis[b] = d;
    pre[b] = a;
    return true;
}
​
void solve() {
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, s));
    memset(dis, ___③___, sizeof(dis));
    memset(pre, -1, sizeof(pre));
    dis2 = dis+n;
    pre2 = pre+n;
    dis[s] = 0;
    while (!q.empty()) {
        int aa = q.top().second; q.pop();
        if (vis[aa]) continue;
        vis[aa] = true;
        int a = aa % n;
        for (int e = head[a]; e; e = nxt[e]) {
            int b = to[e], c = w[e];
            if (aa < n) {
                if (!upd(a, b, dis[a]+c, q))
                    ___④___;
            } else {
                upd(n+a, n+b, dis2[a]+c, q);
            }
        }
    }
}
​
void out(int a) {
    if (a != s) {
        if (a < n) out(pre[a]);
        else out(___⑤___);
    }
    printf("%d%c", a%n+1, " \n"[a == n+t]);
}
​
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    s--, t--;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a-1, b-1, c);
    }
    solve();
    if (dis2[t] == inf) puts("-1");
    else {
        printf("%d\n", dis2[t]);
        out(n+t);
    }
}

39. {{ select(39) }} ① 处应填（ ）

• upd(pre[b], n+b, dis[b], q)
• upd(a, n+b, d, q)
• upd(pre[b], b, dis[b], q)
• upd(a, b, d, q)

40. {{ select(40) }} ② 处应填（ ）

• make_pair(-d, b)
• make_pair(d, b)
• make_pair(b, d)
• make_pair(-b, d)

41. {{ select(41) }} ③ 处应填（ ）

• 0xff
• 0x1f
• 0x3f
• 0x7f

42. {{ select(42) }} ④ 处应填（ ）

• upd(a, n+b, dis[a]+c, q)
• upd(n+a, n+b, dis2[a]+c, q)
• upd(n+a, b, dis2[a]+c, q)
• upd(a, b, dis[a]+c, q)

43. {{ select(43) }} ⑤ 处应填（ ）

• pre2[a%n]
• pre[a%n]
• pre2[a]
• pre[a%n]+1