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

1. $(1047)_8 = \quad (\quad )$。

{{ select(1) }}

• $(1011011101)_2$
• $(11010)_5$
• $(20213)_4$
• $(308)_{16}$

2. 若逻辑变量 A、C 为真，B、D 为假，以下逻辑表达式的值为假的是 $\quad (\quad )$。

{{ select(2) }}

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

3. 小恺编写了如下函数，希望计算斐波那契数列 $f(n)$ 第 n 项对 10000 取余数的值（运行空间限制 128MB，时限 1 秒）。调用 $f(12345)$ 最可能发生的问题：

int f(int x) {
    if(x <= 2)
        return 1;
    int ans = f(x - 1) + f(x - 2);
    ans %= 10000;
    return ans;
}

{{ select(3) }}

• 运行时间超时
• 栈溢出
• 访问无效内存
• 返回错误的答案

4. 表达式 a+b*(c-d)/e-f 的后缀表达式为 $\quad (\quad )$。

{{ select(4) }}

• -a/*b-c-cdef
• abcd-*e/+f-
• +ab*-cd/e-f
• f-e/d-d*b+a

5. 某 MV 时长 4 分钟，每秒 10 帧，每帧 2048×1152 像素 32 位真彩色（未压缩），音频比特率 128kbps。存储空间约为（ ）。

{{ select(5) }}

• 21 GiB
• 27 GiB
• 168 GiB
• 2 GiB

6. 下图是一棵二叉树，它的后序遍历是 （ ）。

{{ select(6) }}

• ABDEFC
• DBEFAC
• DFEBCA
• ABCDEF

7. 五个本质不同的点（无重边或自环）组成无向图的个数是（ ）。

{{ select(7) }}

• 10
• 1024
• 15
• 120

8. 元素 $a, b, c, d, e, f$ 依次入栈，不合法的出栈序列为（ ）。

{{ select(8) }}

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

9. 同时扔出 k 枚相同的六面骰子，点数排序后不同结果有（ ）。

{{ select(9) }}

• $6^k - 2^k$
• $A_{k+1}^{k-1}$
• $C_k^{k-1}$
• $C_{k+5}^5$

10. 箱中有 6 个球（编号 1-6），拿 3 次球（放回/不放回），数字之和的期望分别是（ ）。

{{ select(10) }}

• 10.5, 10.5
• 9, 9
• 9, 10.5
• 10.5, 9

11. 计算下式的值（mod 为取模，$n! = 1 \cdot 2 \cdot 3 \cdots n$)：

{{ select(11) }}

• 10081
• 10085
• 0
• 10083

12. 当 x=10 时，以下代码中 ans 的值：

int ans=0;
void dfs(int x){
    ++ans;
    if(x<=1)return;
    dfs(x/3);
    if(x/3+1<x) dfs(x/3+1);
    if(x/3+2<x) dfs(x/3+2);
}

{{ select(12) }}

• 24
• 25
• 26
• 27

13. 最大子段和问题（分治算法，非动态规划），最优平均复杂度为（ ）。

{{ select(13) }}

• $\Theta(n \log^2 n)$
• $\Theta(n \log n)$
• $\Theta(n)$
• $\Theta(1)$

14. 算法时间递推式：$T(n)=9T(n/3)+n$，$T(1)=1$，时间复杂度是（ ）。

{{ select(14) }}

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

15. 中国计算机学会成立于（ ）年。

{{ select(15) }}

• 1961
• 1962
• 1971
• 1972

---

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

程序 1

#include <cstdio>
#include <cstring>
const int maxn = 1003;
int type, n, m;
char s[maxn], t[maxn];
int main() {
    scanf("%d %s %s", &type, t, s);
    n = strlen(s); m = strlen(t);
    if (type < 2) {
        for (int i = 0; i < m; ++i) s[i] = t[i];
    } else if (type == 2) {
        strcpy(s, t);
    } else {
        for (int i = 0; i < m; i += 4) {
            unsigned int code = 0, pos = i;
            for (int j = 1; pos < i+4; j *=100, ++pos) {
                if (pos == m) break;
                code += t[pos] * j;
            }
            pos = i;
            while (code != 0) {
                s[pos++] = code % 100;
                code /= 100;
            }
        }
    }
    for (int i = 0; i < n; ++i) printf("%c", s[i]);
    printf("\n");
}

判断题：
16. 所有 < 改为 != 后输出不变（ ）
{{ select(16) }}

• √
• ×

17. 输入 1 xyz abcd 时输出 xyzd（ ）
    {{ select(17) }}

• √
• ×

18. 输入 1 xyz abcd 和 2 xyz abcd 输出相同（ ）
    {{ select(18) }}

• √
• ×

19. 第 25~28 行 while 改为 do-while 后输出不变（ ）
    {{ select(19) }}

• √
• ×

选择题：
20. 第 13 行改为 for (int i = 0; i < strlen(t); ++i) s[i] = t[i]（type=1），时间复杂度为（ ）。
{{ select(20) }}

• $\Theta(n + m)$
• $\Theta(n + m^2)$
• $\Theta(n^2 + m)$
• $\Theta(n^2 + m^2)$

21. 输出不同的输入组合是（ ）。
    {{ select(21) }}

• 1 ab abc 和 3 ab abc
• 1 AB ABC 和 3 AB ABC
• 1 de fgh 和 3 de fgh
• 1 DE FGH 和 3 DE FGH

程序 2

#include <iostream>
using namespace std;
const int INF = 1000000000;
#define Front 0
#define Back 1
#define Left 2
#define Right 3
#define Up 4
#define Down 5
int w[6], a[1003][1003];
const int way1[] = {Up, Right, Down, Left};
const int way2[] = {Up, Front, Down, Back};
const int way3[] = {Left, Front, Right, Back};
int get_max(int &a, int b) {
    return a = max(a, b);
}
int right_rotate(int &u) {
    for (int i = 0; i < 4; ++ i)
    if (u == way1[i])
    return u = way1[(i + 1) % 4];
    return u;
}
int front_rotate(int &u) {
    for (int i = 0; i < 4; ++ i)
    if (u == way2[i])
    return u = way2[(i + 1) % 4];
    return u;
}
const int anchorX = Up;
const int anchorY = Front;
const int anchorZ = Right;
int find_down(int u, int v) {
    if (u == Down || u == Up) return anchorX^(u == Up);
    if (v == Down || v == Up) return anchorY^(v == Up);
    for (int i = 0; i < 4; ++ i)
    if (u == way3[i])
    return anchorZ ^ (v == way3[(i + 1) % 4]);
    return -1;
}
int n, m, dp[1003][1003][6][6];
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> a[i][j];
    for (int i = 0; i < 6; ++ i)
        cin >> w[i];
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            for (int a = 0; a < 6; ++ a)
                for (int b = 0; b < 6; ++ b)
                    dp[i][j][a][b] = -INF;
    dp[0][0][anchorX][anchorY] = a[0][0] * w[Down];
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            for (int p = 0; p < 6; ++ p)
                for (int q = 0; q < 6; ++ q)
                    if (dp[i][j][p][q] != -INF) {
                        int x = dp[i][j][p][q];
                        int u1 = p, v1 = q;
                        right_rotate(u1);
                        right_rotate(v1);
                        get_max(dp[i][j + 1][u1][v1], x + w[find_down(u1, v1)] * a[i][j + 1]);
                        int u2 = p, v2 = q;
                        front_rotate(u2);
                        front_rotate(v2);
                        get_max(dp[i + 1][j][u2][v2], x + w[find_down(u2, v2)] * a[i + 1][j]);
                    }
    int ans = -INF;
    for (int p = 0; p < 6; ++ p)
        for (int q = 0; q < 6; ++ q)
            ans = max(ans, dp[n - 1][m - 1][p][q]);
    printf("%d\n", ans);
    return 0;
}

判断题：
22. 存在输入使 find_down 返回 -1（ ）
{{ select(22) }}

• √
• ×

23. 时间复杂度为 $\Theta(n^2m^2)$（ ）
    {{ select(23) }}

• √
• ×

24. 先 front_rotate 再 right_rotate 结果相同（ ）
    {{ select(24) }}

• √
• ×

选择题：
25. 更换 anchorX/Y/Z 后输出不变的选项（ ）。
{{ select(25) }}

• Left、Front、Down
• Left、Up、Front
• Left、Down、Back
• Down、Right、Front

26. 输入以下数据时输出（ ）（2 分）：

5 5
2 8 15 1 10
5 19 19 3 5
6 6 2 8 2
12 16 3 8 17
12 5 3 14 13
1 1 1 1 1 1

{{ select(26) }}

• 95
• 97
• 94
• 103

27. 输入以下数据时输出（ ）（2 分）：

2 5
2 8 15 3 10
5 19 19 3 5
1 2 3 4 5 6

{{ select(27) }}

• 194
• 157
• 193
• 201

程序 3

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 309;
const int MAXM = 109;
const int MAXP = 100000;
typedef long long ll;
int n, m, seed,rt,btm,s[MAXN],len,dfncnt,full_dist,P,t;
int lg[MAXN],dfn[MAXN],fa[MAXN],dep[MAXN], lson[MAXN];
vector <int> e[MAXN];
vector <int> L[MAXN],leaves;
int F[MAXN];
namespace LCA {
    int st[24][MAXN];
    int minNode(int x, int y){return dep[x]<dep[y] ? x:y;}
    void init() {
        for (int i = 1; i <= n; ++i) st[0][dfn[i]]=fa[i];
        for (int i = 1; i <= lg[n]; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                st[i][j] = minNode(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
    int lca(int u, int v) {
        if (u == v) return u;
        if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
        int d = lg[v - u++];
        return minNode(st[d][u], st[d][v - (1 << d) + 1]);
    }
}
namespace Gen {
    mt19937 rnd;
    int pos[MAXN], deg[MAXN];
    vector <pair<int, int>> edges;
    void calc() {
        for (int i = 1; i <= n - 2; ++i)
            ++deg[pos[i]];
        set <int> ret; ret.clear();
        for (int i = 1; i <= n; ++i)
            if (deg[i] == 1) ret.insert(i);
        for (int i = 1; i <= n - 2; ++i) {
            int npos = *ret.begin();
            edges.push_back(make_pair(npos, pos[i]));
            ret.erase(ret.begin());
            --deg[pos[i]];
            if (deg[pos[i]] == 1)
                ret.insert(pos[i]);
        }
        edges.push_back(make_pair(*ret.begin(), n));
    }
    void build() {
        for (auto i : edges) {
            int u = i.first, v = i.second;
            e[u].push_back(v); e[v].push_back(u);
        }
    }
    void generate(int seed) {
        rnd.seed(seed);
        edges.clear();
        for (int i = 1; i <= n; ++i) deg[i] = 1;
        for (int i = 1; i <= n - 2; ++i)
            pos[i] = rnd() % n + 1;
        calc();
        build();
    }
}
int dfs(int u, int _fa, int &bottom) {
    dfn[u] = ++dfncnt;
    if (e[u].size() == 1) leaves.push_back(u);
    lson[u] = -1; fa[u] = _fa; dep[u] = dep[_fa] + 1;
    int maxlen = 0, dson = u, temp;
    for (int v: e[u])
        if (v != _fa) {
            int p = dfs(v,u,temp);
            if (p > maxlen) maxlen = p, lson[u]=v, dson=temp;
        }
    bottom = dson;
    return maxlen + 1;
}
#define dist(u, v) (dep[u]+dep[v]-2*dep[LCA::lca(u, v)])
int v[MAXP+9], prime[MAXP + 9], prime_cnt, vis[MAXP+9];
void prime_init(int n) {
    prime_cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) prime[++prime_cnt] = v[i] = i;
        for(int j=1; j <= prime_cnt && i*prime[j]<=n; ++j) {
            if (v[i] < prime[j]) break;
            v[i * prime[j]] = prime[j];
        }
    }
}
vector<int> answer, gline;
void solve() {
    cin >> n >> m >> seed >> t;
    lg[0] = lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) e[i].clear();
    leaves.clear();
    if (!t) Gen::generate(seed);
    else {
        for (int i = 1, u, v; i < n; ++i) {
            cin >> u >> v;
            e[u].push_back(v); e[v].push_back(u);
        }
    }
    dep[0] = 0; dfs(1, 0, rt);
    dfncnt=0; leaves.clear();
    len = dfs(rt, 0, btm); LCA::init();
    for (int k = rt; ~k; k = lson[k]) gline.push_back(k);
    for (int i = 1, tmp; i <= m; ++i) {
        cin >> s[i];
        L[i].clear();
        for(int j = 1; j <= s[i]; ++j) {
            cin >> tmp; L[i].push_back(tmp);
        }
        F[i] = dist(L[i].front(), L[i].back());
        for (unsigned j = 0; j < L[i].size() - 1; ++j)
            F[i] += dist(L[i][j], L[i][j + 1]);
        int tmp = F[i] >> 1;
        while (tmp > 1) vis[v[tmp]] = 1, tmp /= v[tmp];
    }
    full_dist = dist(leaves.front(), leaves.back());
    for (unsigned i = 0; i < leaves.size() - 1; ++i)
        full_dist += dist(leaves[i], leaves[i + 1]);
    P = -100000;
    for (int i = 2; i <= prime_cnt; ++i)
        if (full_dist+2*len<prime[i] * 2 && !vis[prime[i]]) {
            P = prime[i] * 2; break;
        }
    for (int i = 1; i <= m; ++i) {
        F[i] >>= 1;
        while (F[i]>1) vis[v[F[i]]] = 0, F[i] /= v[F[i]];
    }
    int left=P-full_dist;
    int font = left / (2 * (len - 1)); answer = leaves;
    while (font--) answer.push_back(rt), answer.push_back(btm), left -= 2 * (len - 1);
    if (left>>=1) answer.push_back(rt), answer.push_back(gline[left]);
    for (int qwq: answer) cout << qwq << " ";
    cout << endl;
}
int main() {
    prime_init(MAXP);
    int T; cin >> T;
    while (T--) solve();
}

判断题：
28. LCA::lca() 单次时间复杂度 $\Theta(\log n)$（ ）
{{ select(28) }}

• √
• ×

29. t=0 时 len 期望与 $\sqrt{n}$ 同阶（ ）
    {{ select(29) }}

• √
• ×

30. full_dist 最大值不超过 2n（ ）
    {{ select(30) }}

• √
• ×

选择题：
31. 输入以下数据时输出（ ）（2 分）：

1
5 2 123456 1
1 2
2 3
3 4
4 5
2 1 4
2 3 5

{{ select(31) }}

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

32. 输入以下数据时输出（ ）（2 分）：

1
25 4 623532 0
3 11 3 5
5 24 17 15 19 17
6 14 21 16 8 18 21
8 21 18 17 19 24 21 24 17

{{ select(32) }}

• 19 24 17 5 17 19 24 4 3 20 11
• 19 24 17 15 8 16 21 14 19 8 19 13
• 14 18 21 8 9 21 14 8 15 24 17 19
• 14 18 21 8 9 21 14 8 22 16 14

33. 答案序列长度的理论上界（ ）。
    {{ select(33) }}

• $\Theta(n^{0.5})$
• $\Theta(n\log n)$
• $\Theta(\log n)$
• $\Theta(n)$

---

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

程序 1：凑出 17

#include <cstdio>
using namespace std;
const int maxn = 25;
const int aim = 17;
int n;
int a[maxn];
bool ans;

int getBit(const int s, int p) {
    return ①;
}

int main() {
    scanf("%d", &n);
    for (②) scanf("%d", a + i);
    for (int s=0, upperBound = ③; s <= upperBound; ++s){
        ④;
        for (int j = 0; j < n; ++j) if (getBit(s, j) == 1){
            sum += a[j];
        } else {
            ⑤;
        }
        if (int(sum) == aim) {
            ans = true;
            break;
        }
    }
    printf("%s\n", ans ? "Yes" : "No");
}

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

• (s >> p) & 1
• (s << p) & 1
• s & (1 << p) & 1
• s & (1 >> p) & 1

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

• int i = 0; i <= n; ++i
• int i = 1; i <= n; ++i
• int i = 0; i < n; ++i
• int i = 1; i < n; ++i

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

• 1 << n
• (1 << n) | 1
• (1 << n) + 1
• (1 << n) -1

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

• int sum = 0
• unsigned long long sum = 0
• unsigned short sum = 0
• unsigned int sum = 0

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

• sum = a[j] + sum
• sum = a[j] - sum
• sum = -a[j] + sum
• sum = -a[j] - sum

程序 2：树同构问题

#include <iostream>
#include <vector>
#include <algorithm>
typedef std::vector<int> Nodes;
struct RootedTree {
    int size, root;
    std::vector<Nodes> edges;
};
RootedTree read() {
    RootedTree res;
    std::cin >> res.size >> res.root;
    res.edges.resize(res.size + 1);
    for (int i = 1; i < res.size; ++ i) {
        int u, v;
        std::cin >> u >> v;
        res.edges[u].push_back(v);
        res.edges[v].push_back(u);
    }
    return res;
}
std::vector<Nodes> D; // 某个深度下的所有结点
std::vector<int> fa;
int dfs_depth(const RootedTree &tree, int now, int f, int depth, int nodesDiff) {
    if (①) // 1
        D.push_back(Nodes());
    int nowId = now + nodesDiff;
    D[depth].push_back(nowId);
    if (f != -1)
        fa[nowId] = f + nodesDiff;
    int maxDepth = 0;
    for (int i = 0; i < tree.edges[now].size(); ++ i) {
        int child = tree.edges[now][i];
        if (②) { // 2
            maxDepth = std::max(maxDepth, dfs_depth(tree,child,now,depth+1,nodesDiff));
        }
    }
    return maxDepth + 1;
}
typedef std::vector<int> Hash;
std::vector<Hash> hash;
bool cmp(const int x, const int y) {
    return ③; // 3
}
bool check(const RootedTree &t1, const RootedTree &t2) {
    if (t1.size != t2.size)
        return false;
    int size = t1.size;
    D.clear();
    fa.clear();
    fa.resize(size * 2 + 1);
    int dep1 = dfs_depth(t1, t1.root, -1, 0, 0);
    int dep2 = dfs_depth(t2, t2.root, -1, 0, size);
    if (dep1 != dep2)
        return false;
    hash.clear();
    hash.resize(size * 2 + 1);
    std::vector<int> rank(size * 2 + 1);
    for (④) { // 4
        for (int i = 0; i < D[h + 1].size(); ++ i) {
            int node = D[h + 1][i];
            hash[fa[node]].push_back(rank[node]);
        }
        std::sort(D[h].begin(), D[h].end(), cmp);
        rank[D[h][0]] = 0;
        for (int i = 1, cnt = 0; i < D[h].size(); ++ i) {
            if (⑤) // 5
                ++ cnt;
            rank[D[h][i]] = cnt;
        }
    }
    return hash[t1.root] == hash[t2.root + size];
}
int main() {
    RootedTree treeA, treeB;
    treeA = read();
    treeB = read();
    bool isomorphism = check(treeA, treeB);
    std::cout
        << (isomorphism ? "wow!": "emm...")
        << std::endl;
    return 0;
}

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

• D.size() < depth
• D.size() > depth
• D.size() != depth
• D.size() == depth

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

• child != f + nodesDiff
• child != f
• child + nodesDiff == f + nodesDiff
• child + nodesDiff != f

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

• rank[fa[x]] < rank[fa[y]]
• hash[x].size() < hash[y].size()
• rank[x] < rank[y]
• hash[x] < hash[y]

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

• int h = dep1-1; ~h; --h
• int h = dep1-1; h; --h
• int h = dep1-2; ~h; --h
• int h = dep1-2; h; --h

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

• hash[D[h][i]] != hash[D[h][i-1]]
• rank[D[h][i]] != rank[D[h][i-1]]
• hash[D[h][i]] < hash[D[h][i-1]]
• rank[D[h][i]] < rank[D[h][i-1]]