简介中国矿业大学《数据结构》往届试卷及答案以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 分但考点高度一致。说句实在话这套题如果考前三天才开始看优先盯填空是性价比最高的策略因为填空考的是一个又一个“固定结论”背住数字就能拿分。表三套卷子的题型构成对比年份 / 试卷单选填空简答程序题满分2011-2012A 卷无每空 2 分 × 20每题 10 分 × 510 分 × 11002012-2013A 卷无每空 2 分 × 20每题 10 分 × 510 分 × 1100理学院 2012-2013A 卷每题 2 分 × 10每空 3 分 × 10每题 10 分 × 320 分 × 1100高频考点在三年里几乎没换过递归工作栈、二维数组地址计算、完全二叉树节点编号、循环队列的队空与队满、字符串函数运算、二叉树的先序/中序/后序序列、二叉排序树构造、栈的输入输出序列、无向完全图边数、折半查找比较次数、排序平均复杂度。这里有个很明显的命题偏好——每年都出“求具体数字”的题比如三个栈输入序列 1,2,3问你“以 2 开头并且不可能的序列是什么”比如折半查找 “在几次比较后才能找到 11”答案是 2 次。这类空不需要你写长推导只需要你平时亲手算过一遍考场上一眼扫出答案。2.2 简答 5 题哈夫曼、MST、哈希、排序、最短路径轮流坐庄简答题是整份卷子的大头50 分每题 10 分五年知识点覆盖相当集中。从三份试卷看下来命题人就是围绕五个大模块转圈哈夫曼编码与带权路径长度 WPL、最小生成树Kruskal 或 Prim、哈希表构造与冲突处理、某一种排序的完整过程追踪、单源最短路径。理学院版本没有单独考图和最短路径但换成了二叉树重建过程与 Huffman 编码本质还是同一个套路。表三套卷子简答题覆盖对照考点2011-20122012-2013理学院 2012-2013哈夫曼编码 WPL8 个权值WPL2298 个权值WPL2528 个字母频率Huffman 树最小生成树KruskalPrim 邻接表未单出哈希表线性探测二次线性探测未单出排序过程快速排序希尔排序 k4,2,1未单出最短路径未单出DijkstraH 点到各点未单出二叉树遍历重建未单出未单出前序 中序重建二叉树注意 2011-2012 简答题第 1 题和第 2 题题目给的数据是 {15,3,14,2,6,9,16,17}答案写的 WPL2292012-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. 三道必练大题的手算全过程从数组地址到哈夫曼 WPL3.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×80)×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 哈夫曼编码每个关键码的深度决定 WPL229 还是 252简答题第 1 题年年出现2011-2012 给的是权值集合 {15,3,14,2,6,9,16,17}答案备注“图不唯一 WPL229”。没有图只有这个数字很多人复习时会对着它发懵图不唯一我按自己的方法合并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 深度 43 深度 46 深度 39 深度 314、15 深度 216、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 卷子里标答自己写了“图不唯一”而 WPL229 对应的是另一棵等价树。不同合并顺序下两个同层节点的父节点深度可能不同但这不影响“WPL 取最小值”的性质。实际阅卷时只要你的合并过程合法、最终 WPL 数字对就给你满分。所以做哈夫曼题一定要写过程哪怕树形和标答不一样过程对了就有分。2012-2013 的权值是 {15,8,14,2,6,9,16,17}多了一个 8少了 3标答 WPL252。我重新合并了一遍排序 2,6,8,9,14,15,16,17取 268再取 8816取 91423取 151631取 161733取 233154取 335487。这种结构下叶子深度更深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 133放 3 号位4 mod 134放 4 号位5 mod 135放 5 号位7 mod 137放 7 号位24 mod 1311放 11 号位30 mod 134冲突去 5仍冲突去 6放 6 号位54 mod 132放 2 号位63 mod 1311冲突去 12放 12 号位72 mod 137冲突8 号位空放 8 号位87 mod 139放 9 号位95 mod 134从 4 号开始一路冲突5、6、7、8、9 都已占放 10 号位102 mod 131111、12 冲突0 号位空放 0 号位。最终表如下表线性探测哈希表存放结果2011-2012散列地址0123456789101112关键码102空543453077287952463这套操作在代码里其实就是“找空位插入”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 (h1) % m 就是线性探测的“往后挪一格超出表尾就绕回开头”。如果题目换成长度为 13 的二次线性探测探测序列就不是 h1、h2、h3而是 h1²、h-1²、h2²、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; // flag1 表示已经出现过空结点 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。中间的内部节点不做计数只把左右子树的叶子数加起来。很多考研参考书上的写法会和它等价但有一个常见错误是忘了写 tNULL 这个分支导致递归访问空指针时直接崩溃。考试判分时“空树返回 0”这一项占 3 分左右所以务必把边界条件写全。4.3 顺序存储数组下标公式速查程序题有时候还连着考满二叉树节点编号2012-2013 填空第 4 题就是“满二叉树第 10 个节点的父节点是第几个、右孩子是第几个”。按顺序存储的层序编号规则第 i 个节点的父节点是 i/2左孩子是 2i右孩子是 2i1。所以第 10 个节点的父节点是 5右孩子是 21。如果这棵满二叉树有 10 层节点总数是 2^10 - 1 1023。三个空分别填 5、21、1023。这里备注一下这套题里的“完全二叉树”和“满二叉树”两个词经常混用。完全二叉树是空位只能出现在最后一层右侧满二叉树是完全二叉树的特例。题目如果明确说了“满二叉树第 10 个节点”直接用 2i 和 2i1 这套公式如果只说“完全二叉树”节点总数就不能用 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 那套卷的备注写着“图不唯一”但 WPL229 是确定的你看判分标准就知道只有过程没有答案会被扣分答案数字错了过程对也会扣一半。5.4 二次探测只加不减探测序列错得离谱现象二次线性探测存放哈希表时冲突了就往 h1²、h4、h9 一路找下去找遍整张表也没空位。原因二次探测的标准序列是 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 语义scake 的第 3 个字符是 ktchild 的第 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 小时把这三套卷子当模拟考试各做一遍第一套用来暴露盲区第二套用来检验修正效果第三套留到进考场前一晚只看错题。当然如果你的目标是复习更成体系的教材内容这份老题更适合当作“查漏补缺用的指纹库”每隔一段时间回来刷一刷检验自己有没有真正掌握卷子里的那几个核心模块——这才是这份资源的长期用法。希望帮到你。本文还有配套的精品资源点击获取