说明：本卷为模拟练习（卷二），考点在一卷基础上拓展（哈夫曼、树遍历、图算法、字符串、筛法等）。多项选择题每小题 2 分，全部选对得 2 分，选对但不全得 1 分，有错选得 0 分。打印时自动隐藏解析。
一、单项选择题（共 15 题，每题 2 分，共 30 分）
1.二进制数 101101 对应的十进制整数是（ ）。
2.在长度为 n 的有序数组中用二分查找某个元素，最坏情况下的比较次数约为（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
3.队列（Queue）的访问特性是（ ）。
A. 后进先出（LIFO）
B. 先进先出（FIFO）
C. 随机访问
D. 只能访问中间元素
4.一棵满二叉树，若根节点为第 1 层，则第 5 层的节点数是（ ）。
5.下列关于堆排序的说法，正确的是（ ）。
A. 它是一种稳定排序
B. 它是不稳定排序
C. 平均时间复杂度为 O(n²)
D. 需要 O(n) 的额外辅助空间
6.C++ 中表达式 1 + 2 * 3 - 4 / 2 的求值结果是（ ）。（整数除法）
7.对权值集合 {2, 3, 5, 7} 构造哈夫曼（Huffman）树，其带权路径长度 WPL 为（ ）。
8.一棵有 15 个节点的二叉树，其最小可能高度（根高度为 1）是（ ）。
10.求解 n 层汉诺塔问题，最少需要移动圆盘的次数是（ ）。
11.直接插入排序在最好情况（输入序列已按升序排列）下的时间复杂度为（ ）。
A. O(n²)
B. O(n)
C. O(n log n)
D. O(1)
12.根据德·摩根定律，¬(P ∧ Q) 等价于（ ）。
A. ¬P ∧ ¬Q
B. ¬P ∨ ¬Q
C. P ∨ Q
D. P ∧ Q
13.已知某二叉树的前序遍历为 ABDECF，中序遍历为 DBEAFC，则其后序遍历为（ ）。
A. DEBFCA
B. DBEFCA
C. EDBFCA
D. DEBCFA
14.下列算法中，可用于求解"单源最短路径"问题的是（ ）。
A. Dijkstra 算法
B. Kruskal 算法
C. 冒泡排序
D. 快速排序
15.世界上第一台通用电子数字计算机 ENIAC 诞生于（ ）。
A. 1942 年
B. 1946 年
C. 1950 年
D. 1956 年
三、程序阅读题（共 3 题，每空/每问按标注分值，共约 40 分）
1.（13 分）阅读程序，回答问题。
#include <iostream>
#include <string>
using namespace std;
int main() {
string s = "abracadabra";
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
cout << cnt['a' - 'a'] << " " << cnt['b' - 'a'] << endl;
return 0;
}
（1）程序运行时输出的结果是______。（4 分）
（2）该程序实现的功能是______。（4 分）
（3）若将字符串改为全大写字母（如 "ABC"），程序会出现什么问题？______。（5 分）
2.（13 分）阅读程序，回答问题。
#include <iostream>
using namespace std;
int main() {
const int N = 30;
bool p[31] = {false}; // p[i]=true 表示 i 是合数
for (int i = 2; i * i <= N; i++)
if (!p[i])
for (int j = i * i; j <= N; j += i) p[j] = true;
int c = 0;
for (int i = 2; i <= N; i++) if (!p[i]) c++;
cout << c << endl;
return 0;
}
（1）程序输出结果是______。（4 分）
（2）该程序使用的算法名称是______。（4 分）
（3）该算法的时间复杂度约为______。（5 分）
3.（14 分）阅读程序，回答问题。
#include <iostream>
using namespace std;
int g(int n) {
if (n == 1) return 1;
return 2 * g(n - 1) + 1;
}
int main() {
cout << g(5) << endl;
return 0;
}
（1）程序输出结果是______。（4 分）
（2）函数 g(n) 的闭式（通项公式）是______。（5 分）
（3）该函数的时间复杂度和空间复杂度分别约为多少？（5 分）
答案解析
【单选 1】B。 二进制 101101 = 1×32 + 0×16 + 1×8 + 1×4 + 0×2 + 1×1 = 32+8+4+1 = 45。
【单选 2】B。 二分查找每次将区间减半，最坏需约 log₂n 次比较，复杂度 O(log n)。
【单选 3】B。 队列是先进先出（FIFO），只允许在一端（队尾）入、另一端（队头）出。栈才是 LIFO。
【单选 4】B。 满二叉树第 k 层节点数为 2^(k-1)，第 5 层 = 2⁴ = 16。
【单选 5】B。 堆排序是不稳定排序（如 [2a, 2b, 1] 排序后 2b 可能到 2a 前）；时间复杂度稳定 O(n log n)；原地，额外空间 O(1)。
【单选 6】B。 先算乘除：2*3=6，4/2=2（整数除法），再 1+6-2 = 5。
【单选 7】B。 哈夫曼合并：取最小 2,3→5；再取 5,5→10；再取 10,7→17。总代价（WPL）= 5+10+17 = 32。也可按叶子深度算：2、3 深度 3，5 深度 2，7 深度 1 → 2×3+3×3+5×2+7×1=32。
【单选 8】B。 n 个节点的二叉树最小高度为 ⌊log₂n⌋+1。⌊log₂15⌋=3，故最小高度 4（完全二叉树形态）。
【单选 9】B。 八进制 17 = 1×8 + 7 = 15。
【单选 10】B。 n 层汉诺塔最少移动次数满足 H(n)=2H(n-1)+1，解为 H(n)=2ⁿ-1；H(3)=7。
【单选 11】B。 已升序时，每个元素只需与已排好部分比较一次即停止，总比较约 n-1 次，复杂度 O(n)；最坏（逆序）才 O(n²)。
【单选 12】B。 德·摩根定律：¬(P∧Q) ≡ ¬P ∨ ¬Q；¬(P∨Q) ≡ ¬P ∧ ¬Q。
【单选 13】A。 前序首字母 A 为根；中序 A 左为 DBE、右为 FC。左子树前序 BDE、中序 DBE → B 为左根，D 左、E 右；右子树前序 CF、中序 FC → C 为右根，F 左。后序：左 DEB + 右 FC + 根 A = DEBFCA。
【单选 14】A。 Dijkstra 用于单源最短路径（边权非负）；Kruskal 用于最小生成树。
【单选 15】B。 ENIAC 于 1946 年在美国宾夕法尼亚大学研制成功。
【多选 1】ABC。 栈、队列、数组都是线性结构（元素间一对一）；二叉树是树形（非线性）结构。
【多选 2】ABC。 Prim、Kruskal（最小生成树）与 Dijkstra（最短路）均为典型贪心算法；归并排序属分治。
【多选 3】ABCD。 vector、list、map 是标准容器；stack 是"容器适配器"，初赛常将其与容器一并考查，故选全。
【多选 4】ABC。 图的存储：邻接矩阵、邻接表、十字链表（有向图）、邻接多重表等；哈希表是散列结构，不是图的存储。
【多选 5】ABCD。 渐进关系成立：常数 < 对数 < 线性 < 线性对数 < 平方。
【阅读 1】 程序用 cnt[26] 统计各小写字母频率。（1）"abracadabra" 中 a 出现 5 次、b 出现 2 次，输出 5 2。（2）功能是统计字符串中各小写字母的出现次数（词频统计）。（3）若字符串含大写字母，c-'a' 会得到负数或 ≥26 的下标，访问 cnt[负数/越界] 导致数组越界，行为未定义。
【阅读 2】 这是埃拉托斯特尼筛法：用 bool 标记合数，从 i=2 起到 √N，将 i 的倍数标为合数，最后统计未被标记（即素数）的个数。（1）2~30 间素数有 2,3,5,7,11,13,17,19,23,29 共 10 个，输出 10。（2）埃拉托斯特尼筛法（素数筛法）。（3）时间复杂度约 O(N log log N)。
【阅读 3】 g(1)=1，g(2)=2×1+1=3，g(3)=7，g(4)=15，g(5)=31。（1）输出 31。（2）递推 g(n)=2g(n-1)+1 的闭式为 g(n)=2ⁿ-1（正是 n 层汉诺塔移动次数）。（3）时间复杂度 O(n)（递推 n 次）；空间复杂度 O(n)（递归调用栈深度 n）。
【完善 1】直接插入排序。 ① 取待插入元素 key = a[i]；② 已排好区间末尾 j = i-1；③ 若 a[j]>key 则将 a[j] 后移 a[j+1] = a[j]；④ j-- 继续向前比较；⑤ 找到位置后 a[j+1] = key 插入。
【完善 2】图的 DFS。 ① 进入即标记 vis[u] = true；② 对邻接点 v 判断是否未访问 !vis[v]；③ 未访问则递归 dfs(v)。