该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

单项选择题15题（每题2分），程序阅读题18题（共40分），完善程序题10题（每题3分），共100分

一、单项选择题

共15题，每题2分，共计30分。每题有且仅有一个正确选项。

1、在Linux系统终端中，用于创建新目录的命令是（）。

{{ select(1) }}

• new
• mkdir
• touch
• dir

2、二进制数 $101011_2$ 与 $1101_2$ 的和为（）。

{{ select(2) }}

• $110000_2$
• $111000_2$
• $100000_2$
• $101000_2$

3、对于如下代码段，其时间复杂度为（）。

int s = 0;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        s++;

{{ select(3) }}

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

4、以下排序算法中，通常不是稳定排序的是（）。

{{ select(4) }}

• 冒泡排序
• 插入排序
• 堆排序
• 归并排序

5、元 $a, b, c, d$ 依次进栈，允许进栈、出栈操作任意交替进行，则以下不可能得到的出栈序列是（）。

{{ select(5) }}

• d c b a
• b a c d
• b d a c
• a c b d

6、一个大小为10的哈希表，下标为0到9，哈希函数为 $H(x) = x \bmod 10$，采用线性探查解决冲突。依次插入 21, 31, 41, 22，则 22 最终存放在下标（）。

{{ select(6) }}

• 1
• 2
• 3
• 4

7、根结点深度为1，一棵深度为4的满三叉树共有（）个结点。

{{ select(7) }}

• 13
• 40
• 81
• 121

8、一个包含 10 个顶点的完全无向图共有（）条边。

{{ select(8) }}

• 40
• 44
• 45
• 90

9、对模式串 ababa，若 next[i] 表示子串 P[0..i] 的最长相等真前后缀长度，则 next 数组为（）。

{{ select(9) }}

• 0 0 1 2 3
• 0 1 2 3 4
• 0 0 0 1 2
• 0 0 1 1 2

10、对一个数组进行二分查找时，必须满足的条件是（）。

{{ select(10) }}

• 数组有序
• 数组长度为2的幂
• 数组元素互不相同
• 数组元素均为正数

11、依次将 4, 2, 6, 1, 3, 5, 7 插入一棵初始为空的二叉搜索树，则该树的后序遍历序列为（）。

{{ select(11) }}

• 1 3 2 5 7 6 4
• 4 2 1 3 6 5 7
• 1 2 3 4 5 6 7
• 7 5 6 3 1 2 4

12、从10个位置中选出3个位置，要求任意两个被选位置不相邻，共有（）种选法。

{{ select(12) }}

• 36
• 48
• 56
• 120

13、整数 $a$ 在模 $m$ 意义下存在乘法逆元，当且仅当（）。

{{ select(13) }}

• $a < m$
• $a$ 是质数
• $m$ 是质数
• $\gcd(a, m) = 1$

14、已知 $f(1) = 1, f(2) = 1$，当 $n \geq 3$ 时，$f(n) = f(n-1) + f(n-2)$，则 $f(6)$ 的值为（）。

{{ select(14) }}

• 8
• 10
• 13
• 21

15、有4个顶点 1, 2, 3, 4，有向边为 $1 \to 3, 2 \to 3, 3 \to 4$，则该图共有（）种拓扑排序。

{{ select(15) }}

• 1
• 2
• 3
• 4

---

二、程序阅读题

共3题，判断题正确填√，错误填×。

特殊分值说明：

• 第16~18题、第22~24题、第28~30题（判断题）每题1.5分
• 第19题（选择题）每题2.5分
• 第20~21题、第25~27题、第31~33题（选择题）每题3分

阅读程序（一）

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

int n, ans;

void dfs(int p, int q) {
    if (p == n) {
        ans++;
        return;
    }
    
    dfs(p + 1, 0);
    
    if (!q)
        dfs(p + 1, 1);
}
int main() {
    cin >> n;
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

假设输入的 $n$ 是正整数。

判断题

16、当输入为3时，程序输出5。（）

{{ select(16) }}

• 正确
• 错误

17、在程序运行过程中，参数 $p$ 可能等于 $n + 1$。（）

{{ select(17) }}

• 正确
• 错误

18、在所有递归调用中，参数 $q$ 的值只可能是0或1。（）

{{ select(18) }}

• 正确
• 错误

单项选择题

19、当输入为5时，程序输出为（）。

{{ select(19) }}

• 8
• 10
• 13
• 16

20、若删除第13行的 if (!q)，当输入为4时，程序输出为（）。

{{ select(20) }}

• 8
• 12
• 15
• 16

21、设 $\varphi = \frac{1 + \sqrt{5}}{2}$，该程序递归调用次数的量级为（）。

{{ select(21) }}

• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(\varphi^n)$
• $\Theta(2^n)$

---

阅读程序（二）

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

const int N = 105;
int n, k;
int a[N], b[N], c[N];
void ps(int p) {
    memset(c, 0, sizeof c);
    
    for (int i = 1; i <= n; i++)
        c[a[i] / p % k]++;
    
    for (int i = 1; i < k; i++)
        c[i] += c[i - 1];
    
    for (int i = n; i >= 1; i--) {
        int x = a[i] / p % k;
        b[c[x]--] = a[i];
    }
    
    for (int i = 1; i <= n; i++)
        a[i] = b[i];
}
int main() {
    cin >> n >> k;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    for (int p = 1; p <= mx; p *= k)
        ps(p);
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

假设输入的 $n$ 不超过100，$2 \leq k \leq 100$，所有 $a_i$ 均为非负整数，且程序运行过程中不会发生整数溢出。

判断题

22、第16行从 $n$ 到1逆序扫描，可以保证每一轮计数排序是稳定的。（）

{{ select(22) }}

• 正确
• 错误

23、若输入中存在负数，该程序仍一定可以正确排序。（）

{{ select(23) }}

• 正确
• 错误

24、每执行一次 ps(p)，数组会按照当前 $k$ 进制位从小到大稳定排序。（）

{{ select(24) }}

• 正确
• 错误

单项选择题

25、当输入为：

5 10
31 14 25 11 20

第一次执行完 ps(1) 后，数组 $a$ 的内容依次为（）。

{{ select(25) }}

• 20 31 11 14 25
• 20 11 31 14 25
• 11 20 31 14 25
• 31 11 14 20 25

26、对于第25题中的输入，程序最终输出为（）。

{{ select(26) }}

• 31 25 20 14 11
• 11 14 20 25 31
• 20 11 31 14 25
• 11 20 14 25 31

27、设输入中最大数为 $M$，该程序的时间复杂度为（）。

{{ select(27) }}

• $\Theta(n + k)$
• $\Theta(n \log n)$
• $\Theta((n + k) \log_k M)$
• $\Theta(n^2)$

---

阅读程序（三）

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

const int N = 105;
const int P = 1000000007;

int n, m, s, t;
int dis[N], cnt[N];
vector<int> g[N];

int main() {
    cin >> n >> m >> s >> t;
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    
    memset(dis, -1, sizeof dis);
    
    queue<int> q;
    dis[s] = 0;
    cnt[s] = 1;
    q.push(s);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                cnt[v] = cnt[u];
                q.push(v);
            } else if (dis[v] == dis[u] + 1) {
                cnt[v] = (cnt[v] + cnt[u]) % P;
            }
        }
    }
    cout << dis[t] << " " << cnt[t] << endl;
    return 0;
}

假设输入的是有向图，且点编号均在合法范围内。

判断题

28、如果从 $s$ 无法到达 $t$，程序会输出 -1 0。（）

{{ select(28) }}

• 正确
• 错误

29、如果输入中有两条完全相同的有向边，则可能影响 cnt[t] 的值。（）

{{ select(29) }}

• 正确
• 错误

30、程序中的 cnt[t] 统计的是从 $s$ 到 $t$ 的所有简单路径条数。（）

{{ select(30) }}

• 正确
• 错误

单项选择题

31、当输入为：

5 6 1 5
1 2
1 3
2 4
3 4
2 5
3 5

程序输出为（）。

{{ select(31) }}

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

32、该程序的时间复杂度为（）。

{{ select(32) }}

• $\Theta(n)$
• $\Theta(m)$
• $\Theta(n + m)$
• $\Theta(nm)$

33、如果将队列 queue<int> 改为栈 stack<int>，且其他代码不变，则程序仍一定正确。（）

{{ select(33) }}

• 正确
• 错误
• 只在无环图上正确
• 只在完全图上正确

---

三、完善程序题

共2题，每空3分，共计30分。

完善程序（一）：DAG路径计数

给定一个 $n$ 个点、$m$ 条边的有向无环图，点编号为1到 $n$。求从1到 $n$ 的不同路径数量，答案对 1000000007 取模。

试补全程序。

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

const int N = 100005;
const int P = 1000000007;

int n, m;
int deg[N], dp[N];
vector<int> g[N];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        ①;
        deg[v]++;
    }
    
    queue<int> q;
    
    for (int i = 1; i <= n; i++)
        if (②) q.push(i);
    
    dp[1] = 1;
    
    while (!q.empty()) {
        int u = q.front();
        
        q.pop();
        for (int v : g[u]) {
            dp[v] = ③;
            
            if (④)
                q.push(v);
        }
    }
    
    cout << ⑤ << endl;
    return 0;
}

34、①处应填（）。

{{ select(34) }}

• g[u].push_back(v)
• g[v].push_back(u)
• g[u].push_back(u)
• g[v].push_back(v)

35、②处应填（）。

{{ select(35) }}

• deg[i]
• deg[i] == 0
• deg[i] == 1
• i == 1

36、③处应填（）。

{{ select(36) }}

• dp[u]
• (dp[v] + 1) % P
• (dp[v] + dp[u]) % P
• (dp[u] + 1) % P

37、④处应填（）。

{{ select(37) }}

• --deg[v] == 0
• deg[v] == 0
• deg[v]-- == 0
• deg[u] == 0

38、⑤处应填（）。

{{ select(38) }}

• dp[1]
• dp[m]
• dp[n]
• deg[n]

---

完善程序（二）：逆序对计数

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$，求逆序对数量，即满足 $i < j$ 且 $a_i > a_j$ 的二元组 $(i, j)$ 数量。

试补全程序。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200005;
int n, m;
int a[N], b[N], tr[N];
int lb(int x) {
    return ①;
}
void add(int x, int v) {
    for (; x <= m; x += lb(x))
        ②;
}
int qry(int x) {
    int s = 0;
    for (; x; x -= lb(x))
        ③;
    return s;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - (b + 1);
    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        int x = lower_bound(b + 1, b + m + 1, a[i]) - b;
        ans += ④;
        ⑤;
    }
    cout << ans << endl;
    return 0;
}

39、①处应填（）。

{{ select(39) }}

• x & -x
• x | -x
• x ^ -x
• x + 1

40、②处应填（）。

{{ select(40) }}

• tr[x] = v
• tr[x] += v
• tr[v] += x
• x += tr[x]

41、③处应填（）。

{{ select(41) }}

• s = tr[x]
• s += x
• s += tr[x]
• tr[x] += s

42、④处应填（）。

{{ select(42) }}

• qry(x)
• qry(x - 1)
• qry(m) - qry(x)
• qry(m)

43、⑤处应填（）。

{{ select(43) }}

• add(x, 1)
• add(x - 1, 1)
• add(m, x)
• qry(x)