第1篇 数据结构 2
第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篇 计算机组成原理 152
第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篇 操作系统 264
第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篇 计算机网络 342
第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