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

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

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

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

A. 负责外设与主机之间的信息交换 B. 控制和管理计算机系统的各种硬件和软件资源的使用 C. 负责诊断机器的故障 D. 将源程序编译成目标程序

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

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

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

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

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

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

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

A. 霍夫曼编码问题 B. 0-1 背包问题 C. 最小生成树问题 D. 单源最短路径问题

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

A. $O(n+e)$ B. $O(n^2)$ C. $O(e^2)$ D. $O(n)$

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

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

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

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

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

A. $30<n<40$ B. $40<n<50$ C. $50<n<60$ D. $20<n<30$

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

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

A. $\texttt{abc*+d-}$ B. $\texttt{-+*abcd}$ C. $\texttt{abcd*+-}$ D. $\texttt{abc+*d-}$

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

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

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

A. $O((m + n^2) \log n)$ B. $O(mn + n^3)$ C. $O((m + n) \log n)$ D. $O(n^2)$

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

A. 欧拉(Leonhard Euler) B. 冯·诺伊曼(John von Neumann) C. 克劳德·香农(Claude Shannon) D. 图灵(Alan Turing)

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

假设输入的 $n$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：

判断题

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

A. 正确 B. 错误

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

A. 正确 B. 错误

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

A. 正确 B. 错误

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

A. 正确 B. 错误

单选题

若输入 $n$ 为 $100$，且输出为 $127$，则输入的 d[i]d[i] 中不可能有（ ）。

A. 127 B. 126 C. 128 D. 125

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

A. 若输出为偶数，则输入的 d[i]d[i] 中最多有两个偶数 B. 若输出为奇数，则输入的 d[i]d[i] 中至少有两个奇数 C. 若输出为偶数，则输入的 d[i]d[i] 中至少有两个偶数 D. 若输出为奇数，则输入的 d[i]d[i] 中最多有两个奇数

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

判断题

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

A. 正确 B. 错误

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

A. 正确 B. 错误

单选题

（2.5 分）当输入的 $d[i]$ 是严格单调递增序列时，第 17 行的 swap 平均执行次数是( )。【注意：本题为错题，选A即可】

A. $O(n \log n)$ B. $O(n)$ C. $O(\log n)$ D. $O(n^2)$

（2.5 分）当输入的 $d[i]$ 是严格单调递减序列时，第 17 行的 swap 平均执行次数是( )。

A. $O(n^2)$ B. $O(n)$ C. $O(n \log n)$ D. $O(\log n)$

（2.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)$

（2.5 分）若输入的 $d[i]$ 都为同一个数，此程序平均的时间复杂度是( )。

A. $O(n)$ B. $O(\log n)$ C. $O(n \log n)$ D. $O(n^2)$

判断题

输出可能为 $0$。（ ）

A. 正确 B. 错误

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

A. 正确 B. 错误

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

A. 正确 B. 错误

单选题

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

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

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

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

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

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

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

1.（分数背包）小 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}$ 可从大到小排序后进行贪心选择。

试补全程序。

①处应填（ ）

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]

②处应填（ ）

A. w[1] <= B B. v[1] <= B C. w[1] >= B D. v[1] >= B

③处应填（ ）

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];

④处应填（ ）

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]

⑤处应填（ ）

A. curW,curV B. curW, 1 C. curV, curW D. curV, 1

（最优子序列）取 $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$ 个整数 $a_1,a_2,\cdots,a_n$。

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

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

试补全程序。

①处应填（ ）

A. x >>= 1 B. x ^= x &(x ^ (x + 1)) C. x -= x | -x D. x ^= x &(x ^ (x - 1))

②处应填（ ）

A. (a & MS) << B B. a >> B C. a & (1 << B) D. a & (MS << B)

③处应填（ ）

A. -INF B. Max[y][x] C. 0 D. Max[x][y]

④处应填（ ）

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)

⑤处应填（ ）

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))

参考答案（请提交答案后再看）