第四套

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

1. 对于图，以下何种说法是正确的？{{ select(1) }}

• 2 - 可染色的图不是二分图
• 在有向图中，一个点只能属于一个强连通分量
• 无向欧拉图可能存在度数为奇数的点
• 边双连通分量删掉一个点后一定是点双连通分量

2. 在 $0,1,2,3,4,5,6,7$ 中选取 $4$ 个不重复的数字能组成几个不同的偶数，不允许前导 $0$？{{ select(2) }}

• 70
• 1680
• 210
• 630

3. 对于数据结构，一下何种说法是正确的？{{ select(3) }}

• ST 表的单次区间查询复杂度为 O(log n)
• 完全二叉树的某个节点可能只有右儿子
• 二叉树的前序遍历可以唯一的确定二叉树的形态
• c++ 内置的优先队列不是使用红黑树实现的

4. 定义

那么代码 int res = dfs(n); 的复杂度为{{ select(4) }}

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

5. 以下数中何数最大{{ select(5) }}

• $100_8$
• $121_7$
• $40_{16}$
• $1000001_2$

6. 投掷一枚六面骰子，若每一面都是等概率，那么至少几次投掷才能保证至少有一次出现点数为 $6$ 的概率大于 $\frac{1}{2}$？{{ select(6) }}

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

7. 字符串序列 aba 在序列 abababacabab 中出现了几次？{{ select(7) }}

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

8. 对于最短路算法，以下正确的是？{{ select(8) }}

• Dijkstra 算法是一种求解任意图的单源最短路的算法
• Floyd 算法的复杂度为 $O(n^2)$
• Bellman–Ford 算法可以判断负环
• Dijkstra 算法暴力实现的复杂度为 $O(n\text{log}n)$

9. 树上任意两节点之间最长的简单路径即为树的直径。若树有多条直径，则下面哪种树的直径中点一定重合{{ select(9) }}

• 满二叉树
• 边权绝对值为 $1$ 的树
• 深度为 $3$ 的树
• 边权为正的树

10. 从 $0$ 到 $10$ 中选择 $5$ 个数形成一个序列，问其中有多少个单调递增的序列{{ select(10) }}

• $462$
• $231$
• $924$
• $480$

11. 罐中放有 $1$ 个白球和 $2$ 个黑球，每次从罐中随机抽取一个球，并连同 $2$ 个同色球一起放入罐中。则在第 $5$ 次取球时取出白球的概率为 {{ select(11) }}

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

12. $4095$ 个节点的二叉树最少有多少层 {{ select(12) }}

• $11$
• $12$
• $13$
• $14$

13. 树的前序遍历为 ABDEHCFGI，中序遍历为 DBHEAFCGI，则树的后序遍历为 {{ select(13) }}

• DHEBFIGCA
• DHEBFIGAC
• DHEBIFGCA
• DHEBIFGAC

14. 以比较为基本运算，只考虑数组元素间的比较，在 $n$ 个数的数组中找次大的数，在最坏情况下至少要做（）次运算。{{ select(14) }}

• $2n$
• $n$
• $2n-1$
• $2n-3$

15. 现有一个地址区间为 $0$ 到 $12$ 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储（到 $10$ 冲突了就从 $0$ 开始往后），现在要依次存储 $(0,1,2,3,4,5,6,7)$，哈希函数为 $h(x)=x^2+\lfloor x/2\rfloor \mod 13$。请问 $7$ 存储在哈希表哪个地址中？{{ select(15) }}

• $2$
• $4$
• $6$
• $0$

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

#include <iostream>

using namespace std;

const int mod = 998244353;
int n;
int num[1002][1002];

void init() {
    num[0][0] = 1;
    for(int i = 0; i <= 1000; i++) {
        for(int j = 0; j <= i; j++) {
            num[i][j+1] = (num[i][j+1] + num[i][j]) % mod;
            num[i+1][j] = (num[i+1][j] + num[i][j]) % mod;
        }
    }
}

int sol1(int x) {
    return num[x][x];
}

int sol2(int x) {
    int ans = 1;
    for(int i = 2; i <= x; i++) {
        ans = 1ll * ans * (4*i-2) % mod / (i+1) % mod;
    }
    return ans;
}

int main() {
    init();
    cin >> n;
    cout << sol1(n) << endl;
    cout << sol2(n) << endl;
}

$0\leqslant n \leqslant 1000$

判断题

16. 当输入为 5 时，输出的第一行为 $42$。{{ select(16) }}

• √
• ×

17. 当输入为 4 时，输出的第二行为 $13$。{{ select(17) }}

• √
• ×

18. 无论 $n$ 为何值，两行的输出一定相等。{{ select(18) }}

• √
• ×

19. 当 $n$ 为 $1000$ 时，输出的第二行一定小于 $10^7$。{{ select(19) }}

• √
• ×

单选题

20. sol1(n) 的时间复杂度为。{{ select(20) }}

• $O(1)$
• $O(n)$
• $O(n\sqrt n)$
• $O(n^2)$

21. sol2(n) 的时间复杂度为。{{ select(21) }}

• $O(1)$
• $O(n)$
• $O(n\sqrt n)$
• $O(n^2)$

$1 \leqslant n \leqslant 19$ , 保证图连通且无自环和重边

判断题

22. 将第 $22$ 行删除，输出不变。{{ select(22) }}

• √
• ×

23. 存在一种输入，使得输出为负数。{{ select(23) }}

• √
• ×

24. 当输入为 3 3 1 2 2 3 3 1 时，输出为 1。{{ select(24) }}

• √
• ×

单选题

25. 时间复杂度为。{{ select(25) }}

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

26. 当 $m=n$ 时，输出最大是。{{ select(26) }}

• $0$
• $1$
• $2$
• $3$

27. 当 $m=n+1$ 时，输出最大是。{{ select(27) }}

• $0$
• $1$
• $2$
• $3$

$1 \leqslant n \leqslant 30$ , 图连通且无重边和自环

判断题

28. 当输入为 2 1 1 2 时，输出为 1 1。{{ select(28) }}

• √
• ×

29. 将第 $22$ 行改为 dis[1] = -1 ，输出一定不变。{{ select(29) }}

• √
• ×

30. 将第 $31$ 行改为 dis[v] <= dis[u] + 1 输出除了最后一个数，其余一定变大。{{ select(30) }}

• √
• ×

单选题

31. （2 分）当输入为 4 4 1 2 1 3 2 4 3 4 时，输出为。{{ select(31) }}

• 1 1 1 2
• 1 1 2 2
• 1 2 2 1
• 1 1 1 1

32. 时间复杂度为。{{ select(32) }}

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

33. 当输入中 $m=n+1$ 时，输出应满足。{{ select(33) }}

• 最大值可能大于 $n+1$。
• 至少有 $n/2$ 个数大于 $1$。
• 输出可能为 1 2 4 4 4 ...。
• 至多有 $n/2$ 个数大于 $1$。

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

给定 $n$ 个点 $m$ 条边的无向简单图，顶点编号从 $1$ 到 $n$。定义奇/偶环为包含奇/偶数条边的简单环。

分别回答图中是否有奇/偶环。

程序通过找双连通分量的方式完成，试补全程序。

34. (1)处应填 {{ select(34) }}

• dep[v] == 0
• dep[v] != 0
• dep[u] == dep[v]
• dep[u] < dep[v]

35. (2)处应填 {{ select(35) }}

• dep[u] & 1 == dep[v] & 1
• ((dep[u] + dep[v]) & 1) == 0
• (dep[u] + dep[v]) & 1
• dep[u] & 1 != dep[v] & 1

36. (3)处应填 {{ select(36) }}

• --st[up[u]]; ++st[v];
• ++st[u]; --st[up[v]];
• --st[u]; ++st[up[v]];
• ++st[up[u]]; --st[v];

37. (4)处应填 {{ select(37) }}

• st[u] >= 2
• st[u] >= 1
• st[u] <= 2
• st[u] <= 1

38. (5)处应填 {{ select(38) }}

• to[u].insert(v); to[v].insert(u);
• to[u].push(v); to[v].push(u);
• to[u].add(v); to[v].add(u);
• to[u].push_back(v); to[v].push_back(u);

斐波那契是满足递推式 $F_0 = F_1 = 1$ , $F_{n+2}=F_{n+1}+F_n$ 的序列

现给定一个长度为 $n$ 的数列 $c$ ，你需要将每一个数分成若干个部分

问是否存在一种对部分进行重排后形成的序列满足

1. 同一个数分成的部分在序列中不相邻
2. 序列第 $i$ 项的值为 $F_i$

已知对于斐波那契数列有

• $F_0+F_2+\cdots+F_{2n}=F_{2n+1}-1$

• $F_1+F_3+\cdots+F_{2n+1}=F_{2n+2}$

  

  $1 \leqslant k \leqslant 100$ , $1 \leqslant c_i \leqslant 10^9$

39. (1)应填 {{ select(39) }}

• fib[i] = fib[i-1] + fib[i-2]
• fib[i] = fib[i-1] - fib[i-2]
• fib[i+1] = fib[i] + fib[i-1]
• fib[i+1] = fib[i] - fib[i-1]

40. (2)应填 {{ select(40) }}

• fib[i+2]
• fib[i+1]-1
• fib[i+2]-1
• fib[i+1]

41. (3)应填 {{ select(41) }}

• (int i=x; i>=0; i--)
• (int i=0; i<=x; i++)
• (int i=x; i>0; i--)
• (int i=0; i<x; i++)

42. (4)应填 {{ select(42) }}

• (u.first <= fib[i])
• (u.first < fib[i])
• (u.first > fib[i])
• (u.first >= fib[i])

43. (5)应填 {{ select(43) }}

• last_used = u.first;
• last_used = u.second;
• last_used = -1;
• last_used = i;