1. 请选出以下最大的数（ ）。

    A.$(550)_{10}$ B.$(777)_{8}$ C.$2^{10}$ D.$(22F)_{16}$

    B 的十进制数是 $511$，C 的十进制数是 $1024$，D 的十进制数是 $559$。

    最大数为 $1024$，选 $C$。

  2. 操作系统的功能是（ ）

    A.负责外设与主机之间的信息交换

    B.控制和管理计算机系统的各种硬件和软件资源的使用

    C.负责诊断机器的故障

    D.将源程序编译成目标程序

    显然答案为 $B$。

  3. 现有一段 $8$ 分钟的视频文件，它的播放速度是每秒 $24$ 帧图像，每帧图像是 一幅分辨率为 $2048\times 1024$ 像素的 $32$ 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。

    A.$30G$ B.$90G$ C.$150G$ D.$450G$

    $8\times 60\times 24\times 2048\times 1024\times 32\div 8\div 1024\div 1024\div 1024=90$

    答案为 $B$。

  4. 今有一空栈 $S$，对下列待进栈的数据元素序列 $a,b,c,d,e,f$ 依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。

    A.$b$ B.$a$ C.$d$ D.$c$

    模拟一下就会发现答案为 $B$。

  5. 将 $(2, 7, 10, 18)$ 分别存储到某个地址区间为 $0\sim 10$ 的哈希表中，如果哈希函数 $h(x)=(\,\,\,)$，将不会产生冲突，其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

    A.$x^2 \bmod{11}$

    B.$2\times x \bmod{11}$

    C.$x \bmod{11}$

    D.$\lfloor \dfrac{x}{2} \rfloor \bmod{11}$，其中 $\lfloor \dfrac{x}{2} \rfloor$ 表示 $\dfrac{x}{2}$ 下取整

    同样模拟一下就会发现答案为 $D$。

  6. 下列哪些问题不能用贪心法精确求解？（ ）

    A.霍夫曼编码问题

    B.$0-1$ 背包问题

    C.最小生成树问题

    D.单源最短路径问题

    $0-1$ 背包是 $\texttt{DP}$，显然不能用贪心求解，选 $B$。

  7. 具有 $n$ 个顶点，$e$ 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。

    A.$O(n+e)$

    B.$O(n^2)$

    C.$O(e^2)$

    D.$O(n)$

    $\texttt{DFS}$ 一遍是将所有点和边都遍历一次，所以时间复杂度为 $O(n+e)$，选 $A$。

  8. 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，$24$ 个顶点的二分图至多有（ ）条边。

    A.$144$ B.$100$ C.$48$ D.$122$

    $24$ 个顶点的二分图，每一边都有 $12$ 个点时 $12\times 12=144$ 最大，选 $A$。

  9. 广度优先搜索时，一定需要用到的数据结构是( )

    A.栈 B.二叉树 C.队列 D.哈希表

    $\texttt{BFS}$ 要用到队列，选 $C$。

  10. —个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 $n$ 在以下哪个区间？已知 $n<60$。( ）

    A.$30<n<40$

    B.$40<n<50$

    C.$50<n<60$

    D.$20<n<30$

    用中国剩余定理可知 $n=53$，选 $C$。

  11. 小明想通过走楼梯来锻炼身体，假设从第 $1$ 层走到第 $2$ 层消耗 $10$ 卡热量，接着从第 $2$ 层走到第 $3$ 层消耗 $20$ 卡热量，再从第 $3$ 层走到第 $4$ 层消耗 $30$ 卡热量，依此类推，从第 $k$ 层走到第 $k+1$ 层消耗 $10k$ 卡热量 $(k>1)$？如果小明想从 $1$ 层开始，通过连续向上爬楼梯消耗 $1000$ 卡热量，至少要爬到第几层楼？ （ ）。

    A.$14$ B.$16$ C.$15$ D.$13$

    小学奥数题，答案为 $C$。

  12. 表达式 a*(b+c)-d 的后缀表达形式为（ ）。

    A.$\texttt{abc*+d-}$

    B.$\texttt{-+*abcd}$

    C.$\texttt{abcd*+-}$

    D.$\texttt{abc+*d-}$

    如下图：

    后缀形式为 abc+*d-，选 $D$。

  13. 从一个 $4 \times 4$ 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。

    A.$60$ B.$72$ C.$86$ D.$64$

    第一个方格有 $4\times 4$ 种选法，第二个方格有 $3\times 3$ 种选法，因为会重复计算，所以答案为 $4\times 4\times 3\times 3\div 2=72$ 种，选 $B$。

  14. 对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 $\texttt{Dijkstra}$ 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

    A.$O((m + n^{2}) \log n)$

    B.$O(mn + n^{3})$

    C.$O((m + n) \log n)$

    D.$O(n^{2})$

    注意是没有优化的 $\texttt{Dijkstra}$，所以时间复杂度为 $O(n^{2})$，选 $D$。

  15. 1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

    A.欧拉(Leonhard Euler)

    B.冯·诺伊曼(John von Neumann)

    C.克劳德·香农(Claude Shannon)

    D.图灵(Alan Turing)

    答案为 $C$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> d[i];
  int ans = -1;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (d[i] < d[j])
         ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

程序大意：求最大的 $d_{i} |d_{j}$。

  1. $n$ 必须小于 $1000$，否则程序可能会发生运行错误。（ ）

    $n$ 可以等于 $1000$，错误。

  2. 输出一定大于等于 $0$。（ ）

    当 $n=0$ 时输出 $-1$，错误。

  3. 若将第 $13$ 行的 j=0 改为 j = i + 1 程序输出可能会改变。 （ ）

    显然 $j$ 从 $0$ 到 $i$ 的这段循环在前面已经做过了，所以不会改变，正确。

  4. 将第 $14$ 行的 d[i] < d[j] 改为 d[i] != d[j]，程序输出不会改变。（ ）

    显然值与 $d_{i}$ 和 $d_{j}$ 的大小无关，正确。

  5. 若输入 $n$ 为 $100$，且输出为 $127$，则输入的 $d_{i}$ 中不可能有（ ）。
    A.$127$ B.$126$ C.$128$ D.$125$

    如果 $d_{i}$ 中有 $128$，那么输出一定大于等于 $128$，选 $C$。

  6. 若输出的数大于 $0$，则下面说法正确的是( ）。

    A.若输出为偶数，则输入的 $d_{i}$ 中最多有两个偶数

    B.若输出为奇数，则输入的 $d_{i}$ 中至少有两个奇数

    C.若输出为偶数，则输入的 $d_{i}$ 中至少有两个偶数

    D.若输出为奇数，则输入的 $d_{i}$ 中最多有两个奇数

    如果输出为偶数，且 $d_{i}$ 中只有一个偶数，那么 偶数 | 奇数=奇数，奇数 | 奇数=奇数，输出不可能为偶数，矛盾，所以至少有两个偶数，选 $C$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假设输入的 $n,k$ 和 $d_{i}$ 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

  1. 第 $9$ 行的 $x$ 的数值范围是 $L+1$ 到 $R$，即 $[L+1,R]$。（ ）

    显然数值范围是 $[L,R]$，错误。

  2. 将第 $19$ 行的 d[a] 改为 d[b]，程序不会发生运行错误。（ ）

    运行到 $19$ 行时 $d_{a}=d_{b}$，不会运行错误，正确。

  3. 当输入的 $d_{i}$ 是严格单调递增序列时，第 $17$ 行的 swap 平均执行次数是( )。

    A.$O(n \log n)$

    B.$O(n)$

    C.$O(\log n)$

    D.$O(n^2)$

    错题，复杂度应该为 $\log^{2}n$。

  4. 当输入的 $d_{i}$ 是严格单调递减序列时，第 $17$ 行的 swap 平均执行次数是( )。

    A.$O(n^2)$

    B.$O(n)$

    C.$O(n \log n)$

    D.$O(\log n)$

    类似快排，但不会递归到两侧，所以是 $O(n)$，选 $B$。

  5. 若输入的 $d_{i}$ 为 $i$，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。

    A.$O(n)$，$O(n^2)$

    B.$O(n)$，$O(n \log n)$

    C.$O(n \log n)$，$O(n^2)$

    D.$O(n \log n)$，$O(n \log n)$

    平均时间复杂度是 $O(n)$，最坏就是 $T(n)=n+(n-1)+\cdots+1$，为 $O(n^{2})$，选 $A$。

  6. 若输入的 $d_{i}$ 都为同一个数，此程序平均的时间复杂度是( )。

    A.$O(n)$

    B.$O(\log n)$

    C.$O(n \log n)$

    D.$O(n^2)$

    总有 $a=b=L+1$，此时复杂度为 $O(kn)$，近似 $O(n^{2})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <queue>
using namespace std;

const int maxl = 20000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
  public:
    int find(string x) {
        for (int i = 0; i < cnt; ++i)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];

class Queue {
    string q[maxl];
    int head, tail;
  public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x;  }
} q[2];

string st0, st1;
int m;

string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st , int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}

int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
            !(q[0].empty() && q[1].empty());
            p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
                (check(LtoR(st, m, len - 1), p, step) ||
                 check(RtoL(st, 0, m), p, step)))
                ||
                (p == 1 &&
                 (check(LtoR(st, 0, m), p, step) ||
                  check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

程序大意：求最少操作次数使得 $st0=st1$，每次操作可以将 $[0,m-1]$ 右移或将 $[m,n]$ 左移，左移与右移的操作为 LtoR 与 RtoL。

  1. 输出可能为 $0$。（ ）

    当 $st0=st1$ 时输出 $0$，正确。

  2. 若输入的两个字符串长度均为 $101$ 时，则 $m=0$ 时的输出与 $m=100$ 时的输出是一样的。（ ）

    两种 $m$ 对应的移动的方向都不同，结果肯定不同，错误。

  3. 若两个字符串的长度均为 $n$，则最坏情况下，此程序的时间复杂度为 $O(n!)$。（ ）

    所有字符串的全排列的时间复杂度为 $O(n!)$，每次查询最坏的时间复杂度也是 $O(n!)$，字符串判断是否相等的时间复杂度为 $O(n)$，所以总时间复杂度为 $O((n!)^{2}n)$，错误。

  4. 若输入的第一个字符串长度由 $100$ 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 $m$ 为 $0$，则输出为（ ）。

    A.$49$ B.$50$ C.$100$ D.$-1$

    倒序不可能变成正序，选 $D$。

  5. 己知当输入为 0123\n3210\n1 时输出为 $4$，当输入为 012345\n543210\n1 时输出为 $14$，当输入为 01234567\n76543210\n1 时输出为 $28$，则当输入为0123456789ab\nba9876543210\nl 输出为（）。其中 \n 为换行符。

    A.$56$ B.$84$ C.$102$ D.$68$

    可以发现长度为 $4$ 的时候输出 $4$,长度为 $6$ 的时候输出 $14$，长度为 $8$ 的时候输出 $28$，中间的差值为 $10$ 与 $14$，为公差为 $4$ 的等差数列那么长度为 $10$ 的时候输出 $46$，长度为 $12$ 的时候输出 $68$，选 $D$。

  6. 若两个字符串的长度均为 $n$，且 $0<m<n-1$，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（ ）。提示：考虑输入与输出有多少对字符前后顺序不一样。

    A. 若 $n,m$ 均为奇数，则输出可能小于 $0$。

    B. 若 $n,m$ 均为偶数，则输出可能小于 $0$。

    C. 若 $n$ 为奇数、$m$ 为偶数，则输出可能小于 $0$。

    D. 若 $n$ 为偶数、$m$ 为奇数，则输出可能小于 $0$。

    考虑逆序对个数，不难发现，当位移长度为奇数时，逆序对数量的奇偶性不会改变，如 123 到 231，逆序对数量的奇偶性不改变，如果是偶数如 1234 到 2341，逆序对数量的奇偶性改变，选 $C$。

（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$。第 $i$ 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $a(0<a<l)$，并将一块价值是 $w$，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $a\times w$，体积是 $a\times v$，另一块的价值是 $(1-a)\times w$，体积是 $(1-a)\times v$。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 $n=3,B=8$，三块蛋糕的价值分别是 $4,4,2$，体积分别是 $5,3,2$。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$，价值是 $2.4$，另一份体积是 $2$，价值是 $1.6$，然后把体积是 $3$ 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 $8.4$，故程序输出 $\dfrac{42}{5}$ 。

输入的数据范围为：$1\leq n\leq 1000$，$1\leq B\leq 10^5$，$1\leq w_i,v_i\leq 100$。

提示：将所有的蛋糕按照性价比 $\dfrac{w_i}{v_i}$ 可从大到小排序后进行贪心选择。

试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
} 

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n" w, v);
}
void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d" &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if (①) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if  (②) {
        ③
    } else {
        print(B * w[1] , v[1]);
        return 0;
    }
    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print (④);
            return 0;
        }
    print(⑤);
    return 0;
}

  1. ①处应填（ ）

    A.w[j] / v[j] < w[j+1] / v[j+1]

    B.w[j] / v[j] > w[j +1] / v[j+1]

    C.v[j] * w[j+1] < v[j+1] * w[j]

    D.w[j] * v[j+1] < w[j+1] * v[j]

    考虑最终是要对于每个 $j$ 都有 $\dfrac{w_{j}}{v_{j}}\ge \dfrac{w_{j+1}}{v_{j+1}}$，所以当 $\dfrac{w_{j}}{v_{j}}<\dfrac{w_{j+1}}{v_{j+1}}$ 时，也就是 $w_{j}\times v_{j+1}<w_{j+1}\times v_{j}$ 时要交换，选 $D$。

  2. ②处应填（ ）

    A.w[1] <= B

    B.v[1] <= B

    C.w[1] >= B

    D.v[1] >= B

    考虑 else 是在处理第一块蛋糕都装不下的情况，那么 if 就是在判断第一块蛋糕能不能放得下，即 $v_{1}$ 是否小于等于 $B$，选 $B$。

  3. ③处应填（ ）

    A. print(v[1],w[1]); return 0;

    B. curV = 0; curW = 0;

    C. print(w[1], v[1]); return 0;

    D. curV = v[1]; curW = w[1];

    如果可以放下第一块蛋糕，则赋初值，选 $D$。

  4. ④处应填（ ）

    A.curW * v[i] + curV * w[i], v[i]

    B.(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]

    C.curW + v[i], w[i]

    D.curW * v[i] + (B - curV) * w[i], v[i]

    装不下第 $i$ 块蛋糕时，则加上剩余背包容量可以装的第 $i$ 块蛋糕的价值，选 $D$。

  5. ⑤处应填（ ）

    A.curW,curV

    B.curW, 1

    C.curV, curW

    D.curV, 1

    都可以装的情况下输出价值总和，选 $B$。

（最优子序列）取 $m = 16$，给出长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n(0 \le a_i < 2^m)$。对于一个二进制数 $x$，定义其分值 $w(x)$ 为 $x + \operatorname {popcnt}(x)$，其中 $\operatorname{popcnt}(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列 $b_1,b_2,\dots,b_k$，定义其子序列分值 $S$ 为 $w(b_1 \oplus b_2) + w(b_2 \oplus b_3) + w(b_3 \oplus b_4) + \cdots + w(b_{k-1} \oplus b_k)$。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n(1 \le n \le 40000)n$ 接下来一行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

提示：考虑优化朴素的动态规划算法，将前 $\dfrac{m}{2}$ 位和后 $\dfrac{m}{2}$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 $8$ 位是 $x$、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。

试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x) 
{
    int s = x;
    while(x) 
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y) 
{
    if(x < y)
        x = y;
}

int main() 
{
    int n;
    LL ans = 0;
    cin >> n;
    for(int x = 0; x <= MS; x++)
        for(int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for(int i = 1; i <= n ; i++) 
    {
        LL a;
        cin >> a;
        int x = ② , y = a & MS;
        LL v = ③;
        for(int z = 0; z < = MS; z++)
            to_max(v, ④);
        for(int z = 0; z < = MS; z++)
            ⑤;
        to_max(ans , v);
    }
    cout << ans << endl;
    return 0;
}

  1. ①处应填（ ）

    A.x >>= 1

    B.x ^= x &(x ^ (x + 1))

    C.x -= x | -x

    D.x ^= x &(x ^ (x - 1))

    就是 lowbit，代入一个值算一下即可，选 $D$。

  2. ②处应填（ ）

    A.(a & MS) << B

    B.a >> B

    C.a & (1 << B)

    D.a & (MS << B)

    $x$ 取前 $8$ 位数，选 $B$。

  3. ③处应填（ ）

    A.-INF

    B.Max[y][x]

    C.0

    D.Max[x][y]

    赋初值，选 $C$。

  4. ④处应填（ ）

    A.Max[x][z] + w(y ^ z)

    B.Max[x][z] + w(a ^ z)

    C.Max[x][z] + w(x ^ (z << B))

    D.Max[x][z] + w(x ^ z)

    此处的贡献是两个最后 $8$ 位数的异或和，即 $y\oplus z$，选 $A$。

  5. ⑤处应填（ ）

    A.to_max(Max[y][z], v + w(a ^ (z << B)))

    B.to_max(Max[z][y], v + w((x ^ z) << B))

    C.to_max(Max[z][y], v + w(a ^ (z << B)))

    D.to_max(Max[x][z], v + w(y ^ z))

    加上前八位的贡献，选 $B$。