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