一、单项选择题

1. B。$8$ 位占用 $1$ 字节，所以 $64$ 位占用 $8$ 字节。
2. C。折半查找的最大比较次数为 $⌈log21000⌉=10$次。其中 $⌈x⌉$ 表示 $x$ 向上取整的结果。
3. C。$128$ 位等价于 $128 / 8 = 16B$ ，两张照片占用的空间为 $2×2048×2048×16B=128MB$。
4. B。$(1011.11)2=1×23+0×22+1×21+1×20+1×2-1+1×2-2=8+0+2+1+0.5+0.25=11.75$。
5. B。无向图中的顶点度数之和$=边数 \times 2=20+0 \times 24=40$，所以顶点个数 $= 40 / 4 = 10$。

6. A。 徐老师（洗菜） 第 $0-15$ 分钟 第 $15-30$ 分钟 第 $30-45$ 分钟 爸爸（切菜） 第 $15-25$ 分钟 第 $30-35$ 分钟 第 $45-55$ 分钟 妈妈（烧菜） 第 $25-45$ 分钟 第 $45-65$ 分钟 第 $65-85$ 分钟 每位家庭成员完成工作的最快时间如上标所示，所以做完三道菜的最短时间为 $85$ 分钟。

7. C。根据表达式 (a + b) * (c + d) 构造表达式树，据此可得后缀表达式为 a b + c d + * 。

8. C。对于字符串 hetao： • 以 h开头的子串有 $5$ 个，分别是 h、he、het、heta、hetao（字符串本身也算其子串）； • 以 e 开头的子串有 $4$ 个，分别是 e、et、eta、etao； • 以 t 开头的子串有 $3$ 个，分别是 t、ta、tao； • 以 a 开头的子串有 $2$ 个，分别是 a、ao； • 以 o 开头的子串有 $1$ 个，是 o。 初次以外，题目中没有强调非空子串，所以空串也应该算其子串。所以字符串 hetao 的子串个数为 $5+4+3+2+1+1=16$。

9. C。按照 入栈、入栈、入栈、出栈、出栈、入栈、入栈、入栈、出栈、入栈、出栈、出栈、出栈、出栈 的顺序，入栈序列 a,b,c,d,e,f,g 对应的出栈序列为 c,b,f,g,e,d,a。

10. D。(x∨y)∧(y∨z)=(true)∧(true)=true。
11. B。$8$ 层的满二叉树的节点个数为 $2^0+2^1+...+2^7=2^8-1=255$。
12. C。符号位为 $1$，可推出是负数，所以可以按照 补码=反码+1 的规律推出补码 $10101010$ 对应的反码为 $10101001$，再将反码的数值位取反得到原码为 $11010110$。
13. C。画图即可
14. B。$84$ 的哈希值为 $84 mod 11 = 7$，存放在地址空间 $7$ 中，$25$ 的哈希值为 $25 mod 11 = 3$，存放在地址空间 $3$ 中，$38$ 的哈希值为 $5$,$57$的哈希值为 $2$，$71$ 的哈希值为 $71 mod 11 = 5$，此时发现 $5$ 已经存放了数据了，那么查看 $6$ 能否存放，发现是空的，则存放在 $6$
15. B。 $3$ 名医生分配到 $3$ 所学校课视为 $3$ 个人的排列 $A_3^3$，从 $6$ 名护士中选出 $2$ 名护士去第 $1$ 所学校的方案数为 $C_6^2$，从剩余 $4$ 名护士中选出 $2$ 名护士去第 $2$ 所学校的方案数为 $C_4^2$，剩余 $2$ 名护士去第 $3$ 所学校的方案数为 $C_2^2$，所以总的方案数为 $A_3^3×C_6^2×C_4^2×C_2^2=540$。

二、阅读程序

第一小题

1. 错误。输入的字符串可包含出字母和数字字符以外的字符，只不过程序并不会处理。
2. 错误。程序运行时不会发生错误，因为 s[n]=='\0'，不满足任何一个 if 条件。
3. 正确。因为输入的字符串可能包含 $ASCII$ 码大于 'z' 的 $ASCII$ 码的字符，此时对于 $cnt$ 数组来说，可能发生数组越界。
4. 正确。因为数字字符对应的是 $cnt[0]$ 到 $cnt[9]$，所以当输入的字符串全由数字字符组成时，结果必然在 $0 \sim 9$ 范围内。
5. C。字符串 ABCDcbaAcDbC 中字符 'C/c' 出现的次数最多（ $4$次），对应的下标为 $2$ 。
6. C。字符串 a2B3233CCDC 中字符 'C/2' 出现的次数最多（ 'C'出现了 $3$ 次，'2' 出现了 $2$ 次，共 $5$ 次），对应的下标为 $2$。

第二小题

1. 错误。由于存在大量的重叠问题，所以计算 $f(n,m)$ 的时间复杂度远超 $O(nm)$。
2. 错误。即使去掉第 $4$ 行的代码，程序在 $m=1$ 时会返回 $n$，在 $n < 1$ 时会返回 $0$，所以不会无限递归下去。
3. 错误。即使同时去掉第 $4$ 行和第 $5$ 行的代码，程序在 $n < 1$ 和 $m < 1$ 时也会返回 $0$，所以不会无限递归下去。
4. D。$f(5,6)=175$。
5. B。$f(100,2)=f(1,1)+f(2,1)+f(3,1)+...+f(99,1)=1+2+3+...+99=4950$。
6. B。需要注意的是，当去掉第 $4$ 行的代码后，边界条件是：当 $m=0$ 时返回 $n$，否则当 $n=1$ 时，$f(n,m)$ 返回 $0$，据此计算得到 $f(3,6)=7$。

第三小题

本题基于倍增思想构造 $ST$ 表求解 $RMQ$ 问题，输出 $s[x]$ 到 $s[y]$ 中 $ASCII$ 码最大的那个字符。

1. 错误。解析：当输入为 CGFCDBAE 2 6 时，输出为 F。需要注意的是——数组下标从 $0$ 开始计算。
2. 正确。解析：因为 $f$ 数组的第二维只开了 $8$ 的大小，所以虽然第一维的大小是 $1000$，但是只要 $n$ 大于 $2^7=128$ 时，计算 $f$ 数组元素时就会发生数组越界。
3. 错误。解析：因为 $ST$ 表需要先计算所有的 $f[i][0]$，再由f[i][0]推导出所有的 $f[i][1]$，再由 $f[i][1]$ 推导出所有的 $f[i][2]$，所以代码第 $19$ 行和 $20$ 行的代码的顺序不能改变。
4. B。解析：函数 $Log2(x)$ 返回的是 $⌊log2x⌋$的结果（其中 $⌊x⌋$ 表示 $x$ 向下取整），所以 $Log2(x)$ 的返回值是 $3$。
5. D。解析： HETAOACCEP 中 $ASCII$ 码最大的字符是 T。
6. B。解析： InHETAO 中 $ASCII$ 码最大的字符是 n，需要注意的是小写英文字母的 $ASCII$ 码都大于大写英文字母。

三、完善程序

第一小题

1. A。需要将循环变量 $i$ 进行初始化。
2. C。数组下标从 $0$ 到 $n-1$，所以循环的条件是 $i < n$。
3. C。程序的目的是不断地比较 $a[i-1]$ 和 $a[i]$，若 $a[i-1] > a[i]$ 则交换 $a[i-1]$ 和 $a[i]$，所以当 $a[i-1]<=a[i]$，则不用交换，直接 $i++$ 即可。
4. B。第 $14 \sim 16$ 行使用三步交换法交换 $a[i]$ 和 $a[i-1]$ 的数值。
5. C。在 (5) 处填写 $i=0$ 或 $i=1$ 程序仍然能够正常运行，但是通过分析可以发现，若设 $i'$ 为目前 $i$ 变化成的最大的值，则 $a[1] \sim a[i'-1]$ 已满足升序，所以及时将 $i$ 重置为 $0$ 或 $1$，它仍会不停自增到 $i'$ 并根据条件进行交换与自减操作，所以执行 $i=0$ 或 $i=1$ 的计算量总是大于等于执行 $i--$ 的计算量，所以执行 $i--$ 是最快的方案。执行 $i++$ 是错误的。

第二小题

通过分析问题代码，可得本题的思路是先找到满足 $a[i-1] > a[i]$ 的最小的下标 $i$，然后从 $a[i]$ 到 $a[n-1]$ 中找到最大的满足 $a[j] < a[i-1]$ 的 $a[j]$，并将 $a[i-1]$ 与 $a[j]$ 交换，然后对 $a[i] \sim a[n-1]$ 从大到小排序，即实现求解 $a$ 的上一个排列。

1. B。通过上面的分析可得 $cmp$ 函数想要实现的效果是 从大到小排，所以函数将返回 $a > b$。
2. A。若循环结束时 $i$ 的值为 $0$，说明序列是升序的，一个升序的排列本身就是最小的排列，没有上一个排列。
3. C。因为 $a[i]$ 到 $a[n-1]$ 是升序的，且 $a[i] < a[i-1]$，所以从 $i$ 到 $n-1$ 找到最后一个满足 $a[j] < a[i-1]$ 的 $a[j]$ 即为要交换的那个数，且 $a[j+1] > a[i-1]$。
4. B。需要将 $a[i]$ 到 $a[n-1]$ 中最大的那个 $< a[i-1]$ 的数（即 $a[j]$）找出来与 $a[i-1]$ 交换，所以是将 $a[i-1]$ 与 $a[j]$ 进行交换。
5. C。需要将 $a[i]$ 到 $a[n-1]$ 从大到小排序。