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

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

特殊分值说明：

• 第16~18题（判断题）每题2分
• 第19题、第25题（选择题）每题2分
• 其余判断题每题1.5分，其余选择题每题3分

一、单项选择题（共15题）

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

1、在Linux系统终端中，用于复制文件的命令是（）。

{{ select(1) }}

• ls
• cd
• cp
• mv

2、二进制数 $101101_2$ 与 $011011_2$ 的和为（）。

{{ select(2) }}

• $1000100_2$
• $1001000_2$
• $0111000_2$
• $1110000_2$

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

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

{{ select(3) }}

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

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

{{ select(4) }}

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

5、最适合实现先进先出功能的数据结构是（）。

{{ select(5) }}

• 栈
• 队列
• 堆
• 二叉搜索树

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

{{ select(6) }}

• 7
• 8
• 9
• 10

7、根结点高度为1，一棵含有2026个结点的二叉树高度至少为（）。

{{ select(7) }}

• 10
• 11
• 12
• 2026

8、从数字 0, 1, 2, 3, 4, 5 中选取4个互不相同的数字组成四位数，一共可以组成（）个不同的四位数。

{{ select(8) }}

• 240
• 300
• 360
• 120

9、一棵二叉搜索树的后序遍历序列为：1 3 2 5 7 6 4，则它的前序遍历序列为（）。

{{ select(9) }}

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

10、以下哪类图一定存在拓扑排序？

{{ select(10) }}

• 有向无环图
• 强连通有向图
• 完全无向图
• 含有有向环的图

11、车牌后5位中，前2位必须是大写英文字母，后3位必须是数字，每一位都可以重复，则共有（）种可能。

{{ select(11) }}

• 26000
• 52000
• 676000
• 1757600

12、有一个包含9个顶点的完全图，顶点编号为1到9，任意两点 $i, j$ 之间边权为 $|i - j|$。该图最小生成树的总权值为（）。

{{ select(12) }}

• 8
• 9
• 10
• 36

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

{{ select(13) }}

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

14、一个长度为 $n$ 的01字符串中有 $k$ 个1，每次操作可以交换相邻两个字符。最坏情况下，将所有1移动到字符串最右侧所需的交换次数为（）。

{{ select(14) }}

• $k$
• $\frac{k(k-1)}{2}$
• $k(n-k)$
• $\frac{(2n-k-1)k}{2}$

15、Dijkstra算法用于求单源最短路时，通常要求图中所有边权满足（）。

{{ select(15) }}

• 边权均为整数
• 边权非负
• 边权互不相同
• 图必须是无向图

---

二、阅读程序

除特殊说明外，判断题每题1.5分，选择题每题3分，共40分。

特殊分值说明：

• 第16~18题（判断题）每题2分
• 第19题、第25题（选择题）每题2分
• 其余判断题每题1.5分，其余选择题每题3分

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

阅读程序（一）

#include <iostream>
using namespace std;

unsigned f(unsigned x) {
    x ^= x << 3;
    x ^= x >> 5;
    return x & 255;
}

int main() {
    unsigned x;
    cin >> x;
    cout << f(x) << endl;
    return 0;
}

假设输入的 $x$ 是不超过255的自然数。

判断题

16、当输入为0时，程序输出0。

{{ select(16) }}

• 正确
• 错误

17、对任意合法输入，程序输出一定小于256。

{{ select(17) }}

• 正确
• 错误

18、当输入为1时，程序输出8。

{{ select(18) }}

• 正确
• 错误

单项选择题

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

{{ select(19) }}

• 60
• 62
• 63
• 64

20、当输入为32时，执行完语句 x ^= x << 3; 后，变量 $x$ 的值为（）。

{{ select(20) }}

• 256
• 320
• 288
• 296

21、函数 $f$ 的时间复杂度为（）。

{{ select(21) }}

• $\Theta(1)$
• $\Theta(\log x)$
• $\Theta(x)$
• $\Theta(x \log x)$

---

阅读程序（二）

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

bool ck(vector<int> &a, int x, ll k) {
    ll s = 0;
    for (int i = 0, j = 0; i < (int)a.size(); i++) {
        while (a[i] - a[j] > x) j++;
        s += i - j;
    }
    return s >= k;
}

int sol(vector<int> a, ll k) {
    sort(a.begin(), a.end());
    int l = 0, r = a.back() - a[0];
    while (l < r) {
        int m = (l + r) / 2;
        if (ck(a, m, k)) r = m;
        else l = m + 1;
    }
    return l;
}

int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << sol(a, k) << endl;
    return 0;
}

假设输入合法，且所有计算均不会溢出。

判断题

22、函数 sol 的参数 a 是按值传递，因此 main 中的数组顺序不会被 sol 改变。

{{ select(22) }}

• 正确
• 错误

23、当数组 $a$ 已经按非降序排列时，ck(a, x, k) 判断的是差值不超过 $x$ 的数对数量是否至少为 $k$。

{{ select(23) }}

• 正确
• 错误

24、将 if (ck(a, m, k)) r = m; 改为 if (ck(a, m, k)) r = m - 1; 后，程序仍一定正确。

{{ select(24) }}

• 正确
• 错误

单项选择题

25、当输入为：

5 4
1 5 9 2 6

程序输出为（）。

{{ select(25) }}

• 1
• 3
• 4
• 5

26、设 $A = \max a_i - \min a_i + 1$，函数 sol 的时间复杂度为（）。

{{ select(26) }}

• $\Theta(n)$
• $\Theta(n \log n)$
• $\Theta(n \log n + n \log A)$
• $\Theta(n^2)$

27、程序整体求解的是（）。

{{ select(27) }}

• 数组中第 $k$ 小的元素
• 数组中第 $k$ 大的元素
• 数组中第 $k$ 小的两数之和
• 数组中第 $k$ 小的两两绝对差

---

阅读程序（三）

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

int n;
int a[22], b[1 << 20];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int m = 1 << n;
    for (int s = 0; s < m; s++) {
        int c = 0, v = 0;
        for (int i = 0; i < n; i++) {
            if (s >> i & 1) {
                c++;
                v += a[i];
            }
        }
        if (c % 2) b[s] = -v;
        else b[s] = v;
    }
    sort(b, b + m);
    cout << b[0] << " " << b[m - 1] << endl;
    int t = 0;
    for (int i = 0; i < m; i++)
        if (b[i] == 0) t++;
    cout << t << endl;
    return 0;
}

假设 $1 \le n \le 20$，且所有 $a_i$ 均为正整数。

判断题

28、第一行输出的第一个数一定不大于0。

{{ select(28) }}

• 正确
• 错误

29、若所有 $a_i$ 同时乘以2，则第二行输出也一定乘以2。

{{ select(29) }}

• 正确
• 错误

30、删除 sort(b, b + m); 后，第二行输出不变。

{{ select(30) }}

• 正确
• 错误

单项选择题

31、当输入为：

3
1 2 4

第一行输出为（）。

{{ select(31) }}

• -7 6
• -7 7
• 0 6
• -4 6

32、当输入为：

4
1 2 3 4

第二行输出为（）。

{{ select(32) }}

• 1
• 2
• 4
• 8

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

{{ select(33) }}

• $\Theta(2^n)$
• $\Theta(n \cdot 2^n)$
• $\Theta(n^2)$
• $\Theta(n!)$

---

三、完善程序（每题3分，共30分）

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

完善程序（一）

给定一个 $n$ 个点、$m$ 条边的无向带权图，边权均为非负整数。给定起点 $s$ 和终点 $t$。

现在有一张折扣卡，可以在经过某一条边时使用一次，使这条边的费用变为 $\lfloor w/2 \rfloor$。折扣卡最多使用一次，也可以不使用。

求从 $s$ 到 $t$ 的最小费用。

试补全程序。

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

const int N = 100005;
const ll INF = (1LL << 60);

struct Ed {
    int v, w;
};

struct Sta {
    ll d;
    int u, c;
    bool operator<(const Sta &o) const {
        return ①;
    }
};

int n, m, s, t;
vector<Ed> g[N];
ll dis[N][2];

int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++)
        dis[i][0] = dis[i][1] = INF;
    priority_queue<Sta> q;
    ②;
    q.push({0, s, 0});
    while (!q.empty()) {
        Sta x = q.top();
        q.pop();
        if (③) continue;
        for (auto e : g[x.u]) {
            int v = e.v;
            int c = x.c;
            if (④ < dis[v][c]) {
                dis[v][c] = ④;
                q.push({dis[v][c], v, c});
            }
            if (!c && ⑤ < dis[v][1]) {
                dis[v][1] = ⑤;
                q.push({dis[v][1], v, 1});
            }
        }
    }
    cout << min(dis[t][0], dis[t][1]) << endl;
    return 0;
}

34、①处应填（）。

{{ select(34) }}

• d > o.d
• d < o.d
• u > o.u
• c > o.c

35、②处应填（）。

{{ select(35) }}

• dis[s][0] = 0
• dis[s][1] = 0
• dis[t][0] = 0
• dis[t][1] = 0

36、③处应填（）。

{{ select(36) }}

• x.d == dis[x.u][x.c]
• x.d != dis[x.u][x.c]
• x.u == t
• x.c == 1

37、④处应填（）。

{{ select(37) }}

• x.d
• x.d + e.w
• x.d + e.w / 2
• dis[v][c] + e.w

38、⑤处应填（）。

{{ select(38) }}

• x.d
• x.d + e.w
• x.d + e.w / 2
• dis[v][1] + e.w

---

完善程序（二）

给定一个长度为 $n$ 的整数数组 $a$，求所有满足 $i < j$ 的 $|a_i - a_j|$ 中第 $k$ 小的值。

试补全程序。

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

const int N = 100005;

int n;
ll k;
int a[N];

bool ck(int x) {
    ll s = 0;
    for (int i = 0, j = 0; i < n; i++) {
        while (①) j++;
        ②;
    }
    return ③;
}

int sol() {
    sort(a, a + n);
    int l = 0, r = ④;
    while (l < r) {
        int m = (l + r) >> 1;
        if (ck(m)) r = m;
        else ⑤;
    }
    return l;
}

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

39、①处应填（）。

{{ select(39) }}

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

40、②处应填（）。

{{ select(40) }}

• s += j
• s += i - j
• s += n - i
• s++

41、③处应填（）。

{{ select(41) }}

• s < k
• s <= k
• s >= k
• s == k

42、④处应填（）。

{{ select(42) }}

• a[n - 1] - a[0]
• a[0] - a[n - 1]
• a[n - 1] + a[0]
• n

43、⑤处应填（）。

{{ select(43) }}

• r = m - 1
• l = m
• l = m + 1
• r = m + 1

---

---