计算机408综合2009-2016年历年真题大题分析及做题笔记

计算机综合历年真题及模拟总结

41 结构 2009 最短路径10’ 描述所给算法正确性 第5章图 42 结构 43 计组 链表15’ 第2章线性表 查询，中断，DMA效率问题8’ 第7章 I/O 2010 散列查找10’ 线性探测再散列 第6章查找 考就地逆置13’ 第2章线性表 单指令字长格式 寻址11’ 第4章指令系统 2011 作图,邻接矩8’ 阵,关键路径 第5章图 求中位数15’ 二路排序路间排序 第7章排序技术 原补码转换,定点整数加减,加法器概念11’ 第2章数据 2012 二路归并merge(),构造哈夫曼或者最佳归并树 第4/6/7章 2013 求顺序查找平均查找长度 第6章查找 2014 主要考察图的链式存储结构 Dijkstra算法 第5章图 2015 作图，邻接矩阵，A2 2016 正则K叉树的页节点及最大最小节点总数计算 第4章树 用快排思想设计|n1-n2|最小|S1-S2|最大 第7章排序技术 考察CPU时钟周期数，中断 第1章第7章 概述和输入输出 也是存储管理中逻辑地址、物理地址、TLB、页表、cache格式统一考察 第3章存储系统 基于优先级调度第5章无向图 删除绝对值相等的节点算法 第2章线性表 数据通路结构示意图 第5章中央处理器 求公共存储链求>n/2个数的计算二叉树接点 主元素 WPL算法 第2章线性表 第2章线性表 第4章树 突发传送、交低位交叉存储 叉存储 第3章存储系第3章存储系统 统 指令流水线/数据左移 第5章中央处理器/第2章数据 属于新题型，指令执行数据通路 第5章中央处理器/第4章指令系统 写PV代码博Cache 指令及微程序控制、流水线数据相关 第4章指令系统/第5章中央处理器 44 计组 微处理器指令执行过程13’ 第5章中央处理器 写PV代码7’ 直接映射cache格式容量计算及命中率12’ 第3章存储系统 CSCAN磁盘调度算直接映射虚, 12’物理地址转换,TLB 第3章存储系统 Cache容量及命指令格式，指中率 令控制信号分 析10’ 第3章存储管理 第4章指令系统 文件实现中连写PV代码信45 写顾客营业员PV代系统 第2章进程管理 法7’ 第4章文件管理 页面调度算法 FIFO,CLOCK 8‘ 第3章存储管理 码 8’ 第2章进程管理 考察文件系统FCB存储位置概念7’ 第4章文件管理 即时理解 第3章存储管理 文件索引实现 第4章文件管理 物馆参观7’ 第2章进程管理 虚拟也是存储管理 第3章内存管理 写出路由表，路由聚合/路由区域自治系统交换协议 第4章网络层 续及链式存储 箱辩论 策略设计（主观） 第2章进程管理 第4章文件系统 第2章进程管理 PV操作写生产二级页表 者和消费者进 程 第3章内存管第2章进程管理 理 写出路由表计算TTL9’ 第4章网络层 DHCP服务器分配IP地址 路由表 第4章网络层 4.3.5 显式链接分配 第4章文件管理 TCP建立释放所需时间，拥塞窗口、平均数据传输速率41题 第5章传输层 46 系统 请求分页求物理地址及访问时间8’ 第3章存储管理 47 网络 划分网段和IP CSMA/CD 传输时以太网数据帧IPV4以太网数据路由聚合技术间，有效数据传输数据报ARP,NATHTTP 帧，IP数据包9’ 9’ 速率计算9’ 分组段头 TCP段头 3次握手代码第4章网络层 第3章数据链路层 第3章数据链路层实现分析 4.3.5 3.6.2 第4章网络层第4章网络层 4.3.4ARP/DHCP/ICMP 第5章传输层 P150 第6章应用层 6.5 万维网P261 10月30：

(1)根据3次模拟3次真题来看综合大题方面在算法实现上和操作系统的PV操作不是太熟，需要多练；选择题方面平衡二叉树，折半查找平均查找长度，堆排序查找插入/删除/建立比较次数及交换次数重点复习。

(2) 41题中主要考察图的算法，以及查找排序的推演过程，注意平均查找长度等计算（散列查找/折半查找），集中在第5，6，7章，模拟前最好都巩固下流程，不能丢分。 (3) 42算法大题，这题暂时来说还是颇具难度，不过一般都是考察队列及链表，树的遍历也有类似考到，后期要加强这方面的练习。 (4) 43题中主要是考察计组当中一些必要计算，如第2章浮点数/定点数加减法，DMA执行效率 (5)44题计组题中考察计算机微指令执行过程是难点，需要攻克，尽量拿分；如果考到存储器/cache等题的要求满分。 (6) 45-46题系统题考PV操作是重难点，需要多练，也是尽量拿分；若考到页面调度算法或者磁盘调度算法要求满分；若考到文件系统题（难点：文件分配方式）也是尽量拿分，因为概念太多了，不保证能记住。 (7) 47题主要是是第4章，注意网段划分/画路由表/以太网数据帧ipv4格式/网络体系机构各层协议/CSMA/CD/TCP拥塞窗口。

10月31日：

(1)计算题中，第四章指令系统中计算变长指令个数的题(如计算一级/二级或者多级指令个数) (2)操作系统中计算磁盘密度，磁道数及容量等。

2012年真题 11月3日： （1）计组 1/熟悉 SHL R1指令，低位交叉存储，DMA周期挪用概念。 11月4日: (1)操作系统 1/TH46文件管理中”文件实现“(考点82)索引计算。涉及直接块，一级索引，二级索引，三级索引。 (2)计组 1/TH44指令流水线技术，涉及计算，以及重点”数据相关”，设计汇编指令，并编写流水线中执行过程。 (3)计算机网络 1/重点复习mac帧/ip数据包分组报头各字段含义/tcp段头各字段含义/ 11月6日：（2013年真题小结） 数据结构：

（1）选择题部分有五道题都考得是第四章树的内容，其余部分，时间复杂度、栈、图、关键路径及排序略有涉及1到两题。 （2）大题方面算法题没什么说的，多练，还有一点就是不要去追求最优解，性价比较低。另外一道都喜欢考相关算法的ASL成功或者失败的，有点难搞，曾经考过的有散列查找、二分查找，顺序查找，二叉排序树。 计算机组成原理： （1）今年大题很难，感觉，以前貌似做过的，现在重新做又像新的一样。账户要是考存储系统中的突发传送机制及交叉存储，TMD交叉存储过程现在不懂了，需要仔细看。还有CPU执行时间概念 （2）指令数据通路示意图要看，过程要熟悉，基本上遇到就懵逼。 操作系统： （1）根据位数算多少KB内存有些细节问题要注意。 计算机网络： （1）路由汇聚，（最长匹配原则）各层次结构协议尽量熟悉。

11月12日： （1）常考点，操作系统：PV操作；计算机网络：IP路由；IP分组格式如总长度（单位B）、首部长度（单位4B）、标志（占3位，0 MF DF）、片偏移（单位8B）；

11月22日： （1）操作系统中cache命中和未命中或者TLB命中和未命中的有效存取时间是T（命中）*命中百分比 + T（未命中）*未命中百分比，而涉及到的13年43题中CPU执行时间是cache命中时的指令执行时间+cache缺失时带来的额外开销，记得要区分开。

12月1日：

（1）在散列函数构造和及计算成功的平均查找长度和失败的平均查找长度时候还有不少问题，希望在最后复习的时候要再练习下这类题目，专科书P260 12月4日：

（1）操作系统部分文件实现部分是超级大重点，必须熟悉各实现方法，如连续分配、链接分配（隐式和显示）、索引；以及位图等。

12月13日：

（1）所有的真题都已经做完了，16年的题跟14、15年的差别还是挺大的增加很多主观题和新题型，如计算机网络不怎么按常理出牌，而且考察的东西更细了。41题第3、4问答案都没怎么看懂。

（2）数据结构中：算法题破天荒考了快排，让我感受到考察的内容年年都在变，而且根本琢磨不到下次它会考什么。

（3）计算机组成原理方面：44题和45题考察的内容很基础，就是题目较新颖，需要分析，可能这是下一年的趋势。所以考试的时候考到这种题还是要着重题意分析，找出本质，时常都在说不能慌，但有几次能做到呢？希望考场上能做到。这次暴露的问题还是关于cache、TLB、页表的关系不太熟。首先访问顺序是TLB(一般是寄存器)->页表->Cache->主存，还有逻辑地址和物理地址的位置关系，很重要。

（4）操作系统方面46题居然考操作系统基于优先级调度策略的主观题，还要设计算法，感觉不能应付！ 47题考的东西就更偏了，直接都不懂题目，无从下手。

（5）总结经验就是要留足20分钟检查下选择题，很重要，只有有点疑问的画出来不要填答案先，方便后续检查，先填答案会对后续检查产生干扰。