admin 管理员组

文章数量: 887021

目录

  • 第1章 计算机系统知识
    • 1.1 计算机硬件基础知识 1
      • 1.1.1 中央处理单元 1
      • 1.1.2 存储器 4
      • 1.1.3 总线 7
      • 1.1.4 输入输出控制 10
    • 1.2 计算机体系结构 14
      • 1.2.1 CISC和RISC…… 15
      • 1.2.2 流水线技术 16
      • 1.2.3 阵列处理机、并行处理机和多处理机 19
    • 1.3 存储系统 20
      • 1.3.1 高速缓存 21
      • 1.3.2 虚拟存储器 24
      • 1.3.3 相联存储器 25
      • 1.3.4 磁盘阵列技术 25
      • 1.3.5 存储域网络 26
    • 1.4 安全性、可靠性与系统性能评测基础知识 26
      • 1.4.1 计算机安全概述 26
      • 1.4.2 加密技术和认证技术 28
      • 1.4.3 计算机可靠性 35
      • 1.4.4 计算机系统的性能评价 38
    • 补充知识点
      • 1. 多媒体基础知识
        • 1.1 多媒体计算机系统
        • 1.2 声音
        • 1.3 图形和图像
        • 1.4 动画和视频
        • 1.5 虚拟现实
      • 2. 数据表示和校验
      • 3. 逻辑运算
  • 第2章 程序语言基础知识
    • 2.1 程序语言概述…… 42
      • 2.1.1 程序语言的基本概念…… 42
      • 2.1.2 程序语言的基本成分…… 46
    • 2.2 程序语言翻译基础…… 52
      • 2.2.1 汇编程序基本原理…… 52
      • 2.2.2 编译程序基本原理…… 54
      • 2.2.3 解释程序基本原理…… 73
    • 补充知识点
      • 中缀、前缀与后缀表达式
  • 第3章 数据结构与算法
    • 3.1 线性结构
      • 3.1.1 线性表
      • 3.1.2 栈和队列
      • 3.1.3 串
    • 3.2 数组和矩阵 87
    • 3.3 树和图 90
      • 3.3.1 树 90
      • 3.3.2 图 97
    • 3.4 常用算法 102
      • 3.4.1 算法概述 102
      • 3.4.2 排序 105
      • 3.4.3 查找 112
      • 3.4.4 递归算法 122
      • 3.4.5 图的相关算法 123
  • 第4章 操作系统知识 128
    • 4.1 操作系统基础知识 128
      • 4.1.1 操作系统的基本概念 128
      • 4.1.2 操作系统分类及特点 129
      • 4.1.3 操作系统的发展 131
    • 4.2 进程管理 131
      • 4.2.1 基本概念 132
      • 4.2.2 进程的控制 135
      • 4.2.3 进程间的通信 135
      • 4.2.4 管程139
      • 4.2.4 进程调度139
      • 4.2.5 死锁 140
      • 4.2.6 线程 140
    • 4.3 存储管理 144
      • 4.3.1 基本概念 145
      • 4.3.2 存储管理方案 146
      • 4.3.3 分页存储管理 147
      • 4.3.4 分段存储管理 148
      • 4.3.5 段页式存储管理 150
      • 4.3.6 虚拟存储管理 151
    • 4.4 设备管理 155
      • 4.4.1 概述 155
      • 4.4.2 I/O 软件 156
      • 4.4.3 设备管理采用的相关技术 157
      • 4.4.4 磁盘调度 160
    • 4.5 文件管理 162
      • 4.5.1 基本概念 163
      • 4.5.2 文件的结构和组织 164
      • 4.5.3 文件目录 165
      • 4.5.4 存取方法和存储空间的管理 166
      • 4.5.5 文件的使用 168
      • 4.5.6 文件的共享和保护 168
      • 4.5.7 系统的安全与可靠性 169
    • 4.6 作业管理 170
      • 4.6.1 基本概念 170
      • 4.6.2 作业调度 172
      • 4.6.3 用户界面 173
  • 第五章 网络基础知识
    • 5.1 计算机网络概述 174
      • 5.1.1 计算机网络概念
      • 5.1.2 计算机网络的分类
      • 5.1.3 网络的拓扑结构
    • 5.2 网络硬件基础 180
      • 5.2.1 网络设备
      • 5.2.2 网络传输介质
    • 5.3 网络的协议与标准 185
      • 5.3.1 网络的标准
      • 5.3.2 局域网协议
      • 5.3.3广域网协议
      • 5.3.4 TCP/IP协议簇
    • 5.4 Internet 基础知识 197
      • 5.4.1 Inernet概述
      • 5.4.2 Internet地址
      • 5.4.3 Internet服务
    • 5.5 信息安全基础知识 210
    • 5.6 网络安全概述 214
    • 补充知识点
      • 1. ISO/OSI 网络体系结构
  • 第 6 章 数据库技术基础
    • 6.1 基础概念
      • 6.1.1 数据库与数据库管理系统
      • 6.1.2 数据库技术的发展
      • 6.1.3 DBMS的功能和特点
      • 6.1.4 数据库系统的体系结构
      • 6.1.5 数据库系统的三级模式结构
    • 6.2 数据模型
      • 6.2.1 数据模型的基本概念
      • 6.2.2 数据模型的三要素
      • 6.2.3 E-R 模型
      • 6.2.4 基本的数据模型
    • 6.3 数据存储和查询
      • 6.3.1 存储管理器
      • 6.3.2 查询处理器
    • 6.4 数据仓库和数据挖掘基础知识
      • 6.4.1 数据仓库
      • 6.4.2 数据挖掘
  • 第7章 关系数据库
    • 7.1 关系数据库概述
      • 7.1.1 基础知识
      • 7.1.2 关系数据库模式
      • 7.1.3 关系的完整性约束
    • 7.2 关系运算
      • 7.2.1 关系代数运算
      • 7.2.2 五种基本的关系代数运算
      • 7.2.3 扩展的关系运算
    • 7.3 元组演算
      • 7.3.1 原子公式
      • 7.3.2 公式的定义
      • 7.3.3 关系代数运算转换为元组演算表达式
    • 7.4 域演算
      • 7.4.1 原子公式
      • 7.4.2 公式的定义
      • 7.4.3 举例
    • 7.5 查询优化
      • 7.5.1 基本概念
      • 7.5.2 关系代数表达式中的查询优化
    • 7.6 关系数据库设计基础理论
      • 7.6.1 基础知识
      • 7.6.2 规范化
      • 7.6.3 Armstrong 公理系统
      • 7.6.4 模式分解及分解后的特性
  • 第八章 SQL 语言
    • 8.1 数据库语言
      • 8.1.1 数据库语言概述
      • 8.1.2 数据库语言的分类
    • 8.2 SQL 概述
      • 8.2.1 SQL 语言的特征
      • 8.2.2 SQL 的基本组成
    • 8.3 数据库定义
      • 8.3.1 基本域类型
      • 8.3.2 创建表(CREATE TABLE)
      • 8.3.3 修改表和删除表
      • 8.3.4 创建和删除索引
      • 8.3.5 视图创建和删除
    • 8.4 数据操作
      • 8.4.1 Select 基本结构
      • 8.4.2 简单查询
      • 8.4.3 连接查询
      • 8.4.4 子查询与聚集函数
      • 8.4.5 分组查询
      • 8.4.6 更名操作
      • 8.4.7 字符串操作
      • 8.4.8 集合操作
      • 8.4.9 视图查询与更新
    • 8.5 完整性约束
      • 8.5.1 主键(Primary Key) 约束
      • 8.5.2 外键(Foreign Key)约束
      • 8.5.3 属性值上的约束
      • 8.5.4 全局约束
    • 8.6 授权(GRANT) 与销权(REVOKE)
    • 8.7 创建与删除触发器 316
      • 8.7.1 概述
      • 8.7.2 创建触发器
      • 8.7.3 更改和删除触发器
    • 8.8 嵌入式SQL 320
      • 8.8.1 SQL 与宿主语言接口
      • 8.8.2 动态SQL
    • 8.9 SQL-99所支持的对象关系模型 323
      • 8.9.1 嵌套关系 323
      • 8.9.2 复杂类型 326
      • 8.9.3 继承 329
      • 8.9.4 引用类型 332
      • 8.9.5 与复杂类型有关的查询 332
      • 8.9.6 函数和过程 335
  • 第 9 章 非关系型数据库 NoSQL 341
    • 9.1 NoSQL 概述 341
    • 9.2 相关理论基础
      • 9.2.1 一致性 342
      • 9.2.2 分区 344
      • 9.2.3 存储分布 344
      • 9.2.4 查询模型 347
    • 9.3 NoSQL 数据库的种类 349
      • 9.3.1 文档存储 350
      • 9.3.2 键值存储 355
      • 9.3.3 列存储 362
      • 9.3.4 图存储 365
      • 9.3.5 其他存储模式 367
    • 9.4 NoSQL 应用案例与新技术 369
      • 9.4.1 HBase 数据库 369
      • 9.4.2 云数据库 GeminiDB 371
  • 第10章 系统开发和运行知识 373
    • 10.1 软件工程基础知识 373
      • 10.1.1 软件生存周期 373
      • 10.1.2 软件生存周期模型 375
      • 10.1.3 典型的软件开发方法 378
      • 10.1.4 软件项目管理 379
    • 10.2 系统分析基础知识 384
      • 10.2.1 系统分析概述 385
      • 10.2.2 需求分析 385
      • 10.2.3 结构化分析方法 386
      • 10.2.4 面向对象分析方法 392
    • 10.3 系统设计基础知识 403
      • 10.3.1 系统设计内容和步骤 403
      • 10.3.2 系统设计的基本原理 405
      • 10.3.3 结构化设计方法 407
      • 10.3.4 面向对象设计方法 409
    • 10.4 系统测试基础知识 410
      • 10.4.1 系统测试的概念 410
      • 10.4.2 软件测试策略 411
      • 10.4.3 软件测试方法 415
    • 10.5 系统运行和维护基础知识 418
      • 10.5.1 系统维护概述 418
      • 10.5.2 系统评价 420
    • 10.6 软件开发方法新进展 421
      • 10.6.1 面向方面的方法 421
      • 10.6.2 软件复用与构件化方法 421
      • 10.6.3 服务化方法 423
  • 第11章 数据库设计
    • 11.1 数据库设计概述
      • 11.1.1 数据库应用系统的生命期
      • 11.1.2 数据库设计的一般策略
      • 11.1.3 数据库设计的基本步骤
    • 11.2 系统需求分析
      • 11.2.1 需求分析的任务、方法和目标
      • 11.2.2 需求分析阶段的文档
      • 11.2.3 案例分析
    • 11.3 概念结构设计
      • 11.3.1 概念结构设计策略与方法
      • 11.3.2 用E-R 方法建立概念模型
    • 11.4 逻辑结构设计
      • 11.4.1 E-R 图向关系模式的转换
      • 11.4.2 关系模式的规范化
      • 11.4.3 确定完整性约束
      • 11.4.4 用户视图的确定
      • 11.4.5 应用程序设计
    • 11.5 数据库的物理设计
      • 11.5.1 数据库物理设计工作过程
      • 11.5.2 数据库物理设计工作步骤
    • 11.6 数据库系统的实施阶段
    • 11.7 数据库运行维护与管理
      • 11.7.1 制定数据库系统的运行计划
      • 11.7.2 数据库系统的运行和维护
      • 11.7.3 数据库系统的管理
      • 11.7.4 性能调整
      • 11.7.5 用户支持
  • 第 12 章 事务管理 451
    • 12.1 事务的基础概念 451
      • 12.1.1 事务 451
      • 12.1.2 事务的特性 452
      • 12.1.3 事务的状态 453
    • 12.2 数据库的并发控制 455
      • 12.2.1 事务调度 455
      • 12.2.2 并发操作带来的问题 458
      • 12.2.3 并发调度的可串行性 459
      • 12.2.4 并发控制技术 461
      • 12.2.5两段锁协议 462
      • 12.2.6 多粒度封锁协议 463
      • 12.2.7 案例分析 465
    • 12.3 数据库的备份与恢复 467
      • 12.3.1 数据库系统故障种类 467
      • 12.3.2 数据库备份 468
      • 12.3.3 数据库恢复 469
    • 12.4 数据库的安全性与完整性 470
      • 12.4.1 数据库的安全性 471
      • 12.4.2 数据库的完整性 475
  • 第十三章 云计算与大数据处理 476
    • 13.1 云计算基础知识 476
      • 13.1.1 云计算的关键特征 476
      • 13.1.2 云计算分类 478
      • 13.1.3 云关键技术 479
      • 13.1.4 云计算实施 483
      • 13.1.5 云计算的安全性 486
    • 13.2 大数据处理基础知识 489
      • 13.2.1 基本概念 489
      • 13.2.2 大数据处理技术 490
      • 13.2.3 大数据应用 496
  • 第十四章 数据库主流应用技术 …… 499
    • 14.1 分布式数据库 …… 499
      • 14.1.1 分布式数据库基本概念 …… 500
      • 14.1.2 分布式数据库的体系结构 …… 503
      • 14.1.3 分布式查询处理和优化 …… 511
      • 14.1.4 分布事务管理 …… 512
      • 14.1.5 新型分布式海量数据库 …… 519
    • 14.2 Web 与数据库 …… 520
      • 14.2.1 Web 概述 …… 520
      • 14.2.2 Web 服务器脚本程序与服务器的接口 …… 521
      • 14.2.3 CGI 的应用 …… 522
      • 14.2.4 ASP 的应用 …… 523
      • 14.2.5 Servlet 和JSP 的应用 …… 525
    • 14.3 XML与数据库 …… 526
      • 14.3.1 什么是XML …… 526
      • 14.3.2 XML 的文件存储面临的问题 …… 527
      • 14.3.3 XML 与数据库的数据转换 …… 528
    • 14.4 面向对象数据库 …… 531
      • 14.4.1 面向对象数据库系统的特征 …… 533
      • 14.4.2 面向对象数据模型 …… 534
      • 14.4.3 面向对象数据库语言 …… 538
      • 14.4.4 对象关系数据库系统 …… 539
    • 14.5 大数据与数据库 …… 545
      • 14.5.1 大数据之数据仓库设计 …… 546
      • 14.5.2 数据转移技术 …… 549
      • 14.5.3 数据仓库主要应用场景——联机分析处理（OLAP） …… 552
      • 14.5.4 数据库主要应用场景——联机事务处理（OLTP） …… 556
    • 14.6 NewSQL 数据库 …… 558
      • 14.6.1 NewSQL 数据库的发展 …… 558
      • 14.6.2 TiDB 的介绍 …… 559
  • 第 15 章 标准化和知识产权基础知识
    • 15.1 标准化基础知识…… 562
      • 15.1.1 标准化的基本概念…… 562
      • 15.1.2 信息技术标准化…… 565
      • 15.1.3 标准化组织…… 567
      • 15.1.4 ISO 9000标准简介…… 569
      • 15.1.5 能力成熟度模型简介…… 570
    • 15.2 知识产权基础知识…… 571
      • 15.2.1 知产产权基本概念…… 571
      • 15.2.2 计算机软件著作权…… 573
      • 15.2.3 计算机软件的商业秘密权…… 584
      • 15.2.4 专利权概述…… 586
  • 第 16 章 数据库设计与案例分析
    • 16.1 SQL 应用案例
      • 16.1.1 SQL 应用案例一
      • 16.1.2 SQL 应用案例二
    • 16.2 数据库设计应用案例
      • 16.2.1 足球联赛信息管理系统
      • 16.2.2 孵化基地管理信息系统
      • 16.2.3 小区停车位管理信息系统
  • 附录：杂七杂八

第1章 计算机系统知识


硬盘属于外存储器（19年第3题）
机械硬盘的性能指标：（18年第4题）
磁盘转速、平均寻道时间、容量
计算机操作的最小时间单位：时钟周期

1.1 计算机硬件基础知识 1

1.1.1 中央处理单元 1

1. CPU的功能
2. CPU的组成
1） 运算器
\qquad 功能：
\qquad (1) 执行所有的算术运算。
\qquad   如加、减、乘、除等基本运算及附加运算。
\qquad (2) 执行所有的逻辑运算并进行逻辑测试。
\qquad   如与、非、或、零值测试或两个值得比较等。
\qquad 组成：（20年第1题）
\qquad (1) 算术逻辑单元 (Arithmetic and Logic Unit，ALU)
\qquad   处理数据，实现对数据的算术运算和逻辑运算
\qquad (2) 累加寄存器 (Accumulator Register，AC)（14年第1题/17年第1题）
\qquad   为算术逻辑单元提供一个工作区，暂存源操作数和计算结果
\qquad (3) 数据缓冲寄存器 (Data buffer Register，DR)
\qquad   暂存由内存储器读写的一条指令或一个数据字，将不同时间段内读写的数据隔离开来
\qquad   作用：作为CPU和内存、外设之间在操作速度上的缓冲，以及数据传送的中转站
\qquad (4) 状态条件寄存器 (Program Status Word，PSW)
\qquad   保存根据算术指令和逻辑指令运行或测试的结构建立的各种条件码内容，主要分为状态标志和控制标志。
\qquad   如运算结果进位标志( C )、运算结果溢出标志(V)、运算结果为0标志(Z)、运算结果为负标志(N)、中断标志(I)、方向标志(D)等。
2）控制器
\qquad 功能：
\qquad 决定了计算机过程的自动化。它不仅要保证程序的正确执行，而且要能够处理异常事件。
\qquad 部件：
\qquad (1) 指令寄存器 (Instruction Register，IR)（10年第5题）
\qquad   暂存从内存读取的指令（操作码+地址码）
\qquad (2) 程序计数器 (Program Counter，PC) （10年第1题/11年第1题/19年第1题/21年第1题）
\qquad   存放将要执行的下一条指令在内存中的地址
\qquad   程序计数器的内容即是从内存提取的第一条指令的地址。当执行指令时，CPU 将自动修改PC 的内容，即每执行一条指令PC 增加一个量，这个量等于指令所含的字节数，以便使其保持的总是将要执行的下一条指令的地址。由于大多数质量都是按顺序来执行的，所以修改的过程通常只是简单的对PC 加1
\qquad (3) 地址寄存器 (Address Register，AR)
\qquad   保存当前CPU 所访问的内存单元的地址
\qquad (4) 指令译码器 (Instruction decoder，ID)
\qquad   对指令中的操作码字段进行分析解释，识别该指令规定的操作，然后向操作控制器发出具体的控制信号
     指令：是对机器进行程序控制的最小单位。
     一条指令通常包括两个部份：操作码和操作数

  操作码指出是什么操作，由指令译码器（ID）来识别。
  操作数直接指出操作数本身或者指出操作数所在的地址。
3）寄存器组
 （1）专用寄存器
     运算器和控制器中的寄存器是专用寄存器，其作用是固定的。
 （2）通用寄存器
     用途广泛并可由程序员规定其用途，其数目因处理器不同而不同。
3. 多核CPU

1.1.2 存储器 4

  1. 存储器的分类
    (1) 按所处位置分类：
     ① 内存
      容量小、速度快
     ② 外存
      容量大、速度慢
    (2) 按构成材料
     ① 磁存储器
     ② 半导体存储器
     ③ 光存储器
    (3) 按工作方式
     ① 读写存储器 (Random Access Memory，RAM)
     ② 只读存储器
    (4) 按访问方式
     ① 按地址访问的存储器
     ② 按内容访问的存储器（09年第3题）
      比如：相联存储器
    (5) 按寻址方式
     ① 随机存储器
     ② 顺序存储器 (Sequentially Addressed Memory，SAM)
     ③ 直接存储器 (Direct Addressed Memory，DAM)
  2. 随机访问存储器
    (1) 静态随机访问存储器（SRAM）
    (2) 动态随机访问存储器（DRAM）
  3. 外存储器
    (1) 磁盘存储器
    磁盘容量：（09年第2题）
    ① 非格式化容量指一个磁盘所能存储的总位数
      非格式化容量 = 面数 × (磁道数/面 ) × 内圆周长 × 最大位密度
    ② 格式化容量指各扇区中数据区容量总和
      格式化容量 = 面数 ×（磁道数/面）×（扇区数/道）×（字节数/扇区）
    (2) 光盘存储器

1.1.3 总线 7

  1. 总线的分类：（09年第4题）
    (1) 数据总线 (Data Bus，DB)
    用来传送数据信息，双向。
    DB 的宽度决定了CPU 和计算机其他设备之间每次交换数据的位数。
    (2) 地址总线 (Address Bus，AB)
    传送CPU 发出的地址信息，单向。
    地址总线的宽度决定了CPU 的最大寻址能力。
    (3) 控制总线 (Control Bus，CB)
    传送控制信号、时序信号和状态信息等。
    CB 中的每一条线的信息传送方向是单方向且确定的，但CB 作为一个整体则是双向的。

补充：
CPU 与其他部件交换数据时，用数据总线传输数据。数据总线宽度指同时传送的二进制位数，内存容量、指令系统中的指令数量和寄存器的位数与数据总线的宽度无关。数据总线宽度越大，单位时间内能进出CPU的数据就越多，系统的运算速度越快。

串行总线将数据一位一位传输，数据线只需要一根（如果支持双向需要2根），并行总线是将数据的多位同时传输（4位，8位，甚至64位，128位），显然，并行总线的传输速度快，在长距离情况下成本高，串行传输的速度慢，但是远距离传输比串行成本低。
单总线结构在一个总线上适应不同种类的设备，通用性强，但是无法达到高的性能要求，而专用总线则可以与连接设备实现最佳匹配。（16年第6题）
在计算机系统中采用总线结构，便于实现系统的积木化构造，便于增减外设，同时可以有效减少信息传输线的数量。
单总线结构
在单总线结构中，CPU与主存之间、CPU与 I/O 设备之间、I/O 设备与主存之间、各种设备之间都通过系统总线交换信息。
优点：控制简单方便、扩充方便。
缺点：由于所有设备部件均挂在单一总线上，使这种结构只能分时工作，即同一时刻只能在两个设备之间传送数据，这就使系统总体数据传输的效率和速度受到限制

2. 常见总线

1.1.4 输入输出控制 10

  1. I/O 设备概述
  2. 程序控制方式
    （1） 无条件传送
    外设总是准备好的，无条件，随时接收和提供数据。
    （2）程序查询方式
    CPU利用程序来查询外设的状态，准备好了再传数据。
  3. 中断方式（18年第1题）
    ♥ CPU不等待，也不执行程序去查询外设的状态，而是由外设在准备好以后，向CPU发出中断请求。
    ♥ CPU的中断响应时间：指从发出中断请求到开始进入中断处理程序（15年第4题）
    ♥ 系统具有多个中断源的处理方法：
    ① 多中断信号线法
    ② 中断软件查询法
    ③ 菊花链法
    ④ 总线仲裁法
    ⑤ 中断向量表法（13年第2题）
      中断向量表用来保存各个中断源的中断服务程序的入口地址。
  4. DMA 方式（13年第4题/17年第3题/19年第2题/20年第3题）
    数据的传输是在主存和外设之间直接进行，不需要CPU 的干预，实际操作是由DMA 硬件直接执行完成的。
    中断方式、程序查询方式和无条件传送方式都是通过CPU 执行程序指令来传送数据的，DMA (Direct Memory Access,直接内存存取)方式下是由DMA 控制器直接控制数据的传送过程，CPU 需要让出对总线的控制权，并不需要CPU 执行程序指令来传送数据。DMA 控制方式是在主存与 I/O 设备间（主存与外设之间）直接建立数据通路进行数据的交换处理。
    （每传送一个数据都需要占用一个存储周期）（21年第3题）
  5. 输入输出处理器（IOP）
    更进一步减轻了CPU 对 I/O 操作的控制，更进一步提高了CPU 的工作效率，但是是以增加更多硬件为代价的

补充知识点：时钟周期、机器周期、指令周期、总线周期、存储周期的区别
（1）时钟周期：计算机中最小的时间单位，等于CPU 主频的倒数。一个时钟周期内，CPU 仅完成一个最基本的动作。
（2）机器周期（CPU 周期）：计算机中为了方便管理，常把一条指令 的执行过程划分为若干个阶段（如取指、间址、执行、中断等）
每一阶段完成一个基本操作。注意：每一个基本操作都是由若干CPU最基本的动作组成。这个基本操作所需要的时间称为机器周期，则机器周期由若干个时钟周期组成。
（3）指令周期：从取指开始到执行完成该指令所需要的全部时间。指令周期包含若干机器周期。
（4）总线周期：存储器和I/O端口是挂接在总线上的，CPU对存储器和I/O接口的访问通过总线实现。把CPU通过总线对微处理器外部（存储器或I/O接口）进行一次访问所需时间称为一个总线周期。
（5）存储周期：存储周期包含存取时间和恢复时间。指两次独立访问存储器操作之间的最小间隔。
存取时间指从启动一次存储器操作到完成该操作所经历的时间。恢复时间指读写操作之后，用来恢复内部状态的时间。
总结：
指令周期>机器周期>时钟周期
存储周期>总线周期

1.2 计算机体系结构 14

  1. 计算机体系结构分类
    (1) 按处理机的数量
     ① 单处理机
     ② 并行处理与多处理系统
     ③ 分布式处理系统
    （2）微观上按并行程度分类
     Flynn分类法、冯泽云分类法、Handler分类法

1.2.1 CISC和RISC…… 15

（21年上第2题）
(1) CISC (Complex Instrunction Set Computer，复杂指令集计算机)
进一步增强原有指令的功能，用更为复杂的新指令取代由原先子程序完成的功能，实现软件功能的硬化，导致机器的指令系统越来越庞大而复杂。普遍使用微程序控制器。
（微处理器x86 属于CISC）
(2) RISC (Reduced Instrunction Set Computer，精简指令集计算机)
通过减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周执行，并通过优化编译，提高指令的执行速度，通用寄存器数量相当多，采用硬线控制逻辑，不用或少用微码控制，优化编译程序，导致机器的指令系统进一步精炼而简单。采用流水线技术。
（ARM 处理器属于RISC）
关键技术：
① 重叠寄存器窗口技术
② 优化编译技术
③ 将流水及超标量技术
④ 硬布线逻辑与微程序相结合在微程序技术中
RISC采用的流水技术：
① 超流水线（Super Pipeline）
② 超标量（Super Scalar）
③ 超长指令字（Very Long Instruction Word,VLIW）（16年第1题）
一种非常长的指令组合，它把许多条指令连在一起，增加了运算的速度。

1.2.2 流水线技术 16

（1）指令控制方式
① 顺序方式
优点：控制简单
缺点：速度慢，各部件利用率低
② 重叠方式
优点：速度有所提高，控制也不太复杂
缺点：会出现冲突、转移和相关等问题
③ 流水方式
一次重叠只是把一条指令解释分解为两个子过程，而流水则是分解为更多的子过程
（2）流水线的种类
① 级别角度：部件级、处理机级以及系统级的流水线
② 功能角度：单功能和多功能流水线
③ 联接方式：静态流水线和动态流水线
（3）流水的相关处理
（4）吞吐率和流水建立时间 （09年第6题/12年第5-6题/14年第5题）
流水线周期
各子任务中执行时间最长的（最慢的）子任务的执行时间。
流水线执行完 n 条指令所需要的时间
Tn = 执行一条指令所需时间 + (n-1) * 流水线周期
吞吐率（18年第3题）
是指单位时间里流水线处理机流出的结果数。对指令而言，就是单位时间里执行的指令数。如果各段流水的操作时间不同，则流水线的吞吐率是最长流水段操作时间。
吞吐率：p=1/max(∆t1，∆t2，…∆tm)，即最长子过程所用时间的倒数。

例题1：一条指令的执行过程可以分解为取指、分析和执行三步，在取指时间 t 取指=3△t，分析时间 t 分析=2△t，执行时间 t 执行=4△t 的情况下，若按串行方式执行，则10条指令全部执行完需要（ ）△t。若按照流水方式执行，则执行完10条指令需要（ ）△t。
串行：（3+2+4）* 10 = 90
流水：（3+2+4）+（10-1）*4= 45
例题2：某指令流水线由5段组成，第1、3、5段所需时间为△t, 第2、4段所需时间分别为3△t、2△t，那么连续输入n条指令时的吞吐率（单位时间内执行的指令个数）TP为（）。
解：
① 流水线周期 = 3
② 流水线执行完 n 条指令所需要的时间 = （3+3+2）+（n-1）*3
③ 吞吐率 = n/(（3+3+2）+（n-1）*3)

补充知识点：
异步流动是指任务从流水线流出的次序同流入流水线的次序不一样，也称为乱序流动或错序流动。性能会下降。
流水线的

1.2.3 阵列处理机、并行处理机和多处理机 19

1.3 存储系统 20


计算机系统中的CPU内部对通用寄存器的存取操作是最快的，其次是Cache,内存的存取速度再次。 （15年第2题）

1.3.1 高速缓存 21

（17年第6题）

  • 高速缓存 (Cache) 是随着CPU 与主存之间的性能差距不断增大而引入的，其容量较小，但速度较快，一般比主存快5~10倍。
  • 主要作用：调和CPU 的速度与内存存取速度之间的差异，从而提升系统性能。（20年第2题）
  • 存储的内容：CPU 近期可能会需要的信息，使用的是程序的局部性原理，是主存内容的副本，因此CPU 需要访问数据和读取指令时要先访问Cache，若命中则直接访问，若不命中再去访问主存。
  • 评价Cache性能的关键指标：Cache的命中率，影响命中率的因素有其容量、替换算法、其组织方式等。Cache的命中率随容量的增大而提高（非线性）。
    基于成本和性能方面的考虑，Cache是为了解决相对较慢的主存与快速的CPU之间工作速度不匹配问题而引入的存储器。
  • CPU 工作时给出的是主存的地址，要从Cache 存储器中读写信息，就需要将主存地址转换成Cache 存储器的地址，这种地址的转换叫作地址映像。
  • 主存地址与Cache 地址之间的转换工作由硬件完成。（12年第1题）
  • 例：CPU 的速度要远快于打印机的速度，为解决这个速度不匹配的问题，可以使用缓存技术，释放CPU 的等待。（21年上第17题）
  1. Cache的地址映射方式
    (1) 全相联映射（16年第2题）
    指主存中任一块都可以映射到Cache 中任一块的方式，也就是说，当主存中的一块需要调入Cache 时，可根据当时Cache 的块占用或分配情况，选择一个块给主存存储，所选的Cache 块可以是Cache 中的任意一块。
    优点：块冲突概率低（块冲突次数最少），Cache空间利用率高（15年第3题）
    缺点：相联目录表容量大导致成本高、查表速度慢

    (2) 直接映像方式
    主存的每一块只能映像到Cache 的一个特定的块中，整个Cache 地址与主存地址的低位部分完全相同
    优点：硬件简单，不需要相联存储器，访问速度快（无需地址变换）
    缺点：Cache 块冲突概率高导致Cache 空间利用率很低。
    例：主存容量为1MB,高速缓存容量为16KB,块的大小为512B

    (3) 组相联方式
    对上述两种方式的折中处理，对Cache 分组，实现组间直接映射，组内全相联
    主存的任何区的0组只能存到Cache 的0组中，1组只能存放到1组中，依此类推。而组内的块可以存入Cache 中相同组的任一块中。
    特点：较低的块冲突概率、较高的块利用率，同时得到较快的速度和较低的成本。
    公式：
    主存地址位数＝区号+组号+主存块号+块内地址
    Cache地址位数＝组号+组内块号+块内地址


2. 高速缓存的替换算法
（1）随机替换算法
（2）先进先出替换算法
（3）近期最少使用替换算法
（4）优化替换算法
3. 高速缓存的性能分析
设Hc 为Cache 的命中率，tc 为Cache 的存取时间，tm 为主存的访问时间，则Cache 存储器的等效加权平均访问时间ta为：
ta=Hctc+（1-Hc)tm

1.3.2 虚拟存储器 24

虚拟存储器实际上是一种逻辑存储器。
常用的虚拟存储器由主存-辅存两级存储器组成。（13年第1题）

1.3.3 相联存储器 25

相联存储器是一种按内容访问的存储器。（12年第3题）
转换检测缓冲区/相联存储器/快表 能够不访问页表，实现快速将虚拟地址映射到物理地址的硬件机制

1.3.4 磁盘阵列技术 25

磁盘存取时间包括寻道时间，定位扇区的时间（也就是旋转延迟的时间）以及读取数据的时间（也就是传输时间），如果磁盘转速提高了一倍，则旋转延迟时间减少一倍。（21年上第4题）

在Windows系统中，磁盘碎片整理程序可以分析本地卷，以及合并卷上的可用空间使其成为连续的空闲区域，从而使系统可以更有效地访问文件或文件夹。（19年第17题）

1.3.5 存储域网络 26

1.4 安全性、可靠性与系统性能评测基础知识 26

1.4.1 计算机安全概述 26

1.4.2 加密技术和认证技术 28

  1. 加密技术
    1） 对称加密技术
    ♥ 文件加密和解密使用相同的密钥，或者虽然不同，也可以从其中一个很容易地推导出另一个。
    1101100010 → 1000110111 → 1101100010
    明文      密文       明文
    ♥ 代表算法：
    (1) 数据加密标准 (Digital Encryption Standard, DES)算法
    主要采用替换和移位的方法加密。它用56位密钥对64位二进制数据块进行加密。
    (2) 三重DES
    用两个56位的密钥。
    (3) RC - 5(Rivest Cipher 5，里维斯特设计提出) （17年第8题）
    适用于大量明文进行加密并传输
    (4) 国际数据加密算法 (International Data Encryption Algorithm, IDEA)
    类似于DES，其密钥长度为128位。
    (5) 高级加密标准 (Advanced Encryption Standard, AES)算法
    基于排列和置换运算。
    2） 非对称加密技术
    ♥ 同样使用两个密钥：加密密钥和解密密钥，一个是公开的，一个是非公开的私有密钥。他们是一对，只有使用对应的密钥才能解密。
    ♥ 非对称加密有两个不同的体制：加密模型和认证模型。
     （1）加密模型：

     （2）认证模型：

♥ 特点
保密性比较好，消除了最终用户交换密钥的需要，但加密和解密花费时间长、速度慢，不适合于对文件加密，而只适用于对少量数据进行加密。
♥ 代表算法
RSA (Rivest, Shamir and Adleman)算法

由于密钥对中的私钥只有持有者才拥有，所以私钥是不可能进行交换的。（17年第9题）

  1. 认证技术
    1）Hash 函数与信息摘要（20年第12题）
    Hash 函数：输入一个长度不固定的字符串，返回一串固定长度的字符串，又称Hash值。
    • 单向Hash 函数用于产生信息摘要。
    • 对于特定的文件而言，信息摘要是唯一的。
    • 在某一特定的时间内，无法查找经Hash 操作后生成特定Hash 值的原报文，也无法查找两个经Hash 操作后生成相同Hash 值的不同报文。
    • 在数字签名中，可以解决验证签名和用户身份验证、不可抵赖性的问题。
    • MD2、MD4 和MD5 是被广泛使用的Hash 函数，它们产生一种128位的信息摘要。
    • 利用报文摘要算法生成报文摘要的目的是防止发送的报文被篡改（13年第7题）

2）数字签名（12年第7题/18年第12、13题）


♥ 数字签名和数字加密的区别和联系
（1）数字签名使用的是发送方的密钥对，任何拥有发送方公开密钥的人都可以验证数字签名的正确性；
数字加密使用的是接收方的密钥对，是多对一的关系，任何知道接收方公开密钥的人都可以向接收方发送数据，但只有唯一拥有接收方私有密钥的人才能对信息解密。
（2）数字签名只采用了非对称加密算法，它能保证发送信息的完整性、身份认证和不可否认性，但不能保证发送信息的保密性；
数字加密（数字信封）采用了对称密钥算法和非对称密钥算法相结合的方法，它能保证发送信息的保密性（18年第11题）

例题1：假定用户A、B 分别从I1、I2两个CA取得了各自的证书，I1、I2互换公钥是A 、B 互信的必要条件。（17年第9题）

例题2：用户A从CA获得用户B的数字证书，并利用（CA 的公钥）验证数字证书的真实性。（11年第7题）

字典攻击：在破解密码或密钥时，逐一尝试用户自定义词典中的可能密码(单词或短语)的攻击方式。与暴力破解的区别是，暴力破解会逐一尝试所有可能的组合密码，而字典攻击会使用一个预先定义好的单词列表(可能的密码)。
密码盐：在密码学中，是指通过在密码任意固定位置插入特定的字符串，让散列后的结果和使用原始密码的散列结果不相符，这种过程称为加盐。
如果密码泄露，黑客可以利用他们数据字典中的密码，加上泄露的密码盐，然后进行散列，然后再匹配，由于密码盐可以加在任意位置，也加大了破解的难度。所以即使密码盐泄露，字典攻击和不加盐时的效果是不一样的。

1.4.3 计算机可靠性 35

  1. 计算机可靠性概述
    （1）计算机系统的可靠性：是指从它开始运行（t=0）到某时刻 t 这段时间内能正常运行的概率，用R(t)表示。
    （2）计算机系统的失效率：是指单位时间内失效的元件数与元件总数的比例，用λ表示。
    （3）平均无故障时间（MTBF)：两次故障之间能正常工作的时间的平均值称为
    平均无故障时间MTBF=1/λ
    （4）计算机系统的可维修性：一般平均修复时间（MTRF）表示，指从故障发生到机器修复平均所需的时间。
    （5）计算机系统的可用性：指计算机的使用效率，它以系统在执行任务的任意时刻能正常工作的概率A表示。
    A=MTBF/(MTBF+MTRF)

  2. 计算机可靠模型（10年第2题/11年第6题/17年第4题/19年第4题）
    (1) 串联系统
    当且仅当所有的子系统都能正常工作时，系统才能正常工作。
    R = R1R2……RN
    (2) 并联系统
    只要有一个子系统正常工作，系统就能正常工作。
    R = 1 - (1- R1)(1- R2)……(1- RN)
    (3) N模冗余系统
    在N 个系统中，只要有n+1 个或n+1 个以上子系统能正常工作，系统就能正常的工作。

例题：

解析：计算机系统是一个复杂的系统，而且影响其可靠性的因素也非常繁复，很难直接对其进行可靠性分析。若采用串联方式，则系统可靠性为每个部件的乘积R=R1×R2×R3×…×Rn；若采用并联方式，则系统的可靠性为R=1-（1-R1）×（1-R2）×（1-R3）×…×（1-Rn）。
在本题中，既有并联又有串联，计算时首先我们要分别计算图中两个并联后的可靠度，它们分别为（1-（1-R）3）和（1-（1-R）2）。，然后是两者串联，根据串联的计算公式，可得系统的可靠度为
（1-（1-R）3）（1-（1-R）2）。

1.4.4 计算机系统的性能评价 38

补充知识点

1. 多媒体基础知识

媒体的分类（14年第12-13题）
媒体可分为感觉媒体、表示媒体、表现媒体、存储媒体和传输媒体。
(1) 感觉媒体
直接作用于人的感官，产生感觉（视、听、嗅、味、触觉）的媒体，语言、音乐、音响、图形、动画、数据、文字等都是感觉媒体。
(2) 表示媒体
指用来表示感觉媒体的数据编码。
(3) 表现媒体 （13年第13题）
进行信息输入或输出的媒体。如键盘
(4) 存储媒体
用于存储表示媒体的物理实体。如光盘
(5) 传输媒体
传输表示媒体的物理实体。如光缆

1.1 多媒体计算机系统
1.2 声音

声音是感觉媒体。（15年第12题）

声音的三个要素：
音强：即音量，是声音的强度，取决于声间的振幅。
音调：由声音的频率决定。
音色：指声音的感觉特性

1. 声音信号的数字化
（13年第11题）
A/D 转换是模拟信号转换为数字信号，比如声音转二进制；
D/A 转换是数字信号转换为模拟信号，比如二进制转声音。
(1) 采样（17年第13题）
每隔一个时间间隔就在模拟声音的波形上取一个幅度值，这个间隔时间称为采样频率。
常用的采样频率为8kHZ、11.025kHz、16kHz、22.05kHz(FM广播音质)、44.1kHz(CD音质)、48kHz(DVD音频或专业领域)，频率越高音质越好。采样频率不应低于声音信号最高频率的两倍。
(2) 量化
就是把经过采样得到的瞬时值将其幅度离散，即用一组规定的电平，把瞬时抽样用最接近的电平值来表示。
量化的级别通常用位(bit)来表示，位数越高则音质越好。
(3) 编码
将声音数据写成计算机的数据格式。
每秒钟所需的存储量可由下式估算出：
文件的字节数 = 采样频率(Hz) * 采样位数 *声道数/8

补充知识点：
（09年第12题）
亚音信号（次音信号）：频率范围 < 20Hz
音频信号：频率范围 20Hz~20kHz
超音频信号（超声波）：频率范围 > 20kHz

1.3 图形和图像

1.颜色
（1）颜色三要素
色调：人眼看到一种或多种波长的光时所产生的彩色感觉。
亮度：表示色所具有的亮度
饱和度：指某一颜色的深浅程度（或浓度）
2. 图像数据获取
3. 图像的属性
（1）分辨率（12年第12题/13年第12题/14年第14题/17年第14题）
是指组成一幅图像的像素密度；也是水平和垂直的像素表示；即用每英寸多少点（dpi）表示数字化图像的大小。
水平分辨率表明显示器水平方向上显示出的像素点数目，垂直分辨率表明垂直方向上显示出的像素点数目。显示深度是指显示器t 显示每个像素点颜色的二进制位数。
用300dpi来扫描一幅3*4英寸的彩色照片，那么得到一幅900 × 1200个像素点的图像
DPI (Dots Per Inch，每英寸点数) 通常用来描述数字图像输入设备（如图像扫描仪）或点阵图像输出设备（点阵打印机）输入或输出点阵图像的分辨率。

例：使用150DPI 的扫描分辨率扫描一幅3×4英寸的彩色照片，得到原始的24位真彩色图像的数据量是（）Byte （16年第14题）
解：150DPI的扫描分辨率表示每英寸的像素为150个。
(3×150)×(4×150)×24/8 = 810000
  1. 图像的压缩编码
    图像数据量=图像的总像素数×像素深度/8（Byte）
  2. 图像文件格式 （09年第13题）
    JPG
1.4 动画和视频
1.5 虚拟现实

补充知识点：
（16年第12题）
WAV 为微软公司开发的一种声音文件格式，它符合RIFF 文件规范，用于保存Windows 平台及其应用程序所广泛支持。
BMP(全称Bitmap)是Windows 操作系统中的标准图像文件格式，可以分为两类：设备相关位图（DDB）和设备无关位图（DIB），使用非常广。BMP文件所占的空间很大。
MP3 是一种音频压缩技术，其全称是动态影像专家压缩标准音频正面3
MOV 即QuickTime 影片格式，它是Apple 公司开发的一种音频、视频文件格式，用于存储常用数字媒体类型。

（16年第13题）
PowerPoint 是微软公司的演示文稿软件。
Premiere 是一款常用的视频编辑软件，由Adobe 公司推出，广泛应用于广告制作和电视节目制作中。
Acrobat 是由Adobe 公司开发的一款PDF (Portable Document Format) 编辑软件。
Photoshop 是由Adobe Systems 开发和发行的图像处理软件。

CIF(Common Intermediate Format) 常用的标准化图像格式。CIF 像素=352×288（11年第13题）

由ISO制定的MPEG系列标准中，MPEG-7称为“多媒体内容描述接口 "(multimedia content description interface)。该标准是建立对多媒体内容的描述标准，满足包括静止图像、图形、3D模型、音频、话音、视频以及以上元素组合在一起的合成多媒体信息的应用领域的要求，并兼顾标准的通用性和扩展性的要求。（11年第14题）

2. 数据表示和校验

  1. 进制的缩写
    二进制：Binary，简称 B
    八进制：Octal，简称 O
    十进制：Decimal，简称 D
    十六进制：Hexadecimal，简称 H

  2. 数的进制
    a. 二进制：用 0 和 1 表示

    b. 八进制：用 0~7 表示

    c. 十进制：用 0~9 表示

    d. 十六进制：用 0~9 和 A~F表示

  3. 进制转换
    (1) 十进制转为二/八/十六进制（整除取余法）：
    ① 正整数转换成二进制：
    把被转换的十进制整数反复地除以2，直到商为0，所得的余数（从末位读起）就是这个数的二进制表示。简称“除2取余法”。计算机内部表示数的字节单位是定长的，如8位，16位，或32位。所以，位数不够时，高位补零。
    例：（83）10=（01010011）2

    ② 负整数转换为二进制
    先是将对应的正整数转换成二进制后，对二进制取反，然后对结果再加一。
    例：（-83）10=（10101101）2

    ③ 小数位转换为二进制
    对小数点后面的数乘以2，取结果的整数部分（1或者0），然后再用小数部分再乘以2，再取结果的整数部分……以此类推，直到小数部分为0或者位数已经够了。
    例：0.125转换成二进制的小数部分0.001

    (2) 二/八/十六进制转为十进制（按权展开）
    ① 整数二进制用数值乘以2的幂次依次相加，小数二进制用数值乘以2的负幂次依次相加。

    ② 整数八进制用数值乘以8的幂次依次相加，小数八进制用数值乘以8的负幂次依次相加。

    ③ 整数十六进制用数值乘以16的幂次依次相加，小数十六进制用数值乘以16的负幂次依次相加。

    (3) 八/十六进制转换为二进制
    ① 八进制357(O)转为二进制：011101111

    ② 十六进制A6F(H) 转为二进制：101001101111

    内存
    1K= 2^10=1024KB=2 ^ 10B

C语言、C++、Shell、Python、Java语言及其他相近的语言使用字首“0x”，例如“0x5A3”。开头的“0”令解析器更易辨认数，而“x”则代表十六进制（就如“O”代表八进制）。在“0x”中的“x”可以大写或小写。对于字符量C语言中则以0x+两位十六进制数的方式表示，如0xFF。

机器字长为n，最高位是符号位，其定点整数的最大值为2^(n-1)-1（14年第2题）
机器字长为n，最高位为符号位，则剩余的n-1 位用来表示数值，其最大值是这n-1 位都为1 ，也就是2^(n-1)-1

海明码（09年第1题/14年第3题/17年第5题）
海明码是一种多重（复式）奇偶检错编码。它将信息用逻辑形式编码，以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。
在数据位之间插入 k 个校验位，通过扩大码距来实现检错和纠错。
设数据位是 n 位，校验位是 k 位，则 n 和 k 必须满足以下关系：

k常取满足该关系的最小值

在计算机中，各类运算等可以采用补码进行，特别是对于有符号数的运算。
在计算机中涉及补码的目的：
一是为了使符号位能与有效值部分一起参加运算，从而简化运算规则，使运算部件的设计更简单；
二是为了使减法运算转换为加法运算，进一步简化计算机中运算器的线路设计。
因此在计算机系统中常采用补码来表示和运算数据，原因是采用补码可以简化计算机运算部件的设计。

例：计算机指令一般包括操作码和地址码两部分，为分析执行一条指令，则其（操作码和地址码都应存入指令寄存器(IR)）
解：程序被加载到内存后开始运行，当CPU执行一条指令时，先把它从内存储器取到缓冲寄存器DR中，再送入IR暂存，指令译码器根据IR的内容产生各种微操作指令，控制其他的组成部件工作，完成所需的功能。
指令寄存器(IR) 用来保存当前正在执行的一条指令。当执行一条指令时，先把它从内存取到数据寄存器(DR) 中，然后再传送到IR。而指令又分为操作码和地址码。

3. 逻辑运算

（10年第4题/12年第20题/17年第2题）
• 逻辑与（又称逻辑乘，类似于且，AND）：两个操作数同时为真则为真，否则哪怕有一个操作数为假，则为假。
• 逻辑或（又称逻辑加，类似于或，OR）：两个操作数只要其中一个为真即为真。
• 逻辑异或：（相异为真，相同为假）
• 逻辑非（NOT，类似于取反，！-）：操作数为真，则结果为假；操作数为假，则结果为真。

例题：
17年第2题
要判断字长为16位的整数a的低四位是否全为0，则（A ）
A. 将a与0x000F进行"逻辑与"运算，然后判断运算结果是否等于0
B. 将a与0x000F进行"逻辑或"运算，然后判断运算结果是否等于F
C. 将a与0xFFF0进行"逻辑异或"运算，然后判断运算结果是否等于0
D. 将a与0xFFF0进行"逻辑与"运算，然后判断运算结果是否等于F

12年第20题
对于逻辑表达式“x and y or not z”，and、or、not分别是逻辑与、或、非运算，优先级从高到低为not、and、or，and、or为左结合，not为右结合，若进行短路计算，则（ ）。
A. x为真时，整个表达式的值即为真，不需要计算y和z的值
B. x为假时，整个表达式的值即为假，不需要计算y和z的值
C. x为真时，根据y的值决定是否需要计算z的值
D. x为假时，根据y的值决定是否需要计算z的值

补充知识点：
在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的。出现概率高的字符使用较短的编码，出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的。（11年第12题）

常用的寻址方式：（12年第4题）
（1）立即寻址。操作数就包含在指令中。
（2）直接寻址。操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址。
（3）寄存器寻址。操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名。
（4）寄存器间接寻址。操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中。
（5）间接寻址。指令中给出操作数地址的地址。
（6）相对寻址。指令地址码给出的是一个偏移量（可正可负），操作数地址等于本条指令的地址加上该偏移量。
（7）变址寻址。操作数地址等于变址寄存器的内容加偏移量。

第2章 程序语言基础知识

2.1 程序语言概述…… 42

2.1.1 程序语言的基本概念…… 42

  1. 低级语言和高级语言
    • 低级语言：机器语言和汇编语言。是一种面向机器的语言，其格式取决于计算机的机器指令。难以理解，程序可读性差，程序设计效率低。
    • 高级语言：面向各类应用的程序语言。如Java、C、C++、Python、PHP、JavaScript等等。与人们使用的语言较为接近，便于理解，提高了程序设计的效率。
    HTML 是超文本标记语言，超文本是指页面内可以包含图片、链接甚至音乐、程序等非文字元素；PHP（超文本预处理器）是一种通用开源脚本语言，它将程序嵌入到HTML 文档中去执行，从而产生动态网页。（14年第20题）
  2. 编译程序和解释程序
    高级程序语言必须进行翻译才能为计算机硬件所理解，常用的翻译方式有汇编、解释和编译。
    • 用汇编语言编写的：需要汇编程序翻译成目标程序，然后执行目标程序。
    • 用高级语言编写的：需要解释程序或编译程序进行翻译，然后再运行。
    （1）解释程序（解释器）：要么直接解释执行源程序，要么将源程序翻译成某种中间代码后再加以执行。它按源程序中语句的执行顺序，逐条翻译并立即执行相关功能。
    （2）编译程序（编译器）：将源程序翻译成目标程序（目标代码），然后再在计算机上运行目标程序。一般分为两个阶段：
    编译阶段：把源程序翻译成目标程序。
    运行阶段：执行目标程序。
    编绎和解释的区别（13年第20题/16年第20题）
    • 编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程。
    • 解释方式下，解释程序和源程序（或其某种等价表示）要参与到程序的运行过程中，运行程序的控制权在解释程序。
    简单来说，在解释方式下，翻译源程序时不生成独立的目标程序，
    而编译器则将源程序翻译成独立保存的目标程序。
    • 编译比解释方式可能取得更高的效率。
    • 解释方式比编译方式更灵活
    • 解释方式可移植性好。

反编译是编译的逆过程。反编译通常不能把可执行文件还原成高级语言源代码，只能转换成功能上等价的汇编程序。（09年第24题）

  1. 程序设计语言的定义
  2. 程序设计语言的分类

补充说明：（09年第25题）
Javasript 并不是严格意义的面向对象语言，而是一种基于对象、事件驱动编程的客户端动态脚本语言。
Ruby 是一种开源的面向对象程序设计的服务器端动态脚本语言。

脚本语言是为了缩短传统的编写-编译-链接-运行过程而创建的计算机编程语言。此命名起源于一个脚本“screenplay”，每次运行都会使对话框逐字重复。早期的脚本语言经常成为批处理语言或工作控制语言。一个脚本通常是解释运行而非编译。（16年第21题）

2.1.2 程序语言的基本成分…… 46

程序设计语言的基本成分：（19年第23题）
(1) 数据
(2) 运算
(3) 控制
顺序、选择、循环
(4) 传输

  1. 程序语言的数据成分
    1）常量和变量
    按照程序运行时数据的值能否改变，将程序中的数据分为常量和变量。
    2）全局变量和局部变量
    按数据的作用域范围，可将其分为全局变量和局部变量。
    系统为全局变量分配的存储空间在程序运行的过程中一般是不改变的，而为局部变量分配的存储单元是可以动态改变的。
    全局变量的存储空间在静态数据区。（15年第22题）
    局部变量的定义：凡是在函数内部定义的变量都是局部变量，包括在函数内部复合语句中定义的变量和函数形参表中说明的形式参数。局部变量只能在函数内部使用，其作用域是从定义位置起至函数体或复合语句体结束为止。局部变量的值通常在其生存期内是变化的。
    3）数据类型
    • 基本类型：整型、字符型、实型和布尔类型
    • 特殊类型：空类型
    • 用户定义类型：枚举类型
    • 构造类型：数组、结构、联合
    • 指针类型：type *
    • 抽象数据类型：类类型
    补充知识点：程序中的数据具有数据属性时，j流可以规定数据对象的取值范围及能够进行的运算，在运算进行前便于进行类型检查，也更有利于为数据合理分配存储单元。（11年第22题）
  2. 程序语言的运算成分
  3. 程序语言的控制成分
    1）顺序结构
      计算过程从所描述的第一个操作开始，按顺序依次执行后续的操作，直到序列的最后一个操作。
    2）选择结构
      选择结构提供了在两种或多种分支中选择其中一个的逻辑。（if else）
    3）循环结构
      循环结构描述了重复计算的过程，通常由三部分组成：初始化、循环体和循环条件(while )
  4. 函数
    函数是一段具有独立功能的程序代码。
    1）函数定义
    C/C++程序中所有函数的定义都是独立的。不允许函数的嵌套定义。
    2）函数声明
    先声明后引用
    3）函数调用 （09年第23题）
    函数调用时基本的参数传递方式有两种：传值调用和引用调用。（13年第21题）
    （1）传值调用
    • 信息传递是单向的，只能将实参的值传递给形参，而形参不能再将值传递给实参。
    • 实参可以是常量（表达式），也可以是变量（数组元素）。
    例： int sum(int x, int y) {
        int z;
        z=x+y;
        return z; }
    函数调用时：sum(2,3)
    （2）引用调用（传地址调用） （14年第21题）
    • 在这种方式下，将实参的地址传递给形参。可以认为形参名实际上是实参的别名，被调函数中对形参的访问和修改实际上就是对实参的访问和修改。因此客观上可以实现双向传递。
    • 因此只能是变量（数组元素），而不能是常量（表达式）。
    例： void swap(int &x, int &y) {
       int temp;
       temp=x; x=y; y=temp }
    函数调用时：sum(a,b)

在程序中，可由程序员（用户）命名的有变量、函数和数据类型（17年第20题）

2.2 程序语言翻译基础…… 52

2.2.1 汇编程序基本原理…… 52

2.2.2 编译程序基本原理…… 54

  1. 编译过程概述
    编译程序的作用是把某种高级语言书写的源程序翻译成与之等价的目
    标程序，其工作过程一般可以分为6个阶段：

编译过程
（1）词法分析
• 任务：对源程序从前到后（从左到右）逐个字符地扫描，从中识别出 一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位， 如关键字（保留字）、标识符、常数、运算符和标点符号、左右括号等。
（2）语法分析 （17年第22题）
• 任务：根据语言的语法规则，在词法分析的基础上，分析单词串是否构成短语和句子，即是否为合法的表达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。
• 如果源程序没有语法错误，语法分析后就能正确地构造出其语法树。
（3）语义分析 （21年上）
• 任务：分析各语法结构的含义，检查源程序是否包含静态语义错误， 并收集类型信息供后面的代码生成阶段使用。
• 语义分析的一个主要工作是进行类型分析和检查。一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如：整除取余运算符只能对整型数据进行运算，如果运算对象为浮点数，则认为是一种类型不匹配的错误。
（4）中间代码生成
• 任务：根据语义分析的输出生成中间代码。
• 常用的中间代码有：
  ① 后缀式（逆波兰式）（10年第17题/11年第20题）
  优点：根据运算对象和运算符的出现次序进行计算，不需要使用括号，也便于使用栈实现求值。
  ② 四元式（三地址码）（16年第22题）
（操作符，操作数1，操作数2，结果）
  ③ 树形表示
（5）代码优化
• 由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进 行的，因此，生成的中间代码往往在时间和空间方面的效率较差。当 需要生成高效的目标代码时，就必须进行优化。
• 优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段 进行。
（6）目标代码生成
• 目标代码生成是编译器工作的最后一个阶段。
• 任务：把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码和汇编指令代码。
• 这个阶段的工作与具体的机器密切相关。
（7）符号表管理（10年第18题/14年第22题）
作用：记录源程序中各种符号（变量等）的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。
符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。
（8）出错处理
源程序中不可避免地会有一些错误，大致分为静态错误和动态错误。
① 动态错误发生在程序运行时，如：变量取零时作除数、引用数组下标错误等。
② 静态错误是指编译阶段发现的程序错误，可分为语法错误和静态语义错误。
  i 语法错误：单词拼写错误、标点符号错、表达式中缺少操作数、括号不匹配等 有关语言结构上的错误。
  ii 静态语义错误：语义分析时发现的运算符和运算对象类型不合法等错误。

（17年第21题）

2.2.3 解释程序基本原理…… 73

编译和解释的区别：（19年第21题）
在编译方式下，机器上运行的是与源码程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程，程序运行速度快；而在解释方式下，解释程序和源程序（或其某种等价表示）要参与到程序的运行过程中，运行程序的控制权在解释程序，边解释边执行，程序运行速度慢。

补充知识点

中缀、前缀与后缀表达式

基础概念
（1） 中缀表达式：
   即我们通常所使用的表达式。如(a+b)c-d
（2）前缀表达式（波兰式）：
   将运算符写在前面，操作数写在后面，且不使用括号。如-×+abcd
（3）后缀表达式（逆波兰式）：
   将运算符写在后面，操作数写在前面，且不使用括号。ab+cd-
三种表达式之间的转换（11年第21题/12年第22题）
例：（a+b)×c-d
（1）中缀表达式转前缀表达式：
  ① 按计算顺序全部加上括号： (((a+b)×c)-d)
  ② 把每一对括号内的运算符移到括号前面： -(×(+(ab)c)d)
  ③ 把所有括号去掉：-×+abcd
（2）中缀表达式转后缀表达式：
  ① 按计算顺序全部加上括号： (((a+b)×c)-d)
  ② 把每一对括号内的运算符移到括号后面： (((ab)+c)d)-
  ③ 把所有括号去掉：ab+cd-

逻辑与运算优先级高于逻辑或
逻辑与运算的短路求值逻辑：若x为假，则可知“x^y” 的值为假，无需再对y求值，因此只有在x为真时继续对y 求值

第3章 数据结构与算法

3.1 线性结构

3.1.1 线性表

  1. 线性表的定义
    一个线性表是n个元素的有限序列（n≥0），通常表示为（a1，a2， a3，……，an）。
  2. 线性表的存储结构
    (1) 顺序存储
    用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。
    优点：可以随机存取表中的元素
    缺点：插入和删除操作需要移动大量的元素

    (2) 链式存储
    用节点来存储数据元素，元素的节点地址可以是连续的，也可以是不连续的。
    优点：插入和删除操作不需要移动元素
    缺点：不能进行数据元素的随机访问

    链表的类别：
    单链表：
    单链表存储不能随机访问表中的任一结点，必须从头结点依次.next。
    循环链表：

    双向链表：

线性表的查找方法 （09年第26题）
(1) 顺序查找
算法非常简单，但是效率较低，因为它是用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。
(2) 折半查找
优点是比较次数少，查找速度快，平均性能好；
缺点是要求待查表是有序表，且插入和删除困难。
适用于不经常变动而查找频繁的有序列表。
一般不进行表的插入和删除操作。
需要对中间元素进行快速定位，在链表结构上无法实现。
(3) 分块查找
又称索引查找，主要用于分块有序表的查找。所谓分块有序是指将线性表 L (一堆数组)分成m个子表(要求每个子表的长度相等)，且第 i+1 个子表中的每一个项目均大于第 i 个子表中的所有项目。因此，分块查找的关键在于建立索引表，其查找的平均长度介于顺序查找和折半查找之间。

3.1.2 栈和队列

  1. 栈 （21年第5题）
    1）栈的定义和基本运算
    2）栈的存储结构
    栈是按“后进先出”的规则进行操作的。
    （1）顺序栈
    用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素。
    存储空间是预先定义或申请的，因此可能会出现栈满的情况。每一个元素入栈时都要判断栈是否已满。需要设置一个头指针指到栈顶。需要附设指针 top 指示栈顶元素的位置
    （2）链栈
    用链表存储栈中的元素。栈中元素的插入和删除仅在栈顶进行，因此不必设置头节点，链表的头指针就是栈顶指针。
    3）栈的应用
    函数调用和返回控制是用栈实现的。（19年第22题）
  2. 队列
    1）队列的定义和基本运算
    2）队列的存储结构
    队列是按“先进先出”的规则进行操作的。 （21年第7题）
    （1）顺序队列
    用一组地址连续的存储单元依次存储队列的数据元素。由于队中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针。
    （2）链队列
    为了便于操作，可给链队列添加一个头节点，并令头指针指向头节点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头节点。

例题：
设栈 s 和队列 q 的初始状态为空，元素a、b、c、d、e依次进入栈s，当一个元素从栈中出来后立即进入队列q。若从队列的输出端依次得到元素c、d、b、a、e，则栈s的容量至少为（）
解：看栈最多的时候能容纳多少元素。

3.1.3 串

字符串是一串文字及符号的简称，是一种特殊的线性表。
字符串的基本数据元素是字符，常常把一个串作为一个整体来处理。

  1. 串的定义及基本运算
    串是仅由字符构成的有限序列，是取值范围受限的线性表。
    一般记为 S=‘a1a2…an’,其中 S 是串名，单引号括起来的字符序列是串值。
    • 串长：即串的长度，指字符串中的字符个数。
    • 空串：长度为0的空串，空串不包含任何字符。
    • 空格串：由一个或多个空格组成的串。
    • 子串：由串中任意长度的连续字符构成的序列称为子串。
    • 串相等：指两个串长度相等且对应位置上的字符也相同。
    • 串比较：两个串比较大小时以字符的ASCII码值作为依据。

  2. 串的存储结构
    （1）顺序存储：用一组地址连续的存储单元来存储串值的字符序列

    （2）链式存储：字符串可以采用链表作为存储结构，当用链表存储串 中的字符时，每个结点中可以存储一个字符，也可以存储多个字符。

  3. 字符串运算

  4. 串的模式比较

3.2 数组和矩阵 87

  1. 数组
    1）数组的定义及基本运算
    一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长 线性表在维数上的扩张，即线性表中的元素又是一个线性表。
    2）数组的顺序存储
    由于数组一般不做插入和删除，且元素个数和元素之间的关系不再发生变动，那 么数组适合采用顺序存储结构。
    二维数组的存储结构可分为以行为主序（按行存储）和以列为主序 （按列存储）两种方法。
    设每个数据元素占用L个单元，m、n为数组的行数和列数，那么：
    以行为主序优先存储的地址计算公式为： Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
    以列为主序优先存储的地址计算公式为： Loc(aij)=Loc(a11)+((j-1)×m+(i-1))×L

  2. 矩阵
    • 这里主要讨论一些特殊矩阵的压缩存储的问题。

• 对多个值相同的元素可以只分配一个存储单元，零元素不分配存储单 元。
• 下面主要讨论对称矩阵、三对角矩阵、稀疏矩阵。
1） 特殊矩阵
（1）对称矩阵
若矩阵An×n中的元素有aij=aji（1≤i，j≤n）的特点，则称之为对称矩阵。 如：
• 则矩阵An×n的n2个元素可以压缩存储到可以存放n(n+1)/2个元素的存储 空间中。 • 假设以行为主序存储下三角（包括对角线）中的元素，并以一个一维 数组B[n(n+1)/2]作为n阶对称矩阵A中元素的存储空间，则B[k] （0≤k<n(n+1)/2）与矩阵元素aij（aji）之间存在着一一对应的关系：
（2）三对角矩阵
• 对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区 域中，其余的矩阵元素都为零。
• 下面主要考虑三对角矩阵，即只有主对角线及其左右两边为非零元素。
• 若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B[k] （0≤k<3n-2）中，则元素位置之间的对应关系为： k=3 × (i-1)-1+j-i+1=2i+j-3 (1≤i,j≤n)

2）稀疏矩阵：
• 在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元 素的分布没有规律，则称之为稀疏矩阵。
• 可以用一个三元组(i,j,aij）唯一确定矩阵中的一个元素。

3.3 树和图 90

3.3.1 树 90

  1. 树的定义
    树是n(n≥0)个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点；其余结点可分为m(m≥0)个互不相交的有限集T1,T2…,Tm，其中每个集合又都是一棵树，并且称为根结点的子树。
    （1）双亲、孩子和兄弟
    （2）结点的度：一个结点的子树的个数记为该结点的度。
    （3）叶子结点：也称为终端结点，指度为零的结点。
    （4）内部结点：度不为零的结点称为分支结点或非终端结点。除根结点之外，分支 结点也称为内部结点。
    （5）结点的层次：根为第一层，根的孩子在第二层，依此类推。
    （6）树的高度：一棵树的最大层次数记为树的高度（或深度）。
    （7）有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能 交换，则称该树为有序树，否则称为无序树。
    （8）森林：m(m≥0)棵互不相交的树的集合。
  2. 二叉树的定义
    定义：二叉树是n(n≥0) 个结点的有限集合，它或者是空树 (n=0)，或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树所组成。

    树和二叉树的区别：
    （1）二叉树中结点的子树要区分左子树和右子树， 即使只有一棵子树，而树中不用区分。
    （2）二叉树中结点的最大度为 2，而树中无限制。
  3. 二叉树的性质 （21年第8题）
    性质1：二叉树第i（i≥1）层上至多有 2^(i-1) 个节点。
    性质2：深度为k 的二叉树至多有 2^k-1 个结点（k≥1）。
    性质3：对任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则 n0=n2+1
    性质4：具有n个结点的完全二叉树的深度为log2n + 1
  4. 二叉树的存储结构
    1）二叉树的顺序存储结构

    2）二叉树的链式存储结构
  5. 二叉树的遍历 （15年第21题）
    遍历是按某种策略访问树中的每个结点，且仅访问一次。
    依据访问根结点次序的不同，可分为前序遍历法、中序遍历法、后序遍历法。
    （1）中序遍历法：（左、根、右）
    ① 中序遍历根的左子树。
    ② 访问根结点。
    ③ 中序遍历根的右子树。
    依此类推。
    （2）前序遍历法：先访问根结点（根、左、右）
    （3）后序遍历法：后访问根结点（左、右，根）
    （4）层序遍历法：按层从上至下、每层从左至右的顺序遍历

    前序遍历：A B E F I J C D G H
    后序遍历：E I J F B C G H D A
    层次遍历：A B C D E F G H I J
  6. 最优二叉树
    最优二叉树又称哈夫曼树，是一类带权路径长度最短的树。
    • 权：是一个人为的概念，表示计算机对每个结点的访问频率。
    • 路径长度：是每一个结点到根结点的路径的长度。
    • 结点的带权路径长度：是指从该结点到根结点之间的路径长度与该结点权的乘积。
    • 树的带权路径长度为树中所有叶子结点的带权路径长度之和。
    • 构造最优二叉树的哈夫曼方法：
    （1）根据给定的 n 个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1,T2，…，Tn}， 其中每棵树 Ti 只有一个带权为 wi 的根结点，其左右子树均空。
    （2）在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树， 置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
    （3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。 重复（2）（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
    • 最优二叉树的一个应用是对字符集中的字符进行编码和译码。
  7. 二叉查找树 （二叉排序树）（09年第27题）
    • 它或者是一棵空树，或者是具有如下性质的二叉树：
    （1）若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值。
    （2）若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值。
    （3）左、右子树本身就是两棵二叉查找树。
    • 对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。
    • 二叉查找树的作用：使用二叉查找树来查找树中的数值比普通的二叉树更为方便。
    • 构造二叉树时需进行平衡华处理，使每个节点左右子树的高度的绝对值不超过1。

给定N个权值作为N个叶子结点，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
霍夫曼树可以用来进行通信电文的编码和解码。

B-树是一种平衡的多路查找树
(1) B-树中，所有非终端结点也就是非叶子结点都会包含关键字；
(2) 所有叶子结点都出现在同一层次上并且不带信息（可以看作是外部结点或查找失败的结点），层次相同也就是高度相同，从根结点到每个叶子结点的路径长度相同；
(3) 所有非终端结点包含的关键字数量是不确定的，指向的子树个数也是不确定的。

3.3.2 图 97

1. 图的定义及术语
图G（Graph）是由两个集合：V和E所组成的，V是有限的非空顶点 （Vertex）集合，E是用顶点表示的边（Edge）集合，图G的顶点集和边集分别记为V（G）和E（G），而将图G记作G=(V，E)。
可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。
在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示
1）有向图：图中每条边都是有方向的。从顶点vi到顶点vj表示为<vi,vj>， 而从顶点vj到顶点vi表示为<vj,vi>。有向边也称为弧。起点称为弧尾， 终点称为弧头。

有向图a的顶点集合为： V(a)={1，2，3，4}
边的集合为： E(a)={<1, 2>，<1, 3>，<4, 2>，<1, 4>，<4, 1>}
2）无向图：图中每条边都是无方向的。顶点 vi和 vj之间的边用(vi,vj)表 示。在无向图中，(vi,vj)和(vj,vi)表示的是同一条边。

左侧无向图b的顶点集合为： V(b)={1，2，3，4，5}
边的集合为： E(b)={(1, 2)，(1, 3)，(1, 4)，(4, 5)，(2, 3)，(3, 4)， (3, 5)}
3）完全图：若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图 共有n(n-1)/2条边，类似地，有n个顶点的有向完全图中弧的数目为 n(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。
4）度、出度、入度：
顶点 v 的度是指关联于该顶点的边的数目，记作D(v)
若为有向图，度表示该顶点的入度和出度之和
顶点的入度是以该顶点为终点的有向边的数目
顶点的出度指以该顶点为起点的有向边的数目
5）路径
6）子图
7）连通图
8）强连通图
9）网：边或者弧具有权值的图

  1. 图的存储结构
    1）邻接矩阵表示法


2）邻接链表表示法
邻接链表是为图的每一个顶点建立一个单链表，第i个单链表中的节点 表示依附于顶点vi的表（对于有向图是以vi为尾的弧）。
• 邻接链表中的表节点有表节点和表头节点两种类型：

无向图的邻接链表表示法

有向图的邻接链表表示法

带权值的网的邻接链表表示法

3.4 常用算法 102

3.4.1 算法概述 102

3.4.2 排序 105

可参考这篇博文，结合动画浅显易懂：六大排序算法
1. 直接插入排序
• 具体做法是：在插入第 i 个记录时，R1，R2，… ，Ri-1已经排好序，将记录Ri 的关键字 ki 依次与关键字 ki-1，ki-2，… ，k1进行比较，从而找到 Ri 应该插入的位置，插入位置及其后的记录依次向后移动。

例：
待排序列：35 12 67 29 51

第1步：35 
第2步：12 35 
第3步：12 35 67 
第4步：12 29 35 67 
第5步：12 29 35 51 67

2. 冒泡排序
• 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推
（左边大于右边交换一趟排下来最大的在右边）

待排序列：35 12 67 29 51
第一次冒泡排序：      
①：12 35 67 29 51       
②：12 35 67 29 51       
③：12 35 29 67 51   
④：12 35 29 51 67

第二次冒泡排序：      
①：12 35 29 51 67 
②：12 29 35 51 67

3. 简单选择排序 （不稳定的排序算法） （21年上第6题）
• n个记录进行简单选择排序的基本方法是： 通过 n-i 次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i（1≤i≤n）个记录进行交换，当 i 等于 n 时所有记录有序排列
找出每次剩下数字中的最小值

例：
待排序列：35 12 67 29 51 
①：找出最小值12，与第一个关键字进行交换：12 35 67 29 51 
②：找出剩下4个记录中的最小值29，与第二个关键字交换：12 29 67 35 51 
③：找出剩下3个记录中的最小值35，与第三个关键字交换：12 29 35 67 51 
④：找出剩下2个记录中的最小值51，与第四个关键字交换：12 29 35 51 67

4. 希尔排序
• 希尔排序又称 “缩小增量排序”，是对直接插入排序方法的改进。 （21年上第9题）
• 先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序

例：
待排序列：  48 37 64 96 75 12 26 48 54 03  
d1=5（距离为5的倍数的记录为同一组）： 48 37 64 96 75 12 26 48 54 03  
d1=5           			   排序后： 12 26 48 54 03 48 37 64 96 75   
d2=3（距离为3的倍数的记录为同一组）： 12 26 48 54 03 48 37 64 96 75   
d2=3                       排序后： 12 03 48 37 26 48 54 64 96 75   
d3=1（距离为1的倍数的记录为同一组，即所有记录为一组）： 12 03 48 37 26 48 54 64 96 75 
d3=1                                       排序后： 03 12 26 37 48 48 54 64 75 96

5. 快速排序
• 通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
• 具体做法：附设两个位置指示变量 i 和 j ,它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为 pivot，则首先从 j 所指位置起向前搜索，找到第一个关键字小于 pivot 的记录时将该记录向前移到 i 指示的位置，然后从 i 所指位置起向 后搜索，找到第一个关键字大于 pivot 的记录时将该记录向后移到 j 所指位置，重复该过程直至 i 与 j 相等为止

3.4.3 查找 112

3.4.4 递归算法 122

3.4.5 图的相关算法 123

第4章 操作系统知识 128

4.1 操作系统基础知识 128

4.1.1 操作系统的基本概念 128

  1. 操作系统定义及作用
    定义/目的：（14年第23题）
    能有效地组织和管理系统中的各种软/硬件资源，合理地组织计算机系统的工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口
    作用：
    （1）通过资源管理提高计算机系统的效率
    （2）改善人机界面向用户提供友好的工作环境
  2. 操作系统的特征与功能
    特征：
    ①并发性
    ②共享性
    ③虚拟性
    ④不确定性
    功能：（20年第18题）
    ① 处理机管理（进程管理）
    进程调度，在单用户单任务的情况下，处理器仅为一个用户的一个任务所独占，进程管理的工作十分简单。
    ② 文件管理
    文件存储空间的管理、目录管理、文件操作管理、文件保护
    ③ 存储管理
    存储分配、存储共享、存储保护、存储扩张
    ④ 设备管理
    设备分配、设备传输控制、设备独立性
    ⑤ 作业管理

4.1.2 操作系统分类及特点 129

4.1.3 操作系统的发展 131

4.2 进程管理 131

进程是资源分配和独立运行的基本单位，进程两个基本属性：可拥有资源的独立单位；可独立调度和分配的基本单位。（20年第21题）

4.2.1 基本概念 132

  1. 程序与进程
  2. 进程的组成
    进程是程序的一次执行。
    进程通常是由程序、数据和进程控制块（Process Control Block, PCB）组成的。
  3. 进程的状态及其状态间的切换
    1）三态模型
     （1）运行：当一个进程在处理机上运行时，则称该进程处于运行状态。
     （2）就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行， 则称此进程处于就绪状态。
     （3）阻塞：也称等待或睡眠状态，一个进程正在等待某一事件发生而暂时停止运行。
    2）五态模型
    3）具有挂起状态的进程状态及其转换

4.2.2 进程的控制 135

4.2.3 进程间的通信 135

  1. 同步与互斥
    （1）进程间的同步：是指在系统中一些需要相互合作，协同工作的进程， 这样的相互联系称为进程的同步。
    （2）进程间的互斥：是指系统中多个进程因争用临界资源而互斥执行。临界资源是指有些资源一次只能供一个进程使用。如打印机、共享变量和表格等。
    （3） 临界区管理的原则
  2. 信号量机制
    1）整型信号量与PV 操作
      信号量是一个整型变量，根据控制对象的不同被赋予不同的值。
     （1）公用信号量：实现进程间的互斥，初值为1或资源的数目。
     （2）私用信号量：实现进程间的同步，初值为0或某个正整数。
      信号量S 的物理意义：S≥0表示某资源的可用数，S<0，则其绝对值表示阻塞队列中等待该资源的进程数。
      P 操作的定义：S=S-1,若S≥0，则执行P 操作的进程继续执行；若 S<0， 则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
      P 操作可以理解为：
        if((S=S-1)≥0)
        继续执行本进程
        else //(S=S-1)<0
        挂起本进程（本进程等待），转到另一个进程

      V 操作定义：S=S+1，若S>0，则执行V操作的进程继续执行；若S≤0，则 从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。
      V 操作可以理解为：
    if ((S=S+1)>0)
        不唤醒队列中的等待进程，继续执行本进程
        else //(S=S+1)≤0
        唤醒队列中的等待进程，同时继续执行本进程

    2）利用PV操作实现进程的互斥
    PV操作是实现进程同步与互斥的常用方法，P操作和V操作是低级通信原语，在执行期间不可分割。其中，P操作表示申请一个资源，V操作 表示释放一个资源。
    3）利用PV操作实现进程的同步

例题：生产者消费者问题
生产者进程P1不断地生产产品送入缓冲区，消费者进程P2不断地从缓冲区中取产品消费。

一个生产者和一个消费者，缓冲区中可存放n件产品，生产者不断地生产产品，消费者不断地消费产品，如何利用PV操作实现生产者和消费者的同步。

  1. 高级通信原语

4.2.4 管程139

4.2.4 进程调度139

  1. 三级调度（20年第19题）
    (1) 高级调度：长调度
    (2) 中级调度：中程调度，对换调度
    (3) 低级调度：短程调度，进程调度

4.2.5 死锁 140

（09年第21、22题）
死锁：是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。

  1. 死锁举例（10年第20题/11年第25-26题/14年第24-25题/17年第24题）
例：现有5个进程，每个进程都需要4个资源，而系统一共有15个资源， 会发生死锁吗？
系统中共有 n 个进程共享同一类资源，当每个进程都需要 k 个资源时， 至少需要多少个资源才不会发生死锁？
至少需要资源：M = (k-1)×n+1

♥ 注：不要死记公式，可以去了解哲学家进餐问题。假设有 n 个哲学家一起用餐，每个哲学家需要 2 支筷子才能够正常用餐，那么至少需要多少支筷子才可以保证 n 个哲学家都能正常用餐。可以想象 n 个哲学家围坐在一个圆桌前，先按顺序一人发一支筷子，那么只需要再多一支筷子就能满足条件。
3. 进程资源图
4. 死锁产生的原因及4个必要条件（21年第20题）
① 互斥条件
② 请求保持条件
③ 不可剥夺条件 ：破坏不可剥夺条件的方法就是强制剥夺资源
④ 环路条件
5. 死锁的处理
死锁的处理策略有：
① 鸵鸟策略（不理睬策略）
② 预防策略
③ 避免策略
④ 检测与解除死锁
1）死锁预防：采用某种策略限制并发进程对资源的请求。
（1）预先静态分配法：破坏“不可剥夺条件”
（2）资源有序分配法：破坏了“环路条件”
2）死锁避免：如银行家算法。（12年第23、24、25题）
银行家算法对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后系统进入不安全状态，则不予分配；若分配资源后系统仍处于安全状态，则实施分配。提高了资源的利用率，但是检测分配后系统是否安全增加了系统开销。

假设系统中有三类互斥资源R1、R2和R3，可用资源数分别为8、7和4，在T0时刻系统中有P1，P2，P3，P4，P5这5个进程，这些进程对资源的最大需求量和已分配资源数如下图所示。那么进程按什么序列执行，系统状态是安全的

解题思路
第一步：计算已经用掉的资源数和剩下可用的资源数：

R1R2R3
总资源数874
已经使用的资源数764
剩下的资源数110

第二步：计算进程还需要的资源数

R1R2R3
P1531
P2011
P3601
P4100
P5231

第三步：给确定接下来的进程执行顺序
还剩下1 1 0 ，那么可以先执行P4,
P4 执行完成之后释放资源后，资源所剩数目：2 3 1
可以执行的进程是P2 和P5，
如果限制性P2 ,那么执行完成后释放资源后所剩资源数：4 4 2
然后执行P5 ,执行完成后释放的资源数：

3）死锁检测：系统定时地运行一个程序来检测是否发生死锁，若有，则设法加以解除。
4）死锁解除：（21年上）
  ① 资源剥夺法
  ② 撤销进程法

4.2.6 线程 140

传统进程的两个基本属性：
① 可拥有资源的独立单位
② 可独立调度和分配的基本单位
传统进程在创建、撤销和切换中，系统必须为之付出较大的时空开销。

引入线程后：线程作为调度和分配的基本单位，进程作为独立分配资源的单位。
一个进程中有多个线程，共享该进程的资源。

线程基本不拥有资源，每个线程自己独有资源很少，线程共享地址空间，但线程的私有数据，线程栈又是单独保存的。（13年上第22题/21年上第19题）
不共享的资源：程序计数器、寄存器和栈。
多个线程共享的有：内存地址空间、代码、数据、文件，全局变量，记账信息等

线程的种类（根据操作系统内核是否对线程可感知）（20年第20题）
（1）用户级线程 （User-Level Threads）
不依赖于内核。该类线程的创建、撤销和切换都不利用系统调用来实现。 用户线程由应用程序所支持的线程实现，内核意识不到用户级线程的实现。
（2）内核支持线程（Kernel-Supported Threads）
依赖于内核。该类线程的创建、撤销和切换都利用系统 调用来实现。内核级线程又称为内核支持的线程。

4.3 存储管理 144

4.3.1 基本概念 145

1. 存储器的结构
（1） 逻辑地址（虚拟地址、相对地址）
程序员使用的地址只是用符号命名的一个地址，称为符号名地址，这个地址并不是主存中真实存在的地址。
（2）物理地址（绝对地址）
是主存中真实存在的地址。
（3）存储空间
逻辑地址空间（地址空间）是逻辑地址的集合，物理地址空间（存储空间）是物理地址的集合

2. 地址重定位
  一个程序，没有运行时，存储在外存，程序运行时，需要装载到内存中，就需要把程序中的指令和数据的逻辑地址转换为对应的物理地址， 这个转换的过程称为地址重定位。
  静态重定位：在程序装入主存时已经完成了逻辑地址到物理地址的变化，在程序的执行期间不会再发生变化。
  动态重定位：在程序运行期间完成逻辑地址到物理地址的变换。

4.3.2 存储管理方案 146

1. 分区存储管理
把主存划分成若干个区域，每个区域分配给一个作业使用。这就是分区存储管理方式。分为固定分区、可变分区和可重定位分区。
（1）固定分区：系统生成时已经分好区。
（2）可变分区：是一种动态分区方式，存储空间的划分是在作业装入时进行的，故分区的个数是可变的，分区的大小刚好等于作业的大小。
（3）可重定位分区：分配好的区域可以移动。

2. 分区保护

4.3.3 分页存储管理 147

  1. 纯分页存储管理
    （1）分页原理
    页：将进程的地址空间划分成若干个大小相等的区域。
    块或页框：将主存的空间也划分成与页相同大小的若干个物理块。
    在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。
    （2）地址结构

    （3）页表
    • 当进程的多个页面离散地分配到主存的多个物理块时，系统应能保证在主存中找到进程要访问的页面所对应的物理块，为此，系统为每个进程建立了一张页面映射表，简称页表。

  2. 块表
  3. 两级页表机制

4.3.4 分段存储管理 148

• 在分段存储管理中，将用户程序或作业的地址空间按内容划分为段，比如主程序 一段，子程序一段，数据专门放一段，每个段的长度是不等的，但是每个段占用一个连续的分区。进程中的各个段可以离散地分配到主存的不同分区中。在系统中为每个进程建立一张段映射表，简称为“段表”

4.3.5 段页式存储管理 150

• 先将整个主存划分成大小相等的存储块（页框）， 将用户程序按程序的逻辑关系分为若干个段，然后再将段划分成页。
段页式系统中同时有段表和页表：
• 段表：段号、页表始址、页表长度
• 页表：页号、物理块号
• 逻辑地址：段号、段内页号、页内地址
• 物理地址：块号、页内地址


4.3.6 虚拟存储管理 151

常用的虚拟管理器由主存-辅存两级存储器组成。（13年第1题）

  1. 程序局部性原理
    程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅限于某个部分，它所访问的存储空间也局限于某个区域内。
    （1）时间局限性：程序中的某条指令一旦执行，则不久的将来很有可能再次被访问；某个存储单元如果被访问，不久的将来它很可能再次被访问。
    （2）空间局限性：一旦程序访问了某个存储单元，则不久的将来，其附近的存储单元也最有可能被访问。
    • 如果我们运行程序的时候，允许将作业的一部分装入主存即可运行程序，而其余部分可以暂时留在磁盘上，等需要的时候再装入主存。这样一来，一个小的主存空间就可以运行比它大的一个作业。从用户角度看，系统具有的主存容量比实际的主存容量要大得多，称为虚拟存储器。

  2. 虚拟存储器的实现
    （1）请求分页系统
    （2）请求分段系统
    （3）请求段页式系统

  3. 请求分页管理的实现
    • 在纯分页的基础上增加了请求调页功能，页面置换功能。
    • 在请求分页系统中，每当所要访问的页面不在主存时便产生一个缺页中断。

  4. 页面置换算法
    （1）最佳置换算法
    是一种理想化的算法，即选择那些是永不使用的， 或者是在最长时间内不再被访问的页面置换出去。
    （2）先进先出置换算法 (FIFO)
    优先淘汰最先进入主存的页面，也就 是在内存中停留时间最长的页面。
    （3）最近最少未使用算法 (LRU)
    优先淘汰最近这段时间用得最少的页 面。系统为每一个页面设置一个访问字段，记录这个页面自上次被访问 以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。
    （4）最近未用置换算法 (NUR)
    优先淘汰最近一段时间未引用过的页面。 系统为每一个页面设置一个访问位，访问位为1代表访问过，为0代表没有被访问过，置换页面时选择访问位为0的置换出去。

4.4 设备管理 155

4.4.1 概述 155

4.4.2 I/O 软件 156

• 设备管理的目标主要是如何提高设备的利用率，即提高CPU与 I/O 设备之间的并行操作速度，并为用户提供方便、统一的界面。
• 为了提供设备的利用率，我们采用了“分层构造”的思想，即把设备管理软件组织成为一系列的层次。
• 主要分为4层：
① 中断处理程序（16年第23题）
当用户通过键盘或鼠标进入某应用系统时，通常最先获得键盘或鼠标输入信息的是中断处理程序
② 设备驱动程序
③ 与设备无关的系统软件
④ 用户级软件
• 各层之间既相互独立，又彼此协作

例：某用户进程现在需要读取硬盘中的数据。
① 与设备无关软件检查高速缓存中有没有要读的数据块，如果有，则直接从高速缓存中调取；如果没有，则调用设备驱动程序，向 I/O 硬件发出一个请求。
② 用户进程转为阻塞状态，等待磁盘操作的完成。磁盘操作完成时，硬件产生一个中断，转入中断处理程序。
③ 中断处理程序检查中断的原因，认识到这时磁盘读取数据的操作已经完成，于是唤醒用户进程取回从磁盘 读取的信息，此次 I/O 请求结束。
④ 用户进程得到了需要读取的数据内容，由阻塞转为就绪状态，继续运行。

按照是否可以被屏蔽，中断的种类（10年第3题）
（1）不可屏蔽中断（非屏蔽中断）
不可屏蔽中断源一旦提出请求，CPU 必须无条件响应，而对可屏蔽中断源的请求，CPU 可以响应，也可以不响应。
典型的非屏蔽中断源的例子是电源掉电
（2）可屏蔽中断
例子是打印机中断

4.4.3 设备管理采用的相关技术 157

  1. 通道技术
  2. DMA 技术
  3. 缓冲技术
  4. Spooling 技术
    • 目的：缓和CPU 的高速性和 I/O 设备的低速性之间的矛盾。
    • 原理：Spooling 技术引入了两个程序，分别实现脱机输入输出操作。预输入程序将输入设备上的数据通过输入缓冲区再传输到高速磁盘的输入井；缓输出程序将高速磁盘中输出井中的数据通过输出缓冲区传输到输出设备。CPU读写数据只需要在高速磁盘上进行，大大提高了工作效率。而且输入输出操作与CPU数据的处理同时进行，这种在联机情况下实现的输入输出与CPU 工作并行的技术叫做Spooling 或假脱机操作。

4.4.4 磁盘调度 160

磁盘调度的分类：先进行移臂调度，再进行旋转调度。
磁盘调度的目标是使磁盘的平均寻道时间最少。
读取磁盘数据的时间 = 寻道时间 + 旋转延迟 + 数据传输时间

  1. 移臂调度算法
    （1）先来先服务
    根据进程请求的先后次序进行调度。保证所有进程的请求都得到回应，但是平均寻道时间可能很长。
    （2）最短寻道时间优先
    选择访问的磁道与当前磁头所在的磁道距离最近的，使得每次的寻道时间最短。
    （3）扫描算法（类似电梯调度）
    不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向。
    （4）单向扫描调度算法
    在扫描算法的基础上，规定磁头只做单向移动。
  2. 旋转调度算法
    （1）如果进程请求访问的是不同编号的扇区（无论是否在同一磁道）， 则总是让首先到达磁头位置下的扇区先进行读写操作。
    （2）如果进程请求访问的是相同编号的扇区（无论是否在同一磁道）， 旋转调度时可以任选一个扇区进行读写操作。

4.5 文件管理 162

4.5.1 基本概念 163

4.5.2 文件的结构和组织 164

• 文件的逻辑结构：从用户角度看到的文件组织形式就是文件的逻辑结构，但实际上这些文件在内存上的存放方式可能并不是这样的。
（1）有结构的记录式文件
（2）无结构的流式文件
• 文件的物理结构：从实现的角度看，文件在存储器上的存放方式。
（1）连续结构
（2）链接结构
（3）索引结构
（4）多个物理块的索引表

4.5.3 文件目录 165

（1）一级目录结构：只有一张目录表，不允许重名，查找速度慢，不能实现文件共享。
（2）二级目录结构：由主文件目录和用户目录组成。
（3）多级目录结构：我们熟悉的Windows 系统，以及UNIX 系统都采用这种多级目录结构。
（14年第27题）
绝对路径：是指从根目录“\”开始的完整文件名，即它是由从根目录开始的所有目录名以及文件名构成。
相对路径：是从当前工作目录下的路径名。

4.5.4 存取方法和存储空间的管理 166

• 在将文件保存到外存时，我们首先要知道哪些存储空间是“占用”的， 哪些存储空间是“空闲”的。因此我们需要对磁盘空间进行管理。
• 常用的空闲空间的管理方法有空闲区表、位示图、空闲块链和成组链接法。
（1）空闲区表
操作系统为磁盘的所有空闲区建立一张空闲表。它适用于连续文件结构。

（2）位示图
在外存上建立一张位示图（bitmap），记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，0表示空闲，1表 示占用。

（3）空闲块链
每一个空闲物理块中设置一个指针，它指向下一个空 闲物理块，所有空闲物理块构成一个链表，链表的头指针放在文件存储 器的一个特定位置上（如管理块中）。
（4）成组链接法
在系统中将空闲块分成若干个组，每100个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。

4.5.5 文件的使用 168

4.5.6 文件的共享和保护 168

4.5.7 系统的安全与可靠性 169

4.6 作业管理 170

4.6.1 基本概念 170

4.6.2 作业调度 172

短期调度（进程调度 / 低级调度 / 微观调度）
一般情况下使用最多的就是短期调度，这也就是通常所说的调度。它的主要任务是按照某种策略和算法将处理机分配给一个处于就绪状态的进程，分为抢占式和非抢占式。
中期调度（交换调度）
核心思想是将进程从内存或从CPU竞争中移出，从而降低多道程序设计的程度，之后进程能被重新调入内存，并从中断处继续执行，这种交换的操作可以调整进程在内存中的存在数量和时机。
长期调度（作业调度/高级调度）
它的频率比较低，主要用来控制内存中进程的数量。

作业调度算法
（1）先来先服务
按作业到达的先后顺序进行调度。
（2）短作业优先
按作业运行时间的长短进行调度，即启动要求运行时间最短的作业。
（3）响应比高优先
响应比高的作业优先启动。
响应比：RP = 作业响应时间/作业执行时间 =（作业等待时间+作业执行时间）/作业执行时间
（4）优先级调度算法
按照系统设定的优先级或者用户指定的优先级， 优先级高的先调度。
（5）均衡调度算法
根据系统的运行情况和作业本身的特性对作业进x行分类，力求均衡地使用系统的各种资源，即注意发挥系统效率，又使用户满意。
例：假设所有作业同时到达，平均周转时间最短的调度算法是：短作业优先（21年上第18题）

时间片轮转调度 （13年第21题）
是一种最古老、最简单、最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
基本原理：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调整时，把CPU 分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便根据此信号来停止该进程的执行，并将它送往就绪队列的末尾，然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。因此用户一次响应的时间为 q=n×q
最适用于交互式系统。

4.6.3 用户界面 173

第五章 网络基础知识

5.1 计算机网络概述 174

5.1.1 计算机网络概念

5.1.2 计算机网络的分类

（1）局域网 (LAN)
传输距离有限，传输速度高，以共享网络资源为目的的网络系统。
（2）城域网 (MAN)
规模介于局域网和广域网之间的一种较大范围的高速网络，一般覆盖临近的多个单位和城市。
（3）广域网 (WAN)
又称远程网，它是指覆盖范围广、传输速率相对较低、以数据通信为主要目的的数据通信网。

5.1.3 网络的拓扑结构

概念：是指网络中通信线路和节点的几何顺序，用以表示整个网络的结构外貌，反映各节点之间的结构关系。
常见的网络拓扑结构有总线型、星型、环型、树型和分布式结构等


路由类型：
当一个Windows 服务器收到一个IP 数据包时，先查找主机路由，再查找网络路由（直连网络和远程网络），这些路由查找失败时，最后才查找默认路由。

路由类型说明
直连网络ID用于直接连接网络，Interface(或 next hop)可以为空
远程网络ID用于不直接连接的网络，可以通过其他路由器到达这种网络，Interface字段是本地路由器的 IP 地址
主机路由
(Host route)		到达特定主机的路由，子网掩码为255.255.255.255
默认路由
(Default route)		无法找到确定路由时使用的路由，目标网络和网络掩码都是0.0.0.0
持久路由
(Persistent route)		利用route add -p命令添加的表项，每次初始化时，这种路由都会加入Windows的注册表中，同时加入路由表

VLAN的优点：（15年第67题）
允许逻辑地划分网段。
把局域网划分成多个VLAN,使得网络接入不再局限于物理位置的约束，这样就简化了在网络中增加、移除和移动主机的操作，特别是动态的配置VLAN，无论主机在哪里，他都处于自己的VLAN中。

5.2 网络硬件基础 180

5.2.1 网络设备

（11年第68题/16年第7题）

  1. 网络传输介质互连设备
  2. 物理层的互连设备
    （1）中继器
    • 它是在物理层上实现局域网网段互连的，用于扩展局域网网段的长度。
    • 在以太网中最多只能使用4个中继器。
    （2）集线器
    • 从一个端口接收信息并向其他端口广播出去，可以看成是一种特殊的多路中继器。
    集线器的各个端口构成一个冲突域，即只能有一个端口发送数据，如果有两个端口同时发送就冲突了。
    集线器的其优点是当网络系统中某条线路节点出现故障时，不会影响网上其他节点的正常工作。
    • 分为无源和有源。无源集线器不对信号作任何处理，只负责将多段介 质连接在一起。有源集线器对传输信号进行再生和放大。
  3. 数据链路层的互连设备
    （1）网桥
    用于连接两个局域网网段，对帧进行过滤。
    • 过滤帧：网桥检查帧的源地址和目的地址，如果不在同一网段上，就把帧转发到另一个网段上， 如果在，则不转发。
    • 隔离不同网段：将不同楼层的网络分成不同的网络段，段中间用网桥连接，这样可以缓解网络通 信繁忙的程度，提高通信效率；另外还可以提高网络的可靠性，一个网络段发生故障不会影响另 一个网络段。
    （2）交换机
    • 多端口网桥，任何一对端口都能进行数据转发。交换机的各个端口构成一个广播域但不是冲突域，即可以有多个端口同时发送数据而不会出现冲突。
    按MAC 地址（物理地址）进行数据转发，比网桥的转发性能要高，数据延迟要小。
    • 交换机的工作过程：从某一节点收到帧后，在其内存的MAC 地址表（端口号-MAC地址）中进行查找， 确认该MAC 地址的网卡连接在哪一个节点，然后将帧转发至该节点。如果没有找到该MAC 地址，就 将数据包广播到所有节点，拥有该MAC 的网卡收到广播后做出应答，交换机将该MAC 地址添加到MAC 地址列表中。
    • 交换机有三种交换技术：端口交换、帧交换和信元交换。
  4. 网络层互联设备
    • 路由器：用于连接多个逻辑上分开的网络，例如不同的子网。
    • 路由器具有很强的异种网互连能力。例如：即使两个互连的网络最低两层的协议不同，也可通过支持多协议的路由器进行连接。
    • 路由器最主要的功能是选择路径。在路由器的存储器中维护着一个路径表，记录各个网络的逻辑地址，用于识别其他网络。
    • 路由器的工作过程：收到某个网络向另一个网络发送的信息包时，打开信息包，并解读信息包中的数据，获得目的网络的逻辑地址（IP地址），使用复杂的程序决定该由哪条路径发送最合适， 然后重新打包并转发出去。
    • 三层交换机：不仅包括所有交换机的功能，还包含了网络层的部分功能。一次路由，多次交换。
    • 工作原理：可以总结为“一次路由，多次交换”。当三层交换机第一次收到一个数据包时必须通过路由功能寻找转发端口，同时记住目标MAC 地址和源MAC 地址，以及其他相关信息，当再次收到目标地址和源地址相同的帧时就直接进行交换了，不再调用路由功能。三层交换机不但具有路由功能，而且比通常的路由器转发得更快。
    • 静态路由是固定路由，从不更新除非拓扑结构发生变化；
    洪泛式将路由信息发送到连接的所有路由器，不利用网络信息；
    随机路由是洪范式的简化；
    自适应路由依据网络信息进行代价计算，依据最小代价实时更新路由。（17年第70题）
  5. 应用层互联设备
    • 网关：主要功能是进行协议转换。
    • 当要连接不同类型而协议差别又较大的网络时，要选用网关设备。它可以将协议进行转换，并将数据重新分组，以便在两个不同类型的网络之间进行通信

总结： （16年第7题）

5.2.2 网络传输介质

  1. 双绞线
  2. 同轴电缆
  3. 光纤
  4. 微波
  5. 红外线和激光
  6. 卫星通信

5.3 网络的协议与标准 185

5.3.1 网络的标准

5.3.2 局域网协议

5.3.3广域网协议

5.3.4 TCP/IP协议簇

• TCP/IP 协议是Internet 的核心协议，是迄今为止发展最为成熟的互联网络协议 系统。TCP/IP 包含以下五个特性：
（1）逻辑编址。每一台连入互联网的设备都要分配一个IP地址，一个IP地址包 含网络号，子网络号和主机号，因此可以通过IP地址很方便地找到对应的设备。
（2）路由选择。在TCP/IP协议中包含了专门用于定义路由器如何选择网络路径 的协议，即IP数据包的路由选择。
（3）域名解析。为了方便用户记忆，专门设计了一种更方便的字母式地址结构， 称为域名。将域名映射为IP地址的操作，称为域名解析。
（4）错误检测与流量控制。TCP/IP协议可以检测数据信息的传输错误，确认已 传递的数据信息已被成功接收，监测网络系统中的信息流量，防止出现网络拥塞。

1. TCP/IP分层模型
在TCP/IP协议栈中，各层级的数据单元
应用层——消息、报文（message）
传输层——数据段（segment）
网络层——分组、数据包（packet）
链路层——帧（frame）
物理层——比特流

2. 网络接口层协议
3. 网际层协议IP
IP 所提供的服务通常被认为是无连接的和不可靠的，它将差错检测和流量控制之类的服务授权给了其他的各层协议，这正是TCP/IP 能够高效率工作的一个重要保证。
• 其主要功能包括：
（1）将上层数据（TCP/UDP数据）或同层的其他数据（如ICMP数据）封 装到IP数据报中
（2）将IP数据报传送到最终目的地
（3）为了使数据能够在链路层上进行传输对数据进行分段
（4）确定数据报到达其他网络中的目的地的路径

文件传输协议FTP利用TCP 连接在客户机和服务器之间上传和下载文件。FTP 协议占用了两个TCP 端口，FTP 服务器监听21号端口，准备接收用户的连接请求。当用户访问FTP 服务器时便主动与服务器的21号端口建立了控制连接。如果用户要求下载文件，则必须等待服务器的20号端口主动发出建立数据连接的请求，文件传输完成后数据连接随之释放。在客户端看来，这种处理方式被叫做被动式FTP，Windows系统中默认的就是这种处理方式。由于有的防火墙阻止由外向内主动发起的连接请求，所以FTP 数据连接可能由于防火墙的过滤而无法建立。为此有人发明了一种主动式FTP，即数据连接也是由客户端主动请求建立的，但是在服务器中接收数据连接的就不一定是20号端口了。
4. ARP和RARP
ARP协议（地址解析协议）（11年第66-67题）
用来将32位的IP 地址解析为48位的物理地址。
OSI 模型中ARP 协议属于数据链路层，而在TCP/IP 模型中，ARP 协议属于网络层。
RARP 是ARP 的逆过程，将物理地址转化为IP地址
实现IP 地址与MAC 地址之间的变换。

RARP（反向地址解析协议）
主要应用于无盘站，通过该协议从服务器上取得它的IP 地址。网络管理员在局域网网关路由器里创建一个表以映射物理地址（MAC）和对应的IP 地址。当机器启动时，其RARP 客户机程序需要向路由器上的RARP 服务器请求相应的IP地址。假设在路由表中已经设置了一个记录，RARP 服务器将会返回IP 地址给机器，此机器就会存储起来使用。

5. ICMP协议
由于IP协议是一个不可靠、非连接的尽力传送协议，数据报是采用分组交换方式在网络上传送的。因此当路由器不能够选择路由器或传送数据报时，或检测到一个异常条件影响它转发数据报时，就需要通知初始源网点采取措施避免问题。而完成这个任务的机制就是ICMP，它是IP 的一部分，属于网络层协议，其报文是封装在IP 协议数据单元中进行传送的，在网络中起到差错和拥塞控制的作用。

6. 传输层协议TCP
是一种面向连接的、可靠的、基于字节流的传输层通信协议。
TCP为了保证报文传输的可靠，给每个包一个序号，同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的字节发回一个确认（ACK）;如果发送端实体在合理的往返时延（RTT）内未收到确认，那么对应的数据（假设丢失）将会被重传。

TCP三次握手
第一次握手
客户端发送连接请求报文段，将SYN 设置为1，Seq为x；然后，客户端进入SYN_SEND 状态，等待服务器的确认。
第二次握手
服务器收到客户端的SYN 报文段，需要对这个SYN 报文段进行确认，设置ACK 为x+1(Seq + 1)；同时，自己还要发送SYN 请求信息，将SYN 置为1，Seq为y；服务器端将上述所有信息放到一个报文段（即SYN + ACK报文段）中，一并发送给客户端，此时服务器进入SYN_RECV状态
第三次握手
客户端收到服务器的SYN + ACK 报文段。然后将ACK 设置为y+1，向服务器发送ACK 报文段，这个报文段发送完毕以后，客户端和服务器端都进入ESTABLISHED状态，完成TCP 三次握手。

7. 传输层协议UDP
UDP (User Datagram Protocol，用户数据报协议)是一种无连接的传输层协议，它主要用于不要求分组顺序到达的传输中，分组传输顺序的检查与排序由应用层完成，提供简单的不可靠的信息传送服务。
UDP 报文没有可靠性保证、顺序保证和流量控制字段等，可靠性较差。但是正因为UDP 协议的控制选项较少，在数据传输过程中延迟小、数据传输效率高，适合对可靠性要求不高的应用程序，或者可以保障可靠性的应用程序，如DNS、TFTP、SNMP等
工作在UDP 协议之上的应用是 VoIP（VoiceOver Internet Protocol）。（13年第47题）
8. 应用层协议
默认情况下，FTP服务器的控制端口为21，数据端口 为20（16年第66题）
电子邮件应用程序利用POP3 协议接收邮件。
POP3 服务默认的TCP 端口号是110.（10年第46题）

5.4 Internet 基础知识 197

5.4.1 Inernet概述

5.4.2 Internet地址

  1. 域名
    （1）域名的格式
    • 计算机主机名.本地名.组名.最高层域名
    例：www.hust.edu；wwwnic；www.5566；www.sina
    （2）URL 的格式 （15年第68题）
    协议://主机.域名[:端口号]/路径/文件名
    例：http://210.42.87.56:80/ducument/admin/a1/index.html https://www.abc:443/text/a2/login.htm
    ftp://ftp.hust.edu/a3/img/b4.jpg
    • https 是一种通过计算机网络进行安全通信的传输协议，经由http 进行通信，利用SSL/TLS建立全信道，加密数据包。https 使用的主要目的是提供对网站服务器的身份认证，同时保护交换数据的隐私与完整性。

  2. IP地址
    （1）IP地址的格式：一个IP地址占4字节(32位)，转成十进制后，为4个十进制数字，中间用 “.” 隔开。每个十进制数字的取值范围为0~255。 129.102.4.11 10000001 01100110 00000100 00001011
    （2）IP地址的分类：IP地址可以分为5类：A类、B类、C类、D类、E类。

    ① A类地址：
    • 标识方法：最高位为0。
    • 真正的网络地址为1-7位（第2至第8位）。
    • 那么A类地址的第一个字节的十进制是0127，共支持1126个网络，即共有27-2个 网络号。
    • 主机地址为后24位，那么每个网络最多有224-2个主机地址。 • 为何要-2？因为：在IP地址中，全0代表的是网络地址，全1代表的是广播地址， 这两个为特殊用途IP地址，不可作为主机地址使用。

    ② B类地址：
    • 标识方法：最高位为10。
    • 真正的网络地址为2-15位（第3至第16位）。
    • 那么B类地址的第一个字节的十进制是128~191，共有214-2个网络号。
    • 主机地址为后面的16位，那么每个网络最多有216-2个主机地址。

    ③ C类地址：为我们最常见的IP地址。
    • 标识方法：最高位为110。
    • 真正的网络地址为3-23位（第4至第24位）。
    • 那么C类地址的第一个字节的十进制是192~223，共有221-2个网络号。
    • 主机地址为后面的8位，那么每个网络最多有28-2个主机地址。

    ④ D类地址：标识方法：最高位为1110。
    • 用于组播，例如用于路由器修改。D类网络地址第一个字节的十进制为224~239。

    ⑤ E类地址：标识方法：最高位为1111。
    • E类地址为实验保留。D类网络地址第一个字节的十进制为240~255。

  3. NAT技术

  4. IPv6简介
    • 现在的IP 协议的版本号为4，所以也称之为IPv4，IPv4 的IP 地址共32位，4个字 节，最多可以有232个IP 地址。
    • IPv6 的地址空间为128位，共16个字节，理论上最多可以有2128个IP 地址。
    • IPv6 采用冒号十六进制记法。16位为一组，用相应的十六进制表示，各组之间 用 “：” 分隔。
    例如：
    686E:8C64:FFFF:FFFF:0:1180:96A:FFFF
    • 允许0压缩，即一连串的0可以用一对冒号表示，如： FF05:0:0:0:0:0:0:B3 FF05::B3 • IPv6
    还可以和IPv4结合使用，如： 0:0:0:0:0:0:128.10.1.1 ::128.10.1.1

5.4.3 Internet服务

HTTPS (Hyper Text Transfer Protocol over Secure Socke Layer) 是以安全为目标的HTTP 通道，使用SSL 协议对报文进行封装。（16年第8题/17年第7题）

• 使用各类Internet服务时，可以使用端口号进行区分，TCP 和UDP 协议的端口号为 16位，支持065535的端口号。其中01023为公共端口，1024~65535需要注册登 记。

  1. 域名服务（DNS）（13年第48题/14年第69题）
    DNS 实现负载均衡是通过循环复用来实现的，如果发现主机名的多个地址资源记录，则可以用他循环使用包含在查询应答中的主机资源记录。默认情况下，DNS 服务器的服务使用就循环复用对资源记录进行排序，这些资源记录是在解析为多个映射的主机名应答中返回的。该功能用于对客户机使用Web 服务器和其他频繁查询的多宿主计算机的负载平衡。要使循环复用正常工作，必须首先在该区域中注册所查询名称的多个主机资源记录，并启用DNS 服务器循环复用。如果DNS 服务器禁止循环复用，那么这些查询的相应顺序以应答列表中资源记录在区域中存储时的静态排序为基础
  2. 远程登陆服务（Telnet）
  3. 电子邮件服务
  4. 万维网服务（WWW）
  5. 文件传输服务（FTP）
    使用的传输层协议是TCP。（15年第70题）
    补充知识点：DHCP 协议的功能是自动分配IP 地址。（15年第69题）

5.5 信息安全基础知识 210

（09年第8题）

  • CA 负责数字证书的审批、发放、归档、撤销等功能，CA颁发的数字证书拥有CA 的数字签名，所以除了CA 自身，其他机构无法不被察觉的改动。
  • CA 可以是民间团体，也可以是政府机构。
  • A 和B 要进行安全通信，必须相互获取对方的数字证书，A和B 的数字证书可以是由不同CA 颁发的。

例：假定用户A、B分别从I1、I2两个CA取得了各自的证书，（I1、I2互换公钥）是AB互信的必要条件。

系统的保护机制应该公开 （21年第10题）

5.6 网络安全概述 214

1. 常见的网络攻击技术
（1）篡改消息
是指一个合法消息的某些部分被修改、删除、延迟、重新排序等。
如修改传输消息中的数据，将“允许甲执行操作”改为“允许乙执行操作”。
（2）伪造（伪装、假冒）
是指某个实体假扮成其他实体，从而以欺骗的方式获取一些合法用户的权利和特权。
（3）重放（21年第14题）
是指攻击者发送一个目的主机已接收过的包，来达到欺骗系统的目的， 主要用于身份认证过程，破坏认证的正确性。
♥ 防范重放攻击的方法
  ① 加时间戳
  ② 一次一密的方式
（4）拒绝服务 (DOS)（21年上第11题）
是指攻击者不断地对网络服务系统进行干扰，改变其正常的作业流程，执行无关程序使系统响应减慢甚至瘫痪，影响正常用户的使用，甚至使合法用户被排斥而不能进入计算机网络系统或不能得到相应的服务。
注意：拒绝服务攻击并不会造成用户密码的泄露。

	① 宽带攻击指以极大的通信量冲击网络，使得所有可用网络资源都被消耗殆尽，最后导致合法的用户请求无法通过。
	② 连通性攻击指用大量的连接请求冲击计算机，使得所有可用的操作系统都被消耗殆尽，最终计算机无法再处理合法用户的请求。
	③ 分布式拒绝服务攻击DDoS是一种基于DoS的特殊形式的拒绝服务攻击，是一种分布的、协同的大规模攻击方式。

（5）窃听（截取）
是指攻击者在未经用户同意和认可的情况下获得了信息或相关的数据。（被动攻击）
（6）流量分析（通信量分析）
是指攻击者虽然从截获的消息中无法得到消息的真实内容， 但攻击者还是能通过观察这些数据报的模式，分析确定出通信双方的位置、通信的次数及消息的长度，获知相关的敏感信息。
（7）字典攻击
一种破解用户密码或密钥的一种攻击方式。事先将所有可能的密码口令形 成一个列表（字典），在破解密码或密钥时，逐一将字典中的密码口令（或组合）尝试进 行匹配。
（8）社会工程学攻击
是指通过与他人进行合法的交流，来使其心理受到影响，做出某些动作或者是透露一些机密信息的方式。这通常被认为是一种欺诈他人以收集信息、行骗和入侵计算机系统的行为。
（9）SQL注入攻击 （21年上第13题）
把SQL 命令插入Web 表单的输入域或页面的请求查找字符串，欺骗服务器执行恶意的SQL 命令。在某些表单中，用户输入的内容直接用来构造（或者影响）动态 SQL 命令，或作为存储过程的输入参数，这类表单特别容易受到SQL 注入式攻击。
（10）会话劫持
是指攻击者在初始授权之后建立一个连接，在会话劫持以后，攻击者具有合法用户的特权权限。
例如，一个合法用户登录一台主机，当工作完成后， 没有切断主机。然后，攻击者乘机接管，因为主机并不知道合法用户的连接已经断开，于是，攻击者能够使用合法用户的所有权限。典型的实例是“TCP会话劫持”。
（11）漏洞扫描（09年第7题）
是一种自动检测远程或本地主机安全漏洞的软件，通过漏洞扫描器可以自动发现系统的安全漏洞。
通常利用通过端口漏洞扫描来检测远程主机状态，获取权限从而攻击远程主机。（16年第9题）
（12）缓冲区溢出
攻击者利用缓冲区溢出漏洞，将特意构造的攻击代码植入有缓冲区漏洞的程序之中，改变漏洞程序的执行过程，就可以得到被攻击主机的控制权。

2. 主动攻击与被动攻击
（1）主动攻击
主动攻击会导致某些数据流被篡改或者产生虚假的数据流。如：篡改消息、伪造消息、重放和拒绝服务。
（2）被动攻击
与主动攻击不同的是，被动攻击中攻击者并不对数据信息做任何修改， 也不产生虚假的数据流。如窃听、流量分析等攻击方式。

3. 安全的分类
（1）物理安全
物理安全是保护计算机网络设备、设施以及其他媒体免 遭地震、水灾、火灾等环境事故及人为操作失误及各种计算机犯罪行为 导致的破坏。主要是场地安全与机房安全。
（2）网络安全
与网络相关的安全。
（3）系统安全
主要指操作系统的安全。
（4）应用安全
与应用系统相关的安全。

MIME 它是一个互联网标准，扩展了电子邮箱标准，使其能够支持，与安全无关。
PGP(Pretty Good Privacy，优良保密协议)，是一套用于信息加密、验证的应用程序。

特洛伊木马 （09年第9题/14年第7题）
通过网络传播的病毒，分为客户端和服务器端两部分，服务器端位于被感染的计算机，客户端是用来控制目标机器的部分，放在攻击者的机器上。特洛伊木马服务器运行后会试图建立网络连接，所以计算机感染特洛伊木马后的典型现象是有未知程序试图建立的网络连接。

“X卧底”
可以窃取手机上的通讯录、呼叫记录、短信记录等隐私数据，还能窃听通话。如果手机上有GPS 功能，“X卧底” 还能调用这项功能获得机主的位置。（13年第8题）
欢乐时光、熊猫烧香、CIH 都是针对计算机的病毒

蜜罐 （21年第12题）
蜜罐就是杀毒软件公司故意用一个防范很差的电脑上网，让它中毒，然后收录到病毒库，这样的杀毒软件就能不断的查杀新出现的病毒，这样引病毒上钩的防范措施就很差的电脑称为蜜罐

蠕虫病毒
不需要宿主程序，它是一段独立的程序或代码，因此也就避免了受宿主程序的牵制，可以不依赖于宿主程序而独立运行，从而主动的实施攻击

防火墙技术 （14年第9题）
防火墙阻挡对网络的非法访问和不安全数据的传递，使得本地系统和网络免于受到许多网络安全威胁。防火墙主要用于逻辑隔离外部网络与受保护的内部网络。
防火墙技术经历了包过滤、应用代理网关和状态检测技术三个发展阶段。

  1. 包过滤防火墙
    • 它处于网络层和数据链路层，一般有一个包检查块（包过滤器），通过该检查模块，对每一个传入和传出网络的IP 包打开进行检查，例如源地址、目的地址、协议和端口等，对于不符合包过滤规则的包进行记录，发出报警并丢弃该包。
    优点：
    （1）过滤型的防火墙通常直接转发报文，它对用户完全透明，速度较快。
    （2）包过滤通常被包含在路由器数据包中，所以不需要额外的系统来处理。
    缺点：
    （1）它可以控制站点与网络之间的相互访问，但不能控制传输数据的内容， 因为内容是应用层数据。
    （2）访问控制粒度太粗糙，不能防范黑客攻击，不能处理新的安全威胁。
  2. 应用代理网关防火墙
    • 能彻底隔断内网与外网的直接通信，内网用户对外网的访问变成了防 火墙对外网的访问，然后再由防火墙转发给内网用户。
    • 所有通信都必须经应用层代理软件转发，访问者任何时候都不能与服 务器建立直接的TCP连接，应用层的协议会话过程必须符合代理的安全 策略要求。
    • 优点：可以检查应用层、传输层和网络层的协议特征，对数据包的检测能力比较强。
    • 缺点：难以配置，处理速度非常慢。
  3. 状态检测技术防火墙
    • 它结合了代理防火墙的安全性和包过滤防火墙的高速等优点，在不损失安全性的基础上，提高了代理防火墙的性能。
    • 状态监测不仅仅根据规则表来检查每一个进出的包，更考虑了数据包 是否符合会话所处的状态，因此提供了完整的对传输层的控制能力， 同时也改进了流量处理速度。
    • 因为它采用了一系列优化技术，使防火墙性能大幅度提升，能应用在各类网络环境中，尤其是在一些规则复杂的大型网络上。

防火墙的性能及特点主要由以下两方面所决定：（14年第8题）
① 工作层次
这是决定防火墙效率及安全的主要因素。一般来说，工作层次越低，则工作效率越高，但安全性就低了；反之，工作层次越高，工作效率越低，则安全性越高。
② 防火墙采用的机制
如果采用代理机制，则防火墙具有内部信息隐藏的特点，相对而言，安全性高，效率低；如果采用过滤机制，则效率高，安全性却降低了

DMZ （Demilitarized zone,隔离区或者非军事化区）
它是为了解决安装防火墙后外部网络不能访问内部网络服务器的问题，而设立的一个非安全系统与安全系统之间的缓冲区，这个缓冲区位于企业内部网络和外部网之间的小网络区域内，在这个小网络区域内可以放置一些必须公开的服务器设施，如企业Web 服务器、FTP 服务器和论坛等。另一方面，通过这样一个DMZ 区域，更加有效地保护了内部网络，因为这种网络部署比起一般的防火墙方案，对攻击者来说又多了一道关卡，因此安全程度从高到低排序为：内网>DMZ>外网（13年第8题）

在IE浏览器中，安全级别最高的区域设置是受限站点。（11年第9题）
其中Internet 区域设置适用于Internet 网站，但不适用于列在受信任和受限制区域的网站；本地Intranet 区域设置适用于在Intranet 中找到的所有网站；可信任站点区域设置适用于你信任的网站；而受限站点区域设置适用于可能会损坏你计算机或文件的网站，它的安全级别高

计算机病毒的分类
文件型：感染可执行文件（包含EXE 和COM 文件）
引导型：影响软盘或硬盘的引导扇区
目录型：修改硬盘上存储的所有文件的地址
宏病毒：某些程序创建的文本文档、数据库、电子表格等文件 （11年第8题）

补充知识点

1. ISO/OSI 网络体系结构

层次层的名称英文主要功能
7应用层Application Layer处理网络应用
6表示层Presentation Layer数据表示
5会话层Session Layer互连主机通信
4传输层Transport Layer端到端连接
3网络层Nework Layer分组传输和路由选择
2数据链路层Data Link Layer传送以帧为单位的信息
1物理层Physical Layer二进制传输

1、物理层
是OSI 参考模型的最低层或第一层。
物理层协议要解决的是主机、工作站等数据端设备与通信线路上通信设备之间的接口问题。
四个特性：
(1) 机械特性
规定了DTE 和DCE 之间的连接形式，包括连接器形状、几何尺寸、引线数目和排列方式等。
(2) 电气特性
规定了发送器和接收器的电气参数及其其他有关电路的特征。电气特性决定了传送速率和传输距离。
(3) 功能特性
接口信号分为数据信号、控制信号和时钟信号。
(4) 规程特性
操作顺序

2、数据链路层
数据链路层工厂把流量控制和差错控制合并在一起。
数据链路层分为MAC(媒介访问控制层)和LLC(逻辑链路控制层)
服务访问点为MAC 地址。

3、网络层
网络层解决对的问题是路由选择、网络拥塞、异构网络互联等问题，其服务访问点为逻辑地址（网络地址）
网络层安全协议：IPSec

4、传输层
服务访问点为端口。
代表协议：TCP、UDP、SPX协议

5、会话层
管理和协调不同主机上各种进程之间的通信，即负责建立、管理和终止应用程序之间的会话。

6、表示层
处理流经结点的数据编码的表示方式问题

7、应用层
直接为端用户服务，提供各类应用程序的接口和用户接口。
例如：HTTP、Telnet、FP、SMTP

第 6 章 数据库技术基础

6.1 基础概念

6.1.1 数据库与数据库管理系统

  1. 数据库系统基本概念 （09年第28题）
    数据库是指长期存储在计算机外存上的、有组织的、可共享并相互联系的数据集合。
  2. 数据库系统应用 （09年第29题）
    应用数据库的主要目的是解决数据共享问题。

数据库安全机制 （11年第46题）
授权机制：指定用户对数据库对象的操作权限
视图机制：通过视图访问而将基本表中视图外的数据对用户屏蔽
数据加密：对存储和传输数据库的数据进行加密
用户标识与鉴别：指用户进入数据库系统时提供自己的身份标识，由系统鉴定为合法用户，只有合法用户才可以进入

6.1.2 数据库技术的发展

6.1.3 DBMS的功能和特点

  1. DBMS 功能
  2. DBMS 特点
  3. DBMS 分类
    DBMS 对不同类别的故障使用不同的恢复方法。其中事务故障和系统故障由DBMS来完成事务级别的恢复，即根据日志文件对未完成的事务进行UNDO 操作，对已完成的事务完成REDO 操作，使数据库恢复到一致的状态。介质故障需要DBA 介入，装载备份文件后交由DBMS 恢复。

6.1.4 数据库系统的体系结构

  1. 集中式数据库系统
  2. 客户端/服务器体系结构
  3. 并行数据库系统
  4. 分布式数据库系统

6.1.5 数据库系统的三级模式结构

（13年第47、48题/16年第28题）

1. 数据抽象
 （1）物理层：描述数据在存储器中是如何存储的。
 （2）逻辑层：描述数据库中存储什么数据以及这些数据间存在什么关系。
 （3）视图层：描述整个数据库的某个部分
2. 数据库的三级模式结构
3. 模式 （10年第23题/11年第28-29题/12年第30-31题/13年第32题/14年第28题）
 （1） 模式（概念级）
  又称概念模式或逻辑模式。他是由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共数据视图。（逻辑层，基本表）
 （2） 外模式（用户级）
  又称子模式，它是某个或某几个用户所看到的的数据库视图，是与某一应用有关的数据库结构。（视图层，视图）
 （3） 内模式（物理级） （16年第28题）
  又称存储模式，它是数据库中全体数据的内部表示或低层描述，是数据库最低一级的逻辑描述，它描述了数据在存储介质上的存储方式和物理结构，对应着实际存储在外存储介质上的数据库。（物理层，存储文件）
4. 两级映像（11年第28-29题/14年第29题/17年第28题）
数据库系统在三级模式之间提供了两级映像：
 （1） 模式/内模式的映像：（21年第63题）
  该映像存在于概念和内部级之间，实现了概念模式到内模式之间的相互转换。
保证了数据与应用程序的物理独立性，简称数据的物理独立性。
 （2） 外模式/模式的映像：
  该映像存在于外部级和概念级之间，实现了外模式到概念模式之间的相互转换。
保证了数据与程序的逻辑独立性，简称数据的逻辑独立性。
正因为这两级映射保证了数据库中的数据具有较高的逻辑独立性和物理独立性。数据的独立性是指数据与程序独立，将数据的定义从程序中分离出去，由DBMS 负责数据的存储，从而简化应用程序，大大减少应用程序编制的工作量。
5. 数据的独立性：
 （1）数据的物理独立性
 它是指当数据库的内模式发生改变时，数据的逻辑结构不变。
 （2）数据的逻辑独立性 （17年第28题）
 它是指用户的应用程序与数据库的逻辑结构是相互独立的，数据的逻辑结构发生变化后，用户程序也可以不修改，但是，为了程序能够正确执行，需要修改外模式/模式之间的映像。比如重建视图。

6.2 数据模型

6.2.1 数据模型的基本概念

1）概念数据模型
也称为信息模型，按用户的观点对数据和信息建模，是现实世界到信息世界的第一层抽象，强调其语义表达功能，易于用户理解
2）基本数据模型

6.2.2 数据模型的三要素

数据模型的三要素：（17年第30题/19年第33题）
(1) 数据结构
(2) 数据操作
(3) 数据约束

6.2.3 E-R 模型

实体-联系(E-R)方法是概念模型中常用的方法，该方法直接从现实世界中抽象出实体和实体间的联系，然后用非常直观的E-R图来表示数据模型。

  1. E-R 方法
  2. 实体
    实体是现实世界中可以区别于其他对象的“事物”或“物体”，每个 实体由一组特性（属性）来表示，其中的某一部分属性可以唯一标识 某个实体，如职工号。
  3. 联系 （13年第39题/17年第40题）
    1）两个不同实体之间的联系 （13年第57、58题）
    （1）一对一（1:1）：一个班长只能在一个班级任职，一个班级只能有一个班长。

（2）一对多（1: *）：一个教师可以教授多门课程，一门课程只能被一位教师讲授。

（3）多对多（* : ）（19年第34题）
一个学生可以选修多门课程，一门课程可以由多位学生选修

2）两个以上不同实体集之间的联系 （三元联系）
（1）1:1:1：
（2）1:1:：
（3）1::：一个特护病房有多个病人和多个医生， 一个医生只负责一个病房，一个病人只属于一个 病房。
（4）:😗：一个供应商可以为多个项目供应多种零件，每个项目可用多个供应商供应的零件，每 种零件可由不同的供应商供应。
3）同一实体集内的二元联系
同一实体集内的两个实体之间相互存在着一定的关系。

4. 属性 （11年第34题/17年第57题）
（1）简单属性和复合属性
简单属性是原子的、不可再分的，复合属性可以细分为更小的部分。
如通信地址可以进一步细分为省、市、街道、 邮编等。
（2）单值属性和多值属性（10年第26题）
指一个属性有单个值或多个值。
如职工的亲属姓名。
（3）NULL属性 （17年第59题）
当实体在某个属性上没有值或属性值未知时，使用 NULL值。表示无意义或不知道。
（4）派生属性 （10年第37题/15年第60题）
可以从其他属性得来。
如参加工作时间和工作年限， 身份证号和年龄等。
5. 扩充的E-R 模型
1）弱实体（18年第34题/19年第35题）
一个实体的存在必须以另一个实体为前提

2）特殊化
某些实体一方面具有一些共性，另一方面还具有各自的特殊性。这样，一个实体集可以按照某些特征区分为几个子实体

7. E-R 模型应用举例
8. 扩充E-R 模型应用举例

E-R 图向关系模式转换时，实体标识符转换为关系的码。

在E-R图设计中，通常将任务分解为多个平等的部分设计，即根据不同的业务及DFD图片段先做分E-R图的设计，再将各分E-R图合并。合并之后形成企业全局E-R图，即可以从总体上认识企业信息。合并过程中会遇到不同分E-R图之间存在的属性冲突、命名冲突及结构冲突，并解决信息冗余。分E-R图是根据信息需求和处理需求来设计的，合并过程中并不考虑信息需求。

6.2.4 基本的数据模型

  1. 层次模型（Hierarchical Model）
    采用树型结构
  2. 网状模型（Network Model）
  3. 关系模型（Relational Model）（09年第30题/18年第36题）
    关系模型是由若干个关系模式组成的集合。一个关系模式相当于一个记录型，对应于程序设计语言中类型定义的概念。关系是一个实例，也是一张表，对应于程序设计语言中变量的概念。
    关系模型比网状、层次模型更为简单灵活。
  4. 面向对象数据模型（Object Oriented Model）

6.3 数据存储和查询

6.3.1 存储管理器

6.3.2 查询处理器

6.4 数据仓库和数据挖掘基础知识

6.4.1 数据仓库

（14年第64题）

  1. 数据仓库的基本特性
    1）面向主题的
    2）数据是集成的
    集成性是指根据决策分析的要求，将分散于各处的原数据进行抽取、筛选、清理、综合等集成工作。
    3）数据是相对稳定的
    4）数据是反映历史变化的
  2. 数据仓库的数据模式
  3. 数据仓库的体系结构（11年第64题）
    底层：数据仓库服务器
    中间层：OLAP 服务器
    顶层：前端工具

6.4.2 数据挖掘

联机分析处理（OLAP） （13年第43题）
用于数据挖掘，从数据仓库中分析数据，为决策提供证据。要求响应时间合理
联机事务处理（OLTP）
更新事务，将数据写入数据库，面向操作人员，要求响应时间快

K-Means 和 DBSCAN 是两个经典的聚类算法，将相似的数据对象归类一组，不相似的数据对象分开。（15年第65题）
K-Means 算法基于对象之间的聚类进行聚类，需要输入聚类的个数。（13年第41题）
DBSCAN 算法基于密度进行聚类，需要确定阈值，两者的聚类结果均与输入参数关系很大。DBSCAN 可以处理不同大小和形状的簇，而K-Means 算法则不适合。若数据分布密度变化大，则这两种算法都不适用。

数据挖掘技术的分类
按所发现的知识类别来分（13年第42题）
（1）关联规则
反映数据项中某些属性或数据集中某些数据项之间的统计相关性，比如“在购买面包和黄油的顾客中，有90%的人也买了牛奶”
（2）特征描述
（3）分类分析（11年第65题/15年第39题）
首先为每一个记录赋予一个标记(一组具有不同特征的类别)，即按标记分类记录，然后检查这些标定的记录，描述出这些记录的特征。这些描述可能是显式的，如一组规则定义；也可能是隐式的，如一个数学模型或公式。
（4）聚类分析（14年第65题）
聚类分析是根据在数据中发现的描述对象及其关系的信息，将数据对象分组。目的是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内相似性越大，组间差距越大，说明聚类效果越好。
（5）趋势和偏差分析
附：离群点在样本空间中，与其他样本点的一般行为或特征不一致的点。

第7章 关系数据库

7.1 关系数据库概述

7.1.1 基础知识

  1. 关系数据库系统
  2. 关系的相关名词
    （1）关系：
    在关系数据库中，实体以及实体间的联系都是用关系来表示的。类似于程序设计语言中变量的概念。
    （2）关系模式：是对关系的描述。类似于程序设计语言中类型定义的概念。
    （3）关系模型：是由若干个关系模式组成的集合。
    （4）属性（Attribute）：用来描述某一个事物的特征。
    （5）域（Domain）：每个属性的取值范围所对应一个值的集合。
    （6）候选码（Candidate Key）：若关系中的某一属性或属性组的值能唯一标识一个元组，则称该属性或属性组 为候选码。
    （7）主码（Primary Key）：又称为主键，若一个关系有多个候选码，则选定其中一个为主码。 只能有一个主码。（13年第33题）
    （8）主属性（Prime attribute）：包含在任何候选码中的各个属性称为主属性。
    （9）非主属性：不包含在任何候选码中的属性称为非主属性。
    （10）外码：如果关系模式R 中的属性或属性组非该关系的码，但它是其他关系的码，那么该属性集对关系模式R 而言是外码。
    （11）全码（All-key）：（15年第29题）
    关系模型的所有属性组是这个关系模式的候选码，称为全码。
    （12）元组/记录：行
    （13）字段、数据项
    （14）元数：属性的个数（列数）
    （15）基数：记录的个数（行数）
    （16）n元关系：元数为几，就是 几元关系。
    例：关系模式： Student(Sno,Sname,SD,Sex)
  3. 笛卡尔积与关系
  4. 关系的三种类型
    （1）基本关系（又称基本表或基表）
    （2）查询表
    （3）视图表

关系数据库中的关系模型事实上可以看作是一个二维表，这个二维表中的列称为属性（或字段），行称为元组（或记录）。

例题：若关系R（H，L，M，P）的主键为全码（All-key），则关系R 的主键应为HLMP

7.1.2 关系数据库模式

7.1.3 关系的完整性约束

关系的完整性约束（20年第38题）
(1) 实体完整性
防止的是对数据的意外破坏。
(2) 用户自定义完整性
就是针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求，由应用的环境决定。如：年龄必须为大于0小于150的整数。
(3) 参照完整性/引用完整性
规定，若F 是基本关系R 的外码，它与基本关系S 的主码K，相对应（基本关系R 和S 不一定是不同的关系）

无损联接分解：
指将一个关系模式分解成若干个关系模式后，通过自然联系和投影等运算仍能还原到原来的关系模式。

例：将一个关系r分解成两个关系r1 和r2，再将分解之后的两个关系r1 和r2 进行自然连接，得到的结果如果比原关系 r 记录多，则称这种分解为（有损连接的分解）

7.2 关系运算

7.2.1 关系代数运算

7.2.2 五种基本的关系代数运算

  1. 并 (Union)
    关系R与S具有相同的关系模式，即R与S的元数相同（结构相同），关系R与S“并” 由属于R或属于S的元组构成的集合组成，记作R∪S，其形式定义如下：
    R∪S={t|tϵR V tϵS}
    式中t为元组变量
  2. 差 (Difference)
    关系R与S具有相同的关系模式，关系R与S的差是由属于R但不属于S的元组构成 的集合，记作R-S，其形式定义如下：
    R-S={t|t ϵ R ˄ tϵS}
  3. 广义笛卡儿积
    两个元数分别为n目和m目的关系R和S的广义笛卡儿积是一个(n+m)列的元组的集合。 元组的前n列是关系R的一个元组，后m列是关系S的一个元组，记作R×S。
  4. 投影及广义投影
    投影是从关系的垂直方向进行运算，在关系R中选择出若干属性列A组成新的关系，记作πA®，其 形式定义如下：
    πA®={t[A]|tϵR}
    广义投影运算允许在投影列表中使用算术运算，实现了对投影运算的扩充。若有关系R，条件 F1,F2,…,Fn中的每一个都是涉及R中常量和属性的算术表达式，那么广义投影运算的形式定义为：
    πF1,F2,…,Fn®
  5. 选择
    选择运算是从关系的水平方向进行运算，是从关系R中选择满足给定条件的诸元组， 记作σF®，其形式定义如下：
    σF®={t|tR∧F(T)=True}
    其中，F中的运算对象是属性名（或列的序号）或常数，运算符、算术比较符（<、 >、⩾、⩽、≠）和逻辑运算符（∧、∨、¬）。
    例如，σ1⩾6®表示选取关系R中第1个属性值大于等于第6个属性值的元组； σ1>'6’®表示选取关系R中第1个属性值大于6的元组。
    注意6和’6’的区别，6是指从左往右数第6个属性，‘6’是指数字6（数值格式或文本 格式）

7.2.3 扩展的关系运算

  1. 交 ( Intersection)
    关系R与S具有相同的关系模式，关系R与S的交由属于R同时又属于S的元组构成， 关系R与S的交记作R⋂S，其形式定义如下：
    R⋂S={t|tϵR∧tϵS}
  2. 连接
    分为θ连接、等值连接与自然连接
    （1）θ连接
    可以由基本的关系运算笛卡儿积和选取运算导出。
    R⨝S=σXθY(R×S)
    • 其中，θ为比较运算符，如>、<、=、≠，X 和Y 分别为R 和S 上可以进行比较的属性组。
    • 例：设有关系R 和S 如下图所示，求 R ⨝ S XθY R.A<S.B
    （2）等值连接
    当θ为“=”时，称为等值连接，记为R⨝S。 X=Y
    （3）自然连接
    是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果集中将重复属性列去掉。如果没有重复属性，那么自然连接就转化为笛卡儿积。
    • 例：设有关系R 与S 如下图所示，求R⨝S。
  3. 除
  4. 外连接
    外连接运算是连接运算的扩展，可以处理缺失的信息。
    （1）左外连接⟕（左侧为准，右侧填充）
    取出左侧关系中所有与右侧关系中任一元组都不匹配的元组，用空值NULL填充所有来自右侧关系的属性，构成新的元组，将其加入自然连接的结果中。
    （2）右外连接⟖（右侧为准，左侧填充）
    取出右侧关系中所有与左侧关系中任一元组都不匹配的元组，用空值NULL填充所有来自左侧关系的 属性，构成新的元组，将其加入自然连接的结果中。
    （3）全外连接⟗

7.3 元组演算

• 元组关系演算是非过程化查询语言，简称元组演算。它只描述所需信息，而不给出获得该信息的 具体过程。
• 在元组演算中，其元组演算表达式中的变量是以元组为单位的，其一般形式为： {t|P(t)}
其中，t是元组变量，P(t)是元组演算公式，公式是由原子公式组成。

7.3.1 原子公式

（1）R(t)
R是关系名，t是元组变量，R(t)表示：t是关系R中的一个元组。
（2）t[i] θ C 或 C θ t[i]
t[i]表示元组变量t的第i个分量，C是常量，θ为算术比较运算符。
（3）t[i] θ u[j]
t 和u 是两个元组变量。t[i] θ u[j] 表示元组变量 t 的第 i 个分量与元组变量 u 的第 j 个分量之间满足 θ 运算。

7.3.2 公式的定义

若一个公式的一个元组变量前有全称量词⩝或存在量词∃符号，则称该变量为约束变量，否则称之 为自由变量。公式可递归定义如下：
（1）原子公式是公式。
（2）如果φ1和φ2是公式，那么，¬φ1，φ1∨φ2，φ1∧φ2，φ1⇒φ2也都是公式。分别表示如下命题： ¬φ1表示“φ1不为真”，φ1∨φ2表示“φ1或φ2为真”，φ1∧φ2表示“φ1和φ2都为真”；φ1⇒φ2表示 “若φ1为真则φ2为真”。
（3）如果是φ1公式，那么，∃t(φ1)是公式。∃t(φ1)表示这样一个命题： “如果有一个t使φ1为真，则∃t(φ1)为真，否则∃t(φ1)为假”。
（4）如果是φ1公式，那么，⩝t(φ1)是公式。⩝t(φ1)表示这样一个命题： “如果对所有的t使φ1为真，则⩝t(φ1)为真，否则⩝t(φ1)为假”。 • 公式中运算符的优先顺序为： • θ > ⩝和∃ > ¬ > ∧和∨ > ⇒，加括号时，括号中的运算符优先。

7.3.3 关系代数运算转换为元组演算表达式

7.4 域演算

域关系演算简称域演算。在域演算中，表达式中的变量是表示域的变量，可将关系的属性名视为域变量，域演算表达式的一般形式为：
{t1,…,tk|P(t1,…,tk)}
其中，t1,…,tk是域变量，P(t1,…,tk)是域演算公式。

7.4.1 原子公式

（1）R(t1,…,ti,…,tk)
R 是k 元关系，ti 是元组变量 t 的第 i 个分量，R(t1,…,ti,…,tk)表示这样一个命题： 以t1,…,ti,…,tk为分量的元组在关系R。
（2）ti θ C 或 C θ ti
ti 表示元组变量 t 的第 i 个分量，C是常量，θ为算术比较运算符。
（3）ti θ uj
ti 和 uj 是两个域变量。ti θ uj表示元组变量 t 的第 i 个分量与元组变量u的第j个分量之间满足θ运算。

7.4.2 公式的定义

若一个公式的一个元组变量前有全称量词⩝或存在量词∃符号，则称该变量为约束变量，否 则称之为自由变量。公式可递归定义如下：
（1）原子公式是公式。
（2）如果φ1和φ2是公式，那么，¬φ1，φ1∨φ2，φ1∧φ2，φ1⇒φ2也都是公式。
（3）如果是φ1公式，那么，∃ti(φ1)是公式。∃ti(φ1)表示这样一个命题： “如果有一个ti使φ1为真，则∃ti(φ1)为真，否则∃ti(φ1)为假”。
（4）如果φ1(t1,…,ti,…,tk)是公式，那么，⩝ti(φ1)是公式。⩝t(φ1)表示这样一个命题： “如果对所有的ti使φ1(t1,…,ti,…,tk)为真，则⩝ti(φ1)为真，否则⩝ti(φ1)为假”。 公式中运算符的优先顺序为： θ > ⩝和∃ > ¬ > ∧和∨ > ⇒，加括号时，括号中的运算符优先。

7.4.3 举例

7.5 查询优化

7.5.1 基本概念

查询优化是指为查询选择最有效的查询计划的过程。一个查询可能会有多种实现方法，关键是如何找出一个与之等价的且操作时间又少的表达式，以节省时间、空间，提高查询效率。
• 在关系代数运算中，笛卡儿积、连接运算是最耗费时间和空间的

7.5.2 关系代数表达式中的查询优化

  1. 优化的准则
    （1）提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式， 以得到较小的中间结果，减少运算量和从外存读块的次数。
    （2）合并乘积与其后的选择运算为连接运算。
    （3）将投影运算与其后的其他运算同时进行，以避免重复扫描关系。
    （4）将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。
    （5）在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、 排序合并连接法。
    （6）存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读 出它的时间比计算的时间少时，就可节约操作时间。
  2. 关系代数表达式的等价变换规则
  3. 查询优化的算法

7.6 关系数据库设计基础理论

7.6.1 基础知识

  1. 函数依赖
    • 定义：设R(U)是属性集U上的关系模式，X、Y是U的子集。若对R(U)的任何一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等， 则称X函数决定Y或Y函数依赖于X，记作：X→Y
    • 如果X→Y，那么对于任意两个相同的X，所对应的Y是一定相同的。
    • 如果X→Y，但Y⊈X，则称X→Y是非平凡的函数依赖。一般情况下总是讨论非平凡的函数依赖。
    • 如果X→Y，但Y⊆X，则称X→Y是平凡的函数依赖。
    • 函数依赖的定义要求关系模式R 的任何可能的 r 都满足上述条件。因此不能仅考察关系模式R 在某一时刻的关系r，就断定某函数依赖成立。
    • 函数依赖是语义范畴的概念，我们只能根据语义来确定函数依赖。

  2. 完全函数依赖与部分函数依赖
    • 定义：在R(U)中，如果X→Y，并且对于X 的任何一个真子集X’，都有X’不能决定Y， 则称Y 对X 完全函数依赖，记作：X→Y。
    如果X→Y，但Y 不完全函数依赖于X，则称Y 对X 部分函数依赖，记作：X→Y。部分函数依赖也称局部函数依赖。
    例：选课关系SC1（学号,课程号,成绩)，F={（学号,课程号）→ 成绩}。 （学号,课程号）→ 成绩，学号⇸成绩,课程号⇸成绩。 选课关系SC2（学号,课程号,学生姓名,课程名称,成绩)，F={（学号,课程号） → 成绩，（学号,课程号）→ 课程名称,（学号,课程号）→ 学生姓名，学号→学生 姓名,课程号 → 课程名称}。 P

  3. 传递函数依赖
    • 定义：在R(U,F)中，如果X→Y，Y→Z，Y⊈X，Y⇸X，则称Z对X传递依赖。 例：供应商（Sno,Sname,Status,City,Pno,Qty），及函数依赖集如下，判断该关系是否存在传递函数依赖和部分函数依赖。
    F={Sno→Sname, Sno→Status, Status→City,(Sno,Pno)→Qty}

码

  1. 候选码和主码：设 K 为R(U,F)中的属性的组合，若K→U，且对于K的任何一个真子集K’，都有K’不 能决定U，则K为R的候选码，若有多个候选码，则选一个作为主码。
    • 候选码通常也可以称为候选关键字，主码通常也可以称为主关键字或主键。
    • 包含在任何一个候选码中的属性叫做主属性，否则叫做非主属性。
    例：选课关系SC1（Sno,Cno,Sname,Cname,G)
    选课关系SC2（Sno,Cno,Sname,Cname)

  2. 外码：若R(U)中的属性或属性组X非R的码，但X是另一个关系的码，则称X是R的外码（Foreign Key）或称外键。
    例：学生（学号，姓名，班主任，所属学院）
    教师（职工号，姓名）
    学院（编号，名称）

多值依赖
• 定义：若关系模式R(U)中，X，Y，Z是U的子集，并且 Z=U-X-Y。当且仅当对R(U)的任何一个关系r，给定一对(x,z)值，有一组Y的值，这组值仅仅决定于 x 值而与z值 无关，则称“Y多值依赖于X”或“X多值决定Y”成立。记为： X→→Y
例：参考书目（课程，教师，参考书）
课程→→参考书
如果Z=∅，为平凡的多值依赖；
如果Z≠∅，则为非平凡的多值依赖。
课程 教师 参考书 数学 王平 数学分析 数学 王平 线性代数 数学 王平 微分方程 计算机网络 李莉 计算机网络基础 计算机网络 李莉 TCP/IP协议详解 X Z Y
• 多值依赖具有如下6条性质：
1、多值依赖具有对称性。即若X→→Y,则X→→Z，其中Z=U-X-Y。
2、多值依赖的传递性。即若X→→Y,Y→→Z,则X→→Z-Y。
3、函数依赖可以看成是多值依赖的特殊情况。
4、若X→→Y,X→→Z,则X→→YZ。
5、若X→→Y,X→→Z,则X→→Y ⋂ Z。
6、若X→→Y,X→→Z,则X→→Z-Y。

7.6.2 规范化

（09年第31-33题/11年第35-36题）

  1. 1NF（第一范式）（12年第35题）
    • 定义：若关系模式 R 的每一个分量是不可再分的数据项，则关系模式R 属于第一范式。记为R∈1NF。
    例：FIRST(Sno,Sname,Status,City,Pno,Qty)
    F={Sno→Sname, Sno→Status, Status→City,(Sno,Pno)→Qty}
    • 存在的问题：
    （1）冗余度大
    每个供应者的 Sno、Sname、Status、City 要与其供应商的零件的种类一样多
    （2）引起修改操作的不一致性
    例如供应者 S1 从天津搬到上海，若不注意，会使一些数据被修改，另一些数据未被修改，导致数据修改的不一致性
    （3）插入异常
    关系模式 FIRST 的主码为Sno、Pno,按照关系模式实体完整性规定主码不能取空值或部分取空值。这样，当某个供应商的某些信息位提供时（如Pno）则不能进行插入操作
    （4）删除异常
    若供应商 S4 的P2 零件销售完了，并且以后不再销售 P2 零件，那么应删除该元组。这样，在基本关系 FIRST 找不到 S4，可S4 又是客观存在的

  2. 2NF（第二范式）
    • 定义：若关系模式 R∈1NF，且每一个非主属性完全依赖于码，则关系模式R∈2NF。
    • 换句话说：当 1NF 消除了非主属性对码的部分函数依赖，则称为 2NF。
    例：学生(学号,姓名,学院编号,学院名称,课程号,成绩)
    F={学号→姓名, 学号→学院编号, 学院编号→学院名称,(学号,课程号)→成绩}
    将学生关系分解为：
    • 学生1(学号,姓名,学院编号,学院名称)∊2NF
    • 学生2(学号,课程号,成绩)∊2NF

  3. 3NF（第三范式）
    • 定义：若关系模式R(U,F) 中不存在这样的码X，属性组Y 及非主属性Z（Z⊈Y）使得 X→Y,(Y⇸X) Y→Z成立，则关系模式R∈3NF。
    • 即：当2NF 消除了非主属性对码的传递函数依赖，则称为3NF。
    例：学生1(学号,姓名,学院编号,学院名称)∈2NF，但∉3NF。
    将学生1分解为：
    • 学生11(学号,姓名,学院编号)∈3NF
    • 学生12(学院编号,学院名称)∈3NF

  4. BCNF（巴克斯范式）
    • 定义：关系模式R∈1NF，若X→Y且Y⊈X时，X必含有码，则关系模式R∈BCNF。
    • 也就是说，当3NF消除了主属性对码的部分函数依赖和传递函数依赖，则称为BCNF。
    • 结论：一个满足BCNF 的关系模式，应有如下性质：
    （1）所有非主属性对每一个码都是完全函数依赖；
    （2）所有主属性对每一个不包含它的码，也是完全函数依赖；
    （3）没有任何属性完全函数依赖于非码的任何一组属性。
    例：R(Pno,Pname,Mname)的属性表示零件号、零件名和厂商名，如果约定，每种零件号只有一个零 件名，但不同的零件号可以有相同的零件名；每种零件可以有多个厂商生产，但每家厂商生产的零件应有不同的零件名。
    函数依赖集如下：
    (Pname,Mname)→Pno, Pno→Pname
    候选码为(Pname,Mname)或(Pno,Mname)
    分解为：
    R1(Pno,Pname)∈BCNF
    R2(Pno,Mname)∈BCNF

  5. 4NF（第四范式） （11年第61题/14年第60题）
    • 定义：关系模式R∈1NF，若对于R的每个非平凡多值依赖X→→Y且Y⊈X时，X必含有码，则关系模式R(U,F)∈4NF。
    • 4NF是限制关系模式的属性间不允许有非平凡且非函数依赖的多值依赖。
    注意：如果只考虑函数依赖，关系模式最高的规范化程度是BCNF，如果考虑多值依赖，关系模式最高的规范化程度是4NF。
    例：学生(学号，选修课程，兴趣爱好)
    • 学生1(学号，选修课程）∈4NF
    • 学生2(学号，兴趣爱好）∈4NF
    书目(ISBN，书名，作者，排名，出版社）
    • 书目1(ISBN，作者，排名）∈4NF
    • 书目2(ISBN，书名，出版社）∈BCNF

    连续依赖 5NF
    当关系模式无损分解为 n 个投影 (n>2) 会产生一些特殊情况。
    如果给定一个关系模式的分解，那么称 R 满足连续依赖 ，当且仅当R 的任何可能出现的合法值都与它在上的投影等价
    总结：
    1NF⊃2NF⊃3NF⊃BCNF⊃4NF⊃5NF 通过分解，可以将一个低一级范式的关系模式转换成若干个高一级范式的关系模式，这种过程叫做规范化。

7.6.3 Armstrong 公理系统

（17年第31题）
设关系模式R<U , F> , U是关系模式R 的属性全集，F 是关系模式R 的一个函数依赖集。对于R<U，F>来说有以下的：
自反律：若Y⊆X⊆U，则X→Y为F 所逻辑蕴含
增广律：若X→Y为F所逻辑蕴含，且Z⊆U，则XZ→YZ为F所逻辑蕴含
传递律：若X→Y和Y→Z为F所逻辑蕴含，则X→Z为F所逻辑蕴含
合并规则：若X→Y，X→Z，则X→YZ为F所蕴涵
伪传递率：若X→Y，WY→Z，则XW→Z为F所蕴涵
分解规则：若X→Y， Z⊆Y ， 则X→Z为F所蕴涵

  1. 函数依赖的闭包F+ （14年第56题）
    • 定义：关系模式R(U,F)中为F 所逻辑蕴含的函数依赖的全体称为F的闭 包，记为：F+。 例：R(U,F)，U=（A,B,C,D）,F={A→B,B→C,AC→D}
  2. 属性的闭包XF+
    • 定义：设F 为属性集U 上的一组函数依赖，X⊆U，XF+={A|X→A能由F根据Armstrong公 理导出}，则称XF+为属性集X关于函数依赖集F的闭包。
    • 即：属性集X的闭包XF+是指所有能由X决定的属性集合。最小函数依赖集
    • 如果函数依赖集F满足下列条件，则称F为一个最小函数依赖集，或称极小函数依赖集或最小覆盖。 （13年第35题）
    （1）F 中的任一函数依赖的右部仅有一个属性，即无多余的属性；
    （2）F 中不存在这样的函数依赖X→A，使得F与F-{X→A}等价，即无多余的函数依赖；
    （3）F 中不存在这样的函数依赖X→A，X有真子集Z使得F与F-{X→A}⋃{Z→A}等价，即去掉各函数依 赖左边的多余属性。 即：
    （1）所有函数依赖的右侧只有一个属性。
    （2）没有冗余的函数依赖。
    （3）所有函数依赖的左侧没有冗余的属性。
    例：关系模式R(U,F), R(A,B,C,D,E), F={A→BC,A→E,A→D,D→E,AC→D}

7.6.4 模式分解及分解后的特性

  1. 分解
  2. 无损连接
    • 分解及无损连接的定义：略，见教材P288
    • 无损连接是指将一个关系模式分解成若干个关系模式后，通过自然连接和投影等运算仍能还原到原来的关系模式，则称这种分解为无损连接分解。
    • 定理：关系模式R(U,F)的一个分解ρ ={ R1(U1,F1),R2(U2,F2)}，具有无损连接的充分必要的条件是： U1⋂U2→U1－U2∈F+或U1⋂U2→U2－U1∈F+。
    • 注意：这个定理只适用于分解为两个子模式的情况，分解为多个子模式的时候不适用。 例：对给定的关系模式R(U,F)，U={A,B,C}，F={A→B}，有两个分解：ρ1 ={AB,BC}和 ρ2 ={AB,AC}。请判断这两 个分解是否无损。
  3. 保持函数依赖
    • 定义：设关系模式R(U,F)的一个分解 ρ ={R1(U1,F1), R2(U2,F2),…,Rk(Uk,Fk)}，如 果F+=(⋃Fi)+，则称分解ρ保持函数依赖。 即：（F1⋃F2⋃F3⋃…⋃Fk)+ = F+
    例：判断是否保持函数依赖：
    (1)关系R(A1，A2，A3)上的函数依赖集F={A1A3→A2,A1A2→A3}，R上的一个分解为ρ={(A1，A2),(A1，A3)}
    (2)给定关系模式R(A1，A2，A3，A4)，R上的函数依赖集F = {A1A3→A2，A2→A3}，若将R分解为ρ={(A1， A2，A4)，(A1，A3)}
    (3)给定关系模式R(U，F)，U ={A,B,C,D}，F={A→B，BC→D}，对关系R分解为R1(A，B，C)和R2(A，C， D)
  4. 判别一个分解的无损连接性算法
  5. 将关系模式转换成3NF 且保持函数依赖的算法
  6. 将关系模式转换成3NF 且无损联接又保持函数依赖的算法
  7. 将关系模式转换成BCNF 且无损联接的算法

第八章 SQL 语言

8.1 数据库语言

8.1.1 数据库语言概述

（1）数据定义语言
DDL提供定义关系模式和视图、删除关系和视图、修改关系模式的命令
（2）数据操纵语言
DML提供查询、插入、删除和修改的命令。

8.1.2 数据库语言的分类

8.2 SQL 概述

8.2.1 SQL 语言的特征

8.2.2 SQL 的基本组成

  1. 数据定义语言。SQL DDL提供定义关系模式和视图、删除关系和视图、修改关系模式的命令。
  2. 交互式数据操纵语言。SQL DML提供查询、插入、删除和修改的命令。
  3. 事务控制。SQL提供定义事务开始和结束的命令。
  4. 嵌入式SQL和动态SQL。用于嵌入到某种通用的高级语言中混合编程。其中，SQL负责操纵数据库， 高级语言负责控制程序流程。
  5. 完整性。SQL DDL包括定义数据库中的数据必须满足的完整性约束条件的命令，对于破坏完整性约束条件的更新将被禁止。
  6. 权限管理。SQL DDL中包括说明对关系和视图的访问权限。
  7. SQL语言中完成核心功能的9个动词：
    （1）数据查询：Select
    （2）数据定义：Create、Drop、Alter
    （3）数据操纵：Insert、Update、Delete
    （4）数据控制：Grant、Revoke

8.3 数据库定义

8.3.1 基本域类型

8.3.2 创建表(CREATE TABLE)

语句格式：CREATE TABLE <表名> (<列名><数据类型>[列级完整性约束条件]
[，<列名><数据类型>[列级完整性约束条件]]…
[，<表级完整性约束条件>])； 注：[ ]表示可选，< >表示必填。

8.3.3 修改表和删除表

8.3.4 创建和删除索引

  1. 索引的作用
    （1）通过创建唯一索引，可以保证数据记录的唯一性。
    （2）可以大大加快数据检索速度。
    （3）可以加速表与表之间的连接，这一点在实现数据的参照完整性方面有特别的意义。
    （4）在使用ORDER BY 和GROUP BY 子句中进行检索数据时，可以显著减少查询中分组和排序的时间。
    （5）使用索引可以在检索数据的过程中使用优化隐藏器，提高系统性能。 索引分为聚集索引和非聚集索引。聚集索引是指索引表索引项的顺序与表中记录的物理顺序一致的索引。
  2. 建立索引
  3. 删除索引

8.3.5 视图创建和删除

  1. 视图的作用（10年第30题/13年第25题/14年第50题）
    视图是虚拟表，从一个或者多个基本表或视图中导出的表
    （1）可以使视图集中数据、简化和定制不同用户对数据库的不同数据要求
    （2）使用视图可以屏蔽数据的复杂性，但是并不会提高访问效率
    （3）视图可以使用户只关心他感兴趣的某些数据和任务
    （4）视图大大简化了用户对数据的操作
    （5）视图可以让不同的用户以不同的方式看到不同或者相同的数据集
    （6）某些情况时，由于数据量大，表的设计时将表进行水平或者垂直分隔，但表的结构的变化对应用程序产生不良的影响
    （7）视图提供了一个简单有效的安全机制
  2. 视图的创建
  3. 视图的删除

补充知识点：
应用程序访问数据库时，出于安全性考虑，不会提供存储数据的基本表供程序访问，一是为了防止表中其他数据的泄密，二是将程序需要读取的数据构建成视图，并提供只读权限供应用程序读取；对于更新操作，由于可更新视图仅限于构建在一个基本表上的视图，对于表更新，由存储过程来提供用户调用，而不是将基本表的结构向应用程序开发人员提供。（11年第50-51题/14年第51题）

8.4 数据操作

8.4.1 Select 基本结构

查询中子句顺序：

8.4.2 简单查询

8.4.3 连接查询

8.4.4 子查询与聚集函数

  1. 子查询
  2. 聚集函数

8.4.5 分组查询

  1. GROUP BY 子句
  2. HAVING 子句

8.4.6 更名操作

Old-name as new-name

8.4.7 字符串操作

LIKE
“%” 匹配任意字符串
“_” 匹配任意一个字符

8.4.8 集合操作

  1. UNION 运算（并集）
  2. INTERSECT 运算（交集）
  3. EXCEPT 运算（差集）

8.4.9 视图查询与更新

  1. 视图查询
  2. 视图更新
    视图更新遵循以下规则：
    （1）从多个基本表通过连结操作导出的视图不允许更新
    （2）对使用了分组，集函数操作的视图不允许更新
    （3）如果视图是从单个基本表通过投影、选取操作导出的则允许进行更新操作，且语法同基本表
  3. With 子句
    提供了一个定义临时视图的方法

8.5 完整性约束

8.5.1 主键(Primary Key) 约束

8.5.2 外键(Foreign Key)约束

8.5.3 属性值上的约束

8.5.4 全局约束

8.6 授权(GRANT) 与销权(REVOKE)

在数据库中用户可以通过对象的所有者、拥有授予相关权限的权限的用户或者DBA 执行GRANT 语句获取对应的权限。（17年第49题）

DBA 是数据库系统中最高权限的用户。（09年第52题）

在Windows 系统中，用户组默认权限由高到低顺序：（12年第8题）
admin>power users>users>everyone

自主存取控制是以人为主体，用户可以自由地将数据的存取权限授予何人，并决定是否允许权限的传播。（09年第50题）

  1. 授权（11年第52-53题/13年第30题/14年第49题/18年第43、44题）
    语句格式：
    GRANT 权限 ON TABLE/DATABASE 表名/数据库名 TO 用户1,用户2… /PUBLIC [WITH GRANT OPTION]
    PUBLIC：表示将权限授予所有人
    WITH GRANT OPTION：表示获得了这个权限的用户还可以将权限赋给其他用户。

  2. 销权（09年第51题/11年第35题/15年第52题/16年第51题）
    语句格式：
    REVOKE 权限 ON TABLE/DATABASE 表名/数据库名 FROM 用户1,用户2… /PUBLIC
    [RESTRICT | CASCADE] （10年第33题）
    RESTRICT：表示只收回语句中指定的用户的权限
    CASCADE：表示除了收回指定用户的权限外，还收回该用户赋予的其他用户的权限。

8.7 创建与删除触发器 316

8.7.1 概述

触发器经常用于加强数据的完整性约束和业务规则等。
触发器与存储过程的唯一区别是触发器不能执行 EXECUTE 语句调用，而是在用户执行 T-SQL 语句时自动触发执行。

触发器的特点
（1）当数据库程序员声明的事件发生时，触发器被激活。声明的事件可以是对某个特定关系的插入、删除或更新。
（2）当触发器被事件激活时，不是立即执行，而是首先由触发器测试触发条件，如果事件不成立，响应该事件的触发器什么都不做。
（3）如果触发器声明的条件满足，则与该触发器相连的动作由 DBMS 执行。动作可以阻止事件发生，可以撤销事件。

创建触发器时需指定：
（1）触发器名称
（2）在其上定义触发器的表
（3）触发事件：触发器将何时激发
（3）触发条件：满足什么条件时执行触发动作
（4）触发动作：指明触发器执行时应做的动作

♥ 触发器可以引用当前数据库以外的对象，但只能在当前数据库中创建触发器。
♥ 不能在临时表或系统表上创建触发器，但触发器可以引用临时表。
♥ 触发器是不能被应用程序显示调用，所以也不能带参数。

8.7.2 创建触发器

触发器的定义包括两个方面：
① 指明触发器的触发事件
② 指明触发器的执行动作。

（1） BEFORE：指示DBMS 在执行触发语句之前激发触发器。
（2） AFTER：指示DBMS 在执行触发语句之后激发触发器。
（3）DELETE：当一个DELETE语句从表中删除行时激发触发器。
（4）INSERT：当一个INSERT语句向表中插入行时激发触发器。
（5）UPDATE/UPDATE OF(列名)：当UPDATE修改表中的值时，激发触发器，也可加（OF 列名）指定是某一列的值被修改时激发触发器。
（6）REFERENCING<临时视图名>：触发器运行过程中，系统会生成两个临时视图，分别存放更新前和更新后的值，对于行级触发器，为OLD ROW 和NEW ROW，对于语句级触发器，为OLD TABLE和NEW TABLE。 REFERENCING new row AS nrow / REFERENCING old row AS orow 。
（7）WHEN<触发条件>：指定触发器的触发条件。当满足触发条件时，DBMS才触发触发器。触发条件中比粗包含临时视图名，不包含查询。
（8）FOR EACH ROW：表示为行级触发器，对每一个被影响的元组（即每一行）执行一次触发过程。
（9）FOR EACH STATEMENT：表示为语句级触发器，对整个事件只执行一次触发过程，为默认方式。

种类关键字含义
DML事件Insert在表或视图中插入数据时触发
DML事件Update修改表或视图中的数据时触发
DML事件Delete在删除表或视图中的数据时触发
DDL事件Create在创建新对象时触发
DDL事件Alter修改数据库或数据库对象时触发
DDL事件Drop删除对象时触发
数据库事件Sartup数据打开时触发
数据库事件Shutdown在使用NORMAL或IMMEDIATE选项关闭数据库时触发
数据库事件Logon当用户连接到数据库并建立会话时触发
数据库事件Logoff当一个会话从数据库中断开时触发
数据库事件Servererror发生服务器错误时触发

8.7.3 更改和删除触发器

  1. 更改触发器
    ALTER
  2. 删除触发器

8.8 嵌入式SQL 320

8.8.1 SQL 与宿主语言接口

SQL提供了将SQL语句嵌入到某种高级语言中的方式，通常采用预编译的方法。

将SQL嵌入主语言使用时应该注意以下问题：

  1. 区分主语言与SQL语句的方式
      EXEC SQL <SQL语句>
  2. 主语言工作单元与数据库工作单元通信 （10年第32题）
    1）SQL 通信区（SQL Communication Area, SQLCA）
    是系统默认定义的全局变量。向主语言传递SQL 语句执行的状态信息，使主语言能够根据此信息控制程序流程。
    2）主变量（共享变量）
    主语言通过主变量向SQL 语句提供参数，主变量是由主语言的程序定义的，并用SQL 的DECLARE 语句说明。
    在SQL 语句中，为了与SQL 中的属性名区分，在引用共享变量时，前面需要加 “：”
    例：
    EXEC SQL BEGIN DECLARE SECTION;
    char Msname[4], Msex[3], givensno[5];
    int Mage;
    char SQLSTATE[6]; //特殊的共享变量，解释SQL语句的执行状况
    EXEC SQL END DECLARE SECTION;
    （1）根据共享变量givensno 值查询学生关系students中学生的姓名、年龄和性别。
    EXEC SQL SELECT sname,age,sex
    INTO :Msname, :Mage, :Msex
    FROM students
    WHERE sno = :givensno;
    （2）某学生选修了一门课程，将其插入学生选课表SC中，假设学号、课程号、成绩已分别赋给主变量HSno、 Hcno 和 Hgrade。
    EXEC SQL INSERT INTO SC(Sno,Cno,Grade)
    Values (:HSno, :HCno, :Hgrade);
    3）游标（14年第52题）
    SQL 语言是面向集合的，一条 SQL 语句可以产生或处理多条记录。而主语言是面向记录的，一组主变量一次只能放一条记录，所以，引入游标，通过移动游标指针来决定获取哪一条记录。
    （1）定义游标
    语句格式：
    EXEC SQL DECLARE <游标名称> CURSOR FOR
      <SELECT语句>
    END_EXEC
    ♥ 它只是一条说明性语句，定义游标后，其中的SELECT语句并不立即执行。
    （2）打开游标
    语句格式：
    EXEC SQL OPEN <游标名称> END_EXEC
    ♥ 该语句执行游标定义中的SELECT语句，同时游标处于活动状态。游标是一个指针，此时指向查询结果的第一行之前。
    （3）推进游标
    语句格式：
    EXEC SQL FETCH <游标名> INTO <变量表> END_EXEC
    ♥ 该语句执行时，游标推进一行，并把游标指向的行（称为当前行）中的值取出，送到共享变量中。
    （4）关闭游标
    EXEC SQL CLOSE <游标名> END_EXEC
    ♥ 该语句关闭游标，使它不再和查询结果相联系。游标关闭后，后面还可以再打开。

数据库有空值，而高级语言中变量没有空值，所以当查询的记录某一属性为空值时，无法将空值赋给主变量，此时主变量仍保持原有值。同样，更新语句也存在主变量不能取空值问题。引入指示变量，用来标识对应主变量值是否为空值，可以解决此问题。（09年第56题/14年第53题）

8.8.2 动态SQL

嵌入式SQL用于高级语言（主语言）和数据库的交互。高级语言用于客户端，实现界面及与用户的交互SQL语言用于后台数据库，主语言将变量值传给SQL，或SQL将值传给主语言，是通过主变量来实现的，主语言需要对SQL语句的执行状态（是否执行成功、查询结果的记录数等）进行检查以确定下一步的处理，需要DBMS将SQL语句执行状态写入SQL通信区（即SQLCA）,主语言从中提取；游标可以将SQL查询到的多条记录逐条提取赋给主变量，交由主语言处理。

在C/S 体系结构中，客户端执行的操作是嵌入式SQL。（09年第55题）

B/S体系结构和C/S体系结构是数据库应用系统常用的两种结构。C/S体系结构通常用于企业内部网络，主要面向企业内部员工，在用户和地域上相对集中，业务逻辑在客户端实现，维护时需要对每一台客户机进行维护；B/S结构主要构建于广域网上，如Internet,用户相对分散，业务逻辑在服务器端实现，维护主要集中在服务器端，便于远程维护，软件重用性高。（11年第57题）

三层C/S 体系结构由逻辑上相互分离的表示层、业务层和数据层构成。其中表示层向客户提供数据，业务层实施业务和数据规则，数据层定义数据访问标准。该体系结构具有很多优点，如逻辑上相对独立，不同层可以用不同的平台、软件和开发语言，但是系统的安装、修改和维护在各层都可能进行。（17年第25题）

8.9 SQL-99所支持的对象关系模型 323

8.9.1 嵌套关系 323

8.9.2 复杂类型 326

8.9.3 继承 329

8.9.4 引用类型 332

8.9.5 与复杂类型有关的查询 332

8.9.6 函数和过程 335

第 9 章 非关系型数据库 NoSQL 341

9.1 NoSQL 概述 341

9.2 相关理论基础

9.2.1 一致性 342

CAP理论（17年第61题）
对于一个分布式系统，一致性、可用性和分区容忍性三个特点最多只能三选二。
（1）一致性 (Consistency)
指系统在执行了某些操作后仍处于一个一致的状态。
（2）可用性 (Availablity)
指对数据的所有操作都有成功的返回。简言之，就是任何请求不管成功或失败都有响应。
（3）分区容忍性 (Partition tolerance)
这一概念的前提是在网络发生故障的时候。 在网络连接上，一些结点出现故障，使得原本连通的网络变成了一块一块的分区， 若允许系统继续工作，那就是分区可容忍的。

ACID理论
（1）原子性 (Atomicity)（14年第45题）
事务的所有操作在数据库中要么都做要么都不做。 不可分割（indivisible）
（2）一致性 (Consistency)
一个事务独立执行的结果，将保持数据的一致性，即数据不会因为事务的执行而遭受破坏。只有一致性属性是并发控制子系统的责任。以确保DBMS 和应用程序开发人员都有责任确保一致性
（3）隔离性 (Isolation) （11年第54题/14年第46题）
一个事务的执行不能被其他事务干扰。并发事务在执行过程中可能会对同一数据进行操作，这些事务的操作应该不会相互干扰，是相互隔离的。
（4）持久性 (Durability)（10年第34题/15年第56题）
一个事务一旦提交，它对数据库的改变必须是永久的， 即使系统出现故障也是如此。

BASE理论
由于CAP 理论的存在，为了提高性能，出现了ACID 的一种变种BASE，它是一个弱一致性的理论，只要求最终一致性。
• BA (Basically Available)：基本可用
• S (Soft state)：软状态，可以理解为“无连接的”的，而与之相对应的是“面向连接”的。
• E (Eventual consistency)：最终一致性，最终整个系统看到的数据是一致的。

9.2.2 分区 344

9.2.3 存储分布 344

9.2.4 查询模型 347

9.3 NoSQL 数据库的种类 349

（15年第63题/16年第63题/18年第70题/19年第69题）

NoSQL 数据库保证的是BASE特性。

Mongodb是一种分布式文档存储数据库，旨在为Web应用提供可拓展的高性能数据存储解决方案。该数据库是一个高性能、开源、无模式的文档型数据库。
Memcached是一种高性能的分布式内存对象缓存数据库，通过缓存数据库查询结果，减少数据库访问次数，以提高动态Web应用的速度，提高可拓展性。
Neo4j是一个高性能的NoSQL图形数据库。该数据库使用图（graph）相关的概念来描述数据模型，把数据保存为图中的节点以及节点之间的关系。
HBase(Hadoop Database) 是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统。

9.3.1 文档存储 350

9.3.2 键值存储 355

9.3.3 列存储 362

9.3.4 图存储 365

9.3.5 其他存储模式 367

9.4 NoSQL 应用案例与新技术 369

9.4.1 HBase 数据库 369

9.4.2 云数据库 GeminiDB 371

第10章 系统开发和运行知识 373

10.1 软件工程基础知识 373

软件需求包含的层次

  1. 业务需求
    反映了组织结构或客户对系统、产品高层次的目标要求，他们在项目视图与范围文档中予以说明。
  2. 用户需求
    文档描述了用户使用产品必须要完成的任务，这在使用实例文档或方案脚本说明中予以说明
  3. 功能需求
    定义了开发人员必须实现的软件功能，使得用户能完成他们的任务，从而满足了业务需求。所谓特性是指逻辑上相关的功能需求的集合，给用户提供处理能力并满足业务需求
  4. 非功能性需求 （13年第14题）
    它描述了系统展现给用户的行为和执行的操作等。它包括产品必须遵从的标准、规范和合约；外部界面的具体细节，性能要求，设计或实现的约束条件及质量属性。

10.1.1 软件生存周期 373

软件生存周期（17年第29题）
（1）可行性分析与项目开发计划
（2）需求分析
（3）概要设计
（4）详细设计
（5）编码和单元测试
（6）综合测试
（7）维护

补充知识点：
模块的扇入扇出适中，模块大小适中以及完善模块功能都可以改进设计质量。（17年第26题）

10.1.2 软件生存周期模型 375

  1. 瀑布模型（Waterfall Model）
    优点：容易理解，管理成本低；强调开发阶段性早期计划及需求调查和产品测试
    缺点：客户必须完整、正确、清晰的表达他们的需求
  2. 增量模型（Incremental Model）
  3. 演化模型（Evolutionary Model）
    优点：任何功能一经开发就能进入测试
    缺点：如果不加控制地让用户接触开发中尚未稳定的功能，可能对开发人员以及用户都会产生负面影响
  4. 螺旋模型（Spiral Model）（15年第27题）
    （1）制订计划
    （2）风险分析
    （3）实施工程
    （4）用户评估
  5. 喷泉模型（Fountain Model）
    优点：提高软件项目开发效率，节省开发时间

10.1.3 典型的软件开发方法 378

  1. 结构化开发方法
    ♥ 面向数据流的设计是以需求分析阶段产生的数据流图为基础，按一定的步骤映射成软件结构，因此又称结构化设计。该方法由美国IBM 公司提出，与结构化分析（SA）衔接，构成了完整的结构化分析与设计技术，目前使用最广泛的设计方法之一。
    ♥ 各种软件系统，不论DFD 如何庞大和复杂，一般可分为变换型和事务型，一个软件系统既可以只有一种数据流类型，也可以是两种数据流类型，在结构化设计中，可以将数据流映射为软件系统的木块结构，不同类型的数据流有不同的映射方法。（14年第15题）
    ♥ 可以按照在软件系统中的功能将模块分为四种类型。（14年第16题）
    传入模块：取得数据或输入数据，经过某些处理，再将其传送给其他模块。
    传出模块：在输出之前可能进行某些处理，数据可能被输出到系统的外部，或者会输出到其他模块进行进一步处理。
    变换模块：从上级调用模块得到数据，进行特定的处理，转换成其他形式，在将加工结果返回给调用模块
    协调模块：一般不对数据进行加工，主要是通过调用、协调和管理其他模块来完成特定的功能。
  2. 原型化开发方法
  3. 面向对象开发方法
  4. 敏捷方法（09年第15题）
    敏捷方法中，重构是一种重新组织技术，重新审视需求和设计，重新明确地描述它们以符合新的和现有的需求，可以简化构件的设计而无需改变其功能或行为。

统一过程（RUP/UP，Rational Unified Process）（13年第15题）
是一种以用例驱动、以体系结构为核心、迭代增量的软件过程模型。
① 初始阶段
目标是为系统建立商业案例并确定项目的边界
② 细化阶段
目标是分析问题的领域，建立健全的体系结构基础，编制项目计划，淘汰项目中最高风险的元素
③ 构造阶段
所有剩余的构件和应用程序功能被开发并集成为产品，所有的功能被详细测试。
④ 交付阶段
确保软件对最终用户是可用的。

10.1.4 软件项目管理 379

（11年第18题）

  1. 成本估算
    （1）成本估算方法
    ① 自顶向下估算方法
    优点：对系统级工作的重视，所以估算中不会遗漏诸如集成、配置管理之类的系统级事务的成本估算，且估算工作量小，速度快
    缺点：低级别上的技术性困难问题使成本上升
    ② 自底向上估算方法
    优点：对每一部分的估算交给负责该部分工作的人来做，所以估算较为准确
    缺点：估算往往缺少各项子任务之间相互联系所需的工作量和与软件开发有关的系统级工作量，所以估算往往偏低
    ③ 差别估算方法
    优点：提高估算的准确度
    缺点：不容易明确“差别” 的界限
    ④ 其他估算方法：专家估算法，类推估算法，算式估算法
    （2）成本估算模型
    常用的软件成本估算模型：Putnam模型，COCOMO模型（参数难以确定）
    COCOMO 模型的种类：（14年第17题）
    ① 基本COCOMO 模型
    静态单变量模型，对整个软件系统进行估算
    ② 中级COCOMO 模型
    静态多变量模型，将系统分为系统和部件两部分
    ③ 详细COCOMO 模型
    将软件系统模型分为系统、子系统和模块
  2. 风险分析（11年第17题/12年第19题/14年第19题）
    风险是一种具有负面后果的，人们不希望发生的事件。
    在进行风险管理时，根据风险的优先级来确定风险控制策略，而优先级是根据风险暴露来确定的。风险暴露是一种量化风险影响的指标，等于风险影响乘以风险的概率。（15年第19题）
    风险影响是风险发生时造成的损失
    风险概率是风险发生的可能性
    风险控制是风险管理的一个重要活动
    （1）风险识别
    （2）风险预测
    （3）风险评估
    （4）风险控制
  3. 进度管理（10年第15题/14年第18题）
    1）Gantt 图

    Gantt 图能清晰地描述每个任务从何时开始，到何时结束，任务的进展情况以及各个任务之间的并行性。但它不能清晰地反映出各任务之间的依赖关系，难以确定整个项目的关键所在，也不能反映计划中有潜力的部分。
    2）PERT 图 （09年第17、18题/13年第16题）

PERT 图不能清晰地描述各任务之间的并行情况。
一种有向图，图中的箭头表示任务，它可以标上完成该任务所需的时间；图中的节点表示流入节点的任务的结束，并开始流出结点的任务。
• 活动（任务）：
• 节点（事件、里程碑）：它本身不消耗时间和资源，仅表示某个时间点。
• 前驱、后继：如果从节点1到节点2之间有路径，则称1为2的前驱， 2为1的后继。
• 最早开始时间：活动或节点最早开始的时间。
• 最晚开始时间：活动或节点最晚必须在这个时间开始， 否则就会影响整个工期。
• 最早结束时间：活动或节点最早结束的时间。
• 最晚结束时间：在不影响整个工期的前提下，活动或节点最晚结束的时间。
• 松弛时间（浮动时间）：在不影响整个工期的前提下，完成该活动有多少机动余地。
• 总工期：完成整个项目所需要的时间。
• 关键活动：最早开始时间等于最晚开始时间的活动。
• 关键路径：由关键活动串联起来的路径。关键路径可能有多条

求关键路径的方法（11年第19题/12年第17题/17年第15题）

  1. 找出从开始节点到结束节点之间的所有路径，计算出每条路径所经历的时间总和，总和最长的就是关键路径，关键路径上的时间总和就是总工期。
  2. 依次找出每个节点的最早开始时间和最晚开始时间，最早开始时间和最晚开始时间相同的节点 联起来的路径就是关键路径。

求松弛时间的方法（17年第16题）
• 节点的最早开始时间：从起点到该节点所经历的最长时间。
• 节点的最晚开始时间：项目总工期减去项目终点到该节点的最长时间。
• 活动的最早开始时间：活动的最早开始时间就是该活动的起始节点的最早开始时间。
• 活动的最晚开始时间：活动的流入节点的最晚开始时间减去该活动的持续时间。
• 活动/节点的松弛时间 = 活动/节点的最晚开始时间－活动/节点的最早开始时间
5. 人员管理
程序设计小组的组织形式：
（1）主程序员组
（2）无主程序员组 （12年第18题）
（3）层次式程序员组

沟通路径的计算 （11年第15题/17年第19题）
假设开发小组由8名人员组成
♥ 无主程序员沟通路径
=( n × (n-1) ) / 2 =（8 × 7）/2 = 28
♥ 主程序员沟通路径
= 8-1 = 7

10.2 系统分析基础知识 384

10.2.1 系统分析概述 385

10.2.2 需求分析 385

确定系统边界属于需求分析阶段的内容。（10年第24题）

10.2.3 结构化分析方法 386

  1. 数据流图/数据流程图（Data Flow Diagram，DFD）（12年第15题）
    作用 （15年第28题/16年第17题）
    描述数据在系统中如何被传送或变换，以及描述如何对数据流进行变换的功能，用于功能建模。
    应注意的问题
    ① 适当地为数据流、加工、数据存储、外部实体命名，名字应反映该成分的实际含义，避免空洞的名字
    ② 画数据流而不要画控制流
    ③ 每条数据流的输入或者输出是加工
    ④ 一个加工的输出数据流不应与输入数据流同名，即使它们的组成成分相同
    ⑤ 允许一个加工有多条数据流流向另一个加工，也允许一个加工有两个相同的输出数据流流向两个不同的加工
    ⑥ 保持父图与子图平衡
    ⑦ 在自顶向下的分解过程中，若一个数据存储首次出现只与一个加工有关，那么这个数据存储不必画出
    ⑧ 保持数据守恒
    ⑨ 每个加工必须有输入数据流，又有输出数据流
    ⑩ 在整套数据流图中，每个数据存储必须既有读的数据流，又有写的数据流，但在某一张子图中可能只有读没有写，或者只有写没有读
  2. 数据字典（DD）
  3. 加工逻辑的描述

接口设计是描述软件与外部环境之间的交互关系，软件内模块之间的调用关系，而这些关系的依据主要是分析阶段的数据流图。（17年第17、18题）

10.2.4 面向对象分析方法 392

  1. 面向对象的基本概念
    （1）对象
    （2）消息
    （3）类
    （4）继承
    （5）多态（17年第27题）
        不同类的对象对同一消息作出不同的响应就叫做多态
    在运行时，可以通过指向基类的指针，来调用实现派生类中的方法。也就是说客户类在调用方法时，并不知道特定子类的实现，都会用统一的方法来调用。
    多态存在的三个条件
    ① 有继承关系
    ② 子类重写父类方法
    ③ 父类引用指向子类对象
    （6）动态绑定（Dynamic Binding）

  2. 统一建模语言（Unified Modeling Language，UML）概述 （09年第71-75题）
    1）UML 的结构
    2）事物
    （1）结构事物
    （2）行为事物
    （3）分组事物
    （4）注释事物
    3）关系
    对象图展现了一组对象以及他们之间的关系，描述了类实例的静态快照

10.3 系统设计基础知识 403

10.3.1 系统设计内容和步骤 403

10.3.2 系统设计的基本原理 405

  1. 抽象
  2. 模块化
  3. 信息隐蔽
    提高软件的可修改性和可测试性和可移植性
  4. 模块独立 （20年第27、28题）
    尽量做到高内聚，低耦合
    1）耦合
    模块的耦合度表现了模块之间相互关联的程度，分为 6 级。
    耦合性越高，则模块的独立性越差。
    模块间耦合的高低取决于模块间接口的复杂性、调用的方式以及传递的信息。 （18年第25题）
    ① 无直接耦合
    两个模块间没有直接的关系，从属于不同模块的控制与调用，之间不传递消息
    ② 数据耦合
    一个模块访问另一个模块时，彼此之间是通过简单数据参数（不是控制参数、公共数据结构或外部变量）来交换输入、输出信息的。
    ③ 标记耦合（19年第25题）
    一组模块通过参数表传递记录信息，就是标记耦合。这个记录是某一数据结构的子结构，而不是简单变量。
    ④ 控制耦合
    指一个模块调用另一个模块时，传递的是控制变量，被调模块通过该控制变量的值有选择地执行块内的某一功能。
    ⑤ 公共耦合
    若一组模块都访问同一个公共数据环境，则它们之间的耦合就成为公共耦合。公共的数据环境可以是全局数据结构、共享的通信区、内存的公共覆盖区等。
    ⑥ 内容耦合（11年第16题）
    程度最高的耦合，当一个模块调用另一个模块的内部数据，或通过非正常入口进入另一个模块内部，这种模块之间的耦合为内容耦合，这种情况往往出现在会变程序设计中。
耦合程度从低到高的顺序：
非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。
最好的是非直接耦合，没有直接联系，模块之间不相互依赖于对方。最差的是内容耦合，一个模块访问了另一个模块的内部数据。

2）内聚
① 偶然内聚
指一个模块内的各个处理元素之间没有任何联系
② 逻辑内聚（12年第16题）
指模块内执行几个逻辑上相似的功能，通过参数确定该模块完成哪一个功能
③ 时间内聚
把需要同时执行的动作组合在一起形成的模块
④ 通信内聚
指模块内所有处理元素都在同一个数据机构上操作，或者值各处处理使用相同的输入数据或者产生相同的输出数据
⑤ 顺序内聚
指一个模块内各个处理元素都密切相关于同一功能且必须顺序执行，前一功能元素的输出就是下一功能元素的输入
⑥ 功能内聚
最强的内聚。指模块内所有元素共同完成一个功能，缺一不可。

内聚程度从高到低的顺序：
功能内聚、顺序内聚、通信内聚、过程内聚、瞬时内聚、逻辑内聚和偶然内聚。

10.3.3 结构化设计方法 407

10.3.4 面向对象设计方法 409

10.4 系统测试基础知识 410

10.4.1 系统测试的概念 410

软件测试的目的是发现软件的错误，验证软件是否满足用户需求，并通过分析软件错误产生的原因，以帮助发现当前开发工作所采用的软件过程缺陷，以便进行软件过程改进。软件测试不能发现软件中的所有错误，也不能保证软件完全正确。软件测试应尽早开始，而不是实现之后再开始，在需求分析阶段即可准备相关测试。

ISO软件质量模型：
软件质量的六大特性：
功能性、可靠性、易用性、效率、维护性、可移植性
软件质量的27个子特性：
功能性：适合性、准确性、互操作性、安全性、功能性的依从性
可靠性：成熟性、容错性可恢复性、可靠性的依从性
易用性：易理解、易学习、易操作、吸引性、可使用性的依从性
效率：时间特性、资源特性、效率的依从性
维护性：易分析性、稳定性、易变更性、易测试性、可维护性的依从性
可移植性：适应性、易安装性、遵循性、易替换性、可移植性的依从性

10.4.2 软件测试策略 411

  1. 软件测试策略
    （1）单元测试
    （2）集成测试
    （3）确认测试
    （4）系统测试
  2. 测试方法
    回归测试是修改了旧代码后，重新进行测试以确认修改没有引入新的错误或导致其他代码产生错误。（13年第17题）

10.4.3 软件测试方法 415

  1. 黑盒测试法
    功能测试，在完全不考虑软件的内部结构和特性的情况下，测试软件的外部特性
  2. 白盒测试法（10年第14题）
    也称结构测试，根据程序的内部结构和逻辑来设计测试用例

10.5 系统运行和维护基础知识 418

10.5.1 系统维护概述 418

10.5.2 系统评价 420

10.6 软件开发方法新进展 421

10.6.1 面向方面的方法 421

10.6.2 软件复用与构件化方法 421

10.6.3 服务化方法 423

第11章 数据库设计

11.1 数据库设计概述

11.1.1 数据库应用系统的生命期

（12年第32-33题）
（1）数据库规划
（2）需求描述与分析
（3）数据库与应用程序设计
是对用户数据的组织和存储设计，应用程序设计是在数据库设计基础上对数据操作及业务实现的设计，包括事务设计和用户界面设计。
（4）数据库设计实现
（5）测试
（6）运行维护

11.1.2 数据库设计的一般策略

（1）自顶向下（Top Down）
（2）自底向上（Bottom Up）

11.1.3 数据库设计的基本步骤

（17年第29题 / 21年第61题）
（1）用户需求分析
（2）概念结构设计
（3）逻辑结构设计
（4）物理结构设计
（5）数据库实施阶段
（6）数据库运行和维护阶段

11.2 系统需求分析

11.2.1 需求分析的任务、方法和目标

需求调查的内容：（09年第57题）
（1）信息要求
（2）处理要求
（3）系统要求，包括安全性要求、使用方式要求和可扩充性要求

11.2.2 需求分析阶段的文档

（09年第58题）

  1. 数据流图（DFD）（11年第58题/15年第28题/18年第61题）
    作用：描述对数据的处理流程
  2. 数据字典（DD）（12年第53题）
    是各类数据描述的集合，是关于数据库中数据的描述，即元数据，而不是数据本身。
    ① 数据项（15年第44题）
    {数据项名，数据项含义说明，别名，数据类型，长度，取值范围，取值含义，与其他数据项的逻辑关系}
    ② 数据结构
    ③ 数据流
    ④ 数据存储
    ⑤ 处理过程

11.2.3 案例分析

11.3 概念结构设计

数据库概念结构设计阶段是在需求分析的基础上，按照用户需求对信息进行分类、聚集和概括，建立概念模型。（09年第59题/17年第29题）
① 首先确定相关的实体，即将所有对象进行分类
② 然后根据各类确定的实体，找出每一实体应具有的属性，这一过程称为聚集
③ 再从相关实体中抽象出子类和父类，这一过程称为概括。

概念结构设计阶段完成的文档是 E-R 图。（10年第36题）

11.3.1 概念结构设计策略与方法

11.3.2 用E-R 方法建立概念模型

概念结构设计工作步骤（17年第38题）
（1）抽象
（2）设计局部视图
（3）合并取消冲突
（4）修改重构消除冗余

  1. 选择局部应用
  2. 逐一设计分E-R图
    （1）属性不可再分，即属性不再具有需要描述的性质，不能有属性的属性
    （2）属性不能与其他实体发生联系，联系是实体与实体间的联系
  3. E-R图合并（12年第55-56题/14年第58-59题/16年第29题）
    分E-R图合并时，存在的冲突：
    （1）属性冲突
    同一属性可能会存在于不同的分E-R图，由于设计人员不同或出发点不同，对属性的类型，取值范围，数据单位等可能不一致。
    （2）命名冲突
    相同意义的属性，在不同的分E-R图上有着不同的命名；名称相同的属性在不同的分E-R图中代表着不同的意义
    （3）结构冲突
    同一实体在不同的分E-R图中有不同的属性，同一对象在某一分E-R图中被抽象为实体而在另一分E-R图中又被抽象为属性。

11.4 逻辑结构设计

逻辑结构设计阶段（09年第60题/16年第32题）
（1）转换为数据模型
（2）关系规范化
（3）模式优化
（4）设计用户子模式（视图设计）

11.4.1 E-R 图向关系模式的转换

1. 实体向关系模式的转换
2. 联系向关系模式的转换 （11年第37-38题）
（1）一对一联系(1:1)
① 将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性包括该联系所关联的两个实体的码及联系的属性，关系的码取自任一方实体的码。
任职(班主任工号，班级编号，任职时间)
② 将联系归并到关联的两个实体的任意一方，给待归并的一方实体属性集中增加另一方实体的码和该联系的属性即可，归并后的实体码保持不变。
班主任（工号，姓名，身份证号，住址，班级编号，任职时间）
或： 班级（班级编号，名称，人数，班主任编号，任职时间）

（2）一对多联系的转换(1：N)
① 将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个实体的码及联系的属性，关系的码是多方实体的码。
任职（工号，公司编号，入职时间，离职时间）
② 将联系归并到关联的两个实体的多方，给待归并的多方实体属性集中增加一方实体的码和该联系的属性即可，归并后的多方实体码保持不变。
员工（工号，姓名，身份证号，公司编号，入职时间，离职时间）

（3）多对多联系的转换(N:N)（12年第28题）
• 多对多联系只能转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个多方实体的码及联系的属性，关系的码是多方实体的码构成的属性组。
选修（学号，课程编号，成绩，出勤率）
• 注：三方联系的多对多对多（N:N:N）也是一样，只能转换成一个独立的关系模式，如：一个供应商可以给多个项目供应多种零件，一个项目可以使用多个供应商供应的多种零件。
供应关系（供应商编号，项目编号，零件号，数量）

11.4.2 关系模式的规范化

11.4.3 确定完整性约束

11.4.4 用户视图的确定

11.4.5 应用程序设计

11.5 数据库的物理设计

物理设计应该考虑的因素：（18年第64题）
（1）事务的执行频率
（2）使用频繁的查询操作
（3）索引设计（11年第59题）

11.5.1 数据库物理设计工作过程

11.5.2 数据库物理设计工作步骤

在数据库中建立存取路径最普遍的方法是建立索引。（12年第54题）

11.6 数据库系统的实施阶段

11.7 数据库运行维护与管理

11.7.1 制定数据库系统的运行计划

11.7.2 数据库系统的运行和维护

  1. 监控数据的收集与分析
  2. 稳定运行中的业务连续性
  3. 数据库维护
    （1）对数据库性能的监测和改善
    （2）数据库的备份及故障恢复
    （3）数据库重组和重构（21年第67题）
    ① 数据库的重组是指在不改变数据库逻辑和物理结构的情况下，去除数据库存储文件中的废弃空间以及碎片空间中的指针链，使数据库记录在物理上紧连。
    ② 数据库的重构是指对数据库的结构做出修改。
  4. 数据库系统的运行统计
  5. 数据库系统的审计（19年第67题）
    ① 记录数据库资源和权限的使用情况
    ② 被动的，可以跟踪但是不能防止
    ③ 会影响到系统的性能，审计跟踪信息会被保存下来引起存储空间的问题
    解决方法：根据不同级别有选择的进行审计。

11.7.3 数据库系统的管理

11.7.4 性能调整

  1. SQL 语句的编码校验（19年第65、66题）
    （1）尽可能地减少多表查询或建立物化视图
    （2）以不相关子查询替代相关子查询
    （3）只检索需要的列
    （4）用带IN 的条件子句等价替换OR子句
    （5）经常提交COMMIT,以尽早释放锁
  2. 表设计的评价
    （1）如果频繁的访问是对两个相关的表进行连接操作，则考虑将其合并
    （2）如果频繁的访问只是在表中的某一部分字段上进行，则考虑分解表，将该部分单独作为一个表
    （3）对于更新很少的表，引入物化视图
    物化视图是一种特殊的物理表，物化视图是相对普通视图而言的，普通视图是虚拟表，任何对视图的查询，都需要转换为对应的SQL 语句进行查询
  3. 索引维护和改进（19年第62~64题 ）
    （1）如果查询是瓶颈，则在关系上建立适应的索引，通常在作为查询条件的属性上建立索引，可以提高查询效率
    （2）如果更新是瓶颈，每次更新都会重建表上的索引，引起效率的降低，则考虑删除某些索引
    （3）选择适当的索引类型，如果是经常使用范围查询，则B树索引比散列索引更高效
    （4）将有利于大多数据查询和更新的索引设为聚簇索引（Cluster）（10年第38题 ）
  4. 设备增强

补充知识点：
聚簇索引要求物理记录次序与索引项次序一致，起到对物理记录的排序和重组织作用，可以提高某些查询的性能。 （09年第61题 ）

11.7.5 用户支持

第 12 章 事务管理 451

12.1 事务的基础概念 451

12.1.1 事务 451

1. 概述
1）事务的概念
事务是一系列的数据库操作，是数据库应用程序的逻辑单位，即应用程序对数据库的操作都应该以事务的方式进行。
事务是一个操作序列，这些操作“要么都做，要么都不做”
事务是由单个用户或应用程序访问或更改数据库内容的动作或一系列动作
2）事务的定义语句
（1）事务开始：BEGIN TRANSACTION
（2）事务结束：END TRANSACTION
（3）提交事务：COMMIT TRANSACTION
该操作表示事务成功地结束，它将通知事务管理器该事务的所有更新操作现在可以被提交或永久地保留。
（4）回滚事务：ROLLBACK TRANSACTION
该操作表示事务非成功地结束，它将通知事务管理器出故障了，数据库可能处于不一致状态，该事务的所有更新操作必须回滚或撤销。

--例：从账户A转入账户B金额x元。  
BEGIN TRANSACTION             // 事务开始         
	read(A);                       // 读账户A的余额         
	A=A-x;                        // A账户金额减去x元         
	IF(A<0)  THEN                
		print (“金额不足，不能转账”) ;                 
		ROLLBACK;           // 撤销该事务，回到事务执行前的状态         
	ELSE                
		write(A);              // 写入账户A的余额                
		read(B);               // 读账户B的余额                
		B=B+x;                
		write(B);                
		COMMIT;             // 提交事务         
		ENDIF;  
END TRANSACTION              // 事务结束

2. SQL 中事务的开始与结束（15年第53题）
SQL 标准规定当一条SQL 语句被执行，就隐式地开始了一个事务，SQL 中的Commit work 和Rollback work 语句之一会结束一个事务。
（1）Commit work
提交当前事务。这意味着该事务所做的更新在数据库中永久保存。一但事务被提交后，一个新的事务自动开始。
（2）Rollback work （11年第55题）
回滚当前事务。这意味着将撤销该事务对数据库的更新。
注意：如果事务已经执行了Commit work，就不能再用Rollback来撤销。对断电、系统崩溃的情况，回滚是在系统重新启动时进行。

显式事务：显式事务又称自定义事务，指用显式的方式定义其开始和结束的事务
隐式

12.1.2 事务的特性 452

（17年第50题）
(1) 原子性 (Atomicity)
要么全做要么全都不做
(2) 一致性 (Consistency)
数据不会因为事务的执行而遭到破坏
(3) 隔离性 (Isolaion)（11年第36题）
一个事务的执行不能被其他事务干扰
(4) 持久性 (Durability)
一个事务一旦提交，对数据库的改变必须是永久的，即便系统出现故障也是如此。

12.1.3 事务的状态 453

1. 事务的状态
（1）活动状态
事务的初始状态，事务执行时处于这个状态。
（2）部分提交状态
当操作序列的最后一条语句执行后，事务就处于部分提交状态。 这时，事务虽然已经完全执行，但由于实际输出可能还临时驻留在内存中，在事务 成功完成前还有可能出现硬件故障，因此，部分提交状态并不等于事务成功执行。
（3）失败状态
由于硬件或逻辑错误，使得事务不能继续正常执行，事务就进入了失败状态，处于失败状态的事务必须回滚。这样，事务就进入了中止状态。
（4）中止状态
事务回滚并且数据库恢复到事务开始执行前的状态。
（5）提交状态
当事务成功完成后，称事务处于提交状态。只有事务处于提交状态后，才能说事务已经提交。

2. 事务的状态转换

• BEGIN TRANSACTION：
开始运行事务，使事务进入活动状态
• END TRANSACTION：
说明事物中的所有读写操作都已完成，使事务进入部分提交状态，把事务的所有操作对数据库的影响存入数据库。
• COMMIT：
标志事务已经成功地完成，事务中的所有操作对数据库的影响已经安全地存入数据库， 事务进入提交状态，结束事务的运行。
• ABORT：
标志事务进入失败状态，系统撤销事务中所有操作对数据库和其他事务的影响，结束事务的运行。

事务进入中止状态后，系统一般有如下两种选择：
（1）重启事务：当事务中止的原因是软硬件错误而不是事务内部逻辑错误时，一般采用重启事务的方法。重启事务可以被看成一个新事务
（2）杀死事务：这样做通常是因为事务中止的原因是事务内部的逻辑错误，或者输入错误，也可能是所需数据在数据库中没找到

12.2 数据库的并发控制 455

12.2.1 事务调度 455

1. 串行调度
是指多个事务依次串行执行，且只有当一个事务的所有操作都执行完成才执行另一个事务的所有操作。
例：有两个事务T0和T1，事务T0从账号A转2000元到账号B；事务T1从账号A转20%的款到账号B。T0和 T1的定义如下所示


2. 并发调度
利用分时的方法同时处理多个事务。

3. 可恢复调度
指满足这样的条件的调度：当事务Tj要读事务Ti写的数据时，Ti事务必须要先于事务Tj提交

12.2.2 并发操作带来的问题 458

（09年第45-46题/11年第38、56题/13年第37题）

  1. 丢失修改
    T1 事务对数据库的修改被T2 事务覆盖而丢失了，破坏了事务的隔离性
  2. 不可重复读
    同一事务内对同一组数据的相同运算结果不同，事务T2 干扰了事务T1 的独立性
  3. 读脏数据
    T1 对数据C 修改之后，在t4 时刻T2 读取修改后的C值做处理，之后T1 回滚，数据C 恢复了原来的值，T2 读的是被丢掉的垃圾
  4. 幻读（补充知识点）（14年第54题）
    一个事务按相同的查询条件查询之前检索过的数据，却发现检索出来的结果集条数变多或者减少(由其他事务插入、删除的)，类似产生幻觉。
    例如：事务T1 中有两次查询学生表中的男生人数，在这两次查询执行中间，事务T2 对学生表中加入了一条男生记录，导致T1 两次查询的结果不一致。此时产生了幻读。

12.2.3 并发调度的可串行性 459

冲突等价（conflict equivalent）
如果调度S 经过一系列非冲突命令交换成S*，则称S 与S* 是冲突等价
冲突可串行化（conflict serializable）
若调度S 与一个串行调度S* 冲突等价，则S 是冲突可串行化的

12.2.4 并发控制技术 461

（13年第31题/15年第45-46题）
排它锁 (Exclusive Locks，简称X锁，写锁)
如果事务T 对数据A 加上X 锁后，就只允许事务T 读取和修改数据A，其他事务对数据A 不能再加任何锁，从而也不能读取和修改数据A，直到事务T 释放A 上的锁。
共享锁 (Share Locks，简称S锁，读锁)
如果事务T 对数据A 加上了S 锁后，事务T 就只能读数据A 但不能修改，其他事务可以再对数据A 加S 锁来读取，只要数据A 上有S 锁，任何事务都只能再对其加S 锁读取而不能加X 锁修改。

12.2.5两段锁协议 462

（15年第54题）

  1. 一级封锁协议
    事务T 在修改数据之前必须先对其加 X 锁，直到事务结束才释放。
    解决了丢失修改，并保证事务T 是可恢复的。
    如果仅仅是读数据不对其进行修改是不需要加锁的。
  2. 二级封锁协议
    是一级封锁协议加上事务T 在读取数据A 之前必须对其加上 S 锁，读完后即可释放S 锁。
    使得一个事务不能读取被其他事务修改中的数据。
    解决了脏读。
  3. 三级封锁协议
    是一级封锁协议加上事务T 在读取数据之前必须对其加上 S 锁，直到事务结束才释放S 锁。
    使得一个事务读取数据期间，其他事务只能读取该数据而不能修改。
    解决了不可重复读。

例：如果想要解决读脏数据，可以使用的方法
解：二级封锁协议和三级封锁协议

两段锁协议：
第一阶段：获得封锁，扩展阶段
第二阶段：释放封锁，收缩阶段

两段封锁协议可以保证可串行化，它把每个事务分解为加锁和解锁两段。但是可能会发生死锁。（17年第51题）

12.2.6 多粒度封锁协议 463

12.2.7 案例分析 465

12.3 数据库的备份与恢复 467

12.3.1 数据库系统故障种类 467

（09年第47题/16年52,53题/17年第53题）

  1. 事务故障（11年第33题/13年第38题）
    ♥ 事务故障是指由于事务程序运行过程中，因为非预期的原因，导致在运行过程中不能达到预期的终点(COMMIT 或显示的ROLLBACK )，造成数据库的不一致。
    ♥ 事务故障的恢复，急需要将产生故障的事务已经完成的对数据库的修改撤销。事务对数据库的修改内容被严格按照执行的时间顺序记录在日志中，可以通过逆向扫描日志文件，将产生故障的事务对数据库的操作逐一恢复(UNDO)，直到事务开始标志，就像该事务未执行一样，即完成恢复。
    DBMS 完成。
    ♥ 通常由如下两类错误引起事务执行失败
    （1）逻辑错误（11年第47题）
    如非法输入，找不到数据，溢出，超出资源限制等原因引起的事务执行失败。（比如a/b,b=0）
    （2）系统错误
    系统进入一种不良状态（如死锁），导致事务无法继续执行。
  2. 系统故障
    数据库系统在运行过程中可能会发生CPU 故障，这属于系统故障。在此类故障中，需要根据日志进行的操作为REDO+UNDO。
    DBMS完成。
    系统故障的恢复仅需要使用日志。（11年第48题）
    3. 介质故障
    指数据库的存储介质发生故障，如磁盘损坏、瞬间强磁场干扰等。这种故障直接破坏了数据库，会影响到所有正在读取这部分数据的事务。
    介质故障需要DBA介入，装载备份文件后交由DBMS进行恢复

12.3.2 数据库备份 468

数据转储（数据备份）
是将数据库自制到另一个磁盘或磁带上保存起来的过程。
（1）静态转储
在系统中无运行事务时进行的转储操作
    动态转储（14年第32题）
转储期间允许对数据库进行存取或修改。后备副本需要配合日志文件
（2）海量转储
每次转储全部数据库
    增量转储
每次只转储上一次转储后更新过的数据
（3）日志文件（14年第30题）
在事务处理的过程中，DBMS把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。
（4）数据库镜像 （09年第49题）
为了避免磁盘介质出现故障影响数据库的可用性，许多DBMS提供数据库镜像功能用于数据库恢复。

12.3.3 数据库恢复 469

  1. 数据库恢复操作的基本原理：冗余机制。

  2. 建立冗余数据常用技术
    (1) 数据转储
    (2) 登记日志文件

  3. 故障恢复的两个操作 （09年第48题）
    （1）撤销事务 (UNDO)
      将未完成的事务撤销，使数据库恢复到事务执行前的正确状态。
      撤销事务的过程：
        ① 反向扫描日志文件（由后向前扫描），查找事务的更新操作；
        ② 对该事务的更新操作执行逆操作，用日志文件记录中更新前的值写入数据库，插入的记录从数据库中删除，删除的记录重新插入数据库中；
        ③ 继续反向扫描日志文件，查找该事务的其它更新操作并执行逆操作直至事务开始标志。
    （2）重做事务 (REDO)
      将已提交的事务重新执行。
      重做事务的过程：
      从事务的开始标志起，正向扫描日志文件，重新执行日志文件登记的该事务对数据库的所有操作，直至事务结束标识。

  4. 故障恢复策略
    （1）事务故障的恢复
    事务故障是事务在运行至正常终止点（SUMMIT 或ROLLBACK）前终止，日志文件只有该事务的开始标识而没有结束标识。对这类故障的恢复通常是通过撤销（UNDO）产生故障的事务，使数据库恢复到该事务执行前的正确状态来完成的。
    事务恢复的步骤：
    ① 反向扫描日志文件，查找该事务的更新操作。
    ② 对事务的更新操作执行逆操作。
    ③ 继续反向扫描日志文件，查找该事务的其他更新操作，并做同样的处理，直到事务的开始标志。
    注：事务故障的恢复是由系统自动完成的，对用户是透明的。
    （2）系统故障的恢复（11年第32题）
    系统故障会使数据库的数据不一致：
    一是未完成的事务对数据库的更新可能已经写入数据库；
    二是已提交的事务对数据库的更新可能还在缓冲区没来得及写入数据库。
    因此对于系统故障，恢复操作是UNDO+REDO：（仅需要使用日志）
    ① 撤销故障发生时未完成的事务（UNDO）。
    ② 重做已经提交的事务（REDO）。
    （3）介质故障的恢复
    介质故障时数据库遭到破坏，需要重装数据库，一般需要DBA 的参与，装载故障前最近一次的备份和故障前的日志文件副本，再按照系统故障的恢复过程执行撤销（UNDO）和 重做（REDO）来恢复。

检查点机制（CHECKPOINT)：（17年第56题）
在日志中设置检查点，当发生故障需要利用日志文件恢复时，反向扫描日志文件，找到检查点，确认检查点时刻正在执行的事务（活动事务），即检查点前有事务开始标志但没有事务结束标志。 对于检查点后提交的事务，执行REDO（重做） 对于检查点后未提交的事务，执行UNDO（撤销）。提高一并故障恢复的效率

12.4 数据库的安全性与完整性 470

12.4.1 数据库的安全性 471

12.4.2 数据库的完整性 475

数据库的完整性是指数据的正确性和相容性。

数据库事务的四种隔离级别： （10年第35题/14年第55题）
(1) Serializable (串行化)
避免脏读、不可重复读、幻读的发生
(2) Repeatable (可重复读)
避免脏读、不可重复读的发生
(3) Read committed (读已提交)
避免脏读的发生
(4) Read uncommitted (读未提交)
最低级别，任何情况都无法保证

MapReduce 的计算过程分解为两个主要阶段：Map 阶段和Reduce 阶段，在同等硬件条件下，MapReduce 的性能远低于并行数据库。MapReduce 中存在数据chunk 的冗余复制。

第十三章 云计算与大数据处理 476

13.1 云计算基础知识 476

标准定义：云计算是一种将可伸缩、弹性、共享的物理和虚拟资源池以按需自服务的方式供应和管理，并提供网络访问的模式。
狭义：云计算是一种提供资源的网络，使用者可以随时获取“云”上的资源，按需求量使用，并且可以看成是无限扩展的，只要按使用量付费就可以。
总之，云计算是以一种方便的使用方式和服务模式，通过互联网按需访问资源池模型（例如网络、服务器、存储、应用程序和服务），以快速和最少的管理工作为用户提供服 务。

13.1.1 云计算的关键特征 476

  1. 关键特征
    1）广泛的网络接入
    用户可以通过网络，采用标准机制访问云中的物理和虚拟资源的特性
    2）可测量的服务
    通过可计量的服务交付使得服务使用情况可监控、控制和计费的特性
    3）多租户
    通过对物理或虚拟资源的分配保证多个租户以及他们的计算和数据彼此隔离和不可访问的特性
    4）按需自服务
    客户根据自身的实际需求，自动或在最少交互的情况下，配置计算能力的特性
    5）快速的弹性和可扩展性
    物理或虚拟资源能够快速、弹性，有时是自动化地供应，以达到快速增减资源目的的特性
    6）资源池化
    将云服务提供者的物理或虚拟资源进行集成，以便服务于一个或多个云服务客户的特性
  2. 其它关键特征
    1）虚拟化技术
    2）可靠性高
    3）性价比高

13.1.2 云计算分类 478

  1. 根据云部署模式和云应用范围分类
    1）公有云
    一般是被一个云计算服务提供商所拥有，该组织将云计算服务销售给公众，公有云通常在远离客户建筑物的地方托管（一般为云计算服务提供商建立的数据中心）
    2）社区云
    云的基础设施被一些组织所共享，并为一个有共同关注点的社区服务。可以是该组织或某个第三方负责管理。
    3）私有云
    云的基础设施是为一个客户单独使用而构建的，因而提供对数据、安全性和服务质量的最有效控制。私有云可部署在企业数据中心中，也可部署在一个主机托管场所，被一个单一的组织拥有或租用。
    4）混合云
    云的基础设施由以上两种或两种以上的云（私有、社区或公有）组成。
  2. 根据云计算的服务层次和服务类型分类
    1）基础设施即服务（Infrastructure as a Service,IaaS)
    提供虚拟化的计算资源，如虚拟机、存储、网络和操作系统。其核心技术是虚拟化。
    典型代表：亚马逊云计算AWS 的弹性计算云 EC2 和简单存储服务 S3，IBM 蓝云
    2）平台即服务（Platform as a Service,PaaS)
    为开发、测试和管理软件应用程序提供按需开发的环境。其核心技术是分布式并行计算。PaaS实际上是指将软件研发的平台作为一种服务。
    典型代表：Google App Engine (GAE) 只允许使用Python 和Java 语言
    3）软件即服务（Software as a Service,SaaS)
    通过互联网提供按需软件付费应用程序，云计算提供商托管和管理软件应用程序，并允许用户连接到应用程序并通过互联网访问应用程序。客户可以自己定制、配置、组装来得到满足自身需求的软件系统。
    典型代表：Salesforce 提供的在线CRM

13.1.3 云关键技术 479

  1. 虚拟化技术
  2. 分布式数据存储
  3. 并行计算
  4. 运营支撑管理

13.1.4 云计算实施 483

13.1.5 云计算的安全性 486

13.2 大数据处理基础知识 489

13.2.1 基本概念 489

大数据的特征一般采用5V来描述：

  1. 多样性（Variety）
    数据类型繁多。
    除了以往的以文本为主的结构化数据，非结构化数据越来越多，如音频，视频，图片，地理位置信息等。
  2. 速度（Velocity）
    处理速度快。
    一方面是数据的增长速度快，另一方面是要求数据访问、处理、交付的速度快，通常要求具有时效性。是大数据区别于传统数据挖掘的最显著特征。
  3. 大量（Volume）
    数据体量巨大。
    聚合在一起供分析的数据规模非常庞大。
  4. 价值（Value）
    价值密度低。
    大数据的本质是需要从海量数据中获取具有高价值的数据。
  5. 真实性（Veracity)
    是指数据是来自于各种、各类信息系统网络以及网络终端的行为或痕迹。

13.2.2 大数据处理技术 490

从大数据生命周期的角度看，大数据处理的基本流程包括：数据采集、数据分析 和数据解释。

13.2.3 大数据应用 496

第十四章 数据库主流应用技术 …… 499

14.1 分布式数据库 …… 499

14.1.1 分布式数据库基本概念 …… 500

  1. 正常运行策略
  2. 分布式数据库的特点（21年第68题）
    （1）数据的集中控制性
    （2）数据独立性
    （3）数据冗余可控性
    （4）场地自治性（09年第63题/11年第63题）
    （5）存取的有效性

分布式数据库的优点：
管理具有不同透明度的数据、提高可靠性和可用性、更容易扩展系统、可以提高性能。

14.1.2 分布式数据库的体系结构 …… 503

  1. 分布式数据库的模式结构
    1）全局外层
    2）全局概念层（16年第62题）
    分布式数据库的全局概念层应具有三种模式描述信息：
    ① 全局概念模式（14年第62题）
    描述分布式数据库全局数据的逻辑结构，是分布式数据库的全局概念视图。
    ② 分片模式
    描述全局数据逻辑划分的视图，是全局数据的逻辑结构根据某种条件的划分，每一个逻辑划分就是一个片段或分片。
    ③ 分配模式
    描述局部逻辑的局部物理结构，是划分后的片段或分片的物理分配视图。
    3） 局部概念层
    4） 局部内层
    全局外层即外模式，局部概念层和局部内层与集中式数据库相同，全局概念是对全局逻辑模式的描述，按照分片映射到各局部概念层。场地自治是指各局部的DBMS可以独立地管理所辖局部数据，通过局部概念层（相当于集中式的模式层）进行访问。局部内层描述的是局部数据的存储模式（内模式）。

  2. 数据分布

  3. 数据分片
    数据分片的方法
    （1）水平分片
    （2）垂直分片
    （3）水平和垂直结合的分片

  4. 分布透明性
    1）分片透明性
    2）分配透明性（位置透明）（10年第40题/13年第40题）
    分配透明包含的两种情形：
    各片段被复制的情况，即每一片段是否被复制、复制了几个副本；
    片段及其副本的场地的位置分配情况
    当分布式数据库具有分配透明性时，用户编写的应用程序要了解全局数据的数据分片情况，但不必了解各逻辑片段的复制副本情况，也不必关系各片段及其副本的站点位置分配情况。
    3）局部数据模型透明性（映像透明）

  5. 分布式数据库管理系统
    应遵循的规则
    （1）本地自治性
    （2）不依赖于中心站点
    （3）可连续操作性
    （4）位置透明性和独立性
    （5）数据分片独立性
    （6）数据复制独立性
    （7）分布式查询处理
    （8）分布式事务管理
    （9）硬件独立性
    （10）操作系统独立性
    （11）网络独立性
    （12） DBMS 独立性

14.1.3 分布式查询处理和优化 …… 511

14.1.4 分布事务管理 …… 512

14.1.5 新型分布式海量数据库 …… 519

14.2 Web 与数据库 …… 520

14.2.1 Web 概述 …… 520

14.2.2 Web 服务器脚本程序与服务器的接口 …… 521

14.2.3 CGI 的应用 …… 522

14.2.4 ASP 的应用 …… 523

14.2.5 Servlet 和JSP 的应用 …… 525

14.3 XML与数据库 …… 526

14.3.1 什么是XML …… 526

（09年第70题）
XML文件的第一行必须是声明该文件是XML文件以及它所使用的XML规范版本。在文件的前面不能够有其他元素或者注释。所有的XML文档必须有一个根元素。XML文档中的第一个元素就是根元素。所有XML文档都必须包含一个单独的标记来定义，所有其他元素都必须成对地在根元素中嵌套。XML文档有且只能有一个根元素。所有的元素都可以有子元素，子元素必须正确地嵌套在父元素中。在XML中规定，所有标识必须成对出现，有一个开始标识，就必须有一个结束标识，否则将被视为错误。

14.3.2 XML 的文件存储面临的问题 …… 527

14.3.3 XML 与数据库的数据转换 …… 528

14.4 面向对象数据库 …… 531

14.4.1 面向对象数据库系统的特征 …… 533

面向对象数据库系统应具有表达和管理对象的能力。对象存在有联系和引用，属于复杂类型。（13年第44题）

14.4.2 面向对象数据模型 …… 534

在面向对象数据库中，域性的值域可以是任何类，包括原子类，如整型值、字符串等。一个属性可以有一个单一值，也可以有一个来自某个值域的值集，即一个对象的属性可以是一个对象，从而形成了嵌套关系。（14年第63题）

14.4.3 面向对象数据库语言 …… 538

14.4.4 对象关系数据库系统 …… 539

14.5 大数据与数据库 …… 545

14.5.1 大数据之数据仓库设计 …… 546

14.5.2 数据转移技术 …… 549

14.5.3 数据仓库主要应用场景——联机分析处理（OLAP） …… 552

14.5.4 数据库主要应用场景——联机事务处理（OLTP） …… 556

（10年第43题）

14.6 NewSQL 数据库 …… 558

14.6.1 NewSQL 数据库的发展 …… 558

14.6.2 TiDB 的介绍 …… 559

第 15 章 标准化和知识产权基础知识

15.1 标准化基础知识…… 562

15.1.1 标准化的基本概念…… 562

  1. 标准、标准化的概念
  2. 标准化的范围和对象
  3. 标准化过程模式
  4. 标准的分类
  5. 标准的代号和编号
  6. 国际标准和国外先进标准

《中华人民共和国标准法》将标准分为4个层次：
(1) 国家标准
GB：强制性国家标准
GB/T：推荐性国家标准
GB/Z：指导性国家标准
GSB：国家实物标准
国家标准有效期为5年。
(2) 行业标准
(3) 地方标准
(4) 企业标准
企业标准以Q开头；企业产品标准应在发布后30天内向政府备案。
除此之外还有国际标准，如：ISO(国际标准化组织)、IEC(国际电工委员会)、ITU(国际电信联盟)

ANSI：美国国家标准协会标准
BS：英国国家标准
JIS：日本工业标准

15.1.2 信息技术标准化…… 565

  1. 信息编码标准化
  2. 汉字编码标准化
  3. 软件工程标准化

15.1.3 标准化组织…… 567

  1. 国际标准化组织
  2. 区域标准化组织
  3. 行业标准化组织
  4. 国家标准化组织

15.1.4 ISO 9000标准简介…… 569

  1. ISO 9000标准
  2. ISO 9000:2000 系列标准
  3. 核心标准简介

15.1.5 能力成熟度模型简介…… 570

软件能力成熟度模型（Capability Maturity Model，CMM）
是对软件组织精华阶段的描述，分为5个成熟度级别（21年上）
（1）初始级
软件过程的特点是无序的，甚至是混乱的，软件处于无章法和步骤可循的状态，或者制定的规范为能覆盖基本的关键过程，且执行没有政策、资源方面的保证，那么仍被视为初始级。
（2）可重复级
已经建立了基本的项目管理过程，可用于对成本、进度和功能特性进行跟踪。焦点集中在软件管理过程上。一个可管理的过程就是一个可重复的过程。一个可重复的过程则能逐渐演化和成熟。
（3）定义级
用于管理和工程的软件过程均已文档化、标准化，并已形成整个软件组织的标准软件过程
（4）管理级
软件过程和产品质量有详细的度量报告，软件产品和过程得到了定量的认识和控制
（5）优化级
通过来自过程、新概念和新技术等方面的各种有用信息的定量分析，能够不断地、持续地进行过程改进。

15.2 知识产权基础知识…… 571

15.2.1 知产产权基本概念…… 571

  1. 知识产权
  2. 知识产权的特点
    （1）无形性
    （2）双重性
    （3）确认性
    （4）独占性
    （5）地域性
    （6）时效性
    发明专利的保护期为20年；实用新型专利权和外观设计专利权的期限为10年；作品发表权的保护期为作者终身及其死亡后50年；商标权的保护期10年
  3. 我国保护知识产权的法规
    知识产权人确定（14年第11题/21年第16题）
    （1）谁先申请谁拥有（除知名商标的非法抢注）
    （2）同时申请，则根据谁先使用（需提供证据）
    （3）无法提供证据，可协商归属，无效时使用抽签（但不可不确定）

商标法实施细则规定，必须使用注册商标的商品范围包括：（17年第11题）

  1. 国家规定并由国家工商行政管理局公布的人用药品和烟草制品
  2. 国家规定并由国家工商行政管理局公布的其他商品。商标法规定，必须使用注册商标的商品在商标未经核准注册时不得在市场上销售。

15.2.2 计算机软件著作权…… 573

（09年第11题/11年第11题）

  1. 计算机软件著作权保护的主题与客体
    1）计算机软件著作权的主体
    2）软件著作权的客体： （12年第10题/20年第14题/21年第15题）
     （1）计算机程序：包括源程序和目标程序
     （2）计算机软件的软件文档：程序设计说明书、流程图、用户手册
  2. 计算机软件受著作权法保护的条件
  3. 计算机软件著作权的权利
    1）计算机软件的著作人身权
    2）计算机软件的著作财产权
     (1) 发表权
     (2) 开发者身份权/署名权（16年第10题/20年第17题）
      不可转让，不受时间的限制，也不因权利人的死亡而消失。
     (3) 修改权
     (4) 复制权
     (5) 发行权
     (6) 出租权
     (7) 信息网络传播权
     (8) 翻译权（11年第10题）
      是指将原软件从一种程序语言转换成另一种程序语言的权利。
     (9) 使用许可权、获得报酬权、转让权
    3）软件合法持有人的权利
  4. 计算机软件著作权的行使
  5. 计算机软件著作权的保护期
    计算机软件著作权的保护期：（19年第16题）
    《中华人民共和国著作权法》和《计算机软件保护条例》是构成我国保护计算机软件著作权的两个基本法律文件。
    《软件条例》第14条 （09年第10题）
    软件著作权自软件开发完成之日起产生，自然人的软件著作权，保护期为自然人终生及其死亡后50年，截止于自然人死亡后第50年的12月31日；
    软件是合作开发的，截止于最后死亡的第50年的12月31日。
    法人或者其他组织的软件著作权，保护期为50年，截止于软件首次发表后第50年的12月31日，但软件自开发完成之日起50年内未发表的，本条例不再保护。
  6. 计算机软件著作权的归属
    ① 独立开发
    ② 合作开发
    ③ 委托开发（17年第10题）
    如无书面合同或者合同未作明确约定的，则著作权人由受托人享有。
    ④ 职务开发
    ⑤ 继承和转让
  7. 软件著作权侵权的法律责任

15.2.3 计算机软件的商业秘密权…… 584

（11年第11题）

  1. 商业秘密
    1）商业秘密的定义
    2）商业秘密的构成条件
    3）商业秘密权
    4）计算机软件与商业秘密
  2. 计算机软件商业秘密的侵权
  3. 计算机软件商业秘密侵权的法律责任

15.2.4 专利权概述…… 586

  1. 专利权的保护对象与特征
    专利权包括发明、实用新型和外观设计
    (1) 发明：指对产品、方法或者其改进所提出的新的技术方案。科学发现不属于发明范畴。期限为20年。
    (2) 实用新型：指对产品的形状、构造或者其结合所提出的适用于实用的新的技术方案。期限为10年。
    (3) 外观设计：又称工业产品外观设计，指对产品的形状、图案或其结合一级色彩与形状、图案相结合锁作出的富有美感并适于工业上应用的新设计。期限为10年。
  2. 授予专利权的条件
  3. 专利的申请
    1）专利申请权
    2）专利申请人
    3）专利申请的原则（17年第12题）
    谁先申请给谁，同一天申请的自行协商，协商不成，均不授权。
    4）专利申请文件
    5）专利申请日
    6）专利申请的审批
    7）申请权的丧失与恢复
  4. 专利权的行使
    1）专利权的归属
    2）专利权人的权利
  5. 专利权的限制
    发明专利权的保护期为自申请日起20年；实用新型专利权和外观设计专利权的保护期限为自申请日起10年
  6. 专利权的侵权行为
    如果一个专利只在美国申请了专利，那么按照这个专利生产的产品在除美国之外的国家销售，其他国家不需要支付该专利的许可使用费。（12年第11题/16年第11题）

专利权人的义务：
在保护期限内，专利权人应该按时缴纳年费。在专利权保护期限内，如果专利权人没有按规定缴纳年费，或者以书面声明放弃其专利权，专利权可以在期满前终止。

根据《著作权法》，人身权是与人身不可分离、不能放弃或转让，并没有直接财产内容的权利。人身权包括发表权、署名权、修改权等。

第 16 章 数据库设计与案例分析

16.1 SQL 应用案例

16.1.1 SQL 应用案例一

16.1.2 SQL 应用案例二

16.2 数据库设计应用案例

16.2.1 足球联赛信息管理系统

16.2.2 孵化基地管理信息系统

16.2.3 小区停车位管理信息系统

附录：杂七杂八

数据流图的设计原则：

  1. 父图与子图的平衡原则
    子图的输入输出数据流同父图相应加工的输入输出数据流必须一致，此即父图与子图的平衡
  2. 数据守恒原则
    对任何一个加工来说，其所有输出数据流中的数据必须能从该加工的输入数据流中直接获得，或者说是通过该加工能产生的数据。
  3. 守恒加工原则
    对同一个加工来说，输入与输出的名字必须不相同，即使它们的组成成分相同。
    (1) 对于每个加工，必须既有输入数据流，又有输出数据流
    (2) 数据流与加工有关，且必须经过加工

Linux中，权限的格式： -rw-rw-rw
(1)第0位确定文件类型
-：普通文件
d:目录
l:连接文件
c: 字符设备文件（键盘、鼠标）
b: 块设备文件（硬盘）
(2)第1~3位确定所有者（该文件的所有者）拥有该文件的权限
R: 读
W: 写
X: 执行（-表示没有）
(3)第4~6位确定所属组（同用户组的）拥有该文件的权限
(4)第7~9位确定其他用户拥有该文件的权限

ADSL
因其下行速率高、频带宽、性能优等特点而深受广大客户的喜爱。它是运行在原有普通电话线上的一种新的高速宽带技术。
事实上，ADSL的传输技术中，ADSL用其特有的调制解调硬件来连接现有双绞线连接的各端。

在UNIX/LINUX 系统中，telnet服务的默认端口是23，ftp 的端口号是21和20。

一个取值域是原子的，是指该域的元素是不可分的单元。

满足BCNF的定义为：BCNF中每个函数依赖左部都包含码。

在数据库系统中，使数据库恢复到故障发生前的一致状态的机制称为恢复机制。

通过一个关系拆分成两个更小的关系来使其满足范式时，必须用相同的属性使两个子关系互相关联来保持数据的完整约束性。

常见的优化策略：
(1) 尽可能减少多表查询或建立物化视图
普通视图是不存储任何数据的，他只有定义，在查询中是转换为对应的定义SQL去查询，而物化视图是将数据转换为一个表，实际存储着数据，这样查询数据，就不用关联一大堆表，如果表很大的话，会在临时表空间内做大量的操作。
(2) 以不相关子查询替代相关子查询
(3) 只检索需要的列
(4) 用带IN的条件子句等价替换OR子句
(5) 经常提交COMMIT,以尽早释放锁

用哈希表存储元素时，需要进行冲突处理，冲突是指关键字不同的元素被映射到相同的存储位置。

当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为
其中n为图中顶点数
而当以邻接表作图的存储结构时，e为无向图中边的数或有向图中弧的数，深度优先搜索遍历图的时间复杂度为
O(n+e)

程序运行过程中，把函数（或过程）调用与响应调用所需要的代码相结合的过程称为动态绑定。静态绑定是指在程序编译过程中，把函数（方法或者过程）调用与响应调用所需的代码结合的过程称之为静态绑定。

地址http://www.dailynews/channel/welcome.htm中
www表示主机名
dailynews域名
www.dailynews表示主机全名
welcome.htm网页文件名

主域名服务在接收域名请求后，首先查询的是本地缓存

概念数据模型：也称信息模型，是按用户的观点对数据和信息进行建模，是现实世界到信息世界的第一层首相，强调其语义表达功能，易于用户理解，是用户和数据库设计人员交流的语言，主要用于数据库设计。在这类模型中，最著名的是实体联系模型，简称E-R模型。

触发器无法传递参数，但是可以访问INSERT和DELETE两张临时表去处理类似问题的。

算术移位时，对于负数，其符号位可能需要特殊处理，逻辑移位中没有符号的概念，只是二进制位序列。算术左移等同于乘以2的操作。（16年第4题）

移位运算符就是在二进制的基础上对数字进行平移。
按照平移的方向和填充数字的规则分为三种：

在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。

中间代码的表达形式：
语法树
后缀式
三地址代码

I/O控制方式（19年第20题）
设备驱动程序是直接与硬件打交道的软件模块。

为在中断处理结束后能使进程正确地返回中断点，系统必须保存当前处理状态字PSW 和程序计数器PC 等信息。这些信息通常保存在特定的堆栈或硬件寄存器中。（13年第3题）

使用ping命令进行网络检测，按照由近及远原则，首先执行的是ping.127.0.0.1，其次是ping本地IP，再次是ping默认网关，最后是ping远程主机。

终端设备与远程站点之间建立安全连接的协议是SSH。（15年第7题.21年上）
SSH为Secure Shell的缩写，是由IETF制定的建立在应用层和传输层基础上的安全协议。SSH是专为远程登录会话和其他网络服务提供安全性的协议。利用SSH协议可以有效防止远程管理过程中的信息泄露问题。SSH最初是UNIX上的程序，后来又迅速扩展到其他操作平台。

用磁盘碎片整理程序对磁盘进行碎片整理，以提高访问文件的速度。

Hash, 一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入通过散列算法变换成固定长度的输出，改输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
哈希表是根据键（Key）而直接访问在内存存储位置的数据结构。
在密码学里面，随机预言机对任何输入都回传一个真正均匀随机的输出，不过对相同的输入，该预言机每次都会用同一方法输出。换句话说，随机预言机是一个将所有可能输入与输出作随机映射的函数。

社会工程学指的是通过与他人的合法地交流，来使其心理受到影响，做出某些动作或者是透露一些机密信息的方式。这通常被认为是一种欺诈他人以收集信息、行骗和入侵计算机系统的行为。

软件开发模型是软件开发的全部过程、活动和任务的结构框架，用以指导软件的开发。螺旋模型综合了瀑布模型和演化模概述概述型的优点，并增加了风险分析，沿着螺线由内向外，每旋转一圈，就得到原型的一个新版本基本。

站在数据库管理系统的角度看，数据库系统体系结构一般采用三级模式结构。
数据库系统在三级模式之间提供了两级映像：模式/内模式映像、外模式/模式映像。
模式/内模式的映像：
该映像存在于概念和内部级之间，实现了概念模式到内模式之间的相互转换。
外模式/模式的映像：
该映像存在于外部级和概念级之间，实现了外模式到概念模式之间的相互转换。
正因为这两级映射保证了数据库中的数据具有较高的逻辑独立性和物理独立性。数据的独立性是指数据与程序独立，将数据的定义从程序中分离出去，由DBMS负责数据的存储，从而简化应用程序，大大减少应用程序编制的工作量。

码分多址(Code Division Multiple Access CDMA)技术比较适合现代移动通信网的大容量、高质量、综合业务、软切换等要求，正受到越来越多的运营商和用户的青睐。
我国自行研制的移动通信3G标准：TD-SCDMA （14年第70题）

链地址法（拉链法）：
在查找表的每一个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。即利用链域将发生冲突的记录链接在一个链表里。

例：对于给定的关键字序列{47,34,13,12,52,38,33,27,5}，若用链地址法（拉链法）解决冲突来构造哈希表，且哈希函数为H(Key)=Key%11，则（34和12在同一个链表中）
解：计算哈希值可得{3,1,2,1,8,5,0,5,5}
可以看到哈希地址冲突最多的是5，其对应链表最长；34和12的哈希值都为1，放在同一链表中

（19年第24题）
原型方法适用于用户需求不清、需求经常变化的情况，可以帮助导出系统需求并验证需求的有效性。
探索型原型的目的是弄清目标的要求，确定所希望的特性，并探讨多种方案的可行性，可以用来探索特殊的软件解决方法。
原型法能够迅速地开发出一个让用户看得见的系统框架，可以用来支持用户界面设计。

数据库审计的概述：
(1) 审计记录数据库资源和权限的使用情况
(2) 审计操作会影响系统性能
(3) 审计追踪信息会扩大对存储空间的要求

例：把网络117.15.32.0/23 划分为117.15.32.0/27，则得到的子网是(16)个。每个子网中可使用的主机地址是(30)个（13年第46题）
解：
子网个数= 2^4 = 16
主机地址个数 = 2^5 -2 = 30

HTML 元素中，(vlink) 属性用于定义超链接被鼠标点击后显示的颜色。

1.无向图中顶点的度
无向图中顶点的度(Degree) 是关联于该顶点的边的数目，也可以说是直接与该顶点相邻的顶点个数，记为D(V)。例如，在图4-9中，V1的度是1，V2的度是2，V3的度是3，V4的度是2

2.有向图中顶点的入度
在有向图中，以顶点V为终点的边的数目称为V的入度(Indeglee)，记为ID(V)。例如，在图4-10中，V1的入度是1，V2的入度是2，V3的入度是1，V4的入度是0

3.有向图中顶点的出度
在有向图中，以顶点V为始点的边的数目，称为V的出度(Outdegree)，记为0D(V)。例如，在图4-10中，V1的出度是0，V2的出度是0， V3的出度是2， V4的出度是2

软件的可移植性(Protability)是指与一个软件从一个环境转移到另一个环境运行的能力有关的一组属性。包括：
(1) 适应性(Adaptabilitu)
是指与软件无需采用有别于为该软件准备的活动或手段就可能适应不同的规定环境有关的软件属性。
(2) 可安装性(Installability)
是指与应指定环境下安装软件所需努力有关的软件属性
(3)遵循性(一致性，Conformance)
是指使软件遵循与可移植性有关的标准或约定的软件属性
(4)可替换性(Replaceability)
是指与软件在该软件环境中用来替代指定的其他软件的机会和努力有关的软件属性。

本文标签： 考点 工程师 笔记 数据库系统

版权声明：本文标题：数据库系统工程师考点笔记 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1725918536h892597.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。