2012 年 408 统考第 41~47 题

2012 年 408 统考第 41~47 题第 41 题数据结构最优合并模式哈夫曼树考察知识点哈夫曼树最优二叉树的构造算法每次选取权值最小的两个结点合并。带权路径长度WPL的计算及其物理意义。二路归并排序中比较次数的计算。知识点详解合并 N 个有序表等价于构建一棵二叉树叶子结点为初始表权值为表长。总比较次数 所有内部结点权值之和 WPL。归并两个长度分别为 a 和 b 的有序表最坏比较次数为a b - 1双指针法每次取一个最小元素直到只剩最后一个元素无需比较。本题中的“坑”致命坑把“有序表归并”当成“无序表的两两比较”算出a*b如 10×35350。记住有序归并不是嵌套循环而是线性扫描。概念坑误以为“长的全部比短的小”是最坏情况其实这恰恰是最好情况只需比较短表长度次。最坏是两表元素交替穿插。表述坑第2问写“局部最优推全局最优”会被扣分。必须点出“WPL”和“哈夫曼算法性质”才能证明是全局最优。第 42 题数据结构链表找共同后缀相交结点考察知识点单链表的基本操作与指针遍历。时间复杂度优化O(nm) 的“对齐尾部”算法。物理地址共享的判断条件指针相等而非数据相等。知识点详解两条链表若共享后缀则从某一结点开始后续所有结点地址完全相同。最优解法先数两条链表的长度让长链表指针先走差值步对齐尾部然后两指针同步后移第一次p q即为答案。本题中的“坑”效率坑题目要求“时间上尽可能高效”暴力双重循环O(n*m)会被扣掉 60%~70% 的分数绝不是“一半分”。判断坑必须比较指针地址p q不能比较数据值p-data q-data因为可能存在两个不同结点存着相同字母。带头结点坑遍历计数和移动时记得从head-next开始跳过无效的头结点。第 43 题计算机组成原理性能计算与存储体系Cache 虚拟内存 DMA考察知识点CPU性能公式MIPS 主频 / CPI。Cache 缺失率与主存带宽的计算。虚拟内存缺页异常的计算。DMA直接存储器存取的工作方式与优先级。低位交叉存储器的带宽计算。知识点详解存储层次CPU → Cache块传输→ 主存页传输→ 磁盘。缺页一定伴随着 Cache 缺失但 Cache 缺失不一定缺页。DMA优先级DMA 优先级高于 CPU因为 DMA 多用于高速 I/O若响应不及时数据缓冲寄存器会溢出导致数据丢失。低位交叉编址带宽若 m 体交叉每 (1/m) 个存储周期启动一个体。在一个完整的存储周期内m 个体会并行完成数据传输。本题中的“坑”单位坑主存总线宽度 32 位 4 字节不是 4 位。DMA 缓冲寄存器 32 位也是 4B计算 DMA 请求次数时注意除 4。带宽计算坑四体交叉中50ns 内传输的是4 × 4B 16B并行而不是串行传输 4 次。算出来是 320MB/s很容易算成 80MB/s。缺页率基数坑缺页次数是基于Cache 缺失次数计算的而不是基于 CPU 的访存总次数。即300,000 × 0.0005%不要直接用30M去乘。第 44 题计算机组成原理指令流水线5 段流水考察知识点5 段流水线IF, ID, EX, M, WB的基本时空图。数据相关写后读 RAW与阻塞Stall。无转发技术时的阻塞条件。按序发射、按序完成的含义。算术移位算术右移保留符号位。知识点详解无转发无旁路后续指令的 ID 段读寄存器必须等待前序指令的 WB 段写寄存器完成否则必须阻塞。按序发射与完成若前一条指令因数据相关阻塞后一条指令即使在 IF 段已取指完成也只能停在 ID 段前等待IF 段被阻塞。本题中的“坑”移位坑-513 补码FDFF算术右移时最高位补 1结果应为FEFF。很多同学会填7EFF当成逻辑右移。阻塞识别坑I3的 ID 段被阻塞是因为要等I1和I2的 WB而I4的 IF 段被阻塞是因为前一条I3卡住了流水线排队不是因为I4自身依赖谁。时空图画坑画带阻塞的时空图时阻塞的段用空档表示气泡指令的后续段EX/M/WB要整体右移。第4问的 17 个周期非常容易数漏。第 45 题操作系统页面置换策略自定义扫描回收策略考察知识点请求分页系统中的驻留集与空闲页框链表管理。自定义页面回收机制定时扫描按访问位回收。缺页处理页面“复活”曾在空闲链表直接取回 vs 全新分配。时间局部性的应用分析。知识点详解该策略像一种“老化算法”的变体每 5 个时间单位清除一次未被访问的页。关键特性回收的页框内容不清空数据还在若该页短时间内又被访问直接从空闲链表“捞回来”即可无需重新从磁盘读入。本题中的“坑”时间线坑最核心访问⟨2, 14⟩发生在t14而第三轮扫描在t15。此时第三轮扫描还未发生所以驻留集里的1和0还没有被回收。很多人误以为扫描先发生从空闲链表头部取走了15但正确答案是从头部取走41。链表顺序坑被回收的页框是插入链表尾部链尾分配时从链表头部链头取。需要严格模拟链表变化否则顺序会乱。“曾被使用过”坑虚拟页 2 从未出现过所以既不在驻留集也不在空闲链表只能走“从头部取新页框”的逻辑。第 46 题操作系统文件系统索引结构混合索引考察知识点磁盘寻址块号占用的字节数计算由总块数决定。直接索引结构下的文件最大长度。混合索引连续区 直接索引下的长度计算。索引表字段位宽的最优分配系统设计优化。知识点详解块号占 n 字节能寻址2^(8n)个块。连续存储区大小 块数最大值 × 块大小。优化本质是“木桶效应”在索引表区固定大小下为了最大化文件长度需要让“起始块号”和“块数”的表示范围都足够大不能浪费位数。本题中的“坑”单位进制坑4TB 2^42 B1KB 2^10 B总块数 2^32。块号最少要4 字节不是 5 字节因为 2^32 刚好够。混合计算坑连续区64MB 直接区84KB最终结果要统一单位65620 KB。字段分配坑原题给的是起始块号占 6B, 块数占 2B问如何优化。起始块号只需 4B 就能寻址全盘多余 2B 纯属浪费。把起始块号缩为 4B块数扩为 4B 即可实现最大容量4TB。注意不能为了省空间把起始块号缩成 2B那样就寻址不完整了。第 47 题计算机网络IP 分组与 TCP 协议解析十六进制转储考察知识点IP 分组头部格式首部长度、总长度、标识、TTL、源/目的 IP。TCP 头部格式源/目的端口、序号、确认号、标志位 SYN/ACK。TCP 三次握手的报文特征。以太网帧最小长度有效载荷至少 46 字节与填充规则。TTL 与路由器跳数的关系。知识点详解判断分组方向看源 IP判断三次握手看 TCP 标志位SYN1, ACK0/1。以太网有效载荷小于 46B 时链路层自动填充 0该填充不影响 IP 层数据。TTL 每经过一个路由器减 1路由跳数 发出 TTL - 到达 TTL。本题中的“坑”字节序坑大小端IP 头中的数字字段如总长度00 30是大端网络序即0x0030 48不是0x3000。填充判定坑判断填充看 IP 头的“总长度”字段IP 头本身 TCP 头 数据而不是看 TCP 数据段长度。总长度 46 就需要填充。确认号计算坑5 号分组的确认号84 6b 41 d6减去 3 号分组的序号84 6b 41 c6得到0x10 16。注意这里的“减”是大端十六进制减法不要算错。路由器数坑问“经过了多少个路由器”TTL 减少了0x40 - 0x31 0xF 15因为初始 TTL 发出时是 64到达时是 49结果是 15。注意有些同学会算成 16把目标主机也算进去了。