本版本为初版，主要为AI生成。 人工核验中

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

1. 32 位无符号整数最大值问题

• 答案：A
• 解析：32 位无符号整数的取值范围是 0∼232−1。计算可得 232=4294967296，因此最大值为 4294967295，其近似值为 4×109，最接近选项 A。

2. 二进制按位与运算问题

• 答案：B
• 解析：已知 x=255，其二进制表示为 11111111；x−1=254，二进制表示为 11111110。按位与运算（&）规则为 “全 1 得 1，有 0 得 0”，因此 255&254=11111110=254，选 B。

3. 递归函数计算问题

• 答案：B
• 解析：根据函数定义逐步展开计算：
  • 当 n≤1 时，返回 1；
  • 若 n 为偶数，返回 calc(n/2)+1；若为奇数，返回 calc(n−1)+calc(n−2)。
  • calc(5)（奇数）：calc(4)+calc(3)
    • calc(4)（偶数）：calc(2)+1，calc(2)（偶数）：calc(1)+1=1+1=2，故 calc(4)=2+1=3；
    • calc(3)（奇数）：calc(2)+calc(1)=2+1=3；
  • 因此 calc(5)=3+3=6，选 B。

4. 哈夫曼树带权路径长度问题

• 答案：B
• 解析：哈夫曼树构造规则为 “每次选两个权值最小的节点合并，新节点权值为两节点之和”，带权路径长度（WPL）为 “每个叶子节点权值 × 其到根节点的路径长度之和”。
  • 构造步骤：
    1. 合并 10 和 12，得新节点 22（路径长度 2）；
    2. 合并 15 和 20，得新节点 35（路径长度 2）；
    3. 合并 22 和 25，得新节点 47（路径长度 3）；
    4. 合并 35 和 47，得新节点 82（根节点）。
  • 计算 WPL：10×3+12×3+15×2+20×2+25×2=30+36+30+40+50=186，选 B。

5. 有向图入度与出度关系问题

• 答案：B
• 解析：有向图中每条边对应一个 “起点出度” 和一个 “终点入度”，即每条边贡献 1 个出度和 1 个入度。因此，所有顶点入度之和 = 所有顶点出度之和 = 边数，选 B。

6. 组合数计算问题

• 答案：C
• 解析：总选法为从 9 人中选 4 人，即 C94​=4!5!9!​=126；排除 “全男”（C54​=5）和 “全女”（C44​=1）的情况，符合条件的选法为 126−5−1=120，选 C。

7. 布尔表达式化简问题

• 答案：C
• 解析：对原式 (a \&& b) || (!c \&& a) 提取公因子 a，可得 a \&& (b || !c)，与选项 A 等价。
  • 选项 B：(a || !c) \&& (b || !c) \&& (a || a) = (a || !c) \&& (b || !c) \&& a = a \&& (b || !c)，与原式等价；
  • 选项 C：a \&& (!b || c)，与 a \&& (b || !c) 不等价（如 a=1,b=1,c=0 时，原式为 1，选项 C 为 0）；
  • 选项 D：!(!a || !b) || (a \&& !c) = (a \&& b) || (a \&& !c) = a \&& (b || !c)，与原式等价。选 C。

8. 递推序列周期问题

• 答案：D
• 解析：由题意，f[0]=1，假设 f[1]=1（递归基例），递推公式为 f[n]=(f[n−1]+f[n−2])%7，计算序列找周期：
  • 序列：1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,...（周期为 16）；
  • 计算 2025÷16=126 余 9，故 f[2025]=f[9]=6，选 D。

9. C++ string 类特性问题

• 答案：B
• 解析：
  • A 错误：string 是动态字符串，长度可通过append、+=等方法修改；
  • B 正确：C++ 支持string对象与char类型直接用+连接（如"abc"+'d'）；
  • C 错误：length()和size()均返回字符串有效字符数，结果完全相同；
  • D 错误：string 内部无需手动添加'\0'，且'\0'不计入长度。选 B。

10. 引用与值传递问题

• 答案：C
• 解析：函数solve(int &a, int b)中，a是引用（关联实参x），b是值传递（拷贝实参y）：
  • 步骤 1：a=a+b=5+10=15（x变为 15）；
  • 步骤 2：b=a−b=15−10=5（仅修改局部变量b，y仍为 10）；
  • 步骤 3：a=a−b=15−5=10（x变为 10）；
  • 最终x=10，y=10，选 C。

11. 路径组合数问题

• 答案：B
• 解析：从(1,1)到(4,5)，需向右走4−1=3步，向下走5−1=4步，总步数 7 步。路径数为从 7 步中选 3 步向右（或 4 步向下），即 C73​=3!4!7!​=35，选 B。

12. 冒泡排序交换次数问题

• 答案：B
• 解析：冒泡排序规则为 “每次将未排序部分的最大值沉到末尾”，对数组[6,1,5,2,4]模拟：
  • 第 1 轮：6 与 1、5、2、4 依次交换（4 次），数组变为[1,5,2,4,6]；
  • 第 2 轮：5 与 2、4 依次交换（2 次），数组变为[1,2,4,5,6]；
  • 第 3、4 轮：无交换。
  • 总交换次数：4+2=6，选 B。

13. 进制转换问题

• 答案：A
• 解析：假设题目中八进制数为2708​（结合选项反推）：
  • 十进制72010​转十六进制：720÷16=45余 0，45÷16=2余 13（D），2÷16=0余 2，即2D016​；
  • 八进制2708​转十进制：2×82+7×8+0=128+56=18410​；
  • 求和：720+184=90410​，转十六进制：904÷16=56余 8，56÷16=3余 8，3÷16=0余 3，即38816​，选 A。

14. 完全二叉树叶子节点数问题

• 答案：C
• 解析：完全二叉树特性：叶子节点数 = ⌈总节点数/2⌉（奇数）或 总节点数/2（偶数）。
  • 总节点数 1000（偶数），叶子节点数 = 1000÷2=500，选 C。

15. 栈与队列操作问题

• 答案：A
• 解析：按规则处理队列A=[7,5,8,3,1,4,2]：
  • 7（奇）→ 栈[7]；5（奇）→ 栈[7,5]；
  • 8（偶）→ 弹出 5→队列P=[5]，栈[7]；
  • 3（奇）→ 栈[7,3]；1（奇）→ 栈[7,3,1]；
  • 4（偶）→ 弹出 1→P=[5,1]，栈[7,3]；
  • 2（偶）→ 弹出 3→P=[5,1,3]。
  • 最终P=[5,1,3]，选 A。

二、阅读程序（共 40 分）

程序（1）：三元组互质计数

判断题

1. 答案：√解析：输入n=2时，i最大为 2，j=i+1=3>2，循环不执行，第 16 行判断语句不会运行。

2. 答案：×解析：删去 “\&& \text{gcd}(i,k)==1” 后，仅判断i与j、j与k互质，未判断i与k，导致三元组不满足 “两两互质”，结果改变。

3. 答案：√解析：n≥3时，存在三元组(1,2,3)（1 与任意数互质，2 与 3 互质），必然满足两两互质，故输出为正整数。

单选题

1. 答案：C解析：原gcd函数逻辑错误（应为 “b==0返回a，否则返回gcd(b,a%b)”）。修改为gcd(a,a%b)后，当a%b=a（如a=3,b=6），会陷入gcd(3,3)→gcd(3,0)的循环（虽最终返回，但极端情况可能死循环）。

2. 答案：C解析：枚举1≤i<j<k≤8的所有三元组，统计两两互质的数量，结果为 35。

3. 答案：A解析：gcd(36,42)计算：42÷36=1余 6，36÷6=6余 0，故返回 6。

程序（2）：数组分组（每组元素差≤k）

判断题

1. 答案：×解析：输入 “3 1 3 2 1” 即n=3,k=1,a=[3,2,1]，排序去重后a=[1,2,3]。分组为[1,2,3]（差≤1），输出 3，非 2。

2. 答案：√解析：输出为 “最少分组数”，最多每组 1 个元素（分组数 = n），最少 1 组（全满足差≤k），故1≤答案≤n。

3. 答案：√解析：去重前数组有重复元素（如a=[1,1,2],k=1），去重后分组数为 2，不去重分组数为 1，结果不同。

单选题

1. 答案：B解析：第 18 行执行时，j是 “最大的索引且a[i]−a[j+1]≤k”，故a[i]−a[j]>k（满足），而题目问 “不包括”，其他选项（A、C、D）均必然满足。

2. 答案：A解析：a=[1−100],k=2，分组为[1−3],[4−6],...,[97−99],[100]，共 34 组。

3. 答案：A解析：删去排序后数组无序，如a=[3,1,2],k=1，排序后分组数为 2，不排序分组数为 3（更大）。

程序（3）：最长公共子序列（LCS）

判断题

1. 答案：√解析：输入n=4,a=[1,2,3,4],b=[1,3,2,2]，LCS 为[1,2]或[1,3]，长度为 2。

2. 答案：√解析：f[i][j]表示前i个a和前j个b的 LCS 长度，f[n][n]是全局最大值，故f[i][j]≤f[n][n]。

3. 答案：×解析：第 18 行处理 “a[i]=b[j]” 的情况（取max(f[i−1][j],f[i][j−1])），删去后f[i][j]可能为 0，导致结果错误。

单选题

1. 答案：D解析：LCS 长度≤数组长度（A 对），≥0（可能为空，B 对），不一定≥1（如a与b无公共元素，C 对），故选 D。

2. 答案：A解析：排序后 LCS 变为 “最长公共元素个数”，如a=[3,2,1],b=[1,2,3]，原 LCS=3，排序后仍为 3；a=[1,3,2],b=[3,2,1]，原 LCS=1，排序后 = 3（变大），故答案变大或不变。

3. 答案：B解析：若a=[1,2,...,n]（升序），则 LCS 问题等价于求b的 “最长上升子序列”（需与a的升序匹配）。

三、完善程序（共 30 分）

（1）字符串解码

33. ①处

• 答案：C解析：判断下一个字符是否为数字，需先确保索引不越界，即i+1<z.length()。

34. ②处

• 答案：B解析：累积数字（如 “12”=1×10+2），公式为count=count×10+(z[i]−′0′)。

35. ③处

• 答案：B解析：循环次数为字符连续出现的次数（即count），需添加count个字符。

36. ④处

• 答案：B解析：无后续数字时，直接添加当前字符ch（即z[i]）。

37. ⑤处

• 答案：C解析：无后续数字时，索引i需向后移动 1 位（i++）。

（2）精明人与糊涂人识别

38. ①处

• 答案：B解析：初始候选者为 0，计数count=1（表示当前候选者有效）。

39. ②处

• 答案：C解析：当count=0（无有效候选者），更换候选者为i，重置count=1。

40. ③处

• 答案：D解析：若候选者与i互相判断至少一个为 “糊涂人”（query(candidate,i)==false 或 query(i,candidate)==false），则两者至少一个是糊涂人，需抵消。

41. ④处

• 答案：A解析：满足抵消条件时，候选者计数减 1（count−−）。

42. ⑤处

• 答案：C解析：最终留下的候选者为精明人，输出candidate。