考研计算机 408 全程课 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 页 · 正面（题目）

1顺序表与链表综合操作

输入第一行n，第二行n个整数。保持首次出现顺序，输出去重后的整数，空格分隔。使用Python 3标准输入输出。

2栈的括号、表达式与递归应用

后缀表达式 3 4 + 2 * 7 - 的值是多少？

3队列、循环队列与层次处理

长度m=8且采用“牺牲一个存储单元”方案的循环队列，最多保存多少个元素？

4数组寻址与特殊矩阵压缩

下三角矩阵按行压缩并从0编号，元素a[4,2]的压缩下标是多少？

5串匹配与KMP失配函数

输入两行文本text和非空模式pattern，输出pattern在text中的出现次数，重叠出现也计数。使用Python 3。

6树、森林与左孩子右兄弟转换

森林有3棵树，其根依次为A、B、C。转换后根结点之间形成的右兄弟指针共有多少条？

7Huffman树、编码与最优前缀码

权值为2、3、7、9的Huffman树，其最小带权路径长度WPL是多少？

8线索二叉树与无栈遍历

含8个结点的普通二叉链表共有多少个空指针域，可供线索化利用？

9图的存储、DFS与BFS

输入n m，随后m行无向边u v（结点0..n-1），最后一行源点s。输出从s到各点的最少边数，不可达输出-1。

10最小生成树：Prim与Kruskal

三角形三条边权分别1、2、5，其最小生成树总权是多少？

第 1 页 · 背面（答案）

读取标准输入，按题面输出；必须通过4组独立测试，不能硬编码样例。

第 2 页 · 正面（题目）

11单源最短路：Dijkstra与Bellman-Ford

无向图边A-B=2、A-C=5、B-C=1，从A到C的最短距离是多少？

12拓扑排序、AOE网与关键路径

AOE网先执行3小时活动，再并行执行4小时和2小时活动，二者都结束后执行1小时活动。总工期是多少小时？

13B树、B+树与磁盘索引

5阶B树中，非根非叶结点最少有多少个关键字？

14散列表、冲突处理与装填因子

表长7，h(k)=k mod 7，依次插入10、17、24并线性探测。成功查找24需要比较多少次？

15八大内部排序：稳定性、复杂度与适用场景

输入n及n个整数，输出数组逆序对数量。必须用可处理较大n的O(n log n)方法。

16外部排序、败者树与多路归并

16个初始归并段进行4路平衡归并，需要多少趟归并？

第 2 页 · 背面（答案）

读取标准输入，按题面输出；必须通过4组独立测试，不能硬编码样例。