834真题限时模拟与复盘：数据结构、哈希表、堆排序和计网计算题-平芜编程栈

简介：面向华中科技大学834计算机综合考研复习的2019年真题PDF，适合备考该校计算机相关专业、希望用原题检验数据结构与计算机网络掌握程度的考生。压缩包共1个PDF文件，约1.37MB，保持试题排版，便于打印、限时模拟和按题型拆分练习。内容覆盖选择题、填空题、判断题与综合计算题，既包含串、链表、队列栈、二叉树遍历、图遍历、排序、哈夫曼编码等数据结构考点，也涉及OSI与TCP/IP参考模型、路由选择、CSMA/CA、DNS查询、TCP报文等计算机网络知识。已有585人学习，可用于熟悉834命题风格、定位薄弱章节；通过选择题辨析概念、填空题检查细节、判断题纠正误区、计算题训练过程表达，并围绕错题整理高频考点，适合冲刺阶段自测和查漏补缺，也可作为同科目期末复习与考研真题训练的对照材料。

1. 一份 834 真题 PDF，救的是「会做但写不对」的那批人

有位考生把 834 的选择题刷到几乎全对，一到手写大题就出事：哈希表平均查找长度算成 2.5，堆排序第一趟画错，计网的 CRC 校验码末位多补了一个 0。这种卷子的分工很清楚——选择题考概念边界，填空题和计算题考「过程能不能一笔不差落在纸上」。这份 2019 年的真题 PDF 保留的是原始卷面形态：选择题 10 道、填空题 10 道、判断题 8 道，加数据结构四道大题和计算机网络的计算与简答。题面里有明显的录入错字和 OCR 乱码，前序序列和中序序列甚至字符集都对不上，恰恰说明它没被精修过，是拿来当限时模拟卷用的，不是拿来背答案的。

2. 拆开卷面：834 的题型骨架与时间配比

拿到 PDF 先别急着翻答案。这张卷子的排版里，分值区被扫描裁掉了一部分，按同类 150 分卷的常见配比还原，选择题每题 2 分、填空每题 2 分、判断每题 1 分，剩下的大头全压在后半段的四道数据结构大题和计网计算题上。这个结构决定了复习策略：前半段是「不能丢」的基本盘，后半段是「拉开差距」的主战场。很多人刷这套卷子翻车，不是因为不会，而是把 60 分钟耗在 28 道客观题上，回头发现最小生成树和哈希表两道题只剩 20 分钟。

2.1 题量与分值的分配表

先按下面的口径把整张卷子的时间切一遍，实际做题时会比拍脑袋分配稳得多：

板块	题量	估算分值	建议用时	允许失误
选择题	10	20	20 分钟	1 道
填空题	10	20	20 分钟	2 道
判断题	8	8	8 分钟	1 道
数据结构大题	4	约 52	60 分钟	半道
计网填空+计算	约 20 空 + 4 题	约 50	42 分钟	1 道

这张表的作用不是精确估值，而是给你一条硬线：客观题超过 50 分钟就必须停手往后走。判断题尤其容易失控，8 道题涉及哈夫曼编码长度、循环队列上溢、连通图 DFS 可达性这些容易反复纠结的点，一旦在某一道上反复摇摆，后面的大题就废了。我的习惯是判断题先按第一直觉落笔，打个问号标记，全部写完再回头，绝不在一道 1 分题上停留超过 40 秒。

2.2 题干关键词到知识点的映射

卷面里每道题其实都自带指向，只是被文字包装住了。把题干里的关键词抽出来，能直接判断该调哪一块知识，判断时间从 30 秒压到 3 秒：

题干关键词	真实考点	落笔前要确认的事
「最后一个结点之后插入」「删除第一个结点」	链表结构选型	尾指针还是头指针，循环还是非循环
「读取第 i 个元素」	数组随机访问	存储是否连续，O(1) 还是 O(n)
「中序 + 前序求后序」	二叉树遍历还原	两序列字符集必须一致
「front / rear / 入队列」	链式队列指针操作	头尾指针各自的含义
「最快选出最小 k 个」	堆排序适用场景	部分排序而非全排序
「邻接表 m 个表结点」	有向图边数统计	表结点数即边数
「散列表长度 7」「线性探测」	哈希冲突处理与 ASL	ASL 数的是比较次数
「32 位帧序号」「接收窗口最大」	滑动窗口序号空间	SR 与 GBN 的窗口上限不同
「生成多项式 x⁴+x³+1」	CRC 校验	补零位数 = 最高次幂

这张映射表可以直接当成考前 10 分钟的速览卡。第 9 题尤其典型：题干说「8000 个记录里最快选出最小的 14 个」，很多人的第一反应是快排，但快排要先做完全部划分，而归并排序更没优势；堆排序建堆 O(n)，取 14 次堆顶 O(k log n)，才是这道题想要的答案。这类题考的从来不是「哪个排序最快」，而是「哪个排序支持部分选择」。

2.3 用 PDF 做一次限时模拟的操作流程

拿到这份 PDF 原件后，我一般走三步：

拆页与屏蔽：把 PDF 拆成「题面」和「解析」两个文件，或者直接把后半部分的答案解析页删除，避免做题时余光扫到。
按上表卡表计时：手机开秒表分四段计时，客观题 48 分钟、数据结构大题 60 分钟、计网 42 分钟，每段结束立刻停笔记录实际用时，不管做没做完。
不看分数看失分类型：做完不急着对答案算总分，先给每道错题打一个标签——概念错、计算错、题面读错、时间不够。四类标签的处理方式完全不同，概念错要回教材，计算错要动手推，题面读错要练审题，时间不够要改节奏。

这一步有个容易被忽略的点：PDF 扫描件里的乱码本身就是训练材料。卷面上那几道字符集对不上的题，正好逼你判断「这题是题面坏了还是我不会」。真实考场上遇到表述含糊的题也一样，先判断是题目问题还是自己知识缺口，再决定要不要花时间。

3. 数据结构计算题的复盘：手推一遍，再让脚本对答案

数据结构那四道大题是整张卷子最值钱的部分，也是背答案最容易出事的部分。卷面上给出的遍历序列和哈希序列在扫描过程里被 OCR 啃掉了几位，如果照着乱码硬套，得出的结论会自相矛盾。正确的做法是：先用手推还原出题面的真实数据，再用一段短脚本验证自己的每一步，最后才去看标准答案。这两步之间的差值，就是你真正缺的东西。

3.1 前序 + 中序还原二叉树：递归落笔法

卷面上这道题的前序序列被扫成ABECD、中序被扫成IBEPJ，两组字符集明显不一致，直接套公式必然出错。按标准解复原，前序应为ABEDC，中序应为EBDAC，这样推出来的后序才是EDBCA。手推的逻辑只有一条：前序的第一个字符是根，拿着这个根去中序里切出左右子树，再对左右子树递归。手推熟练之后，用代码把同一套逻辑写一遍，是最省事的自检方式：

def build_post(preorder: str, inorder: str) -> str: """由前序 + 中序还原二叉树，返回后序序列""" if not preorder: return "" if len(preorder) != len(inorder) or set(preorder) != set(inorder): raise ValueError("前序与中序的字符集或长度不一致，题面可能已被破坏") root = preorder[0] # 前序首位必然是当前子树的根 idx = inorder.index(root) # 根在中序里的位置，左侧是左子树 left_in, right_in = inorder[:idx], inorder[idx + 1:] left_pre, right_pre = preorder[1:1 + idx], preorder[1 + idx:] # 后序 = 左子树后序 + 右子树后序 + 根 return build_post(left_pre, left_in) + build_post(right_pre, right_in) + root print(build_post("ABEDC", "EBDAC")) # 输出 EDBCA

这段代码里最关键的不是递归体，而是第二行那个校验。真题扫描件里的序列经常出现「长度对得上但字符集对不上」的情况，比如卷面那个IBEPJ，长度是 5，前序ABECD长度也是 5，长度校验拦不住，必须加字符集比对。set()比对能在 0.1 秒内把坏题面挡在门外，避免你在一个根本不成立的输入上推半小时。

参数上只有两个入口：preorder和inorder，都是字符串。如果要处理含重复元素的序列，inorder.index(root)会定位到第一个匹配项，此时必须改成「按区间传下标」的写法，否则会切错子树——这是二叉树还原题在含重复关键字时最常见的翻车点，虽然这套卷子没考，但同一考点换个年份就会出现。

3.2 哈希表线性探测：ASL 数的是比较次数，不是冲突次数

卷面这道题的参数很完整：表长 7，散列函数H(k) = k mod 7，关键字序列(26, 32, 9, 28, 14, 68, 46)，冲突用线性探测解决。手推一遍就能发现，前四个关键字一路顺风，从 14 开始出现堆积，到 46 的时候已经惨不忍睹。这种题手推容易数错，用脚本把每一步的比较次数打出来最稳：

KEYS = [26, 32, 9, 28, 14, 68, 46] M = 7 def h(k: int) -> int: return k % M table = [None] * M probe = {} # 记录每个关键字落位用了几次比较 for k in KEYS: pos = h(k) cnt = 1 # 首次定位也算一次比较 while table[pos] is not None: # 位置被占，线性探测往后挪一格 pos = (pos + 1) % M cnt += 1 table[pos] = k probe[k] = cnt print(table) # [28, 14, 9, 46, 32, 26, 68] print(probe) # {26: 1, 32: 1, 9: 1, 28: 1, 14: 2, 68: 2, 46: 7} print(round(sum(probe.values()) / len(KEYS), 3)) # 2.143

跑出来的表是[28, 14, 9, 46, 32, 26, 68]，查找成功的平均查找长度是(1+1+1+1+2+2+7)/7 ≈ 2.14。这里面最容易错的是 46 那一位：46 % 7 = 4，位置 4 被 32 占了，5 被 26 占了，6 被 68 占了，0 被 28 占了，1 被 14 占了，2 被 9 占了，一直探到 3 才落位，累计 7 次比较。很多人算成 4 次，是因为把「冲突了几次」当成了「比较了几次」，漏掉了首次定位和最后那次成功比较。

参数上，M必须是质数，这套卷子取 7 是标准做法；如果表长改成合数，k % M的分布会明显变差，堆积会更严重。while循环里用的是取模后的环形探测，这是线性探测的标准写法，写成pos += 1而不取模，在表尾会直接数组越界。另外，这个脚本只算查找成功的情况，如果题目要求查找失败的 ASL，需要另外按「从每个散列地址出发探测到第一个空位」的规则统计，两套口径不能混用。

3.3 堆排序：初始小根堆与第一趟重建

卷面给的关键字序列是(46, 81, 49, 41, 23, 79, 15, 67)，要求给出初始小根堆和第一趟重建后的结果。这道题的坑全在下标上：如果按 0 基下标写，孩子节点是2i+1和2i+2；按 1 基写，孩子是2i和2i+1。两套写法混着用，第一个元素一定错。我习惯在数组头补一个占位元素，全程用 1 基：

def sift_down(a: list, i: int, size: int) -> None: """1 基下标的小根堆下沉操作""" while 2 * i <= size: child = 2 * i if child + 1 <= size and a[child + 1] < a[child]: child += 1 # 左右孩子里取更小的那个 if a[i] <= a[child]: break # 已经比孩子小，堆性质成立 a[i], a[child] = a[child], a[i] i = child arr = [46, 81, 49, 41, 23, 79, 15, 67] a = [0] + arr # 补占位，让有效下标从 1 开始 n = len(arr) for i in range(n // 2, 0, -1): # 从最后一个非叶结点往前建堆 sift_down(a, i, n) print(a[1:]) # [15, 23, 46, 41, 81, 79, 49, 67] a[1], a[n] = a[n], a[1] # 堆顶与末尾交换，最小值归位 sift_down(a, 1, n - 1) # 对剩余 n-1 个元素重建 print(a[1:]) # [23, 41, 46, 67, 81, 79, 49, 15]

建堆的起点是n // 2，也就是最后一个非叶结点，对 8 个元素来说是下标 4，对应关键字 41。它只有一个左孩子 67，41 更小，不动。接着处理下标 3 的 49，两个孩子是 79 和 15，15 最小，交换；下标 2 的 81，两个孩子是 41 和 23，23 最小，交换；下标 1 的 46，两个孩子是 23 和 15，15 最小，交换之后 46 落到下标 3，还要继续和它的孩子 79、49 比较，确认不再下沉。整个建堆过程是自底向上的，时间复杂度 O(n)。

第一趟排序把堆顶 15 和末尾 67 交换，15 归位到数组最后，然后对前 7 个元素重建。67 从堆顶一路下沉：先和 23、46 里较小的 23 交换，再和 41、81 里较小的 41 交换，落到下标 4 时已经没有孩子，停止。最终结果是[23, 41, 46, 67, 81, 79, 49, 15]。

参数说明上，sift_down的第三个参数size表示「当前还在堆里的元素个数」，第一趟之后要传n-1，最后一趟传 1。这个参数传错是最常见的错法——写成固定值n，交换出去的 15 会被重新拉回堆里，结果就变成了原地转圈。另外，大根堆和小根堆只有比较符号的区别，a[child+1] < a[child]改成>就是大根堆，改的时候两处都要改，只改一处会得到一棵既不是大根堆也不是小根堆的怪树。

4. 计网部分的定量题：把填空题当成可验算的公式

计算机网络那半张卷子看起来零碎，其实绝大部分是可以算出来的，不是靠记。子网地址、CRC 校验码、滑动窗口上限、路由表迭代，这四类题都有明确的算法，只要参数对齐，结果唯一。真正靠背的只有协议分层和少量术语填空。把可算的部分用脚本跑一遍，比抄十遍笔记都管用。

4.1 子网地址与 CRC：两个必须手熟的公式

子网那道题给的是192.168.211.99/24，求网络地址。/24 表示前 24 位是网络位，后 8 位是主机位，把主机位清零就是网络地址，结果是192.168.211.0。这类题手算也快，但用标准库能顺带把广播地址和可用主机数一起验出来：

import ipaddress # strict=False 允许传入带主机位的地址，否则会直接报错 net = ipaddress.ip_network("192.168.211.99/24", strict=False) print(net.network_address) # 192.168.211.0 print(net.broadcast_address) # 192.168.211.255 print(net.num_addresses) # 256，可用主机数为 254

strict=False这个参数是必须的。默认的strict=True要求传入的地址是网络地址本身，输入.99会直接抛ValueError，很多人第一次用会卡在这里，以为是地址写错了。num_addresses统计的是全部地址数，减去网络地址和广播地址才是可用主机数，这个细节在填空题里经常被拿来设坑，问「可用主机数」却填 256 就错了。

CRC 那道题给的多项式是x⁴ + x³ + 1，写成比特串是11001，最高次是 4，所以要在数据后面补 4 个 0，而不是补 5 个。卷面数据被扫花了，用1011001复现同一算法：

def crc(data: str, poly: str) -> str: """模 2 除法求 CRC 校验码，poly 为生成多项式的比特串""" r = len(poly) - 1 # 补零位数 = 多项式最高次幂 bit = list(data + "0" * r) # 数据末尾补 r 个 0 div = [int(c) for c in poly] for i in range(len(data)): # 逐位做模 2 除，商为 1 时异或 if bit[i] == "1": for j in range(len(poly)): bit[i + j] = str(int(bit[i + j]) ^ div[j]) return "".join(bit[-r:]) # 余数即校验码 data, poly = "1011001", "11001" code = crc(data, poly) print(code) # 1010 print(data + code) # 发送序列 10110011010

补零位数是这道题唯一的门槛。len(poly) - 1得到 4，等价于「多项式最高次幂」，因为最高次项系数一定是 1 且不含常数项以外的低次项省略问题。写成len(poly)就补了 5 个 0，余数会变成 5 位，整个校验码全错。接收端验算时，把收到的完整序列再除以同一个生成多项式，余数为 0 表示无错，这一步用同一段函数改一下入口就能复用。

还有一条：模 2 除法里的加法和减法都是异或，不产生进位和借位。手算时如果下意识按十进制借位，结果一定对不上。我见过有人在这一步反复检查公式，其实是运算规则用错了。

4.2 滑动窗口上限：SR 和 GBN 的两套口径

卷面问的是「选择重传 SR 协议中，采用 32 位帧序号，接收窗口最大为多少」。这道题的答案只有一行：序号空间是 2³²，SR 的发送窗口和接收窗口之和不能超过序号空间，且两者通常取等，所以接收窗口最大为 2³¹。这个结论背后是 SR 的核心约束——接收方要缓存失序到达的帧，如果窗口开得太大，新旧帧的序号会重叠，接收方无法分辨收到的是新帧还是重传的旧帧。

对比着记更牢：后退 N 帧 GBN 的发送窗口最大是 2ⁿ − 1，接收窗口固定为 1，因为 GBN 只按序接收。这两组数字在填空题里经常互换着考，判断依据是「接收方有没有缓存能力」。SR 有缓存，窗口对半分；GBN 没缓存，发送窗口比序号空间少一个。写错的原因基本都是把两套公式记混了，而不是不理解。

4.3 距离向量算法的一次迭代

卷面这道题给了三张表：节点 3 更新前的路由表、节点 3 收到的来自其他节点的距离向量、要求填写的更新后路由表。原卷扫描后那张 5×6 的矩阵被 OCR 糊成了乱码，没法直接引用，这里用一组自洽的距离向量复现同一次迭代的算法。节点 3 直连四个邻居 2、4、5、6，链路开销分别是 3、3、1、5，更新前的路由表和收到的向量如下：