本书是计算机专业研究生入学考试真题分析用书,首先给出2010年至2014全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题,然后按数据结构篇、计算机组成原理篇、操作系统篇、计算机网络篇对题进行分析。全书严格按照*新计算机考研大纲,对大纲所涉及的知识点进行集中梳理,给出详细的解题思路,力求达到讲练结合、灵活掌握、举一反三的功效。同时,创新的“书本+在线”的学习方式与网上答疑,可大大提高考生的复习效果,达到事半功倍的复习效率。 2015年计算机专业基础综合考试真题思路分析_电子工业出版社_电子工业出版社_

目 录
2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 1
2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 13
2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 25
2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 37
2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 49
2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 61
真题思路分析——数据结构部分
第1章 绪论 76
真题分布及命题** 76
考点1:时间复杂度与空间复杂度 76
第2章 线性表 79
真题分布及命题** 79
考点2:线性表的顺序表示 79
考点3:线性表的链式表示 82
第3章 栈和队列 87
真题分布及命题** 87
考点4:栈和队列的基本性质 87
考点5:栈和队列的存储结构 89
考点6:双端队列 90
考点7:栈与队列的应用 91
考点8:特殊矩阵的压缩存储 94
第4章 树与二叉树 97
真题分布及命题** 97
考点9:树的基本性质 97
考点10:二叉树的定义与性质 98
考点11:二叉树的遍历 99
考点12:二叉排序树 103
考点13:平衡二叉树 106
考点14:树、森林与二叉树的转换 109
考点15:线索二叉树的基本概念和构造 111
考点16:哈夫曼树与哈夫曼编码 112
第5章 图 115
真题分布及命题** 115
考点17:图的基本概念 115
考点18:图的存储及基本操作 117
考点19:图的遍历 121
考点20:*小(代价)生成树 122
考点21:*短路径 124
考点22:拓扑排序 126
考点23:关键路径 127
第6章 查找 131
真题分布及命题** 131
考点24:顺序查找法&折半查找法 131
考点25:B树及其基本操作、B+树的基本概念 134
考点26:散列(Hash)表 138
第7章 排序 140
真题分布及命题** 140
考点27:插入排序 140
考点28:交换排序 142
考点29:选择排序 144
考点30:二路归并排序 146
考点31:基数排序 148
考点32:各种内部排序方法的比较 149
考点33:外部排序的思想 149
真题思路分析——计算机组成原理部分
第1章 计算机系统概论 152
真题分布及命题** 152
考点34:计算机系统层次结构 152
考点35:计算机的性能指标 153
第2章 数据的表示和运算 155
真题分布及命题** 155
考点36:海明码 155
考点37:数据的存储方式 156
考点38:定点数的表示与运算 158
考点39:IEEE754标准 162
考点40:各种精度数据的转换 164
考点41:浮点数运算 165
第3章 存储系统的层次结构 167
真题分布及命题** 167
考点42:半导体随机存取存储器 167
考点43:主存储器与CPU的连接 169
考点44:低位交叉存储器 170
考点45:高速缓冲存储器(Cache) 171
考点46:虚拟存储器 175
第4章 指令系统 180
真题分布及命题** 180
考点47:指令格式 180
考点48:指令的寻址方式 182
考点49:CISC与RISC 186
第5章 **处理器 188
真题分布及命题** 188
考点50:CPU的功能和基本结构 188
考点51:指令执行过程 189
考点52:数据通路的功能和基本结构 190
考点53:控制器的功能和工作原理 192
考点54:指令流水线 194
第6章 总线 199
真题分布及命题** 199
考点55:总线分类 199
考点56:总线的性能指标 200
考点57:总线标准 201
第7章 输入/输出系统 203
真题分布及命题** 203
考点58:外部设备 203
考点59:磁盘与RAID 204
考点60:I/O接口 205
考点61:程序查询方式 206
考点62:程序中断方式 206
考点63:DMA方式 209
真题思路分析——操作系统部分
第1章 操作系统概述 213
真题分布及命题** 213
考点64:操作系统的概念、特征和功能 213
考点65:内核态与用户态 214
考点66:中断、异常 215
考点67:系统调用 215
第2章 进程管理 217
真题分布及命题** 217
考点68:进程与线程 217
考点69:进程状态与进程控制 218
考点70:处理机调度 219
考点71:进程同步与互斥 223
考点72:经典同步问题 226
考点73:死锁 230
第3章 内存管理 233
真题分布及命题** 233
考点74:内存管理的概念 233
考点75:连续分配管理方式 235
考点76:非连续分配管理方式 236
考点77:虚拟页式存储管理 239
考点78:抖动 246
第4章 文件管理 247
真题分布及命题** 247
考点79:目录结构 247
考点80:文件共享和文件保护 248
考点81:文件的操作 249
考点82:文件实现 250
考点83:磁盘组织与管理 253
第5章 设备管理 256
真题分布及命题** 256
考点84:I/O控制方式 256
考点85:I/O软件的层次结构 256
考点86:I/O调度与缓冲区 258
考点87:设备分配与回收 259
真题思路分析——计算机网络部分
第1章 计算机网络体系结构 261
真题分布及命题** 261
考点88:计算机网络的分层结构 261
考点89:ISO/OSI参考模型和TCP/IP模型 262
第2章 物理层 264
真题分布及命题** 264
考点90:以太网与曼彻斯特编码 264
考点91:奈奎斯特定理和香农定理 265
考点92:电路交换、报文交换与分组交换 266
考点93:物理层接口和物理层设备 267
第3章 数据链路层 268
真题分布及命题** 268
考点94:零比特填充法 268
考点95:流量控制、可靠传输与滑动窗口机制 269
考点96:随机访问介质访问控制 271
考点97:局域网 274
考点98:以太网交换机及其工作原理 275
第4章 网络层 277
真题分布及命题** 277
考点99:IP数据报 277
考点100:子网划分与子网掩码、CIDR 280
考点101:ARP协议与ICMP协议 286
考点102:路由协议 287
考点103:网络层设备 288
第5章 传输层 290
真题分布及命题** 290
考点104:TCP段的分析 290
考点105:TCP连接管理 293
考点106:TCP可靠传输 294
考点107:TCP流量控制与拥塞控制 295
考点108:UDP协议 297
第6章 应用层 298
真题分析及命题** 298
考点109:域名系统DNS 298
考点110:文件传送协议FTP 299
考点111:电子邮件EMAIL 299
考点112:万维网WWW 300
参考文献 303

序 言
当前,随着我国经济和科技高速发展,特别是计算机科学突飞猛进的发展,对计算机相关人才,尤其是中高端人才的需求也将不断增长。硕士研究生入学考试可视为人生的第二次大考试,它是改变命运、实现自我理想的又一次机会,而计算机专业一直是高校考研的热门专业之一。
自计算机专业研究生入学考试实行统一命题以来,初试科目包含了*重要的四门基础课程(数据结构、计算机组成原理、操作系统、计算机网络),很多学生普遍反映找不到方向,复习也无从下手。倘若有一本能够指导考生如何复习的好书,必将对考生的帮助匪浅。我的学生风华他们策划和编写了这一系列的计算机专业考研辅导书,**突出,层次分明。他们结合了自身的复习经验、理解深度以及对大纲把握程度的体会,对考生而言是很有启发和指导意义的。
计算机这门学科,任何机械式的死记硬背都是收效甚微的。在全面深入复习之后,首先对诸多知识点分清主次,并结合做题,灵活运用所掌握的知识点,再选择一些高质量的模拟试题来检测自己理解和掌握的程度,查漏补缺。这符合我执教40余年来一直坚持“教材—习题集—试题库”的教学体系。
从风华他们策划并组建编写团队到初稿成形,直至*后定稿,我能体会到风华和他的团队确实倾注了大量的精力。这套书的出版一定会受到广大考研学生的欢迎,它会使你在考研的路上得到强有力的帮助。
前 言
*后50天,拼的是心态与意志!
你的身边会陆续有一些意志不太坚定的同学放弃自己的梦想,他们的言行或许会影响到你的心情与心态。但我相信,一路用心坚持到*后的人,一定会收获属于自己的那份回报。成功并非遥不可及,坚定自己的梦想,做*好的自己!
对于任何一门考试,真题永远都是*宝贵的资源,研究生入学考试更是如此。真题不仅仅需要实战模拟,更需要方方面面地吃透、再吃透。而由真题引申出的周边核心考点,也一定要牢固掌握,以前考过的知识点极有可能再次涉及,重要的考点往往容易反复出现。《2015年计算机专业基础综合考试真题思路分析》就是一本帮助你实现这样目的的一本书!
我们在认真、细致剖析2009—2014年计算机统考真题的基础上,对真题所涉及的核心知识点进行了详尽分析,并在总结统考命题规律的基础上,针对命题规律编写了高质量的模拟题(即《王道2015年计算机专业基础综合考试*后8套模拟题》),这样的规律可以指明考生在*后阶段的复习方向。也正是基于我们对命题规律的把握,王道论坛组编的*后8套模拟题,不仅连续命中2012—2013年算法设计题,更是点中多道选择题和综合题的核心考点与相关思路。
在考研前的*后30天,同学们一定要抓住专业课复习的四大**:①回顾以前复习中标注的**和难点,毕竟知识都是容易遗忘的;②查漏补缺,特别是之前做错的题目,这是为了以后遇到类似的题不再出错;③仔细分析历年真题,真题涉及的知识点一定是核心考点;④做几套高质量的模拟题。
我们都是CS的“屌丝”,唯有自强不息,才能实现“屌丝”的梦想!
祝福每一个有梦的“屌丝”!
风华漫舞
致读者
——王道单科使用方法的道友建议
我是二战考生,2012年**次考研成绩333分(专业代码:408,成绩81分),痛定思痛后决心再战。潜心复习了半年后终于以392分(专业代码:408,成绩124分)考入上海交通大学计算机系,这半年里我的专业课成绩提高了43分,成了提分主力。从不达线到比较满意的成绩;从闷头乱撞到有了自己明确的复习思路,我想这也是为什么风华哥从诸多高分选手中选我给大家介绍经验的一个原因吧。
整个专业课的复习是围绕王道材料展开的,从一遍、两遍、三遍看单科书的积累提升,到做8套模拟题时的强化巩固,再到看思路分析时的醍醐灌顶。王道书能两次押中原题固然有运气成分,但这也从侧面说明他们的编写思路和选题方向与真题很接近。
下面说说我的具体复习过程:
每天划给专业课的时间是3~4小时。**遍细看课本,看完一章做一章单科书(红笔标注错题),这一遍共持续2个月。第二遍主攻单科书(红笔标注重难点),辅看课本。第二遍看单科书和课本的速度快了很多,但感觉收获更多,常有温故知新的感觉,理解更深刻(风华注,建议这里再速看第三遍,特别针对错题和重难点。模拟题完后再跳看第四遍)。
以上是打基础阶段,注意单科书和课本我仔细精读了两遍,弄懂每个知识点和习题。大概11月上旬开始做模拟题和思路分析,期间遇到不熟悉的地方不断回头查阅单科书和课本。8套模拟题的考点覆盖得很全面,所以大家做题时如果忘记了某个知识点,���万不要慌张,赶紧回去看这个知识盲点,*后的模拟就是查漏补缺。模拟题一定要严格按考试时间去做(14:00~17:00),注意应试技巧,做完试题后再回头研究错题。算法题的*优解法不太好想,如果实在没思路,建议直接“暴力”解决,结果正确也能有10分,总比苦拼出15分来而将后面比较好拿分的题耽误了好(这是我**年的切身教训!)。*后剩了几天看标注的错题,第三遍跳看单科书,考前一夜浏览完网络,踏实地睡着了……
考完专业课,走出考场终于长舒一口气,考试情况也胸中有数。回想这半年的复习,耐住了寂寞和诱惑,雨雪风霜从未间断跑去自习,考研这一人生一站终归没有辜负我的用心良苦。佛教徒说世间万物生来平等,都要落入春华秋实的代谢中去,辩证唯物主义认为事物作为过程存在,凡是存在的终归要结束,你不去为活得多姿多彩拼搏,真到了和青春说再见时你是否会可惜虚枉了青春?风华哥说过我们都是有梦的“屌丝”,我们正在逆袭,你呢?
感谢风华大哥的信任,给我这个机会分享专业课复习经验给大家,作为一个铁杆道友在王道受益匪浅,也借此机会回报王道论坛。祝大家金榜题名!
ccg1990@SJTU
王道程序员训练营
经常有人问我们:“为什么不做考研培训?这个市场很大”?
这里,算作一个简短的回答吧。王道尊重的不是考研这个行当,而是考研学生的精神,他们的梦想,仅此而已。考研可能是部分CS学生实现梦想的阶段,但考研学习的内容,对CSer的职业生涯毕竟没有太多的帮助和意义。对于计算机专业的学生,编程基本功和学习能力才是受用终生的资本,决定了未来在技术道路上能走多远。
而王道团队也只会专注于计算机这个领域,往其纵深发展,从名校考研、到高端编程培训、再到求职**。从2008年初创办至今,王道创始团队,经历了从本科到考研成功,从硕士到社会历练,积累了不少经验和社会资源,但也走过不少弯路。
计算机是一个靠能力吃饭的专业。和很多现在的你们一样,当年的我们也经历过本科时的迷茫,而无非是自觉能力太弱,以致底气不足。学历只是敲门砖,同样是名校硕士,有人走上正确的方向,如鱼得水,成为Offer帝;有人却始终难入“编程与算法之门”,始终与好Offer无缘,再一次体会就业之痛,*后只能“将就”签约。即便是名校硕士,Offer也有8万、15万、20万、25万……三六九等。考研高分≠Offer高薪,我们更欣赏技术上的牛人。
考研结束后的日子,或许是一段难得的提升编程能力的完整时光,趁着还有时间,也该去弥补本科期间应掌握的能力,也是追赶与那些大牛们的差距的时候了。
你将从王道集训营获得
编程能力的迅速提升,结合项目实战,逐步帮你打下坚实的编程基础。动手编程为驱动的教学模式,解决你在编程、算法思维上的不足。也是为未来的深入学习提供方向指导,掌握编程的学习方法,引导进入高端的“编程与算法之门”。
一系列的模拟面试,帮你认识到自身的不足,增强实战经验,并给予专业的建议,让你提前感受名企的面试法则,为你在日后参加名企面试时,能更从容。
道友们在集训营里从菜鸟逐步成长,第二期研究生班目前已有不少道友陆续拿到百度、腾讯、阿里、搜狗等一线互联网公司的实习Offer。这就是竞争力!
……
王道集训营的优势
这里都是王道道友,他们信任王道,乐于分享与交流。
因为都是忠实的王道道友,都曾经历过考研……集训营的住宿、生活都在一起,其乐融融,很快大家也将成为互帮互助的好朋友、好同学。
本科+硕士的生源。考研绝非人生**的出路,给自己换一条路走,去职场上好好发展或许会更好。考上研究生也并不意味着高枕无忧,人生的道路还很漫长。
王道团队皆具有扎实的编程基本功和算法能力,兼职成员更具有多年的名企工作经验,他们用自己的态度、自己的思维去影响集训营的道友,全天候一对一指导大家学习编程、调试,并随时解答大家的疑问……是对道友信任的回报,也是一种责任!
王道集训营只是一个平台,网罗王道论坛上有梦想、有态度的CS屌丝。并为他们的梦想提供土壤和圈子。始终相信那句“物竞天择 适者生存”,这里的生存并不是简简单单的活下来,而是活得有价值、活得有态度!
王道集训营的参与条件
1.面向就业
面临就业,但编程能力偏弱的计算机相关专业学生。
大学酱油模式渡过,投简历如石沉大海,好不容易有次面试机会,又由于基础薄弱、编程太少,以至于面试时有口无言,面试结果可想而知。开始偿债吧,再不抓住当下,未来或将持续迷茫,逝去了的青春是无法复返的,这个世界上后悔药是确定没有的。
眼光和视野放长远一点吧,在这个充分竞争的技术领域,当前的能力决定了你能找一份怎样的工作,踏实的态度和学习的能力决定了你未来能走多远。
2.面向硕士
提升能力,刚考上计算机相关专业的准研究生或在读研究生。
名校研究生已没有什么可以值得骄傲的资本,我们身边所看到的都是名校硕士。同为名校,为什么有人能轻松拿到百度、腾讯、阿里、MS等Offer,年薪15~30万元,发展前景甚好;有人却只能拿6~10万元年薪的Offer,在房价/物价高企的年代,这点收入就等着月光吧。家中父母可能因有名校研究生的孩子而骄傲,可不知孩子其实在外面过得很辛苦。
哪些人不适合来王道集训营?
1.性格轻浮、不踏实,说多做少。或许程序员并不太适合你。
2.依赖思想太强,总是期待老师灌输更多的知识,自己不愿钻研,不愿去解决问题,或者不愿学习解决问题的方法。程序员式的学习方式终生受用。
3.眼光狭窄,心胸狭