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

每题有且仅有一个正确选项。

1. 下列无符号数中，最小的数是（ ），下标表示该数的进制。

{{ select(1) }}

• $(11011001)_2$
• $(75)_{10}$
• $(37)_8$
• $(2A)_{16}$

2. 若逻辑变量 $A$、$C$ 为真，$B$、$D$ 为假，以下逻辑运算表达式为真的有（ ）。

{{ select(2) }}

• $(A \land B) \lor (C \land D \lor \lnot A)$
• $(B \lor C \lor D) \lor D \land A$
• $A \land (D \lor \lnot C) \land B$
• $(D \lor \lnot C) \land \lnot B \land \lnot C$

3. 已知 $a,b,c,d,e,f,g$ 七个人中，$a$ 会讲英语，$b$ 会讲英语和汉语，$c$ 会讲英语、意大利语和俄语，$d$ 会讲汉语和日语，$e$ 会讲意大利语和德语，$f$ 会讲俄语、日语和法语，$g$ 会讲德语和法语。将他们的座位安排在圆桌旁，有多少种本质不同的排列方法可以使每个人都能与他身边的人交流（ ）。

{{ select(3) }}

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

4. 如果对一个已经升序的数组进行排序，下列算法中可能花费时间反而比乱序数组多的是（ ）。

{{ select(4) }}

• 堆排序
• 插入排序
• 冒泡排序
• 快速排序

5. 按中序遍历二叉树的结果为 ABC，有（ ）种不同形态的二叉树可以得到这一遍历结果。

{{ select(5) }}

• $3$
• $4$
• $5$
• $6$

6. 设一个栈与一个队列的初始状态均为空。元素 1、2、3、4、5、6 依次进入栈，且每个元素出栈后即进入队列，若出队的顺序为 2、4、3、6、5、1，则栈的容量至少应该为（ ）。

{{ select(6) }}

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

7. 整型数组 a 中有 n 个元素，能计算 a 中有多少个数字大于 lower 且小于 upper 的函数，应该将下划线依次替换为：

int solve(int a[], int n, int lower, int upper)
{
    std::sort(a, a + n);
    auto begin = std::________(a, a + n, lower);
    auto end = std::________(a, a + n, upper);
    return end - begin;
}

{{ select(7) }}

• lower_bound、lower_bound
• lower_bound、upper_bound
• upper_bound、lower_bound
• upper_bound、upper_bound

8. 二叉树 $T$ 的广度优先遍历序列为 $A,B,C,D,E,F,G,H,I$，已知 $A$ 是 $C$ 的父节点，$D$ 是 $G$ 的父节点，$F$ 是 $I$ 的父节点，树中所有节点的最大深度为 $3$，根节点的深度为 $0$，可知 $E$ 的父节点可能是（ ）。

{{ select(8) }}

• $A,B$
• $B,C$
• $A,B,F$
• $B,C,E$

9. 已知字符集 $A,B,C,D,E,F,G,H$。若各字符的哈夫曼编码依次是 0100、10、0000、0101、001、011、11、0001，则编码序列 0100011001001011110101 的译码结果是（ ）。

{{ select(9) }}

• acgabfh
• adbagbb
• afbeagd
• afeefgd

10. 字符串 ababacbab 和字符串 abcba 的最长公共子串是（ ）。

{{ select(10) }}

• abcba
• cba
• abc
• bcba

11. 设有一个含有 $13$ 个元素的 Hash 表（下标范围为 0~12），Hash 函数是：H(key) = key % 13。用线性探查法解决冲突，则对于序列 {2、8、31、20、19、18、53、27}，18 应放在下标为（ ）的位置。

{{ select(11) }}

• $0$
• $4$
• $5$
• $9$

12. 无向图 G=(V,E)，期中 V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

{{ select(12) }}

• a, b, e, c, d, f
• a, c, f, e, b, d
• a, e, b, c, f, d
• a, b, e, d, f, c

13. 平面上有三条平行直线，每条直线上分别有 $7,5,6$ 个点，且不同直线上的三个点都不在同一条直线上。用这些点为顶点，能组成多少个不同四边形（ ）。

{{ select(13) }}

• $210$
• $751$
• $1495$
• $2250$

14. 已知 p 为 int 类型，q 为 int * 类型，下列赋值语句不符合语法的是（ ）。

{{ select(14) }}

• *q = p;
• p = *q;
• *(p + q) = p;
• *(p + q) = q;

15. 计算机能直接执行的指令包括两部分，它们是（ ）。

{{ select(15) }}

• 源操作数与目标操作数
• 操作码与操作数
• ASCII码与汉字代码
• 数字与字符

二、阅读程序（判断题1分，选择题3分，共计40分）

判断题正确填 T，错误填 F。

第1题

int solve1(int n)
{
    int s = 0;
    for (int i = 1; i <= n; ++i) {
        int f = 1;
        for (int j = i; j >= 1; --j) {
            f = f * i;
        }
        s = s + f;
    }
    return s;
}

int solve2(int n)
{
    int s = 0;
    for (int i = n; i >= 1; --i)
    {
        s = s + 1;
        s = s * i;
    }
    return s;
}

保证 solve1 与 solve2 的参数 n 是正整数。

判断题

16. solve1(4) 的返回值为 33（ ）。

{{ select(16) }}

• 正确
• 错误

17. solve2(3) 的返回值为 10（ ）。

{{ select(17) }}

• 正确
• 错误

选择题

18. 关于 solve1(n) 与 solve2(n) 的大小关系，下列说法正确的是（ ）。

{{ select(18) }}

• 必然有 solve1(n) < solve2(n)
• 必然有 solve1(n) == solve2(n)
• 必然有 solve1(n) > solve2(n)
• 两者大小关系不确定

19. 两个函数都有唯一的从大循环到小的 for 语句，如果将这两条语句的循环次序颠倒，则返回值（ ）。

{{ select(19) }}

• solve1 不变，solve2 变大
• solve1 不变，solve2 变小
• solve1 变小，solve2 变小
• solve1 变大，solve2 变小

20. solve1(n) 与 solve2(n) 的时间复杂度为（ ）。

{{ select(20) }}

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

第2题

bool move(int b[], int n)
{
    for (int i = 0; i < n; ++i) {
        if (b[i] == 1) {
            b[i] = 0;
        }
        else {
            b[i] = 1;
            return true;
        }
    }
    return false;
}

void loop(int n)
{
    int b[n];
    for (int i = 0; i < n; ++i) b[i] = 0;
    do {
        for (int i = 0; i < n; ++i) std::cout << b[i];
        std::cout << "\n";
    }
    while (move(b, n));
}

保证 loop 的参数 n 是一个正整数。

判断题

21. loop(n) 可能会陷入无尽的循环（ ）。

{{ select(21) }}

• 正确
• 错误

22. 无论 n 是多少，loop(n) 输出的 0 与 1 必然一样多。

{{ select(22) }}

• 正确
• 错误

23. 当 $n=6$ 时，输出的第 $5$ 行第 $4$ 列的字符为 0（ ）。

{{ select(23) }}

• 正确
• 错误

24. 当 $n=16$ 时，输出的第 $523$ 行第 $14$ 列的字符为 1（ ）。

{{ select(24) }}

• 正确
• 错误

选择题

25. loop(2) 输出有（ ）行。

{{ select(25) }}

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

26. loop(n) 的时间复杂度为（ ）。

{{ select(26) }}

• $\Theta(2^n)$
• $\Theta(n\cdot2^n)$
• $\Theta(n^2\cdot2^n)$
• $\Theta(4^n)$

27. 以下说法错误的是（ ）。

{{ select(27) }}

• loop(n) 前一半输出全是偶数，后一半输出全是奇数
• 若将 loop(n) 输出的每行内容看成一个数字，则它们是依次递增的
• loop(n) 输出的每一行内容都是不同的
• loop(n) 输出的每一列内容都是不同的

第三题

struct flat_map {
    struct {
        int key;
        int value;
    } bucket[65536];
    int size = 0;

    struct result {
        int index;
        bool hit;
    };
    result find(int begin, int end, int key) {
        if (begin == end)
            return {begin, false};
        else {
            int mid = begin + (end - begin) / 2;
            if (key < bucket[mid].key)
                return find(begin, mid, key);
            else if (bucket[mid].key < key)
                return find(mid+1, end, key);
            else
                return {mid, true};
        }
    }

    int get(int key) {
        result p = find(0, size, key);
        if (p.hit)
            return bucket[p.index].value;
        else
            return 0;
    }

    void put(int key, int value) {
        result p = find(0, size, key);
        for (int i = size; i > p.index; --i)
            bucket[i] = bucket[i - 1];
        size++;
        bucket[p.index].key = key;
        bucket[p.index].value = value;
    }
};

判断题

28. flat_map 实现了一种关系型容器（ ）。

{{ select(28) }}

• 正确
• 错误

29. flat_map 按照键的大小顺序，将键与值配对，存储到了一块连续的内存序列里（ ）。

{{ select(29) }}

• 正确
• 错误

30. 若数组 bucket 的下标在 [b, e) 范围内存在键 k，find(b, e, k) 函数返回的 hit 为 false（ ）。

{{ select(30) }}

• 正确
• 错误

31. 当调用 get(k) 后发现 k 不存在，flat_map 会为 k 分配一块内存并将它对应的值置为 0（ ）。

{{ select(31) }}

• 正确
• 错误

选择题

32. 记 $s$ 表示容器的大小 size，调用 get(key) 的最坏时间复杂度为（ ）。

{{ select(32) }}

• $\Theta(s)$
• $\Theta(\log s)$
• $\Theta(s\log s)$
• $\Theta(s^2)$

33. 记 $s$ 表示容器的大小 size，调用 put(key, value) 的最坏时间复杂度为（ ）。

{{ select(33) }}

• $\Theta(s)$
• $\Theta(\log s)$
• $\Theta(s\log s)$
• $\Theta(s^2)$

34. 以下说法错误的是（ ）。

{{ select(34) }}

• flat_map 的优点是插入数据时移动数据少。
• flat_map 的优点是数据紧凑排列，空间使用效率高。
• flat_map 的优点是查找数据的效率高。
• flat_map 的优点是代码紧凑，实现简短。

35. 若调用 put(k, v) 时已经存在相同的键 k 时，以下哪一种处理策略最符合上述代码的逻辑（ ）。

{{ select(35) }}

• 熔断（Breaker）：抛出异常，向系统报告错误
• 回滚（Rollback）：不做任何修改，撤销 put 操作
• 覆盖（Rewrite）：将键所对应的老值覆盖成新值
• 忽略（Ignore）：对有可能出错的操作置之不理

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

第1题

给定含有 $n$ 个顶点的有向完全图（顶点编号为 $0$ 到 $n-1$）。顶点 $x$ 到 $y$ 的边的权重为 g[x][y]。

请找出一条不重复经过任何点的路径，从顶点 $0$ 出发到顶点 $n-1$ 结束，路径上所有边的权重的异或值尽可能大。

int n, m;
long long g[MAXN][MAXN];
bool visited[MAXN] = {false};

int dfs(int node, int path) {
    if (____(1)____)
    {
        return ____(2)____;
    }

    int best = 0;
    visited[node] = true;
    for (int next = 0 ; next < ____(3)____; ++next)
    {
        if (____(4)____)
        {
            best = std::max(best, ____(5)____);
        }
    }
    visited[____(6)____] = ____(7)____;
}

int solve()
{
    return ____(8)____;
}

36. (1) (2) 处应填（ ）。

{{ select(36) }}

• node == n，path
• node > n，0
• node < n，path
• node > n，1

37. (3) (4) 处应填（ ）。

{{ select(37) }}

• n，visited[next]
• n，!visited[next]
• m，visited[next]
• m，!visited[next]

38. (5) 处应填（ ）。

{{ select(38) }}

• dfs(next, path ^ g[next][node]);
• dfs(next, path ^ g[node][next]);
• dfs(node + 1, path ^ g[next][node]);
• dfs(node + 1, path ^ g[node][next]);

39. (6) (7) 处应填（ ）。

{{ select(39) }}

• node，false
• node，true
• next，false
• next，true

40. (8) 处应填（ ）。

{{ select(40) }}

• dfs(0, 0)
• dfs(1, 0)
• dfs(0, 1)
• dfs(1, 1)

第2题

$n$ 个岛屿由 $n$ 座桥连成环。岛的编号为 $0$ 到 $n-1$，第 $i$ 座桥连第 $i$ 号岛与第 $(i+1)\bmod n$ 号岛。

某旅行团从第 $x_1$ 号岛出发，依次访问的岛编号为 $x_2,\ldots,x_m$。

现在需要选择拆掉一座桥，请问拆掉哪一座桥可以使得旅行团的过桥次数达到最小。

int solve(int n, int m, int x[])
{
    int diff[n];
    for (int i = 0; i < n; ++i) diff[i] = 0;
    int common = 0;
    for (int i = 1; i < m; ++i)
    {
        int prev = x[i - 1];
        int next = x[i];
        int begin, end;
        if (prev < next) {
            begin = prev;
            end = next;
        }
        else {
            begin = next;
            end = prev;
        }
        common += ____(1)____;
        int inc = ____(2)____;
        diff[____(3)____] += inc;
        diff[____(4)____] -= inc;
        prev = next;
    }
    int best = n * m;
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        ____(5)____;
        if (best > sum) best = sum;
    }
    return ____(6)____;
}

41. (1) 处应填（ ）。

{{ select(41) }}

• end - begin
• end - begin - 1
• end - begin + 1
• end - begin - 2

42. (2) 处应填（ ）。

{{ select(42) }}

• common
• end*2 - begin*2
• begin*2 - end*2
• n + begin*2 - end*2

43. (3) (4) 处应填（ ）。

{{ select(43) }}

• begin，end
• begin，end + 1
• end，begin
• end + 1，begin

44. (5) 处应填（ ）。

{{ select(44) }}

• sum += diff[i]
• sum += diff[i + 1]
• sum += diff[i + 1] - diff[i]
• sum += diff[i] - diff[i-1]

45. (6) 处应填（ ）。

{{ select(45) }}

• sum
• best
• best - common
• best + common