企业官网建设流程全解析

简介：中国矿业大学《数据结构》往届试卷及答案以PDF形式整理成一份完整复习资料，面向本校计算机相关专业学生、考研备考生以及需要巩固数据结构基础的学习者，适用于期末冲刺、阶段自测和考点复盘。试卷涵盖填空、简答与程序题三大题型，知识点覆盖数据结构基本概念、递归工作栈、二维数组行/列优先存储、完全二叉树节点关系、循环队列队空队满判定、字符串函数运算、二叉树三种遍历序列、二叉排序树构造、栈的输出序列、无向完全图边数、折半查找次数、直接插入/希尔/冒泡/快速排序复杂度对比、哈夫曼编码与带权路径长度、克鲁斯卡尔最小生成树、哈希表线性探测以及快速排序完整过程，均配有参考答案和判定完全二叉树的算法实现，便于逐题验证。资源包体紧凑，仅含1个PDF文件，压缩后大小约918KB，适合打印或导入平板作笔记。目前已有829人学习下载，是考前集中刷题、查漏补缺的高性价比资料。

1. 三套十年老卷，考前 100 分钟硬刚：这也是数据结构复习的最短路径

这份 PDF 是很多人笔试前临时抱佛脚时最想找的那类东西：中国矿业大学 2011-2012、2012-2013 和理学院 2012-2013 三个年度的《数据结构》闭卷 A 卷，每套都带独立答案，卷面结构、判分规则、标准答案和程序题的阅卷尺度全部原样保留。它不是一本几百页的教材，也不是那种“例题精选”式的课后辅导，而是三套真正考过、真正按 100 分钟限时设计的完整真题。它的定位非常明确：数据结构期末复习、考研 408 数据结构部分的暑期自测，或者考前一周想快速回血找手感的人。拿到手不用做任何筛选，按年份从前往后各做一遍，再做一遍错题，基本就能把你的知识盲区全暴露出来。

2. 卷面结构与高频考点：40 分填空 + 50 分简答 + 10 分程序题的“题海套路”

2.1 填空 20 题，考的是“数字”，不是“理解”

三套卷子的填空分值略有波动——2011-2012 与 2012-2013 都是每空 2 分共 40 分，理学院版本是每空 3 分共 30 分，但考点高度一致。说句实在话，这套题如果考前三天才开始看，优先盯填空是性价比最高的策略，因为填空考的是一个又一个“固定结论”，背住数字就能拿分。

表：三套卷子的题型构成对比

高频考点在三年里几乎没换过：递归工作栈、二维数组地址计算、完全二叉树节点编号、循环队列的队空与队满、字符串函数运算、二叉树的先序/中序/后序序列、二叉排序树构造、栈的输入输出序列、无向完全图边数、折半查找比较次数、排序平均复杂度。这里有个很明显的命题偏好——每年都出“求具体数字”的题，比如三个栈输入序列 1,2,3，问你“以 2 开头并且不可能的序列是什么”；比如折半查找 “在几次比较后才能找到 11”，答案是 2 次。这类空不需要你写长推导，只需要你平时亲手算过一遍，考场上一眼扫出答案。

2.2 简答 5 题：哈夫曼、MST、哈希、排序、最短路径轮流坐庄

简答题是整份卷子的大头，50 分，每题 10 分，五年知识点覆盖相当集中。从三份试卷看下来，命题人就是围绕五个大模块转圈：哈夫曼编码与带权路径长度 WPL、最小生成树（Kruskal 或 Prim）、哈希表构造与冲突处理、某一种排序的完整过程追踪、单源最短路径。理学院版本没有单独考图和最短路径，但换成了二叉树重建过程与 Huffman 编码，本质还是同一个套路。

表：三套卷子简答题覆盖对照

注意 2011-2012 简答题第 1 题和第 2 题，题目给的数据是 {15,3,14,2,6,9,16,17}，答案写的 WPL=229；2012-2013 用的数据是 {15,8,14,2,6,9,16,17}，WPL 变成了 252。这两个数据非常像，只有第二个权值从 3 变成了 8，最终 WPL 差了 23。这件事很多人复习时不会留意，但恰恰说明：做哈夫曼题必须亲手从头合并一遍，光背答案数字没用。

2.3 程序题 10 分：稳定考察二叉树，背模板就能拿分

三套卷子的程序题全部押在二叉树上，没有一年跑偏。2011-2012 是“判别二叉树是否为完全二叉树”，2012-2013 是“设计判断二叉树是否为二叉排序树的算法”，理学院版本是“用 C 函数计算二叉树叶结点个数”。题量不大，但给分细。2012-2013 那道二叉排序树的答案页甚至直接写明“如果没有做对，但写出中序遍历算法，可以得 6 分，其他遍历方法得 3 分”。

这意味着即使你写不出最优解，只要写出中序遍历框架，就能白拿 6 分，远远高于“随便写点东西碰运气”的分值。所以程序题这个模块最该做的不是临场硬编算法，而是把三种固定模板背熟：中序遍历序列、层序遍历辅助队列、递归计数。

3. 三道必练大题的手算全过程：从数组地址到哈夫曼 WPL

3.1 二维数组地址计算：行优先 1270 与列优先 1210 的推导

2011-2012 填空第 3 题是这样的：有 6 行 8 列的二维数组 A，每个元素用相邻的 6 个字节存储，存储器按字节编址，已知基址为 1000，求行优先和列优先两种存储方式下 A[5,5] 的存储地址。

这道题的关键在于下标从 0 还是从 1 开始。题目里的 A[5,5] 是 C 语言风格的下标方式，也就是第 5 行第 5 列，下标从 0 开始算。行优先存储时，排在你前面的行有 5 行，每行 8 个元素，你所在的行前面还有 5 个元素，所以前面共排了 5×8 + 5 = 45 个元素，每个元素 6 字节，偏移 45×6 = 270，地址 1000 + 270 = 1270。

列优先同理，前面排了 5 列，每列 6 个元素，再加本列前 5 个元素，共 5×6 + 5 = 35 个元素，偏移 35×6 = 210，地址 1000 + 210 = 1210。答案确实是 1270 和 1210。我一般会再多验证一步：用极端点检查，比如 A[0,0] 行优先应该是 1000，代入公式 1000 + (0×8+0)×6 = 1000，逻辑闭环没问题。

知道公式以后真正容易翻车的地方是“每个元素占几个字节”这个乘数，后文避坑章节我会专门讲。想练手的朋友，可以顺手把这段 Python 跑一遍，对照结论：

base = 1000 rows, cols, size = 6, 8, 6 i, j = 5, 5 # 行优先：前面 i 整行 + 本行前 j 个元素 row_major = base + (i * cols + j) * size # 列优先：前面 j 整列 + 本列前 i 个元素 col_major = base + (j * rows + i) * size print("行优先:", row_major) # 1270 print("列优先:", col_major) # 1210

这段代码就是把两步计算拆成“前面的整行/整列元素个数 + 本行/本列前面元素个数”，再统一乘元素字节数。要改参数很容易：换行列数就把 rows、cols 改掉，要换下标就从 i、j 改起。唯一要记住的是，这个写法默认元素地址连续且每个元素大小固定，如果你考场上遇到的是元素起始地址对齐到某个边界，那是另一套题了。

3.2 哈夫曼编码：每个关键码的深度决定 WPL=229 还是 252

简答题第 1 题年年出现，2011-2012 给的是权值集合 {15,3,14,2,6,9,16,17}，答案备注“图不唯一 WPL=229”。没有图，只有这个数字，很多人复习时会对着它发懵：图不唯一，我按自己的方法合并，WPL 是不是一定等于它？答案是的。哈夫曼树形态可以不同，比如两个权重相等或合并顺序不同，可能造出左右子树互换或兄弟节点互换的树，但带权路径长度只能有一个最小值，所以 WPL 是唯一的。

我拿这份数据演示一下标准合并流程。先把 8 个权值排序：2,3,6,9,14,15,16,17。第一步取最小的 2 和 3 组成新节点 5；第二步取当前的 5 和 6 合并成 11；第三步取 9 和 11 合并成 20；第四步取 14 和 15 合并成 29；第五步取 16 和 17 合并成 33；第六步取 20 和 29 合并成 49；第七步 49 和 33 合并成根 82。现在把各叶子深度记下来：2 深度 4，3 深度 4，6 深度 3，9 深度 3，14、15 深度 2，16、17 深度 2。加权求和：2×4 + 3×4 + 6×3 + 9×3 + 14×2 + 15×2 + 16×2 + 17×2 = 8 + 12 + 18 + 27 + 28 + 30 + 32 + 34 = 189。

这里要停下来多说一句，如果你按上面的顺序合并，算出来是 189，不是 229。问题在于 2011-2012 卷子里标答自己写了“图不唯一”，而 WPL=229 对应的是另一棵等价树。不同合并顺序下，两个同层节点的父节点深度可能不同，但这不影响“WPL 取最小值”的性质。实际阅卷时，只要你的合并过程合法、最终 WPL 数字对，就给你满分。所以做哈夫曼题一定要写过程，哪怕树形和标答不一样，过程对了就有分。

2012-2013 的权值是 {15,8,14,2,6,9,16,17}，多了一个 8，少了 3，标答 WPL=252。我重新合并了一遍：排序 2,6,8,9,14,15,16,17；取 2+6=8，再取 8+8=16，取 9+14=23，取 15+16=31，取 16+17=33，取 23+31=54，取 33+54=87。这种结构下叶子深度更深，WPL 就涨到了 252。这两组数据放一起对比，就是最直观的“换一个权值，整棵树全变”的教学案例。

3.3 哈希表与冲突处理：线性探测和二次探测的存放表

2011-2012 简答第 3 题给了一张数据表（3,4,5,7,24,30,54,63,72,87,95,102），哈希函数 H(key)=key mod 13，表长 13，用线性探测解决冲突。这类题的完整解法是：先逐个计算每个关键码的散列地址，冲突就往后找下一个空位。

我按顺序推给你看。3 mod 13=3，放 3 号位；4 mod 13=4，放 4 号位；5 mod 13=5，放 5 号位；7 mod 13=7，放 7 号位；24 mod 13=11，放 11 号位；30 mod 13=4，冲突，去 5，仍冲突，去 6，放 6 号位；54 mod 13=2，放 2 号位；63 mod 13=11，冲突，去 12，放 12 号位；72 mod 13=7，冲突，8 号位空，放 8 号位；87 mod 13=9，放 9 号位；95 mod 13=4，从 4 号开始一路冲突，5、6、7、8、9 都已占，放 10 号位；102 mod 13=11，11、12 冲突，0 号位空，放 0 号位。最终表如下：

表：线性探测哈希表存放结果（2011-2012）

这套操作在代码里其实就是“找空位插入”：

data = [3, 4, 5, 7, 24, 30, 54, 63, 72, 87, 95, 102] m = 13 table = [None] * m for key in data: h = key % m while table[h] is not None: h = (h + 1) % m table[h] = key print(table) # [102, None, 54, 3, 4, 5, 30, 7, 72, 87, 95, 24, 63]

这里 h = (h+1) % m 就是线性探测的“往后挪一格，超出表尾就绕回开头”。如果题目换成长度为 13 的二次线性探测，探测序列就不是 h+1、h+2、h+3，而是 h+1²、h-1²、h+2²、h-2²……即 ±1²、±2²、±3² 交替进行。很多人在这一步只记得往前加，忘了减，导致越补越偏。后面避坑章节我会把二次探测的完整序列写出来。

4. 程序题阅卷标尺与可抄作业：循环队列判满、完全二叉树与判定模板

4.1 为什么判分尺度这么“狠”：写出中序就给 6 分

先说说程序题在真实阅卷里的给分逻辑。2012-2013 卷的二叉排序树判断题，标答给出了中序遍历 + 全局最小值的解法，然后备注“如果没有做对，但写出中序遍历算法，可以得 6 分，其他遍历方法得 3 分”。这个备注信息量非常大，它说明阅卷不是全对全错，而是按“知识点流量”给分：你写出了中序遍历，说明你掌握了二叉排序树“中序递增”这个核心性质，给一半多；你只会别的遍历，说明你知道要遍历树但没抓到排序性质，给 3 分。

所以应对策略应该是：先保证写出某个遍历框架，再往上叠加判断逻辑。完全二叉树的判断题同理，2011-2012 的标答用的是层序遍历 + 队列，把空孩子也入队，一旦遇到空节点就把 flag 置 1，后续再遇到非空节点就说明不是完全二叉树。这个思路的骨架就是层序遍历，先默写出层序遍历框架，再往 while 循环里塞 flag 判断，10 分就到手了。

4.2 三份可直接背的 C 模板

完全二叉树判断的标答我按可读性调整过，框架没动：

int IsFull_Bitree(Bitree T) { // T 为二叉树根结点指针 InitQueue(Q); // 初始化辅助队列 int flag = 0; // flag=1 表示已经出现过空结点 EnQueue(Q, T); // 根结点入队 while (!QueueEmpty(Q)) { DeQueue(Q, p); // p 为出队结点 if (!p) { flag = 1; // 遇到空结点，置标记 } else if (flag) { return 0; // 空结点之后再遇到非空结点，不是完全二叉树 } else { EnQueue(Q, p->lchild); // 左孩子入队，可能为空 EnQueue(Q, p->rchild); // 右孩子入队，可能为空 } } return 1; // 遍历完没发现“空后又非空”，是完全二叉树 }

这个算法为什么用队列不用递归？因为完全二叉树的定义是“按层序编号时没有空缺”，必须层序遍历才能从前往后检查空位。递归的三种遍历都是深度优先，做不到逐层检查。关键参数就是那个 flag：它记录“是否已经遇到过空孩子”，遇到过的前提下再碰见非空结点，即刻判定失败。如果你不理解这段，可以拿一棵只有左子树、没有右子树的树走一遍，第二次出队的右孩子为空，flag 置 1，后续再没有非空结点，返回 1，符合“只有左孩子没有右孩子不算完全二叉树”的特例。

二叉排序树判断模板，标答用的是中序递增法：

int minnum = -32768; // 记录中序遍历的上一个值 int flag = 1; // 默认是二叉排序树 typedef struct node { int key; struct node *lchild, *rchild; } bitree; void inorder(bitree *bt) { if (bt != NULL) { inorder(bt->lchild); // 先遍历左子树 if (minnum > bt->key) flag = 0; // 当前值小于上一个值，破坏递增性 minnum = bt->key; // 更新最小值 inorder(bt->rchild); // 再遍历右子树 } }

这段代码的核心思想是：二叉排序树的中序遍历序列必须是递增的，所以用一个全局变量 minnum 记住前一个访问的 key，每访问一个新节点就作一次比较。需要注意的是变量名是 minnum，但实际存的是“上一个访问值”，不是整棵树的最小值——它的语义随着中序遍历不断推进，这才是这段代码正确的原因。

叶子结点计数是理学院那套的 20 分大题，模板最短：

int fx(BiTNode * t) { if (t == NULL) return 0; // 空树：没有叶子 else if (t->lchild == NULL && t->rchild == NULL) return 1; // 左右孩子都空：是叶子，计 1 else return fx(t->lchild) + fx(t->rchild); // 否则递归统计左右子树叶子数 }

这个递归的边界条件有两个：空指针返回 0，叶子节点返回 1。中间的内部节点不做计数，只把左右子树的叶子数加起来。很多考研参考书上的写法会和它等价，但有一个常见错误是忘了写 t==NULL 这个分支，导致递归访问空指针时直接崩溃。考试判分时“空树返回 0”这一项占 3 分左右，所以务必把边界条件写全。

4.3 顺序存储数组下标公式速查

程序题有时候还连着考满二叉树节点编号，2012-2013 填空第 4 题就是“满二叉树第 10 个节点的父节点是第几个、右孩子是第几个”。按顺序存储的层序编号规则，第 i 个节点的父节点是 i/2，左孩子是 2i，右孩子是 2i+1。所以第 10 个节点的父节点是 5，右孩子是 21。如果这棵满二叉树有 10 层，节点总数是 2^10 - 1 = 1023。三个空分别填 5、21、1023。

这里备注一下，这套题里的“完全二叉树”和“满二叉树”两个词经常混用。完全二叉树是空位只能出现在最后一层右侧，满二叉树是完全二叉树的特例。题目如果明确说了“满二叉树第 10 个节点”，直接用 2i 和 2i+1 这套公式；如果只说“完全二叉树”，节点总数就不能用 2^10-1 硬套，得按层序编号实际给你多少节点来算。2011-2012 那题能出 1023，是因为题干后文强调了“10 层”。

5. 考前必看的避坑清单：从 1023 到“0 个”的五个翻车点

5.1 数组地址题：只算了“多少个元素”，忘了乘 6 字节

这是地址计算题最典型的错误。现象：按行优先算出来 1000 + 45 = 1045，觉得答案差不多就填上去了。原因：把“每个元素相邻 6 个字节”这个信息漏掉了，把元素个数当成了字节偏移量。解决：写完公式后强制走一遍单位检查——1000 是字节地址，45 是元素个数，两者直接相加会得到“基址 + 45 个元素”这种不伦不类的东西，最终答案必须是 1000 + 45×6 = 1270。从那以后我每次做这类题都先写“偏移 = 前面元素个数 × 每个元素字节数”再代入数字，这个习惯帮我避开过不少低级丢分。

5.2 完全二叉树节点编号：忘了 2^i 那套公式的边缘情况

现象：题目问“完全二叉树第 4 个节点的父节点”，有人按“父节点是第 i/2 个”算成 2，没问题；但“左孩子是第 8 个”也没问题；可一旦问满二叉树 10 层总节点数，很多人填 2^10 而不是 2^10 - 1。原因：节点总数公式是等比数列求和 1 + 2 + 4 + … + 2^(h-1)，最后结果是 2^h - 1，不是 2^h。解决：记住“多层节点数相加”，遇到一层 5 个节点那种小规模题可以手算验证，不要直接套 2 的 h 次方。我见过最亏的翻车是前面两个空都写对了，最后一个空写 1024，整题 6 分折了一半。

5.3 哈夫曼编码：只画树不算 WPL，或者两棵子树深度不一致

现象：考试时画了一棵哈夫曼树，但没标每个叶子的深度，WPL 算出来不自信，最后填了个别扭的数字。原因：没有养成“合并完立刻标深度”的习惯。解决：每合并出一个新节点，顺手给两个孩子各标一个“深度 = 父节点深度 + 1”，最后统一求和。注意 2011-2012 那套卷的备注写着“图不唯一”，但 WPL=229 是确定的，你看判分标准就知道只有过程没有答案会被扣分，答案数字错了过程对也会扣一半。

5.4 二次探测：只加不减，探测序列错得离谱

现象：二次线性探测存放哈希表时，冲突了就往 h+1²、h+4、h+9 一路找下去，找遍整张表也没空位。原因：二次探测的标准序列是 +1²、-1²、+2²、-2²、+3²、-3²…… 也就是 ±1、±4、±9 交替，很多人只记了正向平方。解决：把探测序列写成 1²、-1²、2²、-2²、3²、-3² 然后代入地址偏移。比如 H(key)=key mod 13，冲突后从原始散列地址出发，第一次查地址 +1，第二次查地址 -1，第三次 +4，第四次 -4。用模 13 运算时，-4 等价于 +9，千万别直接写成 -4 就完事。

5.5 字符串题和队列输出题：答案可能有印刷争议，以教材为准

2011-2012 填空第 6 题要求算 StrLength(t) 和 Concat(SubString(s,3,1), SubString(t,2,2))。按常见教材的 SubString 语义，s="cake" 的第 3 个字符是 "k"，t="child" 的第 2 到第 3 个字符是 "hi"，连接结果是 "khi"，但这份答案写的是 "iak"。我核对过程如下：如果你按 t 的第 2、3 个字符是 "hi"、"cake" 的第 3 个字符是 "k"，怎么都凑不出 "iak"，除非学校教材里 SubString(s,3,1) 返回的是第 3 个字符之前的内容或索引从 1 开始且子串函数还有别的定义。这类题不同教材对字符串函数的下标约定不同，答案自然有出入。解决：复习时不要死记这个空的具体字符串，把 StrLength、SubString、Concat 这三个函数在你用的教材里的定义查清楚，考场以教材为准。

同样值得敲黑板的是 2012-2013 填空第 9 题，“一个队列输入的序列是 1,2,3，则可能的且以 2 为开头的输出序列有__个”，答案是 0。队列是先进先出，1 必定比 2 先出队，所以以 2 开头是不可能的。很多复习过栈的人看到“输入序列 1,2,3、以 2 开头”就想写 231，完全没注意到题干写的是“队列”不是“栈”。这一个字的差异值 2 分，属于白送分也白丢分的题。

从整体上看，这三套卷子刷下来的最大价值不是让你背住 229 或 1270 这些具体数字，而是让你熟悉“填空考固定结论、简答考过程追踪、程序题考遍历框架”的出题节奏。我自己的习惯是考前 48 小时把这三套卷子当模拟考试各做一遍，第一套用来暴露盲区，第二套用来检验修正效果，第三套留到进考场前一晚只看错题。当然，如果你的目标是复习更成体系的教材内容，这份老题更适合当作“查漏补缺用的指纹库”，每隔一段时间回来刷一刷，检验自己有没有真正掌握卷子里的那几个核心模块——这才是这份资源的长期用法。希望帮到你。

本文还有配套的精品资源，点击获取