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

1、计算机综合历年真题及模拟总结2009201020112012201320142015201641 结构最短路径10 描述所给算法正确性第5章图散列查找10 线性探测再散列第6章查找作图,邻接矩8 阵，关键路径第5章图二路归并 merge(),构造 哈夫曼或者最佳归并树第4/6/7章求顺序查找平 均查找长度第6章查找主要考察图的 链式存储结构Dijkstra 算法第5章图作图，邻接矩 阵，A2第5章无向图正则K叉树的页 节点及最大最小 节点总数计算第4章树42 结构链表15，第2章线性表考就地逆置13第2章线性表求中位数15 二路排序路间排序 第7章排序技术求公共存储链 接点第2章线性表求n/2

2、个数的 主元素第2章线性表计算二叉树WPL算法第4章树删除绝对值相 等的节点算法第2章线性表用快排思想设计|n1-n2| 最小 |S1-S2|第7章排序技术43计 组查询，中断，DMA效率问题8，第7章I/O单指令字长格式 寻址11第4章指令系统原补码转换，定点整 数加减，加法器概念11第2章数据Cache 低位交叉存储第3章存储系 统突发传送、交 叉存储第3章存储系 统指令及微程序 控制、流水线数 据相关第4章指令系统 /第5章中央处 理器数据通路结构 示意图第5章中央处 理器考察CPU时钟周 期数，中断第1章第7章 概述和输入输出44计 组微处理器指令执行过程13第5章中央处 理器直接映射

3、cache格 式容量计算及命中率12第3章存储系统直接映射虚，12物理 地址转换,TLB第3章存储系统指令流水线/ 数据左移第5章中央处理器/第2章数 据指令执行数据 通路第5章中央处理器/第4章指 令系统Cache容量及命 中率第3章存储管理指令格式，指 令控制信号分析10第4章指令系 统也是存储管理中 逻辑地址、物理 地址、TLB贞表、cache 格式考察第3章存储系统45写PV代码7CSCANB盘调度算写顾客营业员PV代属于新题型，写PV代码博文件实现中连写PV代码信基于优先级调度系 统第2章进程管 理法7第4章文件管理码8第2章进程管理即时理解第3章存储管 理物馆参观7第2章进程管 理

4、续及链式存储第4章文件系统箱辩论第2章进程管 理策略设计(主观) 第2章进程管理46 系 统请求分页求物 理地址及访问 时间8第3章存储管 理贝囿调度算法FIFO,CLOCI8 第3章存储管理考察文件系统FCB存 储位置概念7第4章文件管理文件索引实现第4章文件管 理虚拟也是存储管理第3章内存管 理PV操作写生产 者和消费者进 程第2章进程管理二级贝表第3章内存管 理显式链接分配第4章文件管理47划分网段和IPCSMA/CD传输时以太网数据帧IPV4以太网数据写出路由表，写出路由表计DHCP服务器TCP建立释放所网路由聚合技术间，有效数据传输数据报 ARPNAIHIIP帧，IP数据包路由聚合/

5、路算 TTL9分配IP地址需时间，拥塞窗络9，速率计算99，分组段头TCP段头3次握手代码由区域自治系 统交换协议路田！口、平均数据传 输速率41题第4章网络层4.3.5第3章数据链路层第3章数据链路层3.6.2第4章网络层4.3.4ARP/DHCP/ICMPP150第6章应用层6.5万维网P261实现分析第4章网络层第5章传输层第4章网络层第4章网络层第4章网络层4.3.5第5章传输层10 月 30:(1)根据3次模拟3次真题来看综合大题方面在算法实现上和操作系统的PV操作不是太熟，需要多练；选择题方面平衡二叉树，折半查找平均查找长度，堆排序查找插入/删除/建立比较次数及交换次数重点复习。4

6、1题中主要考察图的算法，以及查找排序的推演过程，注意平均查找长度等计算(散列查找/折半查找)，集中在第5, 6, 7章，模拟前最好都巩固下流程，不能丢分。42算法大题，这题暂时来说还是颇具难度，不过一般都是考察队列及链表，树的遍历也有类似考到，后期要加强这方面的练习。43题中主要是考察计组当中一些必要计算，如第2章浮点数/定点数加减法，DMA执行效率(5)44题计组题中考察计算机微指令执行过程 是难点，需要攻克，尽量拿分；如果考到 存储器/cache等题的要求满分。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指令流水线技术，涉及计算

8、，以及重点”数据相关”，设计汇编指令，并编写流水线中执行过程。(3)计算机网络1/重点复习mac帧/ip数据包分组报头各字段含义 /tcp段头各字段含义/11月6日：(2013年真题小结)数据结构：(1)选择题部分有五道题都考得是第四章树的内容，其余部分，时间复杂度、栈、图、关键路径及排序略有涉及1到两题。(2)大题方面算法题没什么说的，多练，还有一点就是不要去追求最优解，性价比较低。另外一道都喜欢考相关算法的ASL成功或者失败的，有点难搞，曾经考过的有散列查找、二分查找，顺序查找，二叉排序树。计算机组成原理：(1)今年大题很难，感觉，以前貌似做过的，现在重新做又像新的一样。账户要是考存储系统

9、中的突发传送机制及 交叉存储，TMD交叉存储过程现在不懂了，需要彳f细看。还有 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 (未

10、命中)*未命中百分比，而涉及到的13年43题中CPU执行时间是cache命中时的指令执行时间 +cache缺失时带来的额外开销 ，记得要区分开。12月1日：(1)在散列函数构造和及计算成功的平均查找长度和失败的平均查找长度时候还有不少问题，希望在最后复习的时候要再练习下这类题目，专科书 P26012月4日：(1)操作系统部分文件实现部分是超级大重点，必须熟悉各实现方法，如连续分配、链接分配(隐式和显示)、索引；以及位图等。12月13日:(1)所有的真题都已经做完了，16年的题跟14、15年的差别还是挺大的增加很多主观题和新题型，如计算机网络不怎么按常理出牌，而且考察的东西更细了。41题第3、4问答案都没怎么看懂。(2)数据结构中：算法题破天荒考了快排，让我感受到考察的内容年年都在变，而且根本琢磨不到下次它会考什么。(3)计算机组成原理方面：44题和45题考察的内容很基础，就是题目较新颖，需要分析，可能这是下一年的趋势。所以考试的时候考到这种题还是要着重题意分析，找出本质，时常都在说不能慌，但有几次能做到呢？希望考场上能做到。这次暴露的问题还是关于cache、TLB页表的关系不太熟。首先访问顺序是TLBL般是寄存器)-页表-C