本书汇集了2009~2013年的全国硕士研究生入学计算机专业课统考试题(编号408)。首先,编者不但对所有试题均给出了详细解答,而且对部分试题做到了一题多解,部分试题的解法甚至比标准答案的解法更简捷、更省时省力。其次,编者仍然沿用高分笔记系列书籍的特色,从心理学角度出发,为考生指出了一些可能的错误解法,并点评错因,提醒考生引以为鉴。*后,针对每道真题中涉及的大纲知识点都进行了详细的归纳总结,强化了考生对考题中经常出现的知识点的理解。

前言
第1篇 数据结构
第1章 绪 论 1
1.1 数据结构的基本概念未考 1
1.2 算法及其分析[2,0] 1
1.3 递归算法设计未考 2
第2章 线性表 3
2.1 线性表的定义未考 3
2.2 顺序表[0,2] 3
2.3 单链表[1,2] 6
2.4 双链表未考 11
2.5 循环链表未考 11
2.6 有序表[0,1] 11
第3章 栈、队列和数组 15
3.1 栈[5,0] 15
3.2 队列[3,0] 19
3.3 数组和稀疏矩阵未考 21
第4章 树与二叉树 22
4.1 树的概念[1,0] 22
4.2 二叉树的概念[2,0] 22
4.3 二叉树的遍历[1,0] 23
4.4 二叉树的构造[2,0] 24
4.5 树和二叉树的相互转换[2,0] 25
4.6 线索二叉树[2,0] 26
4.7 二叉排序树[2,0] 27
4.8 平衡二叉树[4,0] 28
4.9 赫夫曼树[2,0] 31
第5章 图 34
5.1 图的基本概念[2,0] 34
5.2 图的存储结构[1,0] 35
5.3 图的遍历[2,0] 35
5.4 *小生成树[1,0] 36
5.5 *短路径[2,0] 37
5.6 拓扑排序[3,0] 38
5.7 关键路径[1,1] 40
第6章 查 找 43
6.1 查找的基本概念未考 43
6.2 线性表[2,0] 43
6.3 B-树[3,0] 44
6.4 B+树未考 46
6.5 散列表[1,1] 46
第7章 排 序 48
7.1 排序的基本概念未考 48
7.2 插入排序[3,0] 48
7.3 交换排序[3,0] 49
7.4 选择排序[2,0] 50
7.5 归并排序[0,1] 52
7.6 基数排序[1,0] 53
7.7 外排序未考 53
第2篇 计算机组成原理
第8章 计算机系统概述 54
8.1 计算机的发展历程未考 54
8.2 计算机硬件的基本组成[1,0] 54
8.3 计算机软件的分类未考 55
8.4 计算机的工作过程[1,0] 55
8.5 计算机性能指标[2,0] 55
第9章 数据的表示和运算 57
9.1 进位计数制及其相互转换未考 57
9.2 真值和机器数[2,0] 57
9.3 BCD码未考 58
9.4 校验码[1,0] 58
9.5 定点数的表示[1,1] 58
9.6 定点数的运算[1,0] 60
9.7 浮点数的表示[4,0] 61
9.8 浮点数的加/减运算[1,0] 63
9.9 算术逻辑单元(ALU)未考 64
第10章 存储器层次结构 65
10.1 存储器的分类[1,0] 65
10.2 存储器的层次化结构未考 65
10.3 半导体存储器[1,0] 65
10.4 只读存储器未考 66
10.5 Flash存储器[1,0] 66
10.6 主存储器与CPU的连接[4,0] 66
10.7 双口RAM和多模块存储器未考 68
10.8 高速缓冲存储器[3,3] 68
10.9 虚拟存储器[2,1] 75
第11章 指令系统 79
11.1 指令格式未考 79
11.2 指令的寻址方式[4,2] 79
11.3 CISC和RISC的基本概念[1,0] 84
第12章 **处理器 85
12.1 CPU的功能和基本结构[1,0] 85
12.2 指令执行过程[2,0] 85
12.3 硬布线控制器与微程序控制器[2,1] 86
12.4 指令流水线[4,1] 89
12.5 多核处理器未考 93
12.6 中断系统[4,0] 93
第13章 总 线 95
13.1 总线的基本概念未考 95
13.2 总线的分类[2,0] 95
13.3 总线的组成和性能指标[2,0] 96
13.4 总线仲裁未考 97
13.5 总线操作和定时未考 97
13.6 总线标准[2,0] 97
第14章 输入/输出系统 99
14.1 I/O系统基本概念未考 99
14.2 输入/输出设备[1,0] 99
14.3 外存储器[2,0] 99
14.4 I/O接口[1,0] 100
14.5 程序查询方式[1,0] 100
14.6 程序中断方式[1,1]综合题见14.7 101
14.7 DMA方式[0,1] 101
14.8 通道方式未考 103
第3篇 操作系统
第15章 操作系统概述 104
15.1 操作系统的概念[1,0] 104
15.2 操作系统的特征[1,0] 104
15.3 操作系统的发展与分类[1,0] 105
15.4 操作系统的主要功能未考 105
15.5 中断和异常[1,0] 105
15.6 用户态与核心态[3,0] 106
15.7 系统调用[2,0] 108
15.8 操作系统的体系结构未考 109
第16章 进程管理 110
16.1 进程的概念和特点[1,0] 110
16.2 进程的三态转化[1,0] 110
16.3 进程的控制[2,0] 111
16.4 线程的概念及线程与进程的比较[2,0] 112
16.5 进程通信未考 113
16.6 处理机的三级调度概念和
调度的基本原则[1,0] 113
16.7 常见进程调度算法[3,0] 114
16.8 同步与互斥的概念未考 116
16.9 互斥实现的软件方法和硬件方法[1,0] 116
16.10 信号量机制[1,0] 118
16.11 经典同步问题[0,3] 118
16.12 管程未考 131
16.13 死锁的原因和必要条件[1,0] 131
16.14 **性算法和银行家算法[3,0] 132
第17章 内存管理 134
17.1 应用程序的编译和链接[1,0] 134
17.2 交换和覆盖未考 134
17.3 分区分配[2,0] 134
17.4 内部碎片和外部碎片未考 135
17.5 基本分页、基本分段存储
管理方式[2,1] 135
17.6 虚拟存储器[1,0] 137
17.7 请求分页管理方式[2,1] 138
17.8 页面置换算法[0,2] 140
17.9 抖动现象与缺页率[1,0] 147
第18章 文件管理 148
18.1 文件的基本概念[1,0] 148
18.2 文件的逻辑结构未考 148
18.3 目录结构[2,0] 148
18.4 文件共享[1,0] 149
18.5 文件保护未考 149
18.6 文件系统的层次结构未考 149
18.7 目录实现未考 149
18.8 文件的外存分配
方式(物理结构)[4,2] 150
18.9 文件存储空间管理未考 153
18.10 磁盘的结构和访问时间未考 153
18.11 磁盘调度算法[1,1] 153
18.12 磁盘管理[1,0] 157
第19章 设备管理 159
19.1 I/O设备的分类与功能未考 159
19.2 I/O控制方式未考 159
19.3 I/O软件层次结构[4,0] 159
19.4 缓冲区[2,0] 160
19.5 设备分配与回收未考 162
19.6 SPOOLing(假脱机)技术未考 162
第4篇 计算机网络
第20章 计算机网络体系结构 163
20.1 计算机网络的概念与组成未考 163
20.2 计算机网络的功能未考 163
20.3 计算机网络的分类未考 163
20.4 计算机网络体系结构[2,0] 163
20.5 ISO/OSI模型和TCP/IP模型[3,0] 164
20.6 计算机网络性能指标[1,0] 165
第21章 物理层 167
21.1 带宽、码元、波特率与速率[1,0] 167
21.2 奈奎斯特定理[1,0] 167
21.3 香农定理未考 168
21.4 编码与调制[1,0] 168
21.5 电路交换、报文交换与分组交换[1,0] 168
21.6 数据报与虚电路未考 169
21.7 传输介质未考 169
21.8 物理层接口特性[1,0] 169
21.9 中继器未考 169
21.10 集线器未考 169
第22章 数据链路层 170
22.1 数据链路层的功能未考 170
22.2 组帧未考 170
22.3 差错控制未考 170
22.4 编码与调制未考 170
22.5 流量控制、可靠传输与
滑动窗口机制未考 170
22.6 停止-等待协议未考 170
22.7 后退N帧协议(GBN)[2,0] 170
22.8 选择重传协议(SR)[1,0] 171
22.9 信道划分介质访问控制[1,0] 171
22.10 随机访问介质访问控制[2,1] 172
22.11 令牌传递协议未考 174
22.12 以太网[3,1] 174
22.13 PPP协议未考 177
22.14 HDLC协议[1,0] 177
22.15 网桥未考 178
22.16 交换机未考 178
第23章 网络层 178
23.1 异构网络互联未考 178
23.2 静态路由、动态路由与层次路由未考 178
23.3 IPv4分组与IPv4地址[0,1] 178
23.4 NAT未考 180
23.5 子网划分、CIDR[3,2] 180
23.6 ARP、DHCP、ICMP协议[2,0] 185
23.7 IPv6未考 186
23.8 自治系统与域内、域间路由未考 186
23.9 RIP[1,0] 186
23.10 OSPF协议未考 187
23.11 BGP协议未考 187
23.12 IP组播未考 187
23.13 移动IP未考 187
23.14 路由器[3,0] 187
第24章 传输层 190
24.1 传输层的功能与寻址未考 190
24.2 端口未考 190
24.3 无连接服务与面向连接服务未考 190
24.4 UDP协议未考 190
24.5 TCP段与流量控制[3,0] 190
24.6 TCP连接管理[2,0] 191
24.7 TCP拥塞控制[1,0] 192
第25章 应用层 194
25.1 客户/服务器模型与P2P模型未考 194
25.2 DNS[1,0] 194
25.3 FTP[1,0] 195
25.4 电子邮件[2,0] 196
25.5 WWW未考 197
25.6 HTTP未考 197
附 录 198
附录A 2013年全国硕士研究生入学统一
考试计算机科学与技术学科联考 198
计算机学科专业基础综合试题 198
计算机学科专业基础综合试题答案及
评分参考 207
附录B 2012年全国硕士研究生入学统一
考试计算机科学与技术学科联考 213
计算机学科专业基础综合试题 213
计算机学科专业基础综合试题答案及
评分参考 222
附录C 2011年全国硕士研究生入学统一
考试计算机科学与技术学科联考 228
计算机学科专业基础综合试题 228
计算机学科专业基础综合试题答案及
评分参考 236
附录D 2010年全国硕士研究生入学统一
考试计算机科学与技术学科联考 243
计算机学科专业基础综合试题 243
计算机学科专业基础综合试题答案及
评分参考 252
附录E 2009年全国硕士研究生入学统一
考试计算机科学与技术学科联考 257
计算机学科专业基础综合试题 257
计算机学科专业基础综合试题答案及
评分参考 265
参考文献 272

1.已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素,则关键字的比较次数*多是( )。
A.4 B.5 C.6 D.7
【10-9】 B。
解法一:
设顺序表L长度为n=16,采用折半查找一个不存在的元素,即为不成功查找。不成功查找的*多比较次数= ?log2(n+1)? = ?log217? =5。
解法二:
假设L[0, ,15],则:
**次,?(0+15)/2? =7,比较的是L[7],假设比L[7]大。
第二次,?(8+15)/2? =11,比较的是L[11],假设比L[11]��。
第三次,?(12+15)/2? =13,比较的是L[13],假设比L[13]大。
第四次,?(14+15)/2? =14,比较的是L[14],假设比L[14]大。
第五次,?(15+15)/2? =15,比较的是L[15],假设比L[15]大。
【总结】
举例法适合在n比较小的情况下使用,在n较大的情况下就不适合了。所以考生*好记住折半查找不成功查找的*坏情况的比较次数是 ?log2(n+1)?。
2.设包含4个数据元素的集合S={"do","for","repeat","while"},各元素的查找概率依次为:p1=0.35,p2=0.15,p3=0.15,p4=0.35。将S保存在一个长度为4的顺序表中,采用折半查找法,查找成功时的平均查找长度为2.2。请回答:
(1)若采用顺序存储结构保存S,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?
(2)若采用链式存储结构保存S,且要求平均查找长度更短,则元素应如何排列?应使用何种查找方法?查找成功时的平均查找长度是多少?
【13-42】 【答案要点】
(1)采用顺序存储结构,数据元素按其查找概率降序排列。
采用顺序查找方法。
查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。
(2)
答案一:
采用链式存储结构,数据元素按其查找概率降序排列,构成单链表。
采用顺序查找方法。
查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。
答案二:
采用二叉链表存储结构,构造二叉排序树,元素存储方式如图6-1所示。

计算机统考从2009~2014年即将跨过6个年头。纵观2009~2013年这5年的题型,2009~2012年每年试题的综合性、灵活性都呈平稳上升趋势,但是在2013年有个急速的下降,也许和部分学校自主命题有关。尽管2013年题目难度有所下降,但是真题仍然是复习的**,只有把握好真题的出题思路,才能以不变应万变。基于此,天勤计算机考研辅导书编写组萌生了写一本关于历年统考真题详解的想法,历经两个月,终于于2012年9月成书,并于2013年7月进行了修订,并将2013年的真题收录其中。该书不但将历年真题的每个考题、考点进行透彻分析,而且还将近5年的所有综合题的评分点进行了详细阐述,准确地帮助考生抓住得分点。

天勤论坛,取名自古训“天道酬勤”,意为考研路上,困苦实多,然而天自有道,勤恳付出者,必有应得之酬劳。天勤论坛由浙大、北航等多所计算机专业名校的研究生创办,团队所有成员皆亲身经历过计算机专业考研的磨炼,于是本着为考生服务的热情,共同搭建了此交流平台。
由天勤论坛组编的高分笔记系列计算机考研辅导书,融入了论坛答疑的精华内容,论坛组织了高分考生进行勘误,不断完善此套书籍。考生在书中遇到疑问,也可在线与作者进行交流。
为提高考生算法设计能力,团队搭建了专门针对计算机考研学子的在线算法测试平台——ACM俱乐部(acmclub.com),希望能借此帮助考生提高复习效率。