计算机考研专业基础综合便携手册

前言

第1篇 数据结构

第1章 绪 论 2

知识体系框架图 2

知识点速记 3

知识点1：代码书写规范 3

知识点2：C/C++语言基础 5

知识点3：时间复杂度与空

间复杂度分析基

础【2,0】 7

知识点4：数据结构相关的

基本概念 7

知识点5：数据逻辑结构 8

知识点6：数据物理结构 9

知识点7：算法 10

第2章 线性表 11

知识体系框架图 11

知识点速记 12

知识点1：线性表的逻辑

特性 12

知识点2：线性表的存储

结构 12

知识点3：线性表的定义 14

知识点4：顺序表操作【0,2】 16

知识点5：单链表操作【0,2】 20

知识点6：双链表操作 24

知识点7：循环链表操作 26

知识点8：一元多项式的表

示及相加 27

第3章 栈、队列和数组 29

知识体系框架图 29

知识点速记 30

知识点1：栈的定义【4,0】 30

知识点2：栈的表示和

实现 30

知识点3：栈的应用 33

知识点4：队列的定义【1,0】 37

知识点5：队列的表示和实

现【2,0】 37

知识点6：队列的应用 42

知识点7：顺序存储 43

知识点8：特殊矩阵的压缩

存储 44

第4章 树与二叉树 46

知识体系框架图 46

知识点速记 47

知识点1：树相关的基本

概念【1,0】 47

知识点2：二叉树的定义 49

知识点3：二叉树的性

质【2,0】 51

知识点4：二叉树的存储

结构 52

知识点5：二叉树的遍历

算法【1,0】 52

知识点6：二叉树的构

造【2,0】 60

知识点7：线索二叉树【1,0】 61

知识点8：树的存储结构 63

知识点9：森林与二叉树的

转换【2,0】 66

知识点10：树和森林的

遍历 70

知识点11：二叉排序

树【1,0】 73

知识点12：平衡二叉

树【3,0】 78

知识点13：赫夫曼树和赫夫曼编码【1,0】 80

第5章 图 83

知识体系框架图 83

知识点速记 84

知识点1：图相关的基本

概念【2,0】 84

知识点2：图的存储结构 85

知识点3：图的遍历【1,0】 89

知识点4：最小（代价）生成树【1,0】 93

知识点5：最短路径【2,0】 96

知识点6：拓扑排序【3,0】 104

知识点7：关键路径【0,1】 105

第6章 查 找 109

知识体系框架图 109

知识点速记 110

知识点1：查找的基本

概念 110

知识点2：顺序查找法 110

知识点3：折半查找

法【1,0】 111

知识点4：二叉排序树 113

知识点5：平衡二叉树 113

知识点6：B?树【2,0】 113

知识点7：B+树 120

知识点8：散列表【1,1】 120

第7章 排 序 124

知识体系框架图 124

知识点速记 125

知识点1：直接插入排

序【2,0】 125

知识点2：折半插入排

序【1,0】 126

知识点3：希尔排序 129

知识点4：简单选择排序 130

知识点5：堆排序【2,0】 131

知识点6：起泡排序【1,0】 135

知识点7：快速排序【2,0】 138

知识点8：二路归并

排序【0,1】 143

知识点9：基数排序 144

知识点10：外部排序 146

知识点11：各种排序算法的

比较 149

第2篇 计算机组成原理

第1章 计算机系统概述 152

知识体系框架图 152

知识点速记 153

知识点1：冯?诺依

曼机【1,0】 153

知识点2：计算机系统未考 154

知识点3：计算机性能

指标【2,1】 156

知识点4：相关概念

总结未考 158

第2章 数据的表示和运算 160

知识体系框架图 160

知识点速记 161

知识点1：真值、机器数

和BCD码未考 161

知识点2：定点数的表

示【3,1】 161

知识点3：定点数的移位

运算未考 166

知识点4：补码定点数的

加减运算【0,1】 167

知识点5：定点数的乘除

运算未考 169

知识点6：浮点数的表示

与IEEE754标

准【2,0】 169

知识点7：浮点数的加减

运算【1,0】 175

知识点8：串行加法器与

并行加法器未考 176

知识点9：算术逻辑单元

（ALU）的功能和结构未考 178

第3章 存储器层次结构 180

知识体系框架图 180

知识点速记 181

知识点1：存储器的分类与

层次化结构未考 181

知识点2：半导体随机存

储器【2,0】 183

知识点3：DRAM存储器

的刷新未考 184

知识点4：只读存储器与

FLASH存储

器【2,0】 187

知识点5：主存储器与CPU

的连接【2,0】 187

知识点6：双口RAM和多模块存储器【0,1】 193

知识点7：Cache的基本

工作原理【2,0】 196

知识点8：Cache和主存

之间的映射方

式【3,0】 197

知识点9：Cache中主存块

的替换算法未考 202

知识点10：Cache写操作

策略未考 203

知识点11：虚拟存储

器【2,1】 204

第4章 指令系统 206

知识体系框架图 206

知识点速记 207

知识点1：指令的基本格式以及几种常见的指令格式未考 207

知识点2：定长操作码指令格式与不定长操作码指令格式未考 209

知识点3：指令的寻址方

式【2,1】 212

知识点4：CISC和RISC的基本概念【1,0】 217

知识点5：标志寄存器与转移条件的逻辑表达式总结【1,0】 218

第5章 中央处理器 220

知识体系框架图 220

知识点速记 221

知识点1：CPU中的寄

存器未考 221

知识点2：指令执行过

程未考 222

知识点3：控制器的结构、

功能和实现未考 224

知识点4：微程序控制

器未考 226

知识点5：指令流水线的基本概念与实现未考 230

知识点6：多核处理器未考 233

知识点7：中断系统未考 234

第6章 总 线 239

知识体系框架图 239

知识点速记 240

知识点1：总线的基本概念、分类与结构未考 240

知识点2：总线的性能指

标未考 241

知识点3：总线仲裁未考 242

知识点4：总线操作和定

时未考 245

知识点5：总线标准未考 246

第7章 输入/输出系统 248

知识体系框架图 248

知识点速记 249

知识点1：I/O设备未考 249

知识点2：硬盘存储器未考 251

知识点3：光盘存储器未考 253

知识点4：I/O接口的功能

和基本结构未考 254

知识点5：I/O端口及其编

址未考 255

知识点6：I/O方式未考 256

第3篇 操作系统

第1章 绪 论 264

知识体系框架图 264

知识点速记 265

知识点1：操作系统的

概念未考 265

知识点2：操作系统的

特征【1,0】 266

知识点3：操作系统的发展

与分类【1,0】 267

知识点4：操作系统的主要

功能未考 269

知识点5：中断和异

常【1,0】 270

知识点6：用户态与核心

态【2,0】 271

知识点7：系统调用【2,0】 272

知识点8：操作系统的体系

结构未考 273

第2章 进程管理 274

知识体系框架图 274

知识点速记 275

知识点1：进程的概念和

特点【1,0】 275

知识点2：进程的三态

转化【1,0】 275

知识点3：进程的控

制【2,0】 276

知识点4：线程的概念及

线程与进程的

比较【2,0】 278

知识点5：进程通信未考 280

知识点6：处理机的三级调

度概念和调度的

基本原则【1,0】 280

知识点7：常见进程调度

算法【2,0】 281

知识点8：同步与互斥的

概念未考 282

知识点9：互斥实现的软

件方法和硬件

方法【1,0】 283

知识点10：信号量机

制【1,0】 284

知识点11：经典同步

问题【0,2】 284

知识点12：管程未考 292

知识点13：死锁的原因和必

要条件【1,0】 293

知识点14：安全性算法和银

行家算法【2,0】 294

第3章 内存管理 296

知识体系框架图 296

知识点速记 297

知识点1：应用程序的编译

和链接【1,0】 297

知识点2：交换和覆盖未考 298

知识点3：分区分配【2,0】 299

知识点4：内部碎片和外部

碎片未考 301

知识点5：基本分页、基本

分段存储管理方

式【2,0】 302

知识点6：虚拟内存【1,0】 303

知识点7：请求分页管理

方式【1,1】 307

知识点8：抖动现象与缺

页率【1,0】 311

第4章 文件管理 315

知识体系框架图 315

知识点速记 316

知识点1：文件的基本

概念【1,0】 316

知识点2：文件的逻辑

结构未考 317

知识点3：目录结构【1,0】 318

知识点4：文件共享【1,0】 320

知识点5：文件保护未考 322

知识点6：文件系统的层

次结构未考 323

知识点7：目录实现未考 323

知识点8：文件的实现未考 324

知识点9：磁盘的结构和

访问时间未考 326

知识点10：磁盘调度

算法【1,1】 327

知识点11：磁盘管理【1,0】 330

第5章 设备管理 332

知识体系框架图 332

知识点速记 333

知识点1：I/O设备的分类

与功能未考 333

知识点2：I/O控制方

式未考 334

知识点3：I/O软件层次

结构【3,0】 334

知识点4：缓冲区【1,0】 336

知识点5：设备分配与

回收未考 337

知识点6：SPOOLing假脱

机技术未考 338

第4篇 计算机网络

第1章 计算机网络体系结构 342

知识体系框架图 342

知识点速记 343

知识点1：实体、对等层、对

等实体未考 343

知识点2：协议【1,0】 343

知识点3：接口未考 344

知识点4：服务【1,0】 344

知识点5：ISO/OSI参考

模型与TCP/IP

模型【2,0】 346

知识点6：计算机网络性能

指标【1,0】 346

第2章 物理层 352

知识体系框架图 352

知识点速记 353

知识点1：信号、信源、信道、信宿未考 353

知识点2：带宽、码元、波特、速率【1,0】 354

知识点3：奈奎斯特定理与

香农定理【1,0】 356

知识点4：数据传输方式、

通信方式、通信

模式未考 357

知识点5：编码与调制未考 358

知识点6：电路交换、报

文交换与分组

交换未考 359

知识点7：数据报与虚

电路未考 361

知识点8：传输介质未考 361

知识点9：物理层接口

特性【1,0】 363

知识点10：物理层设

备未考 364

第3章 数据链路层 365

知识体系框架图 365

知识点速记 366

知识点1：组帧未考 366

知识点2：检错编码和纠错

编码未考 368

知识点3：流量控制与可靠

传输机制【3,0】 372

知识点4：信道划分介质访

问控制未考 374

知识点5：随机访问介质访

问控制【1,1】 376

知识点6：以太网【2,2】 380

知识点7：网桥未考 382

知识点8：交换机【1,0】 385

知识点9：各层设备的广

播域、冲突域

总结未考 386

第4章 网络层 387

知识体系框架图 387

知识点速记 388

知识点1：异构网络互联与

路由转发【0,1】 388

知识点2：IPv4【4,1】与

NAT 389

知识点3：ARP、DHCP、ICMP

与IPv6【2,0】 394

知识点4：RIP、OSPF、

BGP【1,0】 396

知识点5：IP组播未考 399

知识点6：移动IP未考 401

知识点7：路由器的组成

和功能【3,0】 402

第5章 传输层 405

知识体系框架图 405

知识点速记 406

知识点1：传输层的基

本概念与端

口号未考 406

知识点2：UDP数据报未考 407

知识点3：TCP段的首部

格式【0,1】 409

知识点4：TCP的连接管

理【1,1】 412

知识点5：TCP的重传机

制未考 413

知识点6：TCP的拥塞控

制【2,0】 414

第6章 应用层 417

知识体系框架图 417

知识点速记 418

知识点1：DNS系统【1,0】 418

知识点2：FTP【1,0】 419

知识点3：电子邮件【1,0】 422

知识点4：WWW与

HTTP【0,1】 424

知识点5：应用层协议与传

输层协议的关系

总结未考 426

参考文献 428