一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

第1题

在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？() {{ select(1) }}

• pwd
• cd
• ls
• echo

第2题

假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？() {{ select(2) }}

• (O(n))
• (O(log n))
• (O(nlog n))
• (O(1))

第3题

在C++中，以下哪个函数调用会造成栈溢出？() {{ select(3) }}

• int foo(){return 0;}
• int bar(){int x=1;return x;}
• void baz(){int a[1008]; baz();}
• void qux(){return; }

第4题

在一场比赛中，有10名选手参加，前三名将获得金、银、铜牌。若不允许并列、且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？() {{ select(4) }}

• 120
• 720
• 504
• 1000

第5题

下面哪个数据结构最适合实现先进先出（FIFO）的功能？() {{ select(5) }}

• 栈
• 队列
• 线性表
• 二叉搜索树

第6题

已知(f(1)=1)，且对于(n ≥2)有$(f(n)=f(n-1)+f(\lfloor n / 2\rfloor))，则(f(4))$的值为：() {{ select(6) }}

• 4
• 5
• 6
• 7

第7题

假设有一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？() {{ select(7) }}

• 所有顶点的度数均为偶数
• 该图连通
• 该图存在一个欧拉回路
• 该图的边数是奇数

第8题

对数组进行二分查找的过程中，以下哪个条件必须满足？() {{ select(8) }}

• 数组必须是有序的
• 数组必须是无序的
• 数组长度必须是2的幂
• 数组中的元素必须是整数

第9题

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

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

第10题

在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对，表的装因子为(alpha(0<alpha≤1))。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为() {{ select(10) }}

• (O(1))
• (O(log n))
• (O(1/(1-alpha)))
• (O(n))

第11题

假设有一棵h层的完全二叉树，该树最多包含多少个结点？() {{ select(11) }}

• (2^h - 1)
• (2^{h+1} - 1)
• (2^h)
• (2^{h+1})

第12题

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

• 120
• 210
• 630
• 5840

第13题

对于一个整数n，定义(f(n))为n的各位数字之和。问使(f(f(x))=10)的最小自然数x是多少？() {{ select(13) }}

• 29
• 199
• 299
• 399

第14题

设有一个长度为n的01字符串，其中有k个1，每次操作可以交换相邻两个字符。在最坏情况下将这k个1移到字符串最右边所需要的交换次数是多少？() {{ select(14) }}

• k
• (k*(k-1)/2)
• ((n - k)*k)
• ((2n - k - 1)*k/2)

第15题

如图是一张包含7个顶点的有向图，如果要删除其中一些边，使得从节点1到节点7没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？()

{{ select(15) }}

• 1
• 2
• 3
• 4

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

阅读程序（一）

#include <iostream>
using namespace std;
const int N = 1000;
int c[N];

int logic(int x, int y) {
    return (x & y) ^ ((x ^ y)| (~x & y));
}

void generate(int a, int b, int* c) {
    for (int i = 0; i < b; i++) {
        c[i] = logic(a, i) % (b + 1);
    }
}

void recursion(int depth, int* arr, int size) {
    if (depth <= 0 || size <= 1) return;
    int pivot = arr[0];
    int i = 0, j = size - 1;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    recursion(depth - 1, arr, j + 1);
    recursion(depth - 1, arr + i, size - i);
}

int main() {
    int a, b, d;
    cin >> a >> b >> d;
    generate(a, b, c);
    recursion(d, c, b);
    for (int i = 0; i < b; ++i) cout << c[i] << " ";
    cout << endl;
    return 0;
}

判断题

16. 当(1000 ≥ d ≥ 0)时，输出的序列是有序的。() {{ select(16) }}

• 正确
• 错误

17. 当输入“5 5 1”时，输出为“1 1 5 5 5”。() {{ select(17) }}

• 正确
• 错误

18. 假设数组c长度无限制，该程序所实现的算法的时间复杂度是(O(b))的。() {{ select(18) }}

• 正确
• 错误

单选题

19. 函数int logic(int x, int y)的功能是() {{ select(19) }}

• 按位与
• 按位或
• 按位异或
• 以上都不是

20. （4分）当输入为“10 100 100”时，输出的第100个数是() {{ select(20) }}

• 91
• 94
• 95
• 98

阅读程序（二）

#include <iostream>
#include <string>
using namespace std;
const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];

int solve() {
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = (1 << m) - 1; j >= 0; --j) {
            int k = (j << 2) | (s[i] - '0');
            if ((k & 11) == 11 && s[i] == '1') {
                dp[k] = (dp[k] + dp[j]) % P;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < (1 << m); ++i) {
        ans = (ans + 111 * i * dp[i]) % P;
    }
    return ans;
}

int solve2() {
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) {
        int cnt = 0;
        int num = 0;
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                num = num * 2 + (s[j] - '0');
                cnt++;
            }
        }
        ans += num;
    }
    return ans;
}

int main() {
    cin >> n >> m;
    cin >> s;
    if (n <= 20) {
        cout << solve2() << endl;
    }
    cout << solve() << endl;
    return 0;
}

判断题

21. 假设数组dp长度无限，函数solve()所实现的算法的时间复杂度是(O(n*2^m))。() {{ select(21) }}

• 正确
• 错误

22. 输入“11210000000008”时，程序输出两个数32和23。() {{ select(22) }}

• 正确
• 错误

23. （2分）在(n ≤ 10)时，solve()的返回值始终小于41。() {{ select(23) }}

• 正确
• 错误

单选题

24. 当(n=10)且(m=10)时，有多少种输入使得两行的结果完全一致？() {{ select(24) }}

• 1024
• 11
• 10
• 0

25. 当(n ≤ 6)时，solve()的最大可能返回值为() {{ select(25) }}

• 65
• 211
• 665
• 2059

26. 若(n = 8)，(m = 8)，solve和solve2的返回值的最大可能的差为() {{ select(26) }}

• 1477
• 1995
• 2059
• 2187

阅读程序（三）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 29, B2 = 31;
const int K1 = 10, K2 = 13;

typedef long long ll;

int n;
bool p[maxn];
int p1[maxn], p2[maxn];

struct H {
    int h1, h2, len;
    H(bool b = false) {
        h1 = b ? K1 : 0;
        h2 = b ? K2 : 0;
        len = 1;
    }
    H operator + (const H& h) const {
        H hh;
        hh.len = len + h.len;
        hh.h1 = (1LL * h1 * p1[h.len] + h.h1) % P1;
        hh.h2 = (1LL * h2 * p2[h.len] + h.h2) % P2;
        return hh;
    }
    bool operator == (const H& h) const {
        return len == h.len && h1 == h.h1 && h2 == h.h2;
    }
    bool operator < (const H& h) const {
        if (len != h.len) return len < h.len;
        else if (h1 != h.h1) return h1 < h.h1;
        else return h2 < h.h2;
    }
} h[maxn];

void init() {
    memset(p, 1, sizeof(p));
    p[0] = p[1] = false;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p1[i] = (1LL * B1 * p1[i - 1]) % P1;
        p2[i] = (1LL * B2 * p2[i - 1]) % P2;
        if (!p[i]) continue;
        for (int j = i * 2; j <= n; j += i) {
            p[j] = false;
        }
    }
}

int solve() {
    for (int i = n; i >= 1; --i) {
        h[i] = H(p[i]);
        if (2 * i + 1 <= n) {
            h[i] = h[2 * i] + H(p[i]) + h[2 * i + 1];
        } else if (2 * i <= n) {
            h[i] = h[2 * i] + H(p[i]);
        }
    }
    cout << h[1].h1 << endl;
    sort(h + 1, h + n + 1);
    int m = unique(h + 1, h + n + 1) - (h + 1);
    return m;
}

int main() {
    cin >> n;
    init();
    cout << solve() << endl;
    return 0;
}

判断题

27. 假设程序运行前能自动将maxn改为n+1，所实现的算法的时间复杂度是(O(nlog n))。() {{ select(27) }}

• 正确
• 错误

28. 时间开销的瓶颈是init()函数。() {{ select(28) }}

• 正确
• 错误

29. 若修改常数B1或K1的值，该程序可能会输出不同的结果。() {{ select(29) }}

• 正确
• 错误

单选题

30. 在solve()函数中，h[i]的合并顺序可以看作是：() {{ select(30) }}

• 二叉树的BFS序
• 二叉树的先序遍历
• 二叉树的中序遍历
• 二叉树的后序遍历

31. 输入“10”，输出的第一行是？() {{ select(31) }}

• 83
• 424
• 54
• 110101000

32. （4分）输入“16”，输出的第二行是？() {{ select(32) }}

• 7
• 9
• 10
• 12

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

完善程序（一）（序列合并）

有两个长度为N的单调不降序列A和B，序列的每个元素都是小于(10^9)的非负整数。在A和B中各取一个数相加可以得到(N^2)个和，求其中第K小的和。上述参数满足(N<=10^5)和(1<=K<=N^2)。

#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int upper_bound(int* a, int* an, int ai) {
    int l = 0, r = an - a - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] > ai) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return `a + l;`
}

long long get_rank(int sum) {
    long long rank = 0;
    for (int i = 0; i < n; ++i) {
        rank += upper_bound(b, b + n, sum - a[i]) - b;
    }
    return rank;
}

int solve() {
    int l = 0, r = ①;
    while (l < r) {
        int mid = ((long long)l + r) >> 1;
        if (②) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

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

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

• a[n-1] + b[n-1]
• a[n] + b[n]
• 2 * 1000000000
• 1000000000

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

• get_rank(mid) < k
• get_rank(mid) <= k
• get_rank(mid) > k
• get_rank(mid) >= k

35. 函数upper_bound的返回值表示（ ） {{ select(35) }}

• 数组中第一个大于ai的元素地址
• 数组中第一个大于等于ai的元素地址
• 数组中最后一个小于ai的元素地址
• 数组中最后一个小于等于ai的元素地址

36. 在upd函数中，①处应填（ ） {{ select(36) }}

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

37. 在upd函数中，②处应填（ ） {{ select(37) }}

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

完善程序（二）（次短路）

已知一个有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];
    head[a] = tot;
    to[tot] = b;
    w[tot] = c;
}

bool upd(int a, int b, int d, priority_queue<pair<int, int>>& q) {
    if (d >= dis[b]) return false;
    if (b < n) ①;
    dis[b] = d;
    q.push(②);
    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 ", a % n + 1);
}

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("%dn", dis2[t]);
        out(n + t);
        puts("");
    }
    return 0;
}

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

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

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

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

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

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

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

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

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

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