中级软件设计师知识总结_软件设计师中级知识点

---

复习进度

面向对象、知识产权
软件工程基础知识、数据库系统
程序设计语言、操作系统
计算机网络、信息安全知识、多媒体基础
计算机硬件基础
看大题
数据结构与算法
看大题
刷真题

分型

计算机与软件工程知识 : 150分钟,笔试,选择题
75个选择题，满分75分，45分及格
75=（11+12+10）+（6*4）+（5+3+3+2）=33+24+13

软件设计 : 150分钟,笔试,问答题
四个必做题，两个选做题二选一，满分75，15分一题，45分及格
数据流
数据库
UML
算法题
C++/Java面向对象编程

---

上午题：

一、面向对象

1 面向对象的概念

对象 ：属性(数据)+方法(操作)+对象ID
类：具有相同属性对象的集合(实体类、边界类、控制类)
抽象
封装 ：隐藏对象的属性和实网细节,仅对外公开接口
继承与泛化 ：子类继承父类。几个类抽象出共性，为一个上层的类，称为泛化。
多态 ：操作不同对象产生不同的结果
接口 ：是一种特殊的类，只有方法的定义，没有实现。
消息 ：对象之间通信的机制，异步传输
组件：构建
模式和复用：设计模式就是为了复用

面向对象设计原则

单一职责原则 : 设计目的单一的类
开放-封闭原则 : 对扩展开放,对修改封闭
李氏(Liskov)替换原则 : 子类可以替换父类
依赖倒置原则 : 要依赖于抽象,而不是具体实现;针对接口编程,不要针对实现编程
接口隔离原则 : 使用多个专门的接口比使用单一的总接口要好
组合重用原则 : 要尽量使用组合,而不是继承关系达到重用目的
迪米特(Demeter)原则(最少知识法则) : 一个对象应当对其他对象有尽可能少的了解

2 UML

UML包括构造块、规则、公共机制。

考点：
1、规则和公共机制考试不考。
最重要：图
次之：关系
2、用例图：该图的归类有分歧，在选哪些是静态/动态图时，先看其他选项，再确定用例图属于哪个分类。
3、区分惯用法和设计模式：与语言是否相关
区分架构模式和设计模型：是从全局还是局部分析


图：可以分为结构图和行为图或者分为动态图和静态图

静态图/结构图包括：

• 类图：类之间关系的图

• 对象图：对象之间关系的图

• 包图：包之间关系的图

• 组合结构图

• 构件图：在该类图中存在两种类似棒棒糖和插座的符号，棒棒糖符号表示“供接口”；插座式的符号表示“需接口”，该图是描述系统构件与构件之间、类与接口之间的关系图

• 部署图：软件的部件应该部署在哪个硬件的节点上面

• 制品图

动态图/行为图包括：

• 用例图：该图的内容是系统和外部的交互关系。
  该图的归类有分歧，大部分时候归结为动态，小部分时候归结为静态。

• 顺序图/序列图：强调了按时间顺序的通信图

• 通信图/协作图

• 定时图

• 状态图：表达的是状态的变迁、转移的情况

• 活动图：与流程图的结构一致

• 交互概览图

3

4 设计模式

设计模式概念

三种模式的概念及其层次关系：

1.架构模式：是软件设计中的高层决策，例如C/S结构，B/S，SOA

2.设计模式：

反映了开发软件系统过程中所作的基本设计决策，而设计模式则是主要关注软件系统的设计，与具体的实现语言无关，是在软件开发过程中，经过验证的，用于解决在特定环境下的、重复出现的、特定问题的解决方案

3.惯用法：

是最底层的模式，关注软件系统的设计与实现，实现时通过特定的程序设计语言来描述构件与构建之间的关系。每种编程语言都有它自己特定的模式，即语言的惯用法。例如c++语言的惯用法就是：引用–计数

设计模式的分类

设计模式可以被分成三种：创建型模式、结构型模式、行为型模式

创建型模式

创建对象，创建类实例化提供指南。

• 抽象工厂模式：创建系列的对象
• 工厂方法模式：运行时指定创建哪个类的对象，所有子类实例化推迟了
• 构建器模式
• 原型模式：克隆模型
  用new创建新对象消耗的资源多，拷贝直接拷贝内存，效率高
• 单例模式：比如一个浏览器窗口打开多个标签页

结构型模式

处理类和对象的组合型模式

• 组合模式：想表示对象的部分—整体层次结构(对象组合)，比如公司部门结构

• 适配器模式：想使用一个已经存在的类，而它的接口不符合描述

• 装饰模式：在不影响其他对象的情况下，以动态透明的方式给单个对象添加职责
  比如喝咖啡，加奶或加糖

• 桥接模式：不希望在抽象和它的实现部分之间有一个固定判定关系
  

• 享元模式：即对象共享

• 代理模式

行为型模式

用来描述类或对象交互的情况以及职责的分配问题。

• 职责链模式：比如发送者是员工申请报销，500元一下通过1经理直接处理掉，500-1000元，1经理批了，交给2财务；1000-2000元，1经理批了，2财务批了，交给3副总；以此类推
  
• 命令模式
• 解释器模式：构造虚拟机处理问题
• 迭代器模式：->next用到了
• 中介者模式：引入了中间件，A引用B，A变化，B不用修改，只修改中间件即可
  
• 备忘录模式
• 观察者模式：比如excel里填表格时有依赖
• 状态模式
• 策略模式
• 模板方法模式
• 访问者模式

二、软件工程基础知识

考点： 1、工程图(重点) 2、各开发方法(只需要知道哪个用于哪个) 3、概要&详细设计 4、敏捷开发方法

注：重要程度依次递减

1 软件开发模型

开发模型是软件工程当中指导开发的一种开发思想、开发体系

瀑布模型

优点：是结构化方法的模型，每一个阶段都分工明确

缺点：需求分析很难把控，因此一般适用于需求明确或者二次开发

注：瀑布模型适用于软件需求很明确的工程

原型、演化模型、增量模型(解决用户需求分析困难)

构造简易系统，针对需求不明确的情况

（1）原型和瀑布模型是互补关系，原型是为了解决用户需求分析难以把控即需求不明确而提出的，该模型即：先做出初步模型，然后让用户使用，以便于用户进一步明确自己的需求，是一种抛弃式的模型，因为需求一旦明确就会被抛弃

（2）演化模型即是一种渐进式的原型，即它采取原型的设计模式，但不会将其抛弃，而是在此基础上进一步进行设计

（3）增量模型：有原型和瀑布模型的思想，是一种递增式设计，将产品一步一步进行设计，每完成一步就交由客户审视，这样也可以使得下一步的设计更为明确

螺旋模型(强调风险分析)

螺旋模型综合了瀑布模型和演化模型的优点，还增加了风险分析，螺旋模型包含四个方面的活动：制定计划、风险分析(是螺旋模型最为显著的特征)、实施工程、客户评估

具有多个模型的特征

V模型(强调测试)

该模型极为强调测试的作用，测试始终贯穿流程的始终，如：需求分析完成后就写验收测试和系统测试的测试计划，概要设计完成后就写集成测试的测试计划，详细设计后就写单元测试的测试计划、

前面四种模型都是结构化方法下的模型

喷泉模型与RAD快速开发模型(了解)

喷泉模型

1.概述：该模型最大的特点是面向对象

2.特点：基于面向对象的迭代和无间隙

RAD模型

1.概述：该模型最大的特点是能够快速构建业务系统
SDLC瀑布模型
CBSD构件组装模型

2.内容：包括：业务建模、数据建模、过程建模、应用生成、测试与交付
用VB图形化界面构建界面就是RAD

构件组装模型(CBSD)

该模型将软件开发过程中的各个模块都做成构件，最后再将构件进行组装，基于构件的软件开发，主要强调在构建软件系统时复用已有的软件“构件”，在检索到可以使用的构件后，需要针对新系统的需求对构件进行合格性检验适应性修改，然后集成到新系统中

优点：极大的提高了软件开发当中的复用性，缩短时间、节省成本、增强可靠性

统一过程模型(UP/RUP)

特点：
1、由用例驱动
2、以架构为中心
3、迭代和增量

统一过程模型定义了四个技术阶段及其制品，包括：

1.起始阶段：该阶段专注于项目的初创活动

2.精化阶段：精化阶段在理解了最初的领域范围之后进行需求分析和架构演进

3.构建阶段：该阶段关注系统的构建，产生实现模型

4.移交阶段：关注软件提交方面的问题，产生软件增量
使用试用版软件，就是β测试

2 软件开发方法

敏捷开发方法

该方法是一类方法，其特点是快捷，该类方法包括：自适应开发、水晶方法、特征驱动开发、SCRUM、极限编程；他们都遵循一些基本原则和价值观，该类方法适用于做小型项目

1.极限编程(XP)特点：测试先行、结对编程、集体代码所有制、持续集成(可以按日甚至按小时为客户提供可运行的版本)、每周工作40个小时

2.并列争球法特点：使用迭代的方法，其中把每三十天一次的迭代成为一个冲刺，并按需求的优先级来实现产品，多个自组织和自治小组递增实现产品，并通过简短的日常情况会议进行协调

3.水晶法特点：该方法认为每一个不同的项目都需要一套不同的策略、约定和方法论

4.敏捷开发方法的重要技术

重构：重构是一种重新组织技术，重新审视需求和设计，重新明确的描述他们的需求和现有的需求，可以简化构件的设计而无需改变其功能或行为

信息系统开发方法

该类方法包括四种：结构化法、原型法、面向对象方法、面向服务方法；其中结构化方法的典型代表是瀑布模型，原型法的典型代表是原型和演化模型，目前应用最广的方法是面向对象方法，而面向服务方法尚处于摸索阶段

面向对象方法正在成为主流
结构化方法的最大问题是流程结构固化，不灵活

SOA要弄清楚

3 需求分析

需求的分类

软件需求包括三类：业务需求、用户需求、系统需求；系统需求是用户需求的发展，而系统需求包括功能需求、性能需求（非功能需求）、设计约束(即开发语言的选用)

基本需求：用户明确提出的需求，必须要做
期望需求：用户没有明确提出，但是这个系统理所应当具有这些需求，必须要做
兴奋需求：用户没有提出，也没有觉得这个要做，但是开发做出来了
不提倡

4 软件设计

结构化设计

即结构化方法中的软件设计问题，包括概要设计和详细设计，其设计原则是：自顶向下、逐步求精，信息隐蔽（内部信息不向外界展现，只展现接口）、模块独立(通过：高内聚、低耦合、复杂度)

扇入：上层调用
扇出：调用下层模块

内聚与耦合

内聚程度最高是功能内聚，最差的是偶然内聚
耦合是指模块与模块之间的关系，内容耦合的在耦合中程度最高，最差的是非直接耦合

结构化设计的原则

1.保持模块的大小适中

2.尽可能减少调用的深度

3.多扇入，少扇出(上层模块调用自己称之为扇入，自己调用其他模块称之为扇出)

4.单入口，单出口

5.模块的作用域应该在模块之内

6.功能应该是可预测的

系统结构/模块结构

图b需要掌握

结构化分析的结果

包括：一套分层的数据流图、一本数据词典、一组小说明(又称加工逻辑说明)、补充说明

概要设计

概要设计包括四个项目

1.设计软件系统总体结构

2.数据结构设计

3.数据库设计

4.编写概要设计文档：文档中应有概要设计说明书、数据库设计说明书、用户手册以及修订测试计划

注：需求分析确定软件要完成的功能及非功能要求，概要设计将需求转化为软件的模块划分，确定模块之间的调用关系；详细设计将模块进行细化，得到详细的数据结构和算法；编码根据详细设计进行代码的编写，得到可以运行的软件，并进行单元测试

5 软件测试

测试原则与类型

1.原则：
(1)尽早、不断的进行测试；

(2)程序员避免测试自己设计的程序

(3)既要选择有效、合理的数据，也要选择无效、不合理的数据

(4)修改后应进行回归测试

(5)尚未发现的错误数量与该程序已发现错误数成正比
程序A发现30个bug，程序B发现100个bug，修复完成后重点测B

2.类型：软件测试类型分为动态测试(利用到了计算机的测试)和静态测试(纯手工的测试)

(1)动态测试包括：黑盒测试法(即看不到程序内部，只管输入的是什么，输出的是什么)、白盒测试法(从程序结构方面进行测试)、灰盒测试法（将两者结合起来）

(2)静态测试包括：桌前检查（程序员写完代码自己检查一边）、代码走查（代码人工计算执行一遍）、代码审查（交叉检查）

测试用例设计

黑盒测试：

• 等价类划分：即将所有数据类划分为许多个层次，每个数据层次挑选出一个最具代表性的数据进行测试即可

• 边界值分析：即需要对等价类之间的边界值进行测试(一般是端点、略小于端点的值、略大于端点的值)

• 错误推测：即自己推测错误的原因，该方法强调经验

白盒测试(主要是逻辑覆盖测试)：

• 语句覆盖测试：即程序中的每一条语句都要进行测试(覆盖度最低的测试)，通过设计n组数据，使其覆盖掉所有的路径

• 判定覆盖：即所有判断的真假分支都要测试一遍

• 条件覆盖：即在判定时对判定的条件的真假性进行测试

测试阶段

测试阶段可分为四个步骤：单元测试、集成测试、确认测试、系统测试；许多项目只需做到确认测试

• 单元测试：模块性的测试，即对于一个函数，是否达到了其目的，每个模块的功能是否完善

• 集成测试：即模块间的衔接测试，不衔接的模块就将其组装起来，组装方式有两种：一次性组装(一次全部组装)和增量式组装(组装两个模块时测试一下、组装到三个模块时再测试一下…)

• 确认测试：即对需求进行确认，测试该程序是否满足需求，测试包括：内部确认测试、Alpha测试(即项目在开发环境进行测试)、Beta测试(即用户在自己的本地计算机自行测试)、验收测试

• 系统测试：主要是压力、性能、可靠性的测试，而性能测试包括：负载测试、强度测试(即系统资源缺失的情况下系统能否正常运行)、容量测试，压力测试则是测试同时访问人数的极限

软件测试抽象方法

1.演绎法(靠蒙的推理)：从一般性的前提出发，通过推导即“演绎”，得出具体陈述或个别结论的过程

2.归纳法(有素材的推理)：以一系列经验事物或知识素材为依据，寻找出其服从的基本规律或共同规律，并假设同类事物中的其他事物也服从这些规律，从而将这些规律作为预测同类事物的其他事物的基本原理的一种认知方式

McCabe复杂度(必考)

这类题通常将程序抽象为有向图，并要求计算环路复杂度

计算有向图的环路复杂度公式为：V(G)=m-n+2；说明：其中V(G)是有向图G中的环路个数，m是G中的有向弧数(边数)，n是G中的节点数(点数)

6 系统运行与维护

软件维护的概念

软件维护即需要提供软件支持的全部活动，这些活动包括在交付前完成的活动，以及在交付后完成的活动，交付前完成的活动包括交付后运行的计划和维护计划等；交付后的活动包括软件修改、培训、帮助资料等

考点：

• 可维护性

包括可分析性、易分析性(即代码应该容易看懂)、易改变性(耦合性)、易测试性

• 维护类型

包括：

1.改正性维护（25%）：即用户发现bug，然后我就修改bug

2.适应性维护（20%）：即解决运行平台版本更迭的问题
适用数据环境，软件硬件适应

3.完善性维护（50%）：指在运行过程中发现了一些不足，进而对系统的性能等方面进行完善和扩充

4.预防性维护（5%）：对将来可能导致的问题进行预防工作
把需要进行维护的模块进行重构，或者写文档

注：系统设计中，人机交互“黄金三原则”包括：置于用户控制之下、减少用户的记忆负担、保持界面的一致性

软件的质量特性及其子特性

1.功能性：适合性、准确性、互操作性、依从性、安全性

2.可靠性：成熟性、容错性、易恢复性

3.易用性：易理解性、易学性、易操作性

4.效率：时间特性、资源特性

5.可维护性：易分析性、易改变性、稳定性、易测试性

6.可移植性：适应性、易安装性、遵循性、易替换性

软件维护工具

包括：

1.版本控制工具

2.文档分析工具

3.开发信息库工具

4.逆向工程工具

5.再工程工具

7 软件过程能力成熟度模型(CMMI）

CMMI是一个软件开发团队的评级标准，该评级标准分为了阶段式和连续式两种分组

阶段式

一级为混乱级，即未通过CMMI认证的团队都是该等级

二级为项目级，即对某个具体的项目有相关开发经验和开发能力，但只限于模仿和套用

三级为组织级，该级别下的团队有了自己的改进能力，能对他人的项目提出不同的看法、经验。公司有模板、工具、方法，叫组织过程资产。
关键词：文档化、标准化

四级为定量管理级，强调管理量化

五级为优化级，持续优化

连续式

CL0(未完成的)：过程域未执行或未得到CL1中定义的所有目标

CL1(已执行的)：其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特别目标

CL2(已管理的)：其共性目标是已管理的过程的制度化。根据组织级政策规定过程的运作将使用哪个过程，项目遵循已文档化的计划和过程描述，所有正在工作的人都有权使用足够的资源，所有工作任务和工作产品都将被监控、控制、和审评

CL3(已定义级的)：其共性目标集中于已定义的过程的制度化。过程是按照组织的裁剪指南从组织的标准过程中裁剪得到的，还必须收集过程资产和过程的度量，并且用于将来对过程的改进

CL4(定量管理的)：其共性目标集中于可定量管理的过程的制度化，使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的质量目标作为管理准则

CL5(优化的)：使用量化(统计学)手段改变和优化过程域，以满足客户的改变和持续改进计划中的过程域的功效

8 项目管理基础知识

考点：1-2分 时间管理的概念及计算、风险管理的概念

该章节只需要掌握时间管理的概念及计算以及风险管理的概念。
Gantt图，其最为直观的特点是简洁明了，可以很清楚的看到计划的开展，缺点是不能看出任务间的逻辑关系，无法看出哪个任务先做，哪个任务后做

PERT图的计算相关问题

PERT图的缺点是不能清晰地描述各个任务之间的并行关系，每一个原型的左侧是事件执行的顺序号，右上角是最早时间，右下角是最晚时间；事件六的最晚开始时间的计算步骤：先从事件1逐步进行推进，如事件1到事件2最早需要时间加2，事件2到事件5则再需要加2(此时最早时间等于4),而事件1到事件6需要的最早执行时间为3，事件4到事件6的最早时间为4，因此取时间长的为事件6的执行时间(原因是事件六的执行需要事件3和4共同作用),以此类推，事件9所需最早时间为15，再由事件9逆推回来15-4-1=10即为事件6的最晚开始时间

风险管理

1.风险：指“损失或伤害的可能性”，风险可以分为项目风险(由项目经理主导控制的)和技术风险以及商业风险（超出项目经理控制的），特点是关心未来、关心变化、关心选择

2.风险曝光度：计算方法是：风险出现的概率乘以风险可能造成的损失；风险曝光度常用于风险的管控

软件项目估算

常用的估算方法有三种：基于已经完成的类似项目进行估算、基于分解技术进行估算(分解技术包括问题分解和过程分解)、基于经验估算模型(IBM模型、COCOMO模型、Putnam模型)

1.COCOMO：该模型按其详细程度分为基本、中级、详细COCOMO模型

• 基本：该模型是一个静态单变量模型，用于对整个软件系统进行估算

• 中级：该模型时一个静态多变量模型，将软件系统模型分为了系统和部件两个层次，系统由部件构成

• 详细：将软件系统模型分为系统、子系统和模块三个层次

注：COCOMOII模型在模型层次结构中有三种不同的规模估算选择：对象点、功能点和代码行

三、数据库系统

考点： 规范化理论(必考，范式必考)、关系代数(必考)

第一节.数据库概述

内容包括：1.数据库模式

2.ER模型

3.关系代数与元组演算

4.规范化理论

5.并发控制

6.数据库完整性约束

7.分布式数据库

8.数据仓库与数据挖掘

第二节.数据库系统：三级模式—两级映射

数据库系统分为了三个级别的层次，即：内模式，概念模式，外模式

物理数据库，计算机的表现形式是一个文件。

三级模式

1. 内模式：(又称物理数据库模式)；它是和物理层次数据库直接关联的，负责管理存储数据的方式，即数据应以什么格式存放在物理文件上面，以及如何优化这些存储方式；该模式的关注点在于数据如何存放上面
2. 概念模式：即数据库中的”表“，在该模式中，根据业务以及应用，数据被分成了若干张”表“，表之间会有相应的关联
3. 外模式：处于用户的应用层次，即数据库中的“视图”，使用户在对数据的控制上有了更多的手段，有了更为灵活的处置方式
   比如，只使用用户的姓名，创建视图，提取需要的列，不需要表的密码，增加了安全性

两级映射

1. 外模式—概念模式映射：外模式和概念模式具有映射关系，该关系即**“视图”和“表”之间的映射**关系，表变化，改映射关系，不需要改应用程序
2. 概念模式—内模式映射：即用户想要改变存储结构，我们只需要调整这种映射关系，而不需要去修改用户的应用程序

第三节.数据库设计过程

考点：整个设计过程，不同设计阶段的产出物

需求分析——>数据流图，数据字典，需求说明书
概念结构设计层次——>ER模型
逻辑结构设计——>关系模式

第四节.ER模型

在ER模型中，矩形表示实体(如学生,课程)，椭圆表示属性(如学号，姓名，性别，年龄)，菱形表示联系(如选课)；其中学生和课程之间具有多对多关系

ER模型由局部到全局的合成方式

我们在绘制数据库的ER图时，常常从局部开始绘制，然后将许多局部的ER图合成位全局的ER图，而局部的ER图合成全局的ER图时可以有两种方式：逐步集成和一次集成

集成的方法：即逐步集成或者一次集成，逐步集成即首先将两个局部图集成在一起，然后与第三个合并在一起…;一次集成即将所有ER图一次集成；
集成的优点：方式简单，不易出错；缺点：一次集成容易出错，出错后难以纠错，逐步集成步骤繁锁

注：集成产生的冲突，即局部ER模型在继承时的冲突，如属性冲突（如男女用"男女"或者“F/M”表示），命名冲突(如一名多意)，结构冲突(不同抽象级别的冲突，如在一个系统里是一列字段，在另一个系统里是一个完整的表)

ER模型转换为关系模型

1.一个实体型转换为一个关系模式

·1：1联系：即一一对应的关系中，一个实体型转换为一个关系模式，再把这种联系放在任意一个其他实体中，因此在此种转换中需要两个实体的参与

·1：n联系：即一对多的关系中，如部门实体与和员工实体之间；仍然是一个实体型转换为一个关系模型，但这种联系只能记录在多这边，如员工

·m：n联系，即多对多的关系中，此种关系至少需要三个实体参与
多对多的联系也必须转成一个实体

三个实体+一个多对多的关系转换
答案是四个

第五节.关系代数(必考)

以选择题的形式出现；有如下运算:并；交；差；笛卡尔积；投影；选择；联接

各个运算的表示符号

并(∪)、差(-)、笛卡尔积(×)、投影(π)、选择(σ)

差运算

概念：即得到A集合中B所没有的元素，如A-B即得到B在A中所没有的元素

笛卡尔积

概念：该运算的符号为“X”；若A与B进行“X”运算，则：

笛卡尔积中若AXB，则将A第一行记录写下，然后将其重复记录三次，然后将B的三行记录与A重写的记录一一对应的写下，然后对A的第二行记录进行同样的重写，以及将B对应的记录重写…

投影

概念：该操作即将所选的“列”记录下来
图示选择Sno、Sname，那么Sno实际是重复的No001 003 004，Sname同理，所以只有三行

选择

概念：该操作将所选的“行”记录下来
选择是根据某些条件对关系做水平切割，对元组行的选择列出如上述中Sn0-Soooo3(S1)，是指从S1中选择Sno字段为Soooo3的数据。

自然联接

概念：自然连接的结果以左侧关系为主，右侧关系去除重复列，如R(A,B,C,D,E)和E(C,D,E,F)进行自然连接的结果为：(A,B,R.C,R.D,R.E,F)

如图：

π型对应的是映射，也就是选择属性列，π1，4表示选择第一列到第四列，“2=5”表示选择，即当等号左边的属性列满足等号右边的属性列是=时则被选中，要求2=5也就是属性2等于属性5，而RxS则表示R集合与S集合进行联接操作

笛卡尔积不会去掉属性列，S1×S2是Sno、Sname、Sdept、Sno、Age
选择Sno、Sname、Age就是π 1,2,5（S1×S2）

自然选择是把相同等值的属性列去掉，即去掉第二个Sno，是Sno、Sname、Sdept、Age
选择Sno、Sname、Age就是π 1,2,4（S1▷◁S2）

规范化理论

规范化理论——函数依赖

概念

函数依赖：即函数关系，如学号对应姓名，姓名可以重复，但学号是唯一的，且唯一的学号对应相应了可重复的姓名
X->Y

部分函数依赖(部分依赖)：主键是两个属性的组合键，若主键中的一部分可以确定某个属性，则为部分函数依赖
通过(学号，课程号)的组合键，可以通过主键的一部分即学号确定姓名属性

传递函数依赖(传递依赖)：即：若A可以确定B，B可以确定C，则A可以确定C(注意:B不能确定A，因为此时二者即为等价)

规范化理论——价值与用途

在非规范化的关系模式中，可能存在的问题包括：数据冗余，更新异常，插入异常，删除异常

价值

1.价值包括：解决数据冗余，如在记录大学生所属系别时，记录为计算机系就比计算机科学系更为简便，在大量数据的处理中，这一点的改进极为重要
DNO和DNAME是唯一对应的，LOCATION也可以根据DNO唯一确定，这里存储重复

逆或反规范化理论：加数据冗余
规范化理论存在一些问题

规范化理论——键

考点：候选键的概念、求法、候选键和主键的关系、外键求法

数据库系统中的键包括：超键，候选键，主键，外键

元组：在关系中，记录称为元组。元组对应表中的一行；表示一个实体。

键

1.概念：属性的集合

超键

1.概念：唯一能够标识元组(实体，即数据库的一行)的键，可以是单个的属性，也可以是属性的组合

候选键

1.概念：是一种特殊的超键，它是在超键的基础上消除多余属性后的键，可以有多个
和超键的区别：超键可能存在冗余的键(有或没有都可以的键)，候选键去掉冗余的键

学生和姓名的主键可以确定性别，学生和姓名的主键叫超键，不能叫候选键，姓名是冗余的键

2.求解候选键步骤：(1)将关系模式的函数依赖关系用“有向图”的方式表示

(2)找入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能遍历图中所有结点，则该属性集即为关系模式的候选键。注：入度即为第一个只有指向箭头，没有被指箭头的属性

(3)若入度为0的属性集不能遍历图中所有结点(或没有入度为0的属性)，则需要尝试性的将一些中间结点(既有入度，也有出度的结点)并入入度为0的属性集中，直至该集合能遍历所有结点，该集合即为候选键

例1：答案A
例2：ABD->E指ABD组合键确定E，不能化成A->E B->E D->E，这是指单独的A就能确定E
答案ABCD
例3：答案B

主键

概念：只能有一个，如学号和身份证号都能标识一个学生，而主键则是在两个属性集合之中则其一

外键

概念：外键是其他关系的主键，因为许多时候我们需要对表做关联

规范化理论——范式

范式的概念
越往下，范式级别越高，规范化程度越高，数据的力度越小

1NF即一级范式，2NF即为二级范式；一级范式消除非主属性(即该属性不属于候选键的一部分)对候选键的部分依赖后就得到了二级范式，二级范式消除了非主属性对候选键的传递依赖后就得到了第三范式，第三范式在消除了主属性对候选键的传递依赖后就得到了BC范式。

1.范式概念：范式符号为NF；范式分为一级范式。二级范式，三级范式…；随着范式等级的提高，规范程度就会越高，数据表的拆分也将越来越细，而数据表拆分过细会造成性能方面的问题，因此，我们通常对范式的等级采取折中的方式，即做到三级范式

2.第一范式的概念：在关系模式R中，当且仅当所有域(列的取值范围，如性别的取值范围就是男和女)列的取值范围只包含原子值，即每个分量都是不可再分的数据项，则称R是第一范式

不是1NF，因为高级职称人数还可以分为教授和副教授。去掉高级职称人数，直接写教授、副教授就是1NF

3.第二范式的概念：当且仅当R是1NF，且每一个非主属性完全依赖(即：主键中的所有属性共同作用才能决定该属性)主键(且不存在部分依赖)时，则称R是第二范式

SNO学号和CNO共同确定成绩GRADE，存在部份依赖，CNO就可以确定课程学分CREDIT

解决方案：把CNO和CREDIT单独提取出来做一个新的关系模式，去掉原来的关系模式的CREDIT

主键是单属性，即只有一个，不可能存在部分依赖

4.第三范式的概念：当且仅当R是2NF，且E中没有非主属性传递依赖于码时，则称R是第三范式

解决方案：将DNO、DNAME、LOCATION单独提取出成为新的关系模式

5.BC范式的概念：设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每一个依赖的决定因素必定包含R的某个候选码
即把所以依赖写出来，左边部分必须是候选键

SJ可以共同确定T，所以SJ是候选键
S可以确定T，T可以确定J，所以ST是候选键
所以STJ都是主属性，没有非主属性，直接确定R至少是3NF
所有依赖：SJ->T T->J
由于T不是候选键，所有不是BCNF

存在部分函数依赖，如部门名->负责人
答案：CDA

6.主属性的概念：

主属性即为构成候选键的属性，在该关系图中，ST和SJ都是候选键，因此，S,J,T三个属性都属于主属性

7.关系模式的概念：关系模式实际上就是记录类型。它的定义包括：模式名，属性名，值域名以及模式的主键。 关系模式不涉及到物理存储方面的描述，仅仅是对数据特性的描述。

规范化理论——模式分解

范式级别不够时我们采取模式的拆分，拆分完级别就提高了

模式拆分时要保持的原则

1.保持函数依赖分解(不需要保持冗余的函数依赖)
分解前的函数依赖，在分解后的函数依赖依然存在
对于冗余性质的函数依赖不需要仍然存在，比如R（A,B,C）有A->B B->C A->C
那么A->C就是冗余的

2.无损分解：有损即不能还原；无损即可以还原

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

比如R(A,B) A->B和R(B,C) B->C可以还原成R(A,B,C) A->B B->C

判断是否满足无损分解的方法

1.表格法：
成绩拥有学生，标a，右下角写行列数
当学生的姓名属性标a那么

当有任意一行全为a时，该关系模式的分解即为无损分解

2.计算法
只适用于一分为二，R分为R1 R2

第一个p1是无损分解，第二个p2是有损分解

数据库

数据库的并发控制

事务涉及到的SQL语句：
事务开始：BEGIN TRANSACTION
事务提交：COMMIT
事务回滚：ROLLBACK
1
2
3
4

事务的概念

1.概念：把多个操作封装起来，将其看成一个整体来进行操作，可以便于并行并发的处理一些事情；具有的特性：

(1) 原子性：即事务的内容操作要么全部做，要么全不做；
即不能再拆分

(2) 一致性：在事务执行之前，数据保持一致的状态，执行之后数据也是一致的状态

(3) 隔离性：事务之间的执行是独立进行的

(4) 持续性：事务执行之后，其结果造成的影响是持续的，即使数据库崩溃，其对数据库的更新操作也永久有效

并发并行带来的问题

1.丢失更新：
在这两个事务中，T1执行的结果为5，T2执行的结果为2，我们想要得到的是A减去5再减去8的结果，但最终结果为2，因为下一个执行的事务结果会覆盖上一个事务执行的结果

2.不可重复读：
在T1运算中，求A与B的和时，为了提高准确率，程序会再次进行验算，但在第一次运算和第二次运算的间隙，将进行T2运算，T2运算的结果会将A与B的值进行覆盖，这将会产生死锁问题

3.读“脏”数据：

脏数据只是一个临时值，不是真正的数据，不是我们执行过程中真的产生的数据
值70是计算过程产生的数据，属于临时数据，该数据被恢复为了20，使得T2操作将会出错

解决并发并行带来的问题的方法——封锁协议

1.一级封锁协议：事务T在修改数据R之前必须先对其加X(写锁或排他锁)锁，直到事务结束才释放。可防止丢失更新，该锁可以使得除了T以外的所有事务将不能访问R，而事务T则可以阅读或者修改R

2.二级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S(读锁或共享锁)锁，读完后即可释放S锁。可防止丢失修改，还可防止读"脏"数据，该锁的作用是，所有的事务都可以访问R，但包括T在内的所有事务都不能修改R
加上S锁后，还可以加S锁，但不能加X锁
加上X锁后，不能再加任何锁

3.三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可防止丢失修改，防止读"脏"数据与防止数据重复读

4.两段锁协议：可串行化(通过加锁解锁两个阶段使并发事务排队进行)的。可能发生死锁

注：

如果事物T对数据加上X锁后，就只允许事务T读取和修改数据，其他事务对数据A不能再加任何锁，从而也不能读取和修改数据，直到事务T释放数据上的锁

如果事务T对数据加上了S锁后，事务T就只能读数据但不可以修改，其他事务可以再对数据A加S锁来读取，只要数据上有S锁，任何事务都只能再对其加S锁，而不能加X锁

数据库完整性约束

主要有三种约束：实体完整性约束，参照完整性约束，用户自定义完整性约束；约束的作用是提高数据的可靠性

实体完整性约束

概念：即我们在使用数据库时，给数据表定义主键，主键的值不能为空、不能重复

参照完整性约束

概念：即外键中的约束，如：我们设置了一个员工表，其中含有部门号，若部门号设置了参照完整性约束，则在设置部门号时，其内容必须是主键中的内容，若不是，则会报错
允许为空

用户自定义完整性约束

概念：即用户可以设置属性的值的要求，如属性“年龄”；用户可以自行设置“不能输入负数”限定

触发器

概念：即：写脚本来约束数据库，用来设置更为复杂的约束

数据库安全

数据库备份与恢复

备份形式、优缺点、运作方式

数据备份按备份方式可分为热备份和冷备份；按备份的量可分为：完全备份，差量备份，增量备份；

冷备份

1.概念：冷备份也称静态备份，是将数据库正常关闭，在停止状态下，将数据库的文件全部备份(复制)下来

2.优点：非常快速的备份方法(只需要复制文件);容易归档(简单复制即可)；容易恢复到某个时间点上(只需将文件再复制回去)；能与归档方法结合，做数据库“最佳状态”的恢复；低度维护，高度安全

3.缺点：单独使用时，只能提供到某一时间点上的恢复；在实施备份的全过程中，数据库必须要作备份而不能做其他工作；若磁盘空间有限，只能复制到磁带等其他外部存储设备上，速度会很慢；不能按表或按用户恢复

热备份

1.概念：热备份也称动态备份，是利用备份软件，在数据库正常运行的状态下，将数据库中的数据文件备份出来

2.优点：
可以精确备份或恢复按表级别
可在表空间或数据库文件级备份，备份的时间短；备份时数据库仍然可以使用；可达到秒级恢复(恢复到某一时间节点上)；可对几乎所有数据库实体做恢复；恢复是快速的

3.缺点：不能出错，否则后果严重；若热备份不成功所得结果不可用于时间点的恢复；因难于维护，所以要特别小心，不允许“以失败告终”

完全备份，差量备份，增量备份

1.完全备份：备份整个数据库的内容

2.差量备份：仅备份上一次完全备份之后变化的数据(可以解决增量备份可能出现的错误)

3.增量备份：备份上一次备份之后变化的数据

四种转储方式
转储就是一种备份

1.静态海量转储：在系统中无事务运行时进行，每次转储全部数据库

2.静态增量转储：在系统无运行事务时进行，每次只转储上一次转储后更新过的数据

3.动态海量转储：转储期间允许对数据库进行存取或修改，每次转储全部数据库

4.动态增量转储：转储期间允许对数据库进行存取或修改，每次只转储上一次转储后更新的内容

日志文件

1.概念：事务日志是针对数据库改变所做的记录，它可以针对数据库的任何操作(如插入，更新)，并将记录结果保存在独立的文件中

数据库可能的故障与解决办法
rollback可以回滚事务

数据仓库与数据挖掘

数据仓库

1.概念：数据仓库是一种特殊的数据库；数据库系统在刚刚建立时运行速度很快，但随着时间的推移，其存储的数据量越来越大，速度也将逐步下降，而为了提高速度，人们会优化存储，通常采用删除较久远历史数据来进行优化，而这些数据仍然具有部分价值，因此我们会专门用一个数据库来对其进行存放，而用来存放这种数据的数据库并不需要插入，添加，修改等操作，更多的操作是查询，因此我们将这种特殊用途的数据库称之为数据仓库

2.数据仓库的特点——面向主题：不同与一般数据库的面向业务，数据仓库的数据是面向主题的，不是面向对象的

3.数据仓库的特点——集成性：数据仓库会存储诸如月报表，周报表等集成式的数据，而普通数据库并不会这么干

4.数据仓库的特点——相对稳定性：进去的数据将不会进行修改，删除等操作

5.数据仓库的特点——反映历史变化(随着时间变化)：隔一段时间会将数据导入进来

6.数据仓库的建立过程：
首先是从数据源中抽取(从不同的数据源抽取)，清理(使数据格式一致、去除冗余数据)，装载(放到数据仓库中)，刷新(定期向仓库中添加数据);
数据集市即部门级的数据仓库，因为数据仓库的建立从企业全局的战略上讲具有非常大的风险，因此只建立部分数据库最后再将其整合则会降低风险，而其中部门级的数据库则称为数据集市

7.OLAP服务器的概念：即联机分析处理服务器，专门做分析处理工作的，针对特定问题的联机数据访问和分析，最表层是数据的前端工具，前端工具最普通的如查询工具，报表工具，分析工具以及比较独特的数据挖掘工具

数据挖掘

1.数据挖掘方法分类——关联分析：挖掘出隐藏在数据间的相互关系

2.数据挖掘方法分类——序列模式分析：侧重点是分析数据间的前后关系(因果关系)

3.数据挖掘方法分类——分类分析：为每一个记录赋予一个标记再按标记分类

4.数据挖掘方法分类——聚类分析：分类分析法的逆过程

5.数据挖掘方法：(1)决策树

(2)神经网络

(3)遗传算法

(4)关联规则挖掘算法

反规范化

1.反规范化的提出：数据库规范化程度不高会有过多的数据冗余，插入异常，删除异常但规范化程度过高会造成数据表过多，查询时的效率会极大的降低，因此提出了反规范化

2.反规范化的技术：(1)增加派生性冗余：增加冗余

(2)增加冗余列

(3)重新组表

(4)分割表：包括垂直分割和水平分割

大数据技术

海量数据

分布式数据库相关概念

描述为不需要了解物理存储或存储位置，是位置透明
描述为分块存储，是分片透明

透明

1.分片透明：是指用户不必知道数据是如何分片的，它们对数据的操作在全局关系上进行，即关系如何分片对用户是透明的，因此，当分片改变时，应用程序可以不变。分片透明性是最高层次的透明性，如果用户能在全局关系一级操作，则数据如何分布，如何存储等细节不必关心，其应用程序的编写与集中式数据库相同

2.复制透明：用户不用关心数据库在网络中各个结点的复制情况，被复制的数据的更新都由系统自动完成。在分布式数据库系统中，可以把一个场地的数据复制到其他场地存放，应用程序可以使用复制到本地的数据在本地完成分布式操作，避免通过网络传输数据，提高了系统的运行和查询效率，但是对于复制数据的更新操作，就要涉及到对所有复制数据的更新

3.位置透明：是指用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的

4.逻辑透明：是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，逻辑透明对异构型和同构异构的分布式数据库是非常重要的

四、数据结构和算法

上午下午都会考，且难度最高

重点：线性表、树与二叉树、排序与查找、算法基础及常见算法

第一节.数组及稀疏矩阵
数组

主要考察一维二维数组存储地址的计算

一维数组存储地址的计算：a+i*len ；i为索引号，len是每个位置所占的内存大小

二维数组存储地址的计算(分为按行优先和按列优先)：如五行五列的二维数组a中各个元素占两个字节，则元素a[2][3]按行优先存储的存储地址为：13*2+a

稀疏矩阵

即元素先以上下三角矩阵方式排列，然后将其存入数组

考察：计算矩阵中某一个元素对应的数组的下标

第二节.数据结构的定义及线性表的概念
数据结构

1.数据结构的概念：数据结构即计算机存储、组织数据的方式

2.数据逻辑结构：分为线性结构与非线性结构；非线性结构又可以分为树型结构(不存在环路)和“图”(可能存在环路)。

线性表的概念

1.线性表的概念：线性表是线性结构的基本表现

2.线性表常见的存储结构——顺序表(连续的空间下存储数据)：开辟一系列的连续的空间，然后采用一维数组的方式来顺次存储信息

3.线性表常见的存储结构——链表(不连续的空间下存储数据)：每一个存储单元都包含了存储数据的空间及存储指针的空间(因为这一系列的空间不一定是连续的,指针的作用则是作为箭头，在两个空闲的空间之中起到指引作用)

4.三种不同的链表——单链表：即只有一种指针在空间之间依次指向的链表，在单链表中用头指针作为栈顶指针时，入栈和出栈都不需要遍历链表

5.三种不同的链表——循环链表：把尾元素的指针指向头结点(好处是：若当前结点是在尾元素，想要再次经过之前的某个元素，则可以继续next往下走，，直至遇到那个元素，而无需重新定位)的链表

6.三种不同的链表——双向链表：是可以双向的移动的链表(绝大部分结点都必须要有两个指针)，即可以通过头节点往尾结点移动，也可以通过尾结点向头节点移动的链表

7.链表的特点

(1)查询慢：链表中地址不是连续的，每次查询元素都必须从头开始

(2)增删快：链表结构，增加/删除一个元素，对链表整体结构没有影响，所以增删快

(3)结点：链表中的每一个结点包含了一个数据源(存储数组)，两个指针域(存储地址)，两个指针分别存储当前结点的位置和下一个结点的位置，在单链表中，两个结点之间有一条链子连接，但是只是单箭头指向，即从a到b，但不能从b到a，而双向链表则是在两个结点之间架设两条链子，互相指向，此时结点a可以到b，结点b也可以到a

链表的基本操作

1.单链表的删除结点：如a1——>a2——>a3；这三个结点，若要删除a2，则是让指针P的next=指针Q的next；P的next表示指针P(指向a1的指针)的下一个指针。

2.单链表的插入结点：如a1——>a2；若要在a1与a2之间插入一个结点a3；则是令S(指向a3的指针)的next=P的next以及P的next=S

3.双向链表的删除结点

4.双向链表的插入结点

第三节.顺序存储与链式存储的比较
空间性能的比较

1.存储密度：顺序存储的存储密度为1(更优)，而链式存储的密度则小于1

2.容量分配：顺序存储需要事先确定，而链式存储则是动态更改(更优)

时间性能的比较

1.查找运算：普遍情况下二者时间复杂度一样，但特殊情况下顺序表更为方便

2.读运算：顺序存储更优

3.插入运算：链表更优

4.删除运算：链表更优

第四节.线性表——队列与栈
队列与栈的概念

1.队列的概念及特点：结点的存储及读取遵循先进先出的规律，原因是队列可以对两端进行操作

2.栈的概念及特点：结点的存储及读取遵循先进后出的规律，原因是栈只能对一端进行操作

3.特殊队列——循环队列：即一种呈圆形的队列，尾指针会随着结点的依次存储而逐渐后移直至与头指针重合；因此：队满条件=队空条件=“头指针等于尾指针”;解决队满与队空判断条件容易混淆的方法：方法(1)少存一个结点：此时的队满条件为(tail+1)%size=head

队列与栈的练习

图注：对A选项，让四者依次从左边进入，然后依次从左边出去即可实现；对B选项，先让e1和e2依和e4依次先从左边进入，再让e3从右边进入，然后出去的顺序就可以是e4、e2、e1、e3；对C选项，让e1和e2从右边进入，e3和e4从左边进入，然后就可以实现C选项；因此答案为：D

注：栈和队列都属于线性表，不过他们都是操作受到限制的线性表

第五节.广义表
考察广义表的长度计算、深度计算、head及tail运算

广义表的概念

1.概念：广义表是n个表元素组成的有限序列，是线性表的推广，通常用递归的形式进行定义，即表里面可以包含表(嵌套)

2. 表示：LS=(a0，a1…,an)。注：其中LS是表名，ai是表元素，它可以是表(称作子表)，也可以是数据元素(也称原子).其中n是广义表的长度(最外层包含的元素个数),n=0的广义表为空表；而递归定义的重数就是广义表的深度，直观的说，就是定义中嵌套的次数(原子的深度为0，空表的深度为1)

广义表涉及的运算

1.head运算：即“取表头”(表头就是最外层的第一个表元素)

2.tail运算：即取“表尾”(表尾就是除了表头以外的所有其他元素组成的新广义表)

第六节.非线性结构——树与二叉树(import)
基本概念

结点：图中的1、2、3…数字圆形都表示结点，

结点的度：指一个结点所有的孩子结点数(如结点1的度就是2,结点3的结点度即为1)，

树的度：即一个树当中，结点的度最高的那个结点的度数；

叶子结点：如7、8等没有孩子结点的结点都称之为叶子结点；

分支结点：即有分支的结点

内部结点：非叶子结点又非根节点(最上面的那个结点)

父节点和子节点：这是一个相对概念，如2就是4的父节点，4就是2的子节点

兄弟结点：同属于一个父节点的子节点间称之为兄弟结点

层次：行数即为层次，该图中的层次即为4

满二叉树与完全二叉树(特殊的二叉树)

1.满二叉树的概念：整个树可以构成一个完成的三角形即为满二叉树

2.完全二叉树的概念：最后一行的叶子结点的父节点必须要有兄弟结点且它要么也是叶子结点要么只有一个结点且该结点和最后一行的叶子结点紧挨着

3.二叉树的重要特性：

二叉树遍历

分为两大类的遍历方法：层次遍历与(前序遍历、中序遍历、后序遍历)

遍历：将结点按照一定顺序打印出来

1.层次遍历：从根节点开始，按照从上到下，从左到右的顺序依次遍历结点

2.前序遍历(根左右)：即将根节点的访问放在最前面。然后访问左右子树节点

3.中序遍历(左根右)：先访问左子树结点(左子节点以及它的所有子节点构成的新二叉树)，再访问根节点，再访问右子树结点

4.后序遍历(左右根)：先访问左子树结点，再访问右子树结点，再访问根节点

反向构造二叉树(重点考察)

1.概念：知道二叉树的遍历序列，然后反向推出二叉树的构造

2.例题

图注：解题方法-是标注根节点，然后推左右结点

树转二叉树

由于树的应用主要是二叉树的应用，所以我们需要将树转化为二叉树

1.树转二叉树的基本原则：某个结点的孩子结点都会成为它的左子树结点，某个结点的兄弟结点都会成为它的右孩子结点

2.树转二叉树的例题

查找二叉树(一类特殊的二叉树)

1.概念：(每一个)根节点的左子树结点的键值都小于根节点，根节点的右子树结点都大于根节点的一类二叉树即被称之为查找二叉树(或排序二叉树)

2.价值：这种二叉树能极大的提高查询的效率和速度

3.插入运算：(1)若该键值已存在，则不再插入

(2)若查找二叉树为空树，则以欲插入的新结点为查找二叉树

(3)将要插入结点键值与插入后父结点键值比较，就能确定新结点的位置是父结点的左子结点，还是右子结点

4.删除结点：(1)若待删除结点是叶子结点，则直接删除

(2)若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接

(3)若待删除结点p有两个子结点，则在其左子树上，用中序遍历寻找键值最大的结点s，用结点s的值代替结点p的值，然后删除原结点s，结点s必属于上述(1)或(2)

最优二叉树(哈夫曼树)

考察哈夫曼树的构造

这种二叉树是一种工具，用于哈夫曼编码，哈夫曼编码是一种无损压缩的方式,哈夫曼树中每一个父结点的键值都等于其子结点之和(不是子树结点);

1.树的路径长度：即在树中指定一条路径，将路径的段数相加

2.权：在最优二叉树中即某个叶子结点的键值(该键值将代表某个字符出现的频度)

3.带权路径长度：分为结点和二叉树的带权路径长度，结点的带权路径长度等于路径长度乘以权，二叉树的带权路径长度即为所有结点的带权路径长度之和

4.哈夫曼树设计的基本思想：让二叉树的带权路径长度尽可能小

线索二叉树

由于二叉树中有许多结点处于空闲的状态，有许多指针并未被利用，而将其空闲资源利用起来方便遍历则是线索二叉树的由来，线索二叉树根据遍历的分类可以被分成三种线索二叉树：前序二叉树、中序二叉树、后序二叉树

图注：红线代表推出，绿线代表由来；如图一中二叉树的前序遍历为：ABDEHCFGI；

平衡二叉树

即更为平衡、更为饱满的二叉树

1.概念：任意结点的左右子树深度不能相差超过1，即每结点的平衡度(该结点的左右子树结点的深度之差)只能为-1、0或1

图注：图一和图二都属于排序二叉树，但图一的查询效率远低于图二，因为图一不属于平衡二叉树。而图二属于平衡二叉树

第七节.非线性结构——图
图—基本概念

图分为有向图和无向图

1.无向图：在该图中，若每一个顶点与其他所有顶点都有一条边相连，则称该图为无向图

2.有向图：若每一个顶点与其他所有顶带都有两条有向边相互联系，则称该图为有向图

图的存储—邻接矩阵

1.矩阵的大小：若有a个结点，则该矩阵为aXa阶矩阵

2.矩阵的内容：矩阵内只有0和1两种数字，以矩阵的第一个行(hang)为例，第一个结点按照与后续每一个结点是否有边来确定矩阵的内容，若有边则对应的该行该列值为1，无边则为0

3.图的广度遍历过程：从图中某个顶点触发，在访问了顶点之后，一次性访问顶点的各个未被访问的邻接点，然后分别从这些邻接点出发，依次访问它们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直到图中所有已访问的顶点的邻接点都被访问到

图的存储——邻接表

1.概念：首先会有一个表记录每一个结点，即把每个顶点的邻接顶点用链表表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针

图——图的遍历

图的遍历分为深度优先遍历和广度优先遍历

1.深度优先遍历：首先一条路径试探到底，然后再回退回来继续深入下一条路径

2.广度优先遍历：即从顶点开始，一行一行遍历

图——拓扑排序

用一个序列来表达哪些事件可以先执行，哪些事件可以后执行

1.AOV网络：我们把用有向边表示活动之间开始的先后关系，这种有向图称之为用顶点表示活动网络，简称AOV网络

图的最小生成树——普利姆算法

1.最小生成树：如图若有a个顶点，则在图中取a-1条边，用这些顶点和边重新构成一个树，而路径值最短的情况下的树即为最小生成树

2.求最小生成树——普利姆算法(最近点法)：任选一个结点A并将其标定为红点集，其余所有结点标定为蓝点集，然后将离红点集A距离最短的结点B连接起来并将其也纳入红点集，然后继续寻找蓝点集和红点集之间的最短距离结点并将其纳入红点集，重复该操作直至所有结点被纳入红点集(将结点纳入红点集时注意不能形成环)

3.求最小生成树——克鲁斯卡尔算法(最近边法):任选一条边并将其标定为红点集，其余所有边标定为蓝点集，然后将离红点集边端点距离最短的边连接起来并将其也纳入红点集，然后继续寻找蓝点集和红点集之间的最短距离边并将其纳入红点集，重复该操作直至红点集纳入了结点数-1数量的边(将边纳入红点集时注意不能形成环)

第八节.算法基础
算法的特点

1.有穷性：算法必须在执行有穷步之后结束

2.确定性：算法中每一条指令都必须有确切的含义，不能含糊不清

3.算法必须有0个及以上的输入

4.算法必须有1个及以上的输出

5.有效性：算法的每个步骤都能有效执行并能得到确定的结果。例如a=0，b/a就无效

算法的复杂度

包括时间的复杂度(必考)和空间的复杂度

1.时间复杂度的概念：时间复杂度是指程序运行从开始到结束所需要的时间。

2.时间复杂度的分析：通常分析时间复杂度的方法时从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的1时间度量。

3.时间复杂度的计算：一般来说，在算法中，原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间，其定义如下

如T(n)=3n³⁺²ⁿ2+n，则T(n)=O(n^3）

且：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n3)<O(2^n)

注：二叉树的复杂度采用O(log2n)，循环的复杂度采用O(2^n)

4.空间复杂度：是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小

第九节.查找——顺序查找、二分查找、散列表
查找的目的是为了在众多关键值中查找到想要的关键值

顺序查找

1.概念：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败

2.顺序查找的平均查找长度：n+1/2

3.顺序查找的空间复杂度：O(n)

4.顺序查找的优缺点：方法简单但效率较低

二分查找法

不是所有序列都能用二分查找法，能使用该方法的前提是该序列是有序排列的(如从大到小或从小到大)

1.概念：首先将n个有序排列数组的元素最小索引值(非零)和最大索引值相加除以二，然后对其进行向下取整，然后查询该取整后的索引值对应的键值并与待查询键值进行比较，若小于键值则对其右边数组继续使用二分法(从小到大排列的数组中)

2.二分取整的时间复杂度：O(log2n)

3.优势：效率高

散列表

在数据进行存储时遵循一定的规则

1.散列表的概念：散列表查找的基本思想是：已知关键值集合U，最大关键字为m。设计一个函数Hash，它以关键字为自变量x，关键字的存储地址为因变量y，将将关键字映射到一个有限的、地址连续的区间T中，这个区间就称为散列表，散列查找中使用到的转换函数称为散列函数

2.散列表中可能遇到的问题：由于关键值和地址是函数关系，所以可能出现两个关键值对应同一个地址的情况

3.解决办法——线性探测法：按出现顺序来定义函数中y值相同的关键值的处理，如b和a冲突，则将b放在a的下一个空单元

4.解决办法——伪随机数法

第十节.数据的排序
必考内容

数据的排序按照稳定性可以分为稳定与不稳定排序，按照空间结构又可以分为内排序与外排序

直接插入排序

1.概念：即当插入第i个记录时，r1、r2、…rn-1都已经排好序，因此，将第i个记录ri依次与ri-1…r2、r1进行比较，找到合适的位置插入，它简单明了，但速度很慢

2.直接插入排序的步骤：如这样一个序列：57 68 59 52；

（1)68>57；不做处理

（2)57<59<68；则68应在59之后(仍未做处理)

(3)52<57,插在57之前(此时开始处理)：57 59 68 52

希尔排序

属于插入排序的一种，效率高于直接插入排序，善于应对大量数据的排序

1.概念：先取一个小于n的整数a1，然后把文件的全部记录分成a1个组，分组方法为：所有距离为d1的的倍数的记录放在同一个组中。分好组后再在各自的组内进行直接插入排序，排序完成以后解除分组，再取第二个小于a1的整数a2，再对该文件的所有记录进行相同方法的分组并同样进行直接插入排序，再取第三个小于a2的整数a3重复该操作…直至所取的整数an等于1为止

如图:

直接选择排序

1.概念：首先在所有记录中选出排序码最小的记录，把它与第一个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换…依次类推，直到所有记录排完为止

堆排序

1.堆的概念：设有n个元素的序列(K1、K2、…Kn)，当且仅当满足下列关系之一时，称之为堆：

(1)ki<=k2i且ki<=k2i+1；(即每一个结点的孩子结点都比自己大) (2)ki>=k2i且ki>=k2i+1；(即每一个结点的孩子结点都比自己小)；其中(1)称为小顶堆(2)称之为大顶堆

2.堆排序的基本思想：先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依次类推，直到所有元素均输出为止，此时元素输出的序列就是一个有序序列

3.初建堆的过程：对于一个二叉树，要将其调整为大顶堆，应有如下步骤：

(1)取树中的非叶子结点

(2)将非叶子结点各自与其子结点的键值进行比较(从下往上)，如果比其中一个小，则与其交换位置，若比两个都小，则与最大的交换位置

4.堆排序的过程：

(1)初建堆

(2)输出堆顶

(3)取一个叶子结点为新根结点

(4)再次进行堆的重建

(5)输出堆顶…

冒泡排序

1.概念：冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部，由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法

2.步骤：一个数组中若有n个元素，对其采用冒泡排序：将第n个元素与第n-1个元素进行比较，若第n个元素较小，则将其与n-1个元素交换位置，再将n-1位置的元素与第n-2位置的元素进行比较…重复该操作

快速排序

1.概念：快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组成原问题的解(通俗的讲：就是把一个数组拆成了俩个数组)

2.步骤：

(1)在数组中任取一个数为基准

(2)定义一个指针，先指向左边第一个数，再指向右边第一个数，再指向左边第二个数，再指向右边第二个数…

(3)将基准与指针指向的数进行比较，若该数大于基准，则和基准交换位置，若小于基准则位置不变

(4)最后将得到一个以基准为分割数的，右边大于基准的数组集合，左边小于基准的数组集合

归并排序

1.概念：归并也称合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并

2.步骤：合并的过程是：比较A[i]与A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到第一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中

基数排序

1.概念：将关键字拆分为个位、十位、百位…并对其各自位进行排序最后得出结果

2.步骤：对于一个数组R

(1)先收集其个位并对其个位进行排序(个位相同的则按照出现顺序紧挨着)

(2)按照个位排序的顺序将数组元素进行排序

(3)对刚刚排好序的数组收集其十位进行排序

(4)再将数组按照十位排序的顺序将数组元素进行排序

(5)…重复该操作，直至位数排尽

各个排序算法的时间复杂度和空间复杂度及稳定性(必考)

程序设计语言

重点：正规式(必考)、表达式(高频)、传值与传址(高频)

第一节.编译过程

编译过程分为解释型和编译型两类
解释型：敲一行代码，一回车，后台就直接操作相关行为，有错误就告诉你
编译型：运行的时候再做成可执行的程序执行
编译方式生成逻辑上与源程序等价的目标程序，解释方式不生成

词法分析的任务是把源程序的字符串转换为单词符号序列。看关键字有没有写错。

语法分析，词连起来表达的句子有没有问题、或缺了些符号。

语义分析，循环有没有停止条件、是不是死循环、有没有除零操作。

中间代码生成、代码优化，匹配系统，提高运行效率。

词法错误：从左到右逐个扫描源程序中的字符，识别其中如关键字(或保留字)、标识符、常数、运算符以及分隔符(标点符号和括号)等

语法错误：主要是分析句子结构的错误，如非法字符，关键字或标识符拼写错误，语法结构错误，if endif不匹配，缺分号等

语义错误：死循环，零循环，其他逻辑错误等

词法分析的输出是“记号流”；也就是语法分析的输入，而语法分析的输出是“语法树”
1
2
3
4
5
6
7

注：

(1)符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统之中

(2)在对源程序进行编译的过程中，常生成与源程序等价的中间代码，以利于进行优化，常见的中间代码包括：后缀式、三地址码和树等

(3)中间代码的生成与具体的机器没有任何关系，但目标代码的生成与具体的机器有着密切的关系

(4)编译过程中，中间代码生成和代码优化并不是每一个编译编译器都必须的

第二节.文法定义

文法的定义

一个形式文法是一个有序四元组G=(V,T,S,P)，其中：

1. V:非终结符。不是语言组成部分，不是最终结果，可理解为占位符。大写字母代表，这种符号是可以推出其他符号的。

2. T: 终结符。是语言的组成部分，是最终结果。以小写字母代表

3. S:起始符。是语言的开始符号

4. P:产生式。用终结符替代非终结符的规则

文法的类型

分为0型、1型、2型、3型

零型又称短语文法

1型又称上下文有关文法

2型又称上下文无关文法

3型又称正规文法

语法推导树

可以用来进行语法规则的推导，通过推导树，我们可以了解到一种语法能够表达的串以及能够构造的句型是什么样子

例如：

S->aAS|a推导公式即为P产生式

S->aAS|a意为S->aAS和S->a
A->SbA|SS|ba

注：程序设计语言的大多数语法现象可用其中的上下文无关文法来描述

第三节.有限自动机与正规式

有限自动机

(S,0)=B表示S通过路径0可以得到B，而S即为初态，f即为终态

考察形式：设定一个值：如10或01或001，问是否能够构建这样一条通路？，实际上该题即问终态与初态相连，求出其路径，再看其路径值是否与与题意相符

例题

图注：直接把选项中的路径代入图中运行，从初态开始运行，若选项提供的路径使其到达了终态，那么这就是正确的选项，该题中即为C选项

正规式

正规式是描述程序语言单词的表达式

“ | ”代表“或”
“ * ”代表循环多次，如在或运算中，可以任意选择左式和右式的循环次数，循环次数可以从零到无穷大。

例题

（1）
使用S->aA推导，A可以通过推导用小写字母代替
S->aA，A->bS推出S->abS，结合S->aA，就是S->abaA，A->bS推出S->ababS，S->aA，就是S->ababaA，A->bS就是abababS，因此可以识别选项A。
同理可得，选项BC都行
答案是D
（2）
答案是C
使用代入法，看哪个文法可以把（1）的选项全部表达出来，可能是正确答案
A.只要是由a或b组成的都可以表达，范围比G[S]要大，不是等价关系
B.不行
D.不能表示abbaab，不行
可以是空串，

A. A->B不能到C
B.A循环，不能到C
C.A->B->C->B->C
D.A->A->B->C->B
答案是C

第四节.表达式

表达式按照树的遍历分为了前缀表达式、中缀表达式、后缀表达式

考察形式：

首先将表达式(括号无需构造)构造为一颗中序表达树，然后再进行下一步运算，该题答案即为D

第五节.函数调用——传值与传址

函数调用的方式分为两种：传值调用和传址调用

概念及特点

1.传值调用：形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变，调用时实际上是把调用的值复制给了一个变量

2.传址调用(也称引用调用)：形参取的是实参的地址，即相当于实参存储单元的地址引用，因此其值的改变同时就改变了实参的值，调用时实际上是将实参的地址的指针赋值给了变量，因此它的改变会引起实参的改变

传值，xy ab都有自己的存储空间

传址，xy存储的是地址

第六节.程序设计语言的种类、特点及适用范围

C++

1.特点：既支持面向对象程序设计的概念，也支持原来在c语言中的过程式程序设计，因此有人称其为混合式的面向对象语言，属于面向对象的编译型语言

2.适用场景：系统程序的设计，包括嵌入式、桌面式和服务器操作系统的设计，大型软件系统的核心模块的设计，以及各类桌面软件的设计

Java

1.特点：java是一个纯面向对象的程序设计语言，属于半解释型语言

2.适用场景：互联网信息系统的开发

Lisp

1.特点：属于函数式程序设计语言

2.适用场景：用于符号演算、微分和积分演算，游戏推演、以及人工智能的其他领域

Prolog

1.特点：以特殊的逻辑推理形式回答用户的查询

2.应用：多用于数据库和专家系统

Python

1.特点：是一种面向对象、解释型计算机程序设计语言

2.适用场景：快速生成程序的原型，然后对其中有特别要求的部分，用更适合的语言改写，比如3D游戏中的图形渲染模块

C#

1.特点：是一种面向对象的、运行于.NEX Framwork之上的高级程序设计语言

2.适用场景：由微软公司发布的，主要用于构件.NET Windows网络框架

汇编语言

汇编语言是面向机器的程序设计语言，使用汇编语言编写的程序，机器不能直接识别，要由一种程序将汇编语言反映成机器语言，这种起翻译作用的程序叫做汇编程序，汇编程序输入的是用汇编语言书写的源程序，输出的是用机器语言表示的目标程序，汇编语言的指令语句必须具有操作码字段，可以没有操作数字段

操作系统

重点：银行家算法、pv操作、文件管理、存储管理、操作系统的分类及其特点

第一节.操作系统概述

操作系统与计算机体系结构之间的关系

操作系统具备的管理职能

1.进程管理：包括(1)进程的状态；(2)前趋图；(3)pv操作；(4)死锁问题。

2.存储管理：包括(1)段页式存储；(2)页面置换算法。

3.文件管理：包括(1)索引文件；(2)位示图。

4.作业管理

5.设备管理 包括：数据传输控制方式

6.微内核操作系统：包括虚设备与SPOOLING技术

第二节.进程管理—进程的状态

程序的三种基本状态(三态模型)

等待状态下的程序缺少除cpu资源以外的其他资源，如用户指令或外设支持等资源；就绪状态的程序除了CPU资源以外的所有资源都已经准备就绪；处于就绪状态的程序需要排队获取CPU资源，且即使获取到了CPU资源，他们的运行时间也是有限的，因此，时间片到了以后就会从运行状态退出到就绪状态，而程序在运行时出现了某些资源的缺失则会退出至等待状态.

程序进程的五态模型(三态模型的发展)

该模型是三态模型的发展，将就绪状态分为了静止就绪和活跃就绪，静止就绪是该进程已经获得了CPU资源，但由于人为需要，由运行状态将其退出至就绪状态，如我们在听歌时突然来了电话，我们暂时将音乐关闭，这种人为的将程序由运行态转至的就绪态，即为静止就绪，再次调动该程序时，该程序就将由静止就绪转至活跃就绪进而被调用；此外，阻塞态即为三态模型中的等待态

进程控制块的组织方式

分为索引方式和链接方式

1.链接方式：把具有同一状态的进程(PCB)，用其中的链接字链接成一个队列。这样，可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程排在队列前面。此外，也可以根据阻塞原因的不同而把处于阻塞状态的进程的PCB排成等待I/O操作完成的队列和等待分配内存的队列等

2.索引方式：系统根据所有进程的状态建立若干索引表。例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的位置

第三节.进程管理——前趋图

ps.常与pv操作结合起来考察

前趋图的概念

1.概念：前趋图是将一个完整的进程所需的工序按照是否具有先后关系将进程进行再次区分的图象

2.模型示例：

该前趋图以包饺子这一工序为例，首先将包饺子分为了五大步骤，并根据步骤间是否具有先后约束关系将其分为三个大的步骤，这样做的好处是明确了A,B,C三个步骤是平行的，他们之间可以并行，这样可以增大CPU的处理效率。

第四节.进程管理——进程的同步与互斥

ps.进程的同步与互斥是进行pv操作分析的前提

进程的互斥

1.互斥的概念：在同一时刻只允许某一个进程使用资源，即同一资源不能服务于多个进程
反义词：共享

2.互斥的实际应用示例：

单缓冲区下生产者和消费者的关系即为互斥，即生产者将产品投入到市场的时间片内消费者不能进行消费，只有当生产者完成产品的市场投放之后，消费者才能开始消费；这其中生产者的产品投放以及消费者的消费。都可以看作是程序的两个进程

进程的同步

1.同步的概念：运行速度有差异的两个进程同时开始运行，在一定情况下，速度较快的进程会停下来等待速度较慢的进程
反义词：异步

2.进程同步的实际应用示例：

多缓冲区下生产者和消费者的关系即为同步，即生产者在将产品投入市场的同时，消费者也能够对产品进行消费。但若一方速度较快，则另一方需要停下来等待

第五节.进程管理——pv操作

与pv操作相关的几个概念

1.临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机，磁带机等。

2.临界区：每个进程中访问临界资源的那段代码称为临界区。

3.信号量：是一种特殊的变量，符号为s，只用于pv操作

p操作（阻塞）

S代表信号量，该操作表示：S自减一，然后判断是否小于零，若小于零则将该进程阻塞起来，并将其放入进程队列中，让进程处于等待状态，若不小于零，则表示可以往下面执行；该操作即为将进程“挂起”或“申请资源”，该操作一般用于”运行需要条件的操作“

v操作（释放）

该操作表示：S自增一，然后判断S是否小于等于零，若是，则从进程队列中拿出一个进程，并唤醒该进程，使其继续执行；若不是，则可以继续往下面的步骤执行；该操作即将进程“唤醒”或“释放资源”，一般将该操作用于”没有任何约束的上来就可以运行的操作“

pv操作实例

该图为单缓存区下生产者与消费者在市场消费中的pv模式图，生产者的操作有：生产产品，送产品到缓存区；消费者的操作有：从缓存区取产品，消费产品；在这个模型中加如了pv操作后极大的提高了模型的效率，其中p(s1)表示将S1的值代入p操作，V(s2)表示将S2的值代入v操作

此外：pv操作的根本目的是为了解决两个或多个进程运行时的约束关系造成的麻烦，如上例中的单缓存区市场消费问题；此外，有制约关系的操作双方信号量相同

pv操作与前趋图

即pv操作与前趋图结合起来考察

这种例题通过观察箭头的指向来解题，被指箭头用p操作，指向箭头就用v操作，有几个箭头就用几次。

例题

第六节.进程管理——死锁问题

常见习题：计算机系统至少需要多少资源将不可能发生死锁问题；

死锁

1.问题描述：进程管理是操作系统的核心，但如果设计不当，就会出现死锁问题，如果一个进程在等待一件不可能发生的事，则进程就死锁了，此时该进程将一直占用部分系统资源，而如果多个进程产生死锁，就会造成系统资源被占用完毕，进而造成系统死锁

2.解决方案：提高系统资源容量；
例如：

一个进程在得到所有所需资源之后将释放自身占用的资源，因此该例题至少需要13个资源则不可能发生死锁。

计算方法：将每个进程所需资源减去一然后把他们相加，总数再加一，即为避免死锁所需的最少资源

发生死锁的四大必要条件

1.进程互斥

2.保持和等待：在资源总量并未满足完成进程所需资源的总量前提下，每个进程都保持自身占用的资源不变并且一直等待其他进程完成以获取其释放的系统资源

3.不剥夺：系统不会把已分配给一个进程的资源剥夺掉分配给其他进程

4.环路等待：如总共有三个进程，A等待B，B等待C，C等待A;诸如此类的，等待的进程形成了一个闭合环状

注：死锁的预防就是通过打破四大条件来进行

死锁的避免

有两大方法，分别是：

1.有序资源分配法：将系统资源按照顺序分配给进程，一个进程完成后才将资源分配给下一个进程

2.银行家算法

银行家算法

该方法是避免死锁问题的常用方法

1.银行家算法的内容：它的内容即为分配资源的原则，包括：

(1).当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程

(2)进程可以分期请求资源，但请求的总数不能超过最大需求量

(3).当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使该进程在有限的时间里得到资源

2.银行家算法涉及到的题型：

解决该类问题，首先将系统所剩资源数计算出来，然后将每个进程还差的资源数计算出来，进行比较之后，将系统资源分配给差的最少的进程，进而让其释放资源，然后进行下一个所需资源较少的进程的分配，由此将进程执行的顺序计算出来

第七节.存储管理——分区存储组织

以一个例题为例，描述四个算法：首次适应法，最佳适应法，最差适应法，循环首次适应法；它们的概念及关系；

例题：某计算机系统的内存大小为128k，采用可变分区分配方式进行内存分配，现有作业4申请内存9k，几种不同的存储分配算法在分配中，会产生什么样的结果呢?

• 首次适应法
  首次适应法会把即将执行的作业安排在第一个能够容纳它的空间

• 最佳适应法
  该算法会把即将执行的作业安排在内存空间与它最接近的空间进行存放，如该例子中，作业4占据空间9k，通过该算法，计算机就将其存放在了空间为10的地址中；由于在每次存放作业以后内存空间剩余量极低，长期以后该算法会造成内存空间碎片化，降低内存地址的利用率

• 最差适应法
  该算法能够解决内存空间碎片化的问题，如图所示:该算法优先将作业存放至内存空间最大的地址.

• 循环首次适应法
  该算法是将空闲的区域连成环状，将作业在环状区域内顺次进行分配(从第二个空闲区域开始分配)

第八节.存储管理——页式存储，段式存储，段页式存储

• 页式存储组织

1.提出背景：为了解决碎片化的存储

2.概念：把用户程序分成等分大小的n个“页”(并将其编号)，再在地址空间中以nk为基数划分等大小的块(同样将其编号，块号又称页帧号)，运行用户程序时不再将整个程序进行运行，而是根据需要分批次将页调入到块中运行，而页和块之间的对应关系用页表来记录

3.页式存储组织的优缺点：优点：利用率高，碎片小，分配及管理简单

缺点：增加了系统开销(系统每次读取程序都需要先读取页表将其定位，再进行程序的读取，所以至少两次访问内存)；可能产生抖动现象

4.如图：

页号与页帧号的关系必须通过表来进行查询

5.逻辑地址和物理地址

要求物理地址，要先把逻辑地址(由图可知，逻辑地址由页号和页内地址组成)当中逻辑的页号和页内地址分开，要把它们分开，首先将页面大小写成二进制的形式，等于2^n;则说明一个页的页内地址有n位，而在逻辑地址中高于(从右往左)n位的部分就是页号,得到页号之后进行查表，得到相应的页帧号，而物理地址=页帧号+页内地址(该式子中的“+“是拼接，并非做加法)

• 段式存储组织

1.概念：按逻辑结构进行内存的划分，划分为n个段，每一个段的大小无要求，可以相等也可以不等，包括段号和段内地址，例如：可以将main主函数作为一个段，然后将第一个子函数作为一个段，然后将第二个子函数作为一个段…

该种存储方法按函数之间的逻辑对内存进行划分，大小差异较大，存在段表，段表的内容包括段号，段长以及基址，基址：就是该段在地址的起始位置。
优点：多道程序共享内存，各段程序修改互不影响。缺点：内存利用率低，内存碎片浪费大

• 段页式存储组织
  
  段页式存储是结合了段式和页式的一种存储组织，将内存先分段，再分页；
  优点：空间浪费小，存储共享容易，存储保护容易，能够动态连接；缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降(程序在执行时要先查段表，再查页表，使得系统资源消耗增加)

快表

1.概念：快表是一块小容量的相联存储器（按内容存储），由高速缓存器(放在cache之中)组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号

段表、页表放在内存里，称为“慢表”

第九节.存储管理——页面置换算法

1.产生背景：当程序的需要与系统资源的供给发生矛盾时的一种解决方案，即将不用的页面淘汰掉，置换为需要执行的页面

2.页面置换算法的内容：包括四种算法：
(1)最优算法(OPT)：尚处于理论层面

(2)随机算法：随机淘汰一个页面

(3)先进先出算法(FIFO):即淘汰时按照之前执行的先后顺序进行淘汰，有可能产生“抖动”(抖动即：把经常用到的页置换出去，要用的时候发现没有内存了，造成进程中断)。例如，432143543215用3个页面，比4个缺页要少

(4)最近最少使用算法(LRU)：即在保证最近使用的页面不被中断的情况下，将最少使用的页面淘汰，不会产生“抖动”

3.相关例题

”没有使用快表“即表示每读一次程序的块，需要先在内存上面查表，才能读取相应的内存块，所以每一个块需要两次内存的访问(先查表定位程序，再读取程序)，所以6个块(在页式存储结构中，每一个页面对应一个块)总共会产生12次对内存的访问;一个内存单元占据1B的内存，1页=1024B，即0-1023单元，swap存放在1023单元，就是一半在0页，一半在1页，，操作数A和操作数B也跨两个页，所以产生两次缺页中断
所有的指令(无论占据了几个页面)都只产生一次缺页中断，而操作数A和操作数B则各自产生两次缺页中断，因此总共产生了5次缺页中断

第十节.文件管理——索引文件结构

索引一般会有13个节点(默认情况下)，从0开始编号，其中索引0到9这十个索引称为直接索引，直接对应物理盘块，每一个物理盘块都对应了索引文件的内容，而索引10则称为间接索引，里面只存储地址，如一个物理盘块的地址大小为4个字节，而一个物理盘块的大小为4k，则4k\4字节等于1024，代表着1024个物理盘块的地址，因此该索引内可以存储的文件大小为4k1024；该10号索引称之为一级间接索引；索引11则是二级间接索引，即索引的内容还是索引，再索引的内容才是物理盘块，二级简介索引存储的文件大小即为：4k1024*1024；虽然分级越多存储的内容越多，但相应的，效率也会更低

1KB/4B=2 ^ 10 / 2 ^ 2=2^8=256个

第十一节.文件管理——文件和树型目录结构

树型目录结构的路径

1.绝对路径：是从盘符开始的路径

2.相对路径：是从当前路径开始的路径

在该文件树型图中，若文件目录的位置是D1，若要求f2的路径，则绝对路径：/D1/W2/F2；相对路径：W2/F2

文件属性及文件名的组成

1.文件属性：R：只读文件属性 A：存档属性 S：系统文件 H：隐藏文件

2.文件名的组成：驱动器号；路径；主文件名；扩展名

第十二节.文件管理——空闲存储空间的管理

总共有四种管理方法，分别是：空闲区表法；空闲链表法；位示图法；成组链接法

空闲区表法

1.概念：我们可以用一个表来记录哪些地方是空闲的，以便将其管理起来

空闲链表法

1.概念：把空闲区域都链起来，链成一条链表，然后需要空间分配的时候，从这条链表中划出一部分出来即可

位示图法(重点)

常以计算题方式考察

1.概念:将所有存储区域分成无数个物理块，然后以1表示被占用，0表示空闲，将所有空间进行标记

2.例题：

4195号是第4196个位，因此4196/32位=131.125；因此物理块的使用情况应该在第132个字中描述

第几个字从1开始
第几个位置从0开始

成组链接法

第十三节.设备管理——数据传输控制方式

主要是指内存和外设之间的数据传输控制问题，解决方式包括：程序控制方式；程序中断方式；DMA方式；通道；输入输出处理机；前三种要求重点掌握

程序控制方式

1.概念：也称程序查询方式，由这种方式是最为低级的，也是CPU介入最多的一种机制，即整个数据的传输控制很多时候都要CPU的介入，此时外设会处于非常被动的位置，即不会主动的去返回信息，如是否完成等信息，而是由CPU主动发出查询指令，进而对信息进行查询

程序中断方式

1.概念：大部分与程序控制方式相同，但相较于程序控制方式，由于增加了中断方式，主动性更强，即：如果外设完成了数据的传输等操作，外设会发出中断指令，效率比程序控制方式更高

DMA方式

1.概念：也称直接存储器存取方式，在该方式中，会有专门的DMA控制器，只要是外设和内存之间的数据交换过程，就由这个控制器进行管控了，CPU只需要在开头的时候做一些介入，如初始化等操作
效率高很多

设备管理的五个层次

由上到下依次是：
用户进程
与设备无关的系统软件
设备驱动程序
中断处理程序
硬件

第十四节.虚设备与SPOOLING技术

SPOOLING技术

1.概念：例如：四个人通过远程手段准备使用一台打印机，而这台打印机在同一段时间内只能让一个用户使用，若一个用户正在使用该打印机，另一名用户试图使用该打印机时就会提示该打印机被占用，，事实上这样做使得打印机的技术非常的低，而面对这个问提，采用了SPOOLING技术的打印机会进行如下操作：给打印机创建一个缓存区，每一个用户在打印时都会进入缓存区，而从缓存区到真正打印则需要挨个排队，即打印机在打印时不再排斥其他用户的打印操作，而是将其缓存起来，在将当前操作完成后立即进行第二个操作，这样做不仅使得用户的操作界面变得更为友好，也极大的提高了打印机的打印效率

第十五节.微内核操作系统

即把内核做得更小的操作系统

1.概念：把内核做的更小具有许多好处与优势，如提高了可靠性，稳定性，安全性；因为操作系统作为核心的系统软件，如果操作系统出现故障，就会影响整个系统的运行，将内核做的更小就会降低故障的发生率

2.单体内核和微内核的区别及各自优缺点如下图所示

Linux系统的常用命令

attrib：声明

modify：修改

chmod：修改文件权限

change：改变

计算机组成原理和体系结构

第一节.数据的表示

进制的转换

1.R进制转十进制:将每一位数字用R ^ k表示然后相加，k与该位与小数点的距离有关，小数点左边第一位为0，右边第一位为-1，往左递增，网往右递减，如：二进制数10100.01=12^ 4+12^ 2+1*2^-2

2.十进制转R进制: 整数位使用短除法，即将十进制数除以R再取余，直至余数为零，然后将余数由下往上按顺序排列，小数位乘以R，每乘一次就取它的整数位（ 整数位为零时就取零)，直至小数位为零，然后将取得的整数位由上往下排列即可。

3.二进制转八进制及二进制转十六进制：将二进制数以小数点为界向左及向右每三个一组(转八进制),或者每四个一组(转十六进制)，缺的数用零来补充，然后依次转化为相应的进制数然后按顺序排列即可。

原码反码补码移码

1.原码：将一个十进制数转换为二进制数，并且该二进制数的首位表示正负，0表示正，1表示负，不足八位的就在首位与二进制数中间用零填充。如-1的原码就是1000 0001
原码来做计算结果错误，所以使用反码、补码计算
2.反码：原码在计算机中进行加减不能得到正确的答案，而反码的加减则符合事实，正数的反码为本身，负数的反码为其原码除首位不变外全部取反，即零变为一，一变为零

3.补码：正数的补码与原码相同，负数的补码即为其反码加一(补码的运算也符合正确答案)

4.移码：将正数和负数的补码首位取反，其余位不改变（移码的运算也符合正确答案)
用来做浮点运算的解码

5.各自数值表示范围:其中n一般等于8

补码比原码、反码范围大，是因为+0 -0的表示不同

浮点数运算：

1.浮点数的概念：浮点数即科学计数法，如1000=1X10^3; 其中，1为尾数，10为基数，3为指数。

2.计算机中浮点数的运算：当两个指数不等的浮点数相加时，计算机会把低阶浮点数的指数转化为高阶浮点数的指数，如：1.0X10^ 3+1.19X10^ 2,计算机会将1.19X10^ 2转化为0.119X10^ 3,然后作和，然后结果格式化(即通过指数的转化保证尾数必须为非零的一位数)如：0.1119X10^ 3+1.119X10^ 2;得到11.3019X10^ 3以后，要化为1.13019X10^4

格式化后，尾数必须是个位数且不为0

第二节.中央处理器（CPU）

主机由CPU和内存（主存储器）构成
CPU由运算器和控制器组成

运算器(ALU）

包括：
1.算术逻辑单元ALU：运算相关

2.累加寄存器(AC):专门存放算术或逻辑运算的一个操作数和运算结果的寄存器。能进行加，减，读出，移位，求补等操作。是运算器的主要部分。

3.数据缓冲寄存器DR：进行读写数据时暂存的寄存器

4.程序状态寄存器(PSW）（常考）：该部件用来存放两类信息，一类是体现当前指令执行结果的各种状态信息(条件码)，如有无进位，有无溢出，结果正负，信息是否为零等；另一类是存放控制信息，如允许中断，跟踪标志等。

控制器

包括：

1.程序计数器(PC)：程序计数器中存放的是下一条指令的地址。由于多数情况下程序是顺序执行的，所以程序计数器设计成自动加一的装置。当出现转移指令时，就需重填程序计数器

2.指令寄存器(IR)：中央处理器正在执行的操作码表存放在这里，即当前正在执行的所有指令

3.指令译码器：将操作码解码，告诉中央处理器该做什么。

4.时序部件

注：

·CPU的寻址方式除了直接寻址以外还有多种寻址方式，目的是为了在效率和方便性上找一个平衡

·CPU根据指令周期的不同阶段来区分内存中以二进制编码形式存放的指令和数据

·指令最先进入到数据寄存器暂存起来，然后在拿到指令寄存器中，再交由指令译码器来解码进而运算(交给运算器)，而这一过程一结束，就会迅速提取程序计数器中的指令(即下一条指令)，因此，程序计数器中存储的始终是暂未执行的，下一条指令的“地址”；

第三节.计算机体系结构分类(Flynn)

指令流 数据流

第四节.CISC和RISC

考察特点、区别

第五节.流水线

流水线的基本概念

1.指令执行的流程：取指——分析——执行,注：指令执行步骤可能多于三步，应根据题意作答

2.流水线的概念：流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，他们可以同时为多条指令的不同部分进行工作，以提高各部分的利用率和指令的平均执行速度

流水线周期及流水线执行时间计算

1.流水线周期计算：流水线周期为执行时间最长的一段

2.流水线执行时间计算：
(1)理论公式：1条指令完整执行的时间+(指令条数-1)*流水线周期；
(2)实际公式(实际生产中工厂往往采用该方法，因为该方法效率更高)：一个完整指令的步骤数+指令条数-1)*流水线周期；注：计算时优先用理论公式，选项中没有该答案时再采用实际公式

三步的执行时间最长是2ns，所以流水线周期的时间是2

流水线——流水线吞吐率计算

1.概念：是指在单位时间内流水线所完成的任务数量或输出的结果数量

2.计算公式：TP=指令条数/流水线执行时间

3.流水线最大吞吐率计算公式：1/&；其中&是流水线周期
Δt是流水线周期

流水线——流水线的加速比

1.概念：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比

2.加速比计算公式：不使用流水线的执行时间/使用流水线执行时间

流水线——流水线的效率

1.概念：指流水线的设备利用率

2.计算公式：E=n个任务占用的时空区/k个流水段的总的时空区=T0/kTK；即从图形面积求解面积

如：

该流水线的效率即为T0=24/KTk=60；等于0.4

注：所有步骤花费时间相等的指令执行的效率最高，如下图

第六节.层次化存储器结构

内存存储外存的部分内容
cache存储内存的部分内容
CPU只处理cache中的指令
高速缓存存储器cache的作用是精简内存中重复出现的指令，提高CPU的执行效率，使得计算机的运算速度得到极大的提升
结构中由上至下，速度越来越慢，但容量越来越大

第七节.cache

1.cache的功能：提高CPU输入输出的速率，突破冯诺依曼瓶颈，即CPU与存储器系统间数据传送带宽限制，在程序执行过程中，Cache与主存的地址映射是由硬件自动完成的。

2.与cache相关的计算：如果以h代表对cache的访问命中率，t1表示cache的周期时间，t2表示主存储器周期时间，以读操作为例，使用“chche+主存储器”的系统的平均周期为t3，则：t3=h*t1+(1-h)*t2；其中，(1-h)又称为失效率(未命中率)。

注：CPU会在cache中寻找它需要的数据，如果不能找到，CPU就将前往内存中寻找，而chche的访问命中率就是CPU需要的数据在cache中被找到的比例，未能找到的数据CPU将前往内存中进行再次寻找

3.内存与cache地址映射的三种方式：cache与内存的地址映像方式有三种，分别是
直接映像(cache的区号与内存的区号一一对应)
全相连映像(cache的一个块号可以对应多个内存的块号，内存的一个块号也可以对应cache的多个块号)
组相连映像(即两种方式相结合的方法)

注：这三种映射方式都是计算机硬件自动完成的，不是软件

4.替换算法：替换算法的目的是使cache获得尽可能高的命中率，有以下四种：随机替换算法、先进先出算法、近期最少使用算法、优化替换算法

注：现代的计算机cache系统是分为了三个级别的，访问时先从第一层开始访问，直至三个级别的cache都被访问完全时才会访问内存

5.虚拟存储器：即cpu在给出需要访问的内存地址时，给出的并不是真正的物理地址，而是物理地址的抽象，虚拟存储器是由主存-辅存两级存储器组成

局部性原理

时间局部性：经常访问某个指令
空间局部性：访问一个块，紧接着访问它相邻的块

第八节.主存

主存的分类

1.随机存取存储器：简称RAM，断电后所有数据都将清除，有两类RAM：静态的(SRAM)和动态的(DRAM)，SRAM比DRAM速度更快，但价格也更贵。SRAM用来作为高速缓冲存储器(Cache)，DRAM用来作为主存及图形系统的帧缓冲区。SRAM将每个位存储在一个双隐态的存储器单元中，DRAM将每个位存储为对一个电容的充电，由于电容非常小，在10~100ms时间内会失去电荷，所以需要周期性地刷新充电以保持信息

2.只读存储器：简称ROM，断电后仍然能够存储信息

主存的编址（常考）

1.概念：主存的编址就是把许多块芯片组成相应的存储器

注：一般表示方式如下图，其中左图一中的8表示它有8个地址空间，4表示每一个地址空间存储了4位的信息，而两个图一则可以拼接为图二，两个图二可以拼接为图三

2.编址相关计算：

其中H表示十六进制，存储单元数量等于大的内存地址减去小的内存地址再加上一；K=1024，第一个空即为存储单元数量除以1024

（1）
C7FFFH-AC000H+1=（C7FFFH+1）-AC000H=C8000H–AC000H=1C000H
8向前借一位，因为是16进制，所以借了16，就是8+16-C=C
C被借一位变成B

1C000H除以1024=112
（2）求出t=4

第九节.磁盘结构与参数

注：磁道一般分为许多个小的扇形区，即物理块，磁头在依次读取这些物理块时(磁头必须依次读取)，会在读取的同时将其存放进缓存区，缓存区可以是单个，也可以是多个，存放完成后会在缓存区花费时间进行处理，处理期间磁头的读取不会停止，因此，如果缓存区过少，就会出现：读取一个物理块花费了一个周期甚至更长的时间。

磁盘调度管理中，先进行移臂调度寻找磁道，再进行旋转调度寻找扇区

(1)
33ms一圈，有11个块，一个块的旋转时间是3ms，读取时间是3ms
磁头开始旋转就不会停，磁头从R0开始转，经过3ms读取R0转到R1，这时缓存区正在处理记录，不能读取，磁头继续旋转1圈转到R1处读取R1，以此类推，每次记录的读取+处理时间为3ms+33ms，R0-R9都是这样处理。R10不需要旋转，只计算读取+处理时间3ms+3ms，总共是（33+3）*10+（3+3）=366ms

(2)
(3ms+3ms)*11=66ms

第十节.总线

总线的分类

根据总线所处的位置不同，总线通常被分成三种类型

0.概念：总线是连接计算机有关部件的一组信号线，是计算机中用来传送信息代码的公共通道。

1.内部总线：微机内部的，各个外围芯片与处理器之间的总线，属于芯片级别

2.系统总线：系统总线即为各个插线板和系统板之间的总线，属于插线板级别，比如PCI、VGA；包括(1)数据总线：如32位，64位等一次性能够传输的位(2)地址总线：假设该计算机的地址总线为32位，那就代表它的地址空间为2^32个字节，内存空间是4G(3)控制总线：发送相应的控制信号的总线

3.外部总线：即微机和外部设备的总线

注：总线上的多个部件之间只能分时向总线发送数据，但可以同时从总线接收数据

第十一节.系统可靠性分析与设计

串联系统

1.串联系统的结构：只要一个子系统失效，则整个系统都将失效

2.串联系统可靠性的计算：即各个串联子系统可靠性相乘，如上图，其中R为可靠性，此外，1-可靠性即为失效率，而总的失效率即为串联各个部件的失效率作和(近似计算)

并联系统

1.并联系统的结构 注：少数子系统的失效将不会影响整个系统

2.并联系统可靠性的计算：通过计算失效率来求得可靠性，即各个子系统的失效率相乘，再由1减去它，即可得到系统可靠性

模冗余系统与混合系统

1.结构

图片解释：数据输入n个子系统中，它们各自得出自己的结果，然后汇总到表决器，表决器将遵循少数服从多数的原则，输出大多数子系统得到的那个答案然后进行输出
计算几乎不考

第十二节.差错控制——CRC与海明校验码

检错与纠错

1.检错：将错误检查出来

2.纠错：将错误检查出来的同时并进行纠正

码距及其作用

1.码距的概念：指整个编码系统中任意两个码字的最小距离,如A变化X个位得到B，则X就为码距，如：若使用2位长度的二进制编码，若以A=11，B=00为例，A,B之间的最小码距为2

2.码距的作用：增大码距能够起到检错的作用，因为数据在传输的过程中如果链路出现了问题，那么将会使得接收到的二进制数发生变化，若码距过小，则很可能造成信息的混淆，增大码距就使得被改变的二进制数混淆信息的概率极大的降低;若码距再进行增大，则能够起到纠错的作用，因为数据链路出错的概率比较低，只能造成传输中极少二进制数的改变，我们可以根据该传输失真的二进制数中大部分二进制数的构成来进行推断，推断出结果就达到了纠错的目的。

注：在一个码组内为了检测e个误码，要求最小码距d应满足：d>=e+1

在一个码组内为了纠正t个误码，要求最小码距d应该满足：d>=2t+1

循环冗余校验码——CRC

这是一种可以检错但不能纠错的一种编码

1.CRC的概念：在对信息进行编码的时候在其尾部加入一些校验信息，让编码后的数据能够与循环校验码的生成多项式相除余数为零，若不为零则说明传输过程出现了错误，其中，原码加上(增添在右方)校验信息加(做加法)上余数所得的码即为CRC，

注(1)：生成多项式是一个二进制数，如"X^ 4+X^3+X+1",这个生成多项式实际上就是二进制数11011；在相除时，需在原码后方添加一些0，添加的0的个数等于生成多项式的位数减去1，增加的0即为校验信息。

注(2)：二进制的除法与算术除法相似，唯一不同的是所得除数在作减法时，减得的值要取绝对值，即0-1=1；这样使得整个除法运算中不存在借位。

校验码——海明校验码

1.概念：海明码是一种利用奇偶性进行检错和纠错的校验码，是一种插入到信息中的编码，一般为多个码，其插入的位置满足规律：2^ r>=x+r+1；其中，x为信息的二进制数的位数，r为校验码的个数，而插入信息的位置则是2^ r-1，2^ r-2……2^0;如r=3时，校验码就插在1，2，4位置

2.校验码的计算：
如信息1011，根据公式得出其校验码分别放在1，2，4位，因此其海明码将有7位数，其中3，5，6，7位即为信息位，将3写为2^ 0+2^ 1;将5写为2^ 0+2^ 2…将四个信息的位数用此方法表示以后可得到校验位的值的计算公式：r0=i4&i3&i2；r1=i4&i3&i1.r2=i4&i3&i2；其中，r表示校验位的值，且从0开始计数；
在信息位被2^ 表示以后，将都有2^ 2的信息位进行异或操作并将值赋给r2，将都有2^1的信息位进行异或操作并将值赋给r1，r0也一样操作，
&符号即为异或，在异或操作中，二者值相同即等于0，不同即等于1，而ix则是将其信息位施以一种运算：信息位所处的位置为奇数就将其赋值为1，信息位所处的位置为偶数就将其赋值为0，因此i4=1，i3=0，i2=1，i1=1；

3.海明校验码的作用：将信息转换为海明校验码形式以后，我们就能进行纠错，如信息1011，其海明校验码的正确形式为1010101，若收到了1011101，我们可以将两个数的校验码位的数提取出来，并在对应位置进行异或运算，如该例得到了001，则说明第1位’(左数第一个信息位)出错了,若得到了010，则说明第二个信息位出错了。
纠正：把错误位取反

校验码——奇偶校验码

1.概念：一个码距为1的编码系统加上一位奇偶校验码后，码距就变成了2。产生奇偶校验时将信息数据的各位进行模二加法(即异或运算，相同则和为0，相反则和为1)，直接使用这个加法的结果称为奇校验。把这个加法值取反后作为校验码的称为偶校验。从直观的角度而言，奇校验的规则是：信息数据中各位中1的个数为奇数，校验码为1，否则校验码为0，偶校验则相反

2.奇偶校验码的作用：使用一位奇偶校验码的方法可以检测出一个奇数或偶数位的错误，但无法判断是哪一位出现错误，当错误数超过一个时奇偶校验就无法检测出来，所以奇偶校验常用于对少量数据的校验，这种校验方式在通信领域被广泛采用

第十三节.输入输出系统

计算机中主机与外设间进行数据传输的输入输出的控制方法有程序控制方式、中断方式、DMA等，输入输出系统是一组固化到计算机内主板上一个ROM芯片上的程序

1.程序控制方式：由CPU执行程序控制数据的输入输出过程

2.中断方式：外设准备好输入数据或接受数据时向CPU发出中断请求信号，若CPU决定响应该请求，则暂停正在执行的任务，转而执行中断服务程序进行数据的输入输出处理，之后再回去执行原来的被中断的任务，中断时根据中断服务程序的入口地址进行中断

3.DMA(直接存储器控制)：CPU只需向DMA控制器下达指令，让DMA控制器来处理数据的传送，数据传送完毕再把信息反馈给CPU，这样就很大程度上减轻了CPU的负担

注：CPU是在一个总线周期结束时响应DMA请求的，即不是DMA一请求CPU就响应，而是CPU在接收到DMA请求后，在该系统总线周期结束后进行响应，因为DMA控制器在需要的时候会代替CPU作为总线主设备，在不受CPU干预的情况下，控制I/O设备与系统主存之间的直接数据传输

计算机网络

第一节.七层模型

计算机网络构建于七层模型之上

二进制：高电平和低电平

• 中继器：信号会随着距离的增加而逐渐衰减，而中继器则接受一端的信息再将其原封不动的发给另一端，起到延长传输距离的作用
• 集线器：就是多端口的中继器；
• 网桥：是用于连接两个同类型网络的设备，
• 交换机：则是多端口的网桥，用来将多个设备联网起来，
• 三层交换机：则是添加了路由功能的交换机；
• 局域网：只能在两层设备内进行交流，第三层的设备则不能进行交流
  

第二节.网络技术标准与协议

概念
IPX/SPX局域网游戏用的多

图注：

(1)ICMP：称之为因特网的控制协议
用ping检测网络是否通畅

(2)ARP：是地址解析协议(即IP转MC）

(3)RARP：是反向地址解析协议(MC转IP）

(4)TCP：被称为可靠的协议，因其在通信时会建立连接(通过三次握手来建立连接，即A与B三次互发信息)，且在传输信息时有验证机制，以验证数据包是否顺利传输，其上方的FTP，Telnet等协议都是建立在TCP基础上的

(5)UDP：称为不可靠的协议，因其在建立时不会建立连接，因其在传输数据时，会直接将数据发送给另一方

(6)DHCP：用来做动态的IP地址的分配工作

(7)TFTP：是小文件传输协议

(8)SNMP：是简单网络管理协议

(9)DNS：是域名解析协议

(10)位于中间部分的Samba协议、CIFS协议、NFS协议则是可基于两种基本协议

(11)TCP和UDP均提供了端口寻址能力

(12)MIML：是一个互联网标准，扩展了电子邮箱标准，使其能够支持电子邮箱的使用

(13)PGP：是一套用于信息加密、验证的应用程序，可用于加密电子邮件内容

(14)Https：是HTTP的安全版，它是在HTTP的基础上加上了SSL协议，SSL依靠证书来验证服务器的身份，并为浏览器和服务器之间的通信加密

（15）POP3 SMTP是邮件传输协议

（16）Samba（可跨平台）、CIFS、NFS是文件共享协议

常用的端口号

使用TCP协议常见端口主要有以下几种

1）FTP——文件传输协议——21

2）Telnet——远程登陆协议——23

3）SMTP——简单邮件传送协议——25

4）POP3——接收邮件——110

5）HTTP——超文本传输协议——80

使用UDP协议常见端口主要有以下几种：

1）DNS——域名解析服务——53

2）SNMP——简单网络管理协议——161

3）TFTP——简单文件传输的协议——69

TCP协议

DHCP协议

1.概念：负责动态的分配IP地址，客户机在接入网络之后，向DHCP服务器提出IP地址的分配请求，服务器会根据网络IP地址资源情况给客户机分配IP地址

DHCP服务器向客户机分配的IP地址会有租约，租约默认为八天，若客户机的地址一直未改变，DHCP服务器就会将之前的IP地址重新分配给客户机，而DHCP服务器的分配方式则有三种：固定分配，动态分配，自动分配；

较特殊的IP地址： 169.254.X.X(windows系统中分配该IP);0.0.0.0(lilux系统中分配该IP）,这两个IP地址称之为假地址，即未与DHCP服务器连接上时即会被分配这两个地址

2.windows中有关DHCP服务的命令：

ipconfig：显示信息

ipconfig/all：显示详细信息，可查看DHCP服务是否已启用以及显示它已配置且所要使用的附加信息(如IP地址等),并且显示内置于本地网卡中的物理地址

ipconfig/renew：更新所有适配器,即重新申请IP地址

ipconfig/release：释放所有匹配的连接(IP地址)，只能在向DHCP服务器租用其IP地址的计算机上起作用

DNS协议

IP地址是唯一标识计算机的方式，而一大串数字对于用户的记忆并不友好，域名的出现就是为了解决这个问题，而DNS服务器则是负责将域名转为IP地址

1.查询域名的基本方式：
(1)递归查询： 如果主机所询问的本地域名服务器不知道被查询的域名的IP地址，那么本地域名服务器就以DNS客户的身份， 向其它根域名服务器继续发出查询请求报文(即替主机继续查询)，而不是让主机自己进行下一步查询。 因此，递归查询返回的查询结果是所要查询的IP地址，或者是报错，表示无法查询到所需的IP地址。

(2)迭代查询：当根域名服务器收到本地域名服务器发出的迭代查询请求报文时，要么给出所要查询的IP地址，要么告诉本地服务器：“你下一步应当向哪一个域名服务器进行查询”。(一问一答)

然后让本地服务器进行后续的查询。根域名服务器通常是把自己知道的顶级域名服务器的IP地址告诉本地域名服务器，让本地域名服务器再向顶级域名服务器查询。

顶级域名服务器在收到本地域名服务器的查询请求后，要么给出所要查询的IP地址，要么告诉本地服务器下一步应当向哪一个权限域名服务器进行查询。

最后，知道了所要解析的IP地址或报错，然后把这个结果返回给发起查询的主机

注：(1)主机向本地域名服务器的查询一般都是采用递归查询。

(2)本地域名服务器向根域名服务器的查询采用迭代查询。

2.DNS服务器域名请求流程：

(1)客户机提出域名请求，并将该请求发送给本地的域名服务器

(2)当本地的域名服务器收到请求后，就先查询本地的缓存，如果有该记录项，则本地域名服务器就直接把查询的结果返回

(3)如果本地的缓存中没有该记录，则本地域名服务器就直接把请求发给根域名服务器，然后根域名服务器再返回给本地域名服务器一个所查询的域(根的子域)的主域名服务器的地址

(4)本地服务器再向上一步返回的域名服务器发送请求，然后接收请求的服务器查询自己的缓存，如果没有记录，则返回相关的下级的域名服务器的地址

(5)重复第四步，直到找到正确的记录

(6)本地域名服务器把返回的结果保存到缓存，以备下一次使用，同时还将返回结果到客户机

3.Hosts：是一个没有扩展名的系统文件，可以用记事本打开，其作用就是将一些常用的网址与其对应的IP地址建立一个关联“数据库”，当用户在浏览器中输入一个需要登陆的网址时，系统会首先自动从Hosts文件中寻找对应的IP地址，一旦找到，系统会立即打开对应网页，如果没有找到，系统将会把网址提交给DNS域名解析服务器进行IP地址的解析

注意：Hosts文件配置的映射是静态的，如果网络上的计算机更改了请及时更新IP地址，否则不能访问

诊断DNS故障的命令

nslookup：是一个检测网络中DNS服务器是否能正确实现域名的命令行工具

PING命令：常用于测试连通性，在此过程中可看出是直接ping的目标地址

注：nslookup、ping、tracert都可以加上一个主机域名作为其命令参数来诊断DNS故障，nslookup还可以看到本地DNS服务器地址，rp命令是与arp记录有关，与DNS无关联

常见协议的默认端口

https：443

http：80

sql数据库：8080

第三节.计算机网络的分类——拓扑结构

办公室一般是星型
星型的中心节点是交换机

第四节.网络规划与设计

概念

开放性：使用通用化的标准
先进性：保证实用性和开放性的前提，选先进的设备

网络规划与设计——逻辑网络设计

网络规划与设计——物理网络设计

网络规划与设计——分层设计

接入层：接入设备，计费

核心层：只负责高速数据的交换，且采用冗余设计，即采用几台设备处理这些数据，这样做可以提高安全性，因此对设备的性能有较高要求

自下而上设计

第五节.IP地址与子网划分

IP地址的概念及其发展

在IP地址发展的第一阶段中，IPv4地址被划分为ABC三个类别：
在A类地址中，第一个字节表示网络号，后三个字节用来表示主机号，A类地址包含2^24-2台主机，减掉的2是全零的地址和全1的地址，因为全零代表着一个网络的地址而非主机，全1则代表网络中的广播地址,且其首字节的首个位为0，包含的网络号是从0 ~ 127；

B类地址则是主机号与网络号1：1，第一、二个字节表示网络号，三、四个字节用来表示主机号，网络号的范围是128~191；主机数是2^16-2

C类地址则是网络号与主机号为1：3，第一、二、三个字节表示网络号，四个字节用来表示主机号网络号的范围是192~223；主机数是2^8-2

IP地址发展的第二阶段则是将ABC类IP地址各自再划分为数个范围，划分子网；

IP地址发展的第三阶段则是采用了无分类编址，如该表示方式：如172.18.129.0/24；”/“号后面的24表示“前24个位都是网络号

超网：多个网络汇聚成更大的网络

子网划分

1.子网掩码的概念：将一个IP地址划分为n个子网或者将n个子网合并都需要利用子网掩码，用于区分一个IP地址哪些部分是网络号，哪些部分是主机号，为1则对应网络号，为0则对应主机号

2.子网划分的步骤：首先将十进制划分为二进制数，再将网络号的二进制数全部转换为1，再取主机号的二进制数，取二进制数的数量k与子网划分的个数N满足：2^k>=N；再将取到的主机号的二进制数转换为1，最终将该转换过的IP地址二进制数化为十进制数即为子网掩码

划分27个子网，2^5>27，所以取5个bit位做子网号

2^k-2>700求出k=10

特殊含义的IP地址

图注：127网段(127.0.0.1)还可以用来测试计算机的TCP/IP协议组是否正常。

第六节.HTML与无线网

HTML主要的标签

HTML是一种标签语言，是一种网页设计语言

无线网

无线网可分为无线局域网、无线城域网、无线广域网、无线个人网；
覆盖范围：个人<局域<城域<广域;
优势:移动性、灵活性、成本低、容易扩充；
无线局域网的接入方式有两种:接入点模式、无接入点模式；
蓝牙属于无线个人网

第七节.网络接入技术

网络接入技术分为有线接入和无线接入以及3G/4G接入

PSTN：在十多年前非常流行，其上网和通话功能不能同时进行，目前基本被淘汰，但pos机和传真依旧在使用；

ISDN：解决了上网和通话不能同时进行的问题，速度达到128KB；

ADSL：是ISDN的发展，目前是主流的有线网络接入方式，上行速度达到了8MBS；用的电话线的宽带。
ADSL上网拨号有三种方式，即专线方式(静态IP)、pppoA和pppoE。

HFC：目前广泛用于电视机接入网络；光纤到户

TD—SCDMA：是国产的技术，只在中国应用，由移动公司主导推广；目前最为广泛应用的技术是WCDMA，而FDD则是其发展版本。
缺点明显，功耗大。

WCDMA：应用最广泛，做的最好。

TDD：是LTE-Advanced发展而来，是4G时代智能机的主流接入网络的方式

第八节.IPv6

IPv6是设计用于替代现行版本IP协议(IPv4)的下一代IP协议，提出的背景是IP资源不够用以及IP地址分配的不公平，因为世界上百分之70的IP地址都在美国，但目前应用并不广泛。
尚未大规模应用，因为应用层面还没有替换IPv6

IPv6相较于IPv4的优势：

系统安全分析与设计

第一节.信息系统安全属性

安全属性

保密性：最小授权原则(只给应用维持其基本职能最基本的权限)、防暴露(如在命名时可以将名称设置为乱码)、信息加密(防止信息在传输时被截获后破解)、物理保密

完整性(即保证数据在传输过程中不受损耗)：安全协议、校验码、密码校验、数字签名、公证

可用性(只允许合法用户使用这些资源)：综合保障(IP过滤、业务流控制、路由控制选择、审计跟踪)
DDOS攻击的就是可用性

不可抵赖性：数字签名

第二节.对称加密技术与非对称加密技术

是信息加密部分最为基础和核心的部分，
对称加密技术即加密和解密的时候使用相同的密钥；
非对称加密技术即加密与解密时使用不同的密钥，二者配合使用

非对称加密技术(用于简单信息传输，又称公开密钥加密)

某些时候接收方在接受信息时并不知道密钥，因此当我们把信息和密钥一起发送给接收方时，若被截获，则相当于没有加密，而非对称加密技术则能够解决这一问题
加密速度慢，效率低，所以用于对称密钥来传密钥，不适合加密大信息文件

每个人都有自己的公钥，而公钥是明文公开的，大家都知道的，而私钥则是发送方与接受方各自独有且不能被别人知道的，如甲的公钥加密的信息只能由甲的私钥来解密，甲想要把信息发送给乙则可以用乙的公钥加密后再发送给乙，乙收到后再用自己的私钥来解密；该加密方式一般采用1024位加密，因此极为庞大的信息若采用该加密方式则极难解密

对称加密技术(用于复杂信息传输，又称共享密钥加密)

替换：即将替换前后的符号对应关系绘制成为一张表，翻译时直接读表进行替换

3DES更难破解；优点：加密速度快、效率高。缺点：加密强度不高、密钥分发困难

第三节.信息摘要与数字签名

信息摘要(防止信息被篡改)

1.概念：在信息中，摘要是信息的特征值，原始信息发生变化则特征值会改变。

2.应用：在信息传输中，若A与B进行信息传输，内容被丙截获，进而篡改后再发送给乙，则会造成信息错误，因此，若A在将信息传输给乙时可以同时传输一个摘要，B收到信息后将摘要翻译出并与之比较，则能够判断信息是否被篡改。

3.算法：信息摘要采用的算法是单向散列函数(单向Hash函数),即将明文转换为摘要。而摘要不能转换为明文
常用的信息摘要算法还有MD5、SHA等，市场上广泛使用的MD5，SHA算法的散列值分别为128和160位，由于SHA通常采用的密钥长度较长，因此安全性高于MD5。

数字签名(防止抵赖)

用数字化的一种方式给发送者在摘要上签名，证明这个信息是某人发出来的。

是一种防抵赖的技术，可以解决信息摘要中不能解决的一些问题

图注：私钥在非对称技术中用来解密，在数字签名中则用来签名，B在收到A的信息后用A的公钥解密即验证，则信息发自A是不可抵赖的

第四节.数字信封与PGP

数字信封

概念：发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方，接收方收到电子信封后，用自己的私钥解密信封，取出对称私钥解密得原文

PGP协议

1.概念：可以用于电子邮件加密，也可以以用于文件存储加密，采用了杂合算法，包括IDEA、RSA、MD5、ZIP数据压缩算法

2.特性：PGP承认两种不同的证书格式：PGP证书和X.509证书；PGP证书包含PGP版本号、证书持有者的公钥、证书持有者的信息、证书拥有者的数字签名、证书的有效期、密钥首选的对称加密算法。

3.X.509证书：包含证书版本、证书的序列号、签名算法标识、证书有效期、以下数据：证书发行商的名称、证书主体名、主体公钥信息、发布者的数字签名。

用户可以通过使用CA的公钥验证CA的签名的真伪来确定一个网站的合法性

第1~4节练习题

要求邮件以加密方法传输，邮件最大附件内容可达500MB，发送者不可抵赖，若邮件被第三方截获，第三方无法篡改

答：发送方A(公钥：Ea，私钥：Da) 接收方B(公钥：Eb，私钥：Db)

(1)A用随机密钥将明文加密(对称加密技术)
500MB即对大数据文件传送，所以选择对称加密

(2)A再用B的公钥Eb将随机密钥加密

(3)A用自己的私钥将明文的摘要签名
第三方无法篡改：使用信息摘要
无法抵赖：用数字签名

(4)A将被签名的摘要与加密后的信息传输给B

(5)B用B的私钥将A的随机密钥解密出来，并使用随机密钥读取正文

(6)B将正文提取摘要并用A的公钥解密A的摘要(若成功解密，则A发送该信息不可抵赖),然后将两个摘要进行对比，若相同，则证明整个过程中信息未被篡改

第五节.各个网络层次的安全保障

为了解决互联网协议随着信息技术的发展凸显出的安全问题

从第二层开始实行协议保障安全，IPSec是对IP包进行加密的协议

SSH：是建立在应用层基础上的安全协议，SSH是目前较为可靠，专为远程登录会话和其他网络服务提供安全性的协议。利用SSH协议可以有效防止远程管理过程中的信息泄露问题

SSL：SSL是为网络通信提供安全及数据完整性的一种安全协议，在传输层对网络连接进行加密，目前被广泛地用于Web浏览器与服务器之间的身份认证和加密数据传输。

第六节.网络安全——网络威胁与攻击及防火墙技术

网络攻击的分类

网络攻击可以分为主动攻击和被动攻击两种

1.主动攻击：包含攻击者访问他所需信息的故意行为。比如通过远程登陆到特定机器的邮件端口以找出企业邮件服务器的信息；伪造无效IP地址去连接服务器，使接受到错误IP地址的系统浪费时间去连接哪个非法地址。攻击者是在主动地做一些不利于你或你的公司系统的事情，主动攻击包括：拒绝服务攻击、分布式拒绝服务、信息篡改、资源使用、欺骗、伪装、重放等攻击方式

2.被动攻击：主要是收集信息而不是进行访问，数据的合法用户对这种活动一点也察觉不到。被动攻击包括嗅探、信息收集等攻击方式

常见的网络威胁

DOS攻击主要破坏了系统的可用性，使系统无法合法的使用相应的资源；
业务流分析和窃听的区别在于业务流分析侧重长期监听、信息的分析，而窃听则只是获取信息

kerberros系统通常在报文中加入时间戳来防止ARP攻击

防火墙技术

防火墙技术大体可分为网络级和应用级的防火墙技术
防火墙特点：防外不防内
网络级的防火墙层次较低，但效率比较高，主要做法是拒绝接受指定IP段的信息，不管其内容；
应用级防火墙则是层次较高，效率较低，主要做法是：不论信息的来源而直接将信息开箱进行检查，若有问题则拒绝接收；
被屏蔽子网(DMZ)则是一块既不属于内网也不属于外网的隔离区，其目的是为了防止防火墙内部的攻击，存放对外提供服务的服务器比如web服务器，安全性最高

· 防火墙最重要的特性就是利用设置的条件，监测通过的包的特征来决定放行或者阻止数据，同时防火墙一般架设在提供某些服务的服务器前，具备网关的能力，用户对服务器或内部网络的访问请求与反馈都需要经过防火墙的转发，相对于外部用户而言防火墙隐藏了内部网络结构。防火墙作为一种网络安全设备，安装有网络操作系统，可以对流经防火墙的流量信息进行详细的日志和审计

补充：入侵检测技术

包括：专家系统、模型检测、简单匹配

多媒体技术

音频

音频相关概念：

音乐合成方式：

• FM调频音乐合成： 使高频的振荡波的频率按调制信号的规律变化的一种调制方式。采用不同调制波频率和调制指数就可以方便地合成具有不同频谱分布的波形，再现某些乐器的音色。
• WaveTable波形表音乐合成： 将各种真实乐器所能发出的声音（包括音域、音调）录制下来，存储为一个波表文件，播放时，根据MIDI文件记录的乐曲信息向波表发送指令，表格中的信息经过合成，加工后，会放出来。波形表音乐合成技术合成的音乐更真实。

声音信号数字化首先需要进行A/D转换（模数转换）。

音色： 声音的感觉特性，不同的人声和不同的音响都能区分为不同的音色，既音频泛音或谐波成分。
音调： 表示人得听觉分辨个声音得调子高低程度，主要有声音频率决定，同时业余声音强度有关。
音高： 各种不同高低的声音，是声的基本特征的一种。（音乐合成器的信号幅度可以改变音高）
音质： 声音在音响技术中提现，包含音调、音高和音色。

数字语音的采样频率为8kHz，因为语音信号定义的频率最高值为4kHz，而采样频率应该为声音最高频率得二倍。

图像与媒体

图像相关概念：

亮度： 照射在景物或图像上光线的明暗程度。图像亮度增加时，就会显得耀眼或刺眼，亮度越小时，图像就会显得灰暗。
色调： 色调是各种图像色彩模式下原色的明暗程度，级别范围从0到255，共256级色调。在RGB模式中，色调代表红、绿、蓝三种原色的明暗程度，对绿色就有淡绿、浅绿、深绿等不同的色调。
饱和度： 颜色的纯度、颜色的深浅或者掺入白光的程度，饱和度越深，颜色越纯。

相关软件：
Photoshop：图像编辑工具
Premiere：视频编辑软件
Acrobat：PDF编辑软件
Powerpoint：演示文稿软件
WPS：文本工具类软件
Xara3D：动画工具类软件
CoolEdit：音频工具类软件

媒体的种类：

感觉媒体：视觉（图像）、听觉（声音）、触觉
表示媒体：文字、图像、动画、音频、视频等编码；
表现媒体：键盘、鼠标、话筒、显示器、打印机、喇叭
存储媒体：硬盘、光盘
传输媒体：电缆、光纤、电磁波

多媒体的计算问题：

例题：
1、24bit/8bit=3B

DPI： 像素/英寸，图像分辨率的单位，表示每英寸多少像素点，即组成一幅图的像素密度。

显示分辨率： 显示器上能够显示出的像素点数目，即显示器在横向和纵向上能够显示出的像素点数目。
水平分辨率：显示器水平方向上能够显示的像素点数目。
垂直分辨率：显示器在垂直方向上显示的像素数目。

矢量图是常用的图形表示形式，图元是描述矢量图的基本单位。
视频信息是连续的图像序列，帧是构成视频信息的基本单元。

常见多媒体标准：

数据压缩

数据压缩基础技术：

有损压缩与无损压缩：

计算机软件法律法规

考点： 保护期限、知识产权人确定、侵权判断(重点)

保护期限

免费表演他人作品，他人作品必须是已经公开演出过的

知识产权人的确定

侵权判定

发表：指公之于众，不一定在报刊上发表

标准的分类与标准的代号

标准的分类
GB国标

标准的编号

---

下午题：

数据流图

UML

用例图

包含关系：登记外借信息必须先用户登录，必须
扩展关系：修改书籍信息是查询书籍信息的扩展功能，可以不修改，非必须
泛化关系：

类图和对象图

多重度

0…* 和 * 等价

一般考察泛化

顺序图

考察消息
填对象名

活动图

状态图

以状态为节点
框表示事件

通信图/协作图

案例

歌手和乐队的关系是
1个歌手对应0或多个乐队，所以乐队那边是0…*
1个乐队对应2或多个歌手，所以歌手那边是2…*

歌曲和音轨的关系
1个歌曲对应1个或多个音轨，所以音轨是1…*
1个音轨对应0或1个歌曲，所以歌曲是0…1

3.音轨到音轨，多重度都是0…1

ER图

程序设计c++/java

类和派生类

指针

构造函数

虚函数 关键字virtual

接口
虚类

数据结构和算法

分治法

递归

二分

回溯法

一步步往下走到底，不通则返回上一步

贪心法

快速得到解，但不是最优解
如果每一步是取最优，则是最优解
背包问题

动态规划

通常用查表的方式，会存放之前求解的结果