[?]【CSP-J 2021 T5】入栈顺序 a,b,c,d,e，下列（ ）不是合法出栈序列。 A. a,b,c,d,e B. e,d,c,b,a C. b,a,c,d,e D. c,d,a,e,b
答案：D 出 c、d 后栈顶为 b，无法先出 a。
[★]口诀：“栈后进先出，队列先进先出；括号匹配/DFS/后缀用栈，BFS 用队列。”
链表
知识页 06
链表 J/S共有
链表特点：插入与删除非常方便，O(1)；寻找与读取较慢，O(n)。 数组特点：寻找/读取 O(1)；插入/删除中间元素 O(n)。 三种链表：
• 单向链表：next 连接当前与下一结点；
• 双向链表：prev 与 next 分别指向前/后结点；
• 循环链表：最后一个结点的 next 指向第一个结点。
// 链表struct Node { int data; Node* next; };
// 头插：在链表头部插入 data=42 的新结点
Node* newNode = new Node;
newNode->data = 42;
newNode->next = head;
head = newNode;
[?]【CSP-J 2020 T7】链表不具有的特点是（ ）。 A. 可随机访问任一元素 B. 不必事先估计存储空间 C. 插入删除不需要移动元素 D. 所需空间与线性表长度成正比
答案：A 链表不可随机访问，只能顺序遍历。
[?]【CSP-J 2023 T4】在链表头插入 data=42 的新结点，正确操作是（ ）。 A. newNode->data=42; newNode->next=head; head=newNode; B. head->data=42; newNode->next=head; head=newNode; C. newNode->data=42; head->next=newNode; D. newNode->data=42; newNode->next=head;
答案：A 要先设 newNode->next=head，再让 head 指向 newNode；否则会丢链。
[?]【GESP 202309 六级 T9】字符 A~G 概率 0.40,0.30,0.15,0.05,0.04,0.03,0.03，若 B 的编码为 11，则 D 的编码为（ ）。 A. 10010 B. 10011 C. 10111 D. 10001
答案：B 按哈夫曼构造，D 的编码为 10011。
[?]【CSP-J 2023 T10】字符 a~f 频率 5%,9%,12%,13%,16%,45%，下列哪组是对应的哈夫曼编码？（ ） A. 1111,1110,101,100,110,0 B. 1010,1001,1000,011,010,00 C. 000,001,010,011,10,11 D. 1010,1011,110,111,00,01
第 1 题：递归函数 h(x)=x-2，f(x) 若 x<=1 return 1，否则 return x * f(h(x))。若执行 f(6)，返回（ ）。A. 24 B. 48 C. 120 D. 720 第 2 题：给定空栈 S，对 a,b,c,d,e 依次进行 进栈、进栈、进栈、出栈、进栈、出栈、进栈、出栈，栈内剩下的元素不包含（ ）。A. a B. b C. c D. d 第 3 题：双向链表双指针 llink、rlink，在 p 前插入 q，正确的插入顺序是？A/B/C/D 四个选项（涉及 rlink/llink 的先后赋值） 第 4 题：长度 300000 数组查找 val，说法错误的是？A. 顺序查找最坏 300000 次 B. 下标 i 的元素值为 i²，可用二分查找完成 C. 二分查找不超过 19 次判断 D. 值域小可用计数法 第 5 题：无向图 m 条边，所有结点度数之和为（ ）。A. m B. 1.5m C. 2m D. 3m 第 6 题：不符合树的性质的是？A. 边数为结点数减 1 B. 删任意一条边分成两个互不连通部分 C. 任意两点连一条边形成简单环 D. 任意两点有多条简单路径可达 第 7 题：8 个顶点的完全图至少要删（ ）条边才能变为森林？A. 20 B. 21 C. 22 D. 23 第 8 题：给定二叉树后序遍历为（ ）？ 第 9 题：中缀 a+b*(c-d)/e-f 的后缀表达式是（ ）。A. f-e/d-d*b+a B. +ab*-cd/e-f C. abcd-*e/f+- D. -+a/b*cd-ef 第 10 题：某文本字符 abcdef 频次 120/150/50/230/105/330，哪组是哈夫曼编码？A. 1,10,11,100,101,110 B. 110,11,101,10,100,1 C. 101,100,000,01,001,11 D. 100,111,01,101,110,00
[?]【核对 5】无向图 m 条边，度数和？
答案：C（2m） 每条边贡献两个度。
[?]【核对 9】a+b*(c-d)/e-f 后缀？
答案：C 按运算顺序转后缀得 abcd-*e/f+-。
[★]提示：这是 CS2 的“随堂测验（第一、二部分）”，建议 30 分钟完成。
限时练习：完善程序（树的宽度）
知识页 21
限时练习：完善程序（CS2 树宽度）
题目：给一棵 n 个结点的树（根 1），定义树的“宽度”为树上同一层最多的结点数。输入树，求出树的宽度。 代码框架：用 queue 做 BFS 层序遍历，q1 存整层、q2 存下一层；维护 ans = max(层内个数)。
// 完善程序queue<node> q1, q2;
q1.push({1, 1});
while ( ① ) { node u = q1.front(); q1.pop();
for ( ② ) { if ( ③ ) { q2.push({v, u.x}); } }
if ( ④ ) { if (q2.size() > ans) ans = q2.size(); q1 = q2; }
while (!q2.empty()) ⑤;
}
cout << ans;
① A. q1.empty() B. q2.empty() C. !q1.empty() D. !q2.empty() ② A. node v : G[u] B. int v : G[u.x] C. int v = q1.front().x; v!=n; v++ D. int v = q2.front().x; v!=n; v++ ③ A. !q1.empty() B. v.fa != u C. !q2.empty() D. v != u.fa ④ A. q1.empty() && !q2.empty() B. !q1.empty() && q2.empty() C. q2.front().x == u.x D. q2.front().x == n ⑤ A. q1.push(q2.front()) B. q2.pop() C. ans += (q1.front() > 0) D. ans += (q2.front() > 0)
[?]【答案核对】①~⑤ 分别选？
答案：C、B、D、A、B（以讲评为准） ①!q1.empty()；②for(int v : G[u.x]) 遍历邻接表；③v != u.fa（树中避免回到父结点）；④q1.empty() && !q2.empty()（当前层结束且下一层非空）；⑤q2.pop()（清空分层队列）。
[★]提示：这是“树的宽度”完整程序题，BFS 层序 + 分层计数。
限时练习：阅读程序与完善程序（CS5）
知识页 22
限时练习：CS5 阅读程序与完善程序
【阅读程序】(1) 输入 n 及 n 个 [0,10⁵] 整数，程序第 11/13 行做插入排序式冒泡，最后从小到大输出。 判断题：1. 第 13 行 if 判断在运行中共执行 n(n-1)/2 次。（ ）2. 若输入 n 超过 1009，数组将装不下后面输入的数字。（ ）3. 将第 11 行改为 for(int i=1; i<=n; i++)，程序功能改变。（ ）4. 程序功能是将输入整数按从小到大输出。（ ） 选择题：5. 时间复杂度为（ ）。A. O(n) B. O(数组 a 的值域范围) C. O(n log n) D. O(n^2)
6. 若输入 “6 1 3 2 2 2 1 3”，输出为（ ）。A. 2 2 2 B. 1 1 2 2 3 3 C. 3 3 2 2 1 1 D. 3 2 1
[?]【核对 5】该阅读程序时间复杂度？
答案：D（O(n^2)） 双重循环互为相邻比较交换，最坏 O(n^2)。
[?]【核对 6】输入序列输出？
答案：B 从小到大输出 1 1 2 2 3 3。
【阅读程序】判断/选择（CS5 第二篇）：程序统计满足 1≤p≤q≤m 的 (p,q) 计数并累加 b 到 sum。判断：7. 输入 p、q 超过 m 不会越界。（ ）8. sum 变量可不初始化。（ ）9. 第 16、17 行交换位置，结果不变。（ ）10. 第 15 行 i=1 改为 i=0，结果不变。（ ）选择：11. 第 12、13 行的 p 和 q+1 分别改为 p-1 和 q，输出结果（ ）。A. 变大 B. 变小 C. 不变 D. 都有可能
12. 当输入 “4 4 1 2 2 2 3 3 3 1 3” 时，输出为（ ）。A. 6 B. 10 C. 7 D. 8