备战2020年中级软件设计师，整理了近10年上午选择题部分的真题的解析，将所包含的知识点进行了加工和整合，最终浓缩成了这份笔记，便于自己以后需要时再翻阅。这份笔记整理了有一个月时间，都是自己在刷题时顺带记录的，经过了多次排版和修改。因为软考内容比较多、杂，但是考得都不深，自己也比较懒，没有系统的跟着视频或书籍学习，所以对某些知识的理解不透彻。记录的不全面、存在漏记和少计，一些错误也在所难免，希望大家谅解并可以帮我指正

计算机系统知识
程序设计语言基础
操作系统
系统开发和运行
网络基础知识
多媒体
数据库技术
数据结构
常用算法设计方法
面向对象技术
标准化和软件知识产权基础知识

---

计算机系统知识

• 计算机系统基础知识
• 计算机体系结构
• 安全性、可靠性与系统评测基础

---

1、硬件

（1）CPU组成：运算器、控制器、寄存器组和内部总线

（2）控制器组成：程序计数器、指令寄存器、指令译码器、时序产生器、操作控制器

（3）处理机组成：处理器、存储器、总线

（4）总线的分类

• 数据总线(DB) ：宽度会影响系统的运算速度
• 地址总线(AB)
• 控制总线(CB)

总线标准：ISA总线、EISA总线、PCI总线

通过总线复用方式可以减少总线中信号线的数量，以较少的信号线传输更多的信息

总线结构的优点：

• 简化系统结构，便于系统设计制造
• 减少连接线数目，便于布线，减小体积，提高系统可靠性
• 便于接口设计，与总线连接的设备采用类似接口
• 便于系统扩充，更新与灵活配置，实现系统模块化
• 便于设备的软件设计
• 便于故障诊断和维修，降低成本

（5）BIOS(基本输入输出系统)：一组固化到计算机内主板上一个ROM芯片上的程序，保存基本的输入输出程序、开机后自检程序和系统自启动程序

（6）指令系统采用不同寻址方式来扩大寻址空间并提高编程灵活性

（7）CISC(复杂指令集计算机)：进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬件化，导致机器的指令系统越来越庞大而复杂

（8）RISC(精简指令集计算机)：减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周期执行，并通过优化编译提高指令的执行速度，采用硬布线控制逻辑优化编译程序

（9）寻址方式：寻找操作数或操作数地址的方式，具体有

• 立即寻址：操作数就包含在指令中
• 直接寻址：操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址
• 寄存器寻址：操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名
• 寄存器间接寻址：操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中
• 间接寻址：指令中给出操作数地址的地址
• 相对寻址：指令地址码给出的是一个偏移量，操作数地址等于本条指令的地址加上该偏移量
• 变址寻址：操作数地址等于变址寄存器的内容加偏移量

（10）SCSI是一种用于计算机和智能设备之间系统级接口的独立处理器标准

2、存储器

（1）存储器的分类

• 按位置：内存、外存
• 按材料：磁存储器、半导体存储器、光存储器
• 按工作方式：读写存储器、只读存储器
• 按访问方式：按地址访问存储器、按内容访问存储器
• 按寻址方式：随机存储器、顺序存储器、直接存储器
• 按内容：相联存储器

（2）RAM(随机存储器)：存储短时间使用的程序

（3）ROM(只读存储器)：只能读出事先所存数据的固态半导体存储器

（4）高速缓冲存储器(Cache)：位于CPU和主存之间，由硬件实现，是一个高速小容量的临时存储器，与外存和主存容量无关，设计思想是在合理成本下提高命中率。由两部组成:

• 控制部分：判断CPU要访问的信息是否在Cache存储器中，在即为命中，不在则没有命中
• Cache存储器部分：存放主存的部分拷贝

PS：设置多级高速缓存cache可以提高cpu访问主存数据或指令的效率

（5）主存采用动态随机存储器(DRAM)、Cache采用静态随机存储器(SRAM)、带电可擦除可编程只存储器(EEPROM)

（6）虚拟存储器由主存-辅存两级存储器组成

3、I/O

（1）常用I/O控制方式

• 无条件传送方式
• 中断方式：执行现行程序时，出现某些异常情况和特殊请求，CPU暂时停止现行程序，转去对随机发生的更紧迫的事件进行处理，处理完后，CPU将自动返回原来的程序继续执行。CPU与外设可并行工作
  1、中断处理保存现场的目的：能正确返回到被中断的程序继续执行
  2、中断按照是否可以被屏蔽分为两大类：不可屏蔽中断(非屏蔽中断)，如电源掉电；可屏蔽中断：打印机中断
• 程序查询方式：主机进行I/O操作时，首先发出询问信号，读取设备状态并决定下一步是进行数据传输还是等待，CPU一旦启动I/O，必须停止现行程序的运行，并在现行程序中插入一段程序。CPU有踏步等待现象，CPU与I/O串行工作
• DMA(直接内存存取)方式：在主存与I/O设备间(主存与外设)直接成块传送，无需CPU执行程序指令来传送数据，传送速度最快。CPU与外设可并行工作
• 直接存储器存取：CPU只需在开始和结束时作少量处理，而无需干预数据传送过程

（2）I/O软件隐藏了I/O操作实现的细节，方便用户使用I/O设备

（3）I/O接口编址方式

• 与内存单元统一编址
• 单独编址

4、寄存器

（1）寄存器是CPU内部临时存储单元，可分为

• 程序(指令)计数器(PC)：存放待执行指令的地址，具有寄存信息和计数两种功能
• 通用寄存器：暂存运算器需要的数据或运算结果
• 累加寄存器：暂存算术逻辑运算部件ALU运算的结果信息
• 指令寄存器(IR)：暂存正在执行的指令。操作码和地址码都应存入其中。因为透明，看不见，程序员无法访问
• 地址寄存器(AR)：暂存访问时的的地址
• 程序状态寄存器：记录运算中产生的标志信息
• 数据寄存器：数据暂存
• 指令译码器(ID)：对现行指令进行分析、确定指令类型和指令所要完成的操作以及寻址方式，并将相应的控制命令发往相关部件

5、流水线技术

（1）流水线各段执行时间最长的那段时间称为流水线瓶颈，作为流水线的周期

• 吞吐率：单位时间里流水线处理机流出的结果数
• 建立时间：流水线工作，经过一定时间达到最大吞吐率的过程

（2）流水线的特点

• 可同时执行多条指令
• 提高了各部件的利用率
• 提高了系统的吞吐率

6、各种码

（1）补码和移码+0和-0编码相同

（2）使用补码来表示和运算数据可以简化计算机运行部件的设计

（3）n位补码表示的范围是-2^（n-1） — 2^(n - 1) - 1

（4）浮点数由三部分组成：

• 符号位S
• 指数E(阶码)：长度决定浮点表示的范围
• 尾数M：长度决定浮点表示的精度

（5）工业标准IEEE754浮点数格式中阶码采用移码、尾数采用原码表示

（6）两个浮点数进行相加运算，首先需要统一这两个数的阶码，然后再进行尾数的相加处理

（7）码距

• 两个码字的码距：编码系统中任意两个合法编码(码字)之间的二进数位
• 编码系统的码距：编码系统中任意两个码字的最小距离

（8）检验码

• 奇偶检验码：在编码中增加一位检验位来使编码中1的个数为奇数或为偶数，使码距变为2。它只能检测奇数位出错编码，不能发现偶数位出错情况，并且只具备检错功能
• 海明码：利用多组数位的奇偶性来检错和纠错，在n个数据位之外增设k个检验位，形成一个k+n的新的码字，码距最小为2n+1。n与k的关系是2^k-1>= n + k
• 循环冗余检验码：在k位信息码后拼接r位检验码，形成长度为n位的编码。检错能力极强且开销小，采用模二除法运算

7、一些计算及计算公式

（1）硬盘容量计算

• 非格式化容量=面数x(磁道数/面)x内圆周长x最大位密度
• 格式化容量=面数x(磁道数/面)x(扇区数/道)x(字节数/扇区)

（2）可靠性计算

• 串联系统可靠性公式：R=R1xR2x…xRn
• 并联系统可靠性公式：R=1-(1-R1)x(1-R2)x…x(1-Rn)

（3） 流水线计算公式

• 理论公式：(取址+分析+执行) +(指令条数-1) x 流水线周期
• 实践公式：(k+n-1) x 流水线周期 （k:指令分的段数，n:指令条数）

（4）原码、反码、补码、移码之间的计算公式

• 正数：原码=反码=补码
• 负数：反码=原码绝对值取反 、补码=反码+1
• 补码-1得到反码，再按位取反得原码
• 移码=补码符号位取反

（5）其他计算

• 串行计算：在单个计算机上顺序地执行指令
• 并行计算：分为时间和空间两种，时间上地并行指流水线技术，空间上地并行指用多个处理器并发地执行计算

8、磁盘

（1）磁盘格式化：把一张空白的盘划分成一个个小区域并编号，供计算机储存和读取数据

（2）格式化：在磁盘的所有数据区上写零的操作过程

（3）磁盘分区：将磁盘划分成一块块的存储区域。分为两大分区

• 主分区：能够安装操作系统、进行计算机启动的分区，可直接格式化，然后安装系统，直接存放文件
• 扩展分区：

（4）磁盘碎片：空着的磁盘空间

（5）磁盘清理：将删除计算机上所有不需要的文件

（6）磁盘碎片整理：对磁盘产生的碎片和凌乱的文件重新整理，释放更多磁盘空间，提高电脑整体性能和运行速度

9、其他

（1）计算机内存空间划分(自上而下)

• 可执行代码
• 静态数据区
• 栈
• 堆

（2）衡量计算机系统性能的重要指标

• 系统响应时间：用户发出完整请求到系统完成任务给出响应的时间间隔
• 作业吞吐量：单位时间内系统完成的任务量
  响应时间越短，作业吞吐量越大

（3）冗余：对于实现系统规定功能是多余的那部分资源，包括硬件、软件、信息和时间。冗余技术分类

• 结构冗余：按其工作方式分为静态、动态和混合冗余
• 信息冗余：为检测或纠正信息在运算或传输中的错误另外加的一部分信息
• 时间冗余：以重复执行指令或程序来消除瞬时错误带来的影响
• 冗余附加技术：为实现上述冗余技术所需的资源和技术

（4）程序的局限性

• 时间局限性：如果程序中的某条指令一旦被执行，则不久的将来该指令可能再次被执行
• 空间局限性：一旦程序访问了某个存储单元，在不久的将来，其附近的存储单元也有可能被访问

---

程序设计语言基础

• 程序设计基础知识
• 语言处理程序基础

---

1、常见的命名对象

• 变量：内存单元的抽象，用于在程序中表示数据
  指针变量：变量存储的是内存单元地址。可以定义为全局变量，也可以是局部变量
• 函数
• 数据类型

2、编译

（1）编译过程

• 词法分析：将源程序的字符串转换成单词符号序列，进行扫描和分解，识别出一个单词，删掉无用信息，报告分析时的错误**(记号流)**
• 语法分析：以单词符号作为输入，分析单词符号是否形成符合语法规则的语法单位。如程序、表达式、赋值、循环等，按语法规则分析检查每条语句是否有正确的逻辑结构
• 语义分析：检查源程序是否包含语义错误，并收集类型信息供后面代码生成阶段使用。如赋值语句左右端类型不匹配、表达式除数是否为0等
• 目标代码生成：语法和语义都正确地源程序才能生成

（2）反编译：编译的逆过程。不能把可执行文件还原成高级语言源代码，只能转换成功能上等价的汇编程序

（3）编译过程中为变量分配存储单元所用的地址是逻辑地址，程序运行时再映射为物理地址

3、各种语言

（1）动态语言：程序在运行时可以改变其结构。脚本语言都是动态语言，而动态语言都是解释性语言

动态绑定：运行时把过程调用和响应调用所需要执行的代码加以结合
静态绑定：编译时代码结合

（2）汇编语言源程序中的每一条指令语句再源程序汇编时都要产生可供计算机执行的指令代码(目标代码)

（3）伪指令语句用于指示汇编程序如何汇编源程序

标记语言

（4）HTML(超文本标记语言)：用于互联网的信息表示。基本标签有

• alink：设置正在被击中的链接的颜色
• align：用于定义文本的对其方式
• vlink：设置已使用的链接的颜色
• background：设置背景图片的URL
• bgcolor：设置文档整体背景颜色
• tr：定义表格中的一行
• col：定义表格中一个或多个列的属性值
• td：定义表格中的一个单元格
• title：定义文档标题
• table：定义属性

（5） XML(可扩展的标记语言)：丰富了HTML的描述功能。其文档语法规范为

• 文档的第一行必须是XML文档声明
• 文档必须包含

（6）WML(用于WAP的标记语言)：XML的子集

脚本语言

（7）PHP：在服务器端执行的、嵌入HTML文档的脚本语言

可视化程序：

（1）可视化程序设计：以所见即所得的编程思想为原则，力图实现编程工作的可视化，即随时看到结果，程序与结果的调整同步

（2）可视化程序特点：

• 基于面向对象的思想
• 程序开发过程一般遵循一下步骤：先进行界面的绘制工作，再基于事件编写程序代码，以响应鼠标、键盘的各种动作

4、其他

（1）基本数据类型转换(隐式转换)从低精度到高精度

（2）闭包运算符 * 将其运算对象进行若干次连接，如0 * 表示若干个0构成的串，(10 * 1) * 表示偶数个1构成的串

（3）符号表：记录源程序中各个符号(变量等)的必要信息，以辅助语义的正确性检查和代码生成

（4）程序中的数据都必须具有类型，便于为数据合理分配存储单元、对参与表达式计算的数据对象进行检查、规定数据对象的取值范围及能够进行的运算

（5）中间代码：在高级语言源程序翻译为机器语言程序过程中被引入。有利于进行与机器无关的优化处理，提高编译程序的可移植性。表现形式有

• 逆波兰式(后缀表达式)：将运算符写在操作数之后的表达式表示方法
• 四元式
• 三元式

（6）数据空间采用堆存储分配策略

（7）函数调用的基本参数传递方式

• 传值：将实参的值传递给形参，实参可以是表达式、变量、常量、数组元素等，传递是单方向，形参不能再传回给实参
• 传地址：将实参的地址传递给形参，实参必须是变量，不能是表达式或常量，传递是双向的

---

操作系统

• 操作系统基础知识
• 处理机管理
• 存储管理
• 设备管理
• 文件管理
• 作业管理
• 网络操作系统和嵌入式操作系统
• UNIX操作系统实例

---

1、操作系统

（1）计算机系统结构(自上而下)

• 应用软件(最终用户)
• 系统软件(应用软件开发人员)
• 操作系统(系统软件开发人员)
• 计算机硬件(系统软件开发人员)

（2）裸机：未配置软件的计算机

（3）操作系统：建立用户与计算机之间的接口而未裸机配置的一种系统软件

（4）嵌入式操作系统的特点

• 微型化
• 可定制
• 实时性
• 可靠性
• 易移植性

（5）xp系统中，用户可以利用磁盘管理程序对磁盘进行初始化、创建卷、可以选择使用FAT、FAT32或NTFS文件系统格式卷

2、PV操作及死锁

（1）系统中有m个单位的存储器资源被n个进程使用，当每个进程都要求w个单位的存储器资源，当m<nw时，可能会引起死锁

（2）资源R，进程n，死锁不发生的资源最少量为：n(R - 1)+1

（3）PV操作：p操作检查上一个进程是否完成，V操作通知下一个进程本进程已经执行完

（4）进入临界区执行P操作，退出临界区执行V操作

（5）信号量S<0，其绝对值表示等待该资源的进程数

3、磁盘

（1）系统将目录文件修改的结果写回磁盘时系统发生崩溃，则对系统影响相对较大

（2）在移臂调度算法中，先来先服务和最短寻找时间优先算法可能会随时改变移动臂的运动方向

（3）在磁盘调度算法中，先进行移臂调度寻找磁道，再进行旋转调度寻找扇区

（4）地址计算

• 逻辑地址=页号+页内地址
• 物理地址=物理块号+物理地址的页内地址

（5）索引

• 直接索引：索引直接指向物理块，可表示逻辑块号范围：0~4号
• 一级索引：索引节点指向的物理块用来存放地址项，可表示逻辑块号范围：5~260， 261~516号
• 二级索引：索引节点指向的物理块，存放一级索引，可表示逻辑块号范围：517~66052号

3、其他

（1）Spooling技术：用一类物理设备模拟另一类物理设备的技术，是使独占使用的设备变成多台虚拟设备的一种技术，也是一种速度匹配技术

（2）文件级安全管理可设置的属性

• 只执行：只允许用户执行该文件，主要针对.exe和.com文件
• 隐含：指示该文件为隐含属性文件
• 索引：指示该文件是索引文件
• 修改：指示该文件自上次备份后是否还被修改
• 只读：只允许用户读该文件
• 读/写：允许用户对文件进行读和写
• 共享：指示该文件是可读共享文件
• 系统：指示该文件是系统文件

（3）共享锁和排他锁
若事务T1对数据D1加上共享锁，则其他事务只能再对D1加共享锁，而不能加排他锁
若事务T2、T3对数据D2、D3加上排他锁，其他事务不能再对D2、D3加任何锁

（4）SCAN(扫描)调度算法：柱面从小到大，达到最大后再从大到小

（5）CSCAN(单向扫描)调度算法：柱面从小到大，达到最大后再从最小到大

（6）

---

系统开发和运行

• 软件工程基础
• 系统分析基础
• 系统设计基础
• 系统实施
• 系统运行和维护

---

1、软件分析

（1）结构化分析中，使用数据流图来建立系统的逻辑模型，从而完成分析工作，应遵循自顶向下、从抽象到具体的原则

（2）结构化分析组成

• 数据流图：从数据传递和加工的角度，以图形的方式刻画数据流从输入到输出的移动变化过程，基础是功能分解。包含数据流、加工、数据存储和外部实体(人/物、外部系统、组织机构)
• 加工逻辑：
• 数据字典：条目有数据流、数据项、数据存储、基本加工

（3）需求分析阶段就要开始写测试设计文档

2、软件设计

（1）软件设计特点：高内聚、低耦合。

（2）系统设计的主要目的是为系统定制蓝图

（3）软件设计模型关注新系统的总体结构、代码设计、处理过程、数据结构和界面模型等

（4）结构化设计模块划分原则
一个模块的作用范围应该在其控制范围之内

• 模块的大小要适中
• 模块的扇入和扇出要合理
• 深度和宽度适当

3、软件测试

（1）软件测试技术：

• 单元测试(模块测试)：消除程序模块内部存在的错误和缺陷，在代码编写阶段完成。5个特征：模块接口、局部数据结构、重要的执行路径、出错处理和边界条件
• 集成测试(组装测试)：检测和排除子系统结构上的错误和缺陷
• 系统测试：通过与系统需求对比，发现系统与用户需求不符或矛盾的地方
• 功能测试：检查软件是否能实现需求种指定的功能
• 性能测试：测试软件的安全性、精确性、速度和可靠性
• 回归测试：用于识别在改正当前故障的同时可能引入的新故障
• 验收测试：客户对系统进行测试以验证软件系统是否符合他们对需求的理解

（2）两种测试

• 静态测试：被测试程序不在机器上运行而采用人工检测和计算机辅助静态分析手段对程序进行检测
• 动态测试：通过运行程序发现错误

（3）动态测试具体

• 黑盒测试：完全不考虑软件的内部结构和特性的情况下，测试软件的外部特性
• 白盒测试(结构测试)：根据程序的内部结构和逻辑来设计测试用例，对程序的执行路径和过程进行测试，检查是否满足设计的需要。

（4）白盒测试的几种方法(从弱到强)

• 语句覆盖：程序中每条语句至少执行一次。很弱的逻辑覆盖
• 判定覆盖(分支覆盖)：程序中每个判定表达式至少获得一次真值和假值
• 条件覆盖：每一个判定语句中每各逻辑条件的各种可能的值至少满足一次
• 路径覆盖：覆盖被测程序中所有可能的路径

（5）黑盒测试的几种方法

• 等价类划分
• 边界值分析
• 错误猜测
• 因果图的报告

4、软件开发

（1）基于构件的软件开发
主要强调在构建软件系统时复用已有的软件“构件”，在检索到可以使用的构件后，需要针对新系统的需求对构件进行合格性检验、适应性修改，然后集成到新系统

（2）、系统开发计划用于系统开发人员与项目管理人员在项目期内进行沟通，包括任务分解表、PERT图、甘特图和预算分配表

（3）软件项目计划安排进度的方法

• Gantt图：用水平条状图描述，可清楚表示任务持续时间和任务之间的并行，但不能清晰地获得各任务之间的依赖关系

• PERT图：是一种网络模型，描述一个项目地各任务之间的关系，可清楚表示任务持续时间和任务之间的依赖，但不能清晰地描述各个任务之间地并行

（4）软件项目开发关键路径：时间最长和路过节点数最长的路径

（5）进度管理-单代号网络图：结点表示里程碑，边表示活动，边上可标注各活动最早开始时间、活动持续时间、最早完成时间

（6）敏捷开发法scrum的步骤

• Product Basklog：产品待办事项清单
• Sprint Backlog：代办事项清单
• Spring：冲刺迭代

（7）在对软件开发资源进行规划时，为确定构建软件系统所需的人数，需要考虑软件系统的规模、系统的技术复杂性、项目计划和开发人员的技术背景

（8）极限编程(XP)：一种轻量级(敏捷)、高效、低风险、柔性、可预测的、科学的软件开发方式

• 4个价值观：沟通、价值、反馈、勇气
• 5个原则：快速反馈、简单性假设、逐步修改、提倡更改、优质工作
• 12个最佳实践：计划游戏、小型发布、隐喻、简单设计、测试先行、重构、结队编程、集体代码所有制、持续集成、每周工作40个小时、现场客户、编码标准

（9）RUP的4种模型元素

• 角色----谁做
• 活动----怎么做
• 制品----做什么
• 工作流----什么时候做

（10）RUP4个阶段的目标

• 初启阶段：产生构想文件、用例模型的调查、初始业务用例、早期风险评估、项目计划等，结束里程碑是生命周期目标
• 精化阶段：产生补充需求分析、软件架构描述、可执行架构原型等，结束里程碑是生命周期架构
• 构建阶段：产生准备交到最终用户手中的产品，结束里程碑是最初运作能力
• 移交阶段：移交给用户产品发布版本，结束里程碑是产品发布

（11）软件开发过程

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

（12）水晶法(Crystal)：认为每一种不同的项目都需要一套不同侧策略、约定和方法论

5、软件风险

（1）风险预测从风险发生的可能性大小以及风险发生所产生的后果是否严重两个方面评估风险

（2）软件风险包括不确定性和损失两个特性，救火和危机管理是对不适合但经常采用的软件风险管理策略。已知风险和未知风险是对软件风险进行分类的一种方式。员工和预算是在识别项目风险时需要识别的因素

（3）风险分析

• 风险识别：系统化地确定对项目计划地威胁，建立风险条目检查表
• 风险预测(估算)：描述风险发生的可能性或概率，以及如果风险发生时所产生的后果
• 风险评估：根据风险及其发生的概率和产生的影响预测是否影响参考水平值，如定义风险参照水准
• 风险控制：利用技术和方法设法避开或移除风险

（4）风险控制策略

• 风险避免(最好)
• 风险监控
• 风险管理及意外事件计划

6、软件模型

（1）软件能力成熟度模型(CMM)(成熟度由低到高)

• 初始级(1级)：没有健全的软件工程管理制度
• 可重复级(2级)：建立基本的项目管理和实践来跟踪项目费用、进度和功能特性
• 定义级(3级)：使用标准开发过程构建系统
• 管理级(4级)：寻求更主动地应对系统地开发问题
• 优化级(5级)：连续地监督和改进标准化地系统开发过程

（2）能力成熟度集成模型(CMMI)(CMM模型的最新版本)

• 未完成级(0级)：未执行过程
• 已执行级(1级)：过程通过转化可识别的输入工作产品，产生可识别的输出工作产品，关注于过程域的特定目标的完成
• 已管理级(2级)：过程作为已管理的过程制度化，针对单个过程实例的能力
• 已定义级(3级)：过程作为已定义的过程制度化，关注过程的组织级标准化和部署
• 量化管理级(4级)：过程作为定量管理的过程制度化
• 优化级(5级)：过程作为优化过程制度化，表明过程得到很好地执行且持续得到改进

（3）软件过程模型：

• 瀑布模型：适用于软件需求很明确的软件项目的模型
• V模型：瀑布模型的变种，它说明测试活动是如何与分析和设计相联系的
• 原型模型：快速构造软件的原型，在此基础上开发最终软件产品
• 演化模型：获取一组基本**需求(不明确)**后，通过快速分析构造出该软件的一个初始可运行版本，然后逐步演化成最终软件产品
• 螺旋模型：把开发活动和风险管理结合起来，以将风险减到最小并控制风险，适合大型昂贵系统级的软件应用
• 喷泉模型：典型面向对象生命周期模型，以用户需求为动力，以对象作为驱动，具有迭代和无间隙特性
• 增量模型：能够快速构造可运行产品的方法

7、软件维护

（1）软件维护方式

• 正确性维护：改正在系统开发阶段已发生而系统测试阶段尚未发现的错误
• 适应性维护：使应用软件适应信息技术变化和管理需求变化而进行的修改
• 完善性维护：为扩充功能和改善性能而进行的修改
• 预防性维护：为改进应用软件的可靠性和可维护性，为适应未来变化的软硬件的变化，主动增加预防性的新功能

8、软件评判

（1）软件可靠性：一个系统对于给定的时间间隔内，在给定条件下无失效运作的概率，与软件的潜在错误的数量、位置有关，与软件的使用方式有关

（2）MVC(模型-视图-控制器)体系结构有利于代码重用、提高系统的开发效率和系统的可维护性

（3）ISO/IEC9126软件质量模型
质量特性及其子特性

• 功能性(适合性、准确性、互操作性、安全保密性)
• 可靠性(成熟性、容错性、易恢复性)
• 易使用性(易理解性、易学性、易操作性、吸引性)
• 效率(时间特性、资源利用性)
• 可维护性(易分析性、易改变性、稳定性、易测试性)
• 可移植性(适应性、易安装性、共存性、易替换性)

（4）软件复审

• 系统设计阶段的复审：强调容易修改、模块化和功能独立的目的
• 系统实施阶段的复审：强调编码风格和内部说明文档

（5）系统可维护性指标

• 可理解性
• 可测试性
• 可修改性

（6）功能性需求：软件必须完成哪些事，必须实现哪些功能

（7）软件复杂性度量

• 规模：指令数或者源程序行数
• 难度：由程序中出现的操作数所决定的量来表示
• 结构：用与程序结构有关的度量来表示
• 智能度：算法的难易程度

（8）软件设计质量评审

• 设计质量：设计的规格说明书符合用户的要求
• 程序质量：程序按照设计规格说明所规定的情况正确执行

（9）信息系统评价对象，用户关心的是用户需求和运行质量，开发方关心的是系统质量和技术水平

9、软件文档

（1）软件文档

• 开发文档
• 管理文档
• 用户文档

（2）高质量文档的几个特性：

• 针对性
• 精确性
• 清晰性
• 完整性
• 灵活性
• 可追溯性

10、耦合与内聚

（1）模块独立性包括两个度量准则：

• 耦合：模块之间连接越紧密，联系越多，耦合性就越高，而且模块独立性越弱
• 内聚：

（2）如若模块多也可能高耦合，改一个小模块可能影响整个系统导致灾难性错误

（3）7种耦合(以耦合性从低到高排序)：

• 非直接耦合：
• 数据耦合：模块间通过数据参数来交换输入、输出信息
• 标记耦合：一组模块通过数据结构本身传递
• 控制耦合：一个模块通过传送开关、标志、名字等控制信息，明显地控制选择另一模块地功能
• 外部耦合：一组模块都访问同一全局简单变量而不是同一全局数据结构，而且不是通过参数表传递该全局变量的信息
• 公共耦合：一组模块都访问同一个公共数据环境
• 内容耦合：一个模块直接访问另一个模块内部数据、一个模块不通过正常入口转到另一个模块内部、两个模块有一部分程序代码重叠或者一个模块有多个入口

（4）内聚(强度从低到高)

• 偶然内聚：一个模块各成分之间没任何联系
• 逻辑内聚：几个逻辑上相似的功能被放在同一模块中
• 时间内聚：把需要同时执行的动作组合在一起形成的模块
• 通信内聚：模块内所有处理元素都在同一个数据结构上操作，或指各处理使用相同的输入数据会产生相同的输出数据
• 顺序内聚：一个模块的各个成分和同一个功能密切相关，而且一个成分的输出作为另一个成分的输入
• 过程内聚：一个模块内部的处理成分是相关的，而且这些处理必须以特定的次序执行
• 信息内聚：模块的所有功能都是基于同一个数据结构(符号表)
• 功能内聚：模块内所有元素共同完成一个功能

11、软件需求

（1）软件需求包含

• 功能需求：所开发的软件必须具备什么样的功能
• 非功能需求：产品必须具备的属性或品质，如可靠性、性能、响应时间和扩展性
• 设计约束：对解决方案的一些约束说明

11、其他

（1）人机交互黄金三原则：置于用户控制之下、减少用户的记忆负担、保持界面的一致性

（2）几个时间概念
关键路径：从开始到结束的所有路径中，所用时间最长的一条路径
最早开始时间：在关键路径上，从开始到该任务的最早执行时间
最晚开始时间：关键路径的总时间-反向得出该任务的时间
松弛时间：最多延迟执行的时间，两种求法

• 最晚开始时间-最早开始时间
• 关键路径总时间-含该任务的最长路径

（3）重构可以简化构件的设计而无需改变其功能或行为

（4）分支覆盖测试法测试用例时，每个分支至少通过一次

（5）LOC表示构成软件的源代码行数，用于估算软件成本和规模

（6）软件配置管理：一组管理整个软件生存期各阶段中变更的活动，主要包括变更标识、变更控制和版本控制

（7）n个成员的开发小组的沟通路径是n(n-1)/2

（8）管道过滤器体系结构的特点

• 软件构件具有良好的高内聚、低耦合的特点
• 支持软件重用
• 支持并行执行
• 允许对吞吐量、死锁等属性分析
• 系统维护和增强系统性能简单
• 允许将整个系统的输入/输出行为看成多个过滤器的行为的简单合成

（9）COM(组件对象模型)：一种新的软件开发技术，可以开发出各种各样的功能专一的组件，然后将它们按照需要组合起来，构成复杂的应用系统

（10）结构图的组成

• 模块
• 调用
• 数据
• 控制信息
• 转接符号

---

网络基础知识

• 网络概述
• ISO/OSI网络体系结构
• 网络互联的硬件
• 网络的协议与标准
• Internet及应用
• 网络安全

---

1、防火墙与漏洞扫描

（1）包过滤防火墙对数据包的过滤依据包括源IP地址、源端口号、目标IP地址和目标端口号

（2）应用级网关防火墙是内部网和外部网的隔离点，它可对应用层的通信数据流进行监控和过滤

（3）漏洞扫描系统不能用于发现网络入侵者，用于检测网络入侵者的系统称为入侵检测系统

（4）漏洞扫描技术：检测远程或本地系统安全脆弱性的一种安全技术。通过与目标主机TCP/IP端口建立连接并请求某些服务(如TELNET、FTP等)，记录目标主机的应答，搜集目标主机相关信息，从而发现目标主机某些内在的安全弱点

（5）漏洞扫描技术和防火墙、入侵检测系统互相配合，能够有效提高网络的安全性

（6）通过防火墙将网络划分成三个区域(安全级别从高到低)

• 内网
• DMZ
• 外网

（7）防火墙的性能和特点由两点决定

• 工作层次
• 防火墙采用的机制

访问策略规则

• 内网可以访问外网
• 内网可以访问DMZ
• 外网不能访问内网
• 外网可以访问DMZ
• DMZ不能访问内网
• DMZ不能访问外网

2、各层设备

（1）物理层设备

• 中继器：对接收的信号进行再生放大，以延长传输的距离
• 集线器：从一个端口接收信息，并向其他端口广播出去

（2）网络层设备

• 路由器：识别IP地址，进行数据包的转发

（3）数据链路层设备

• 网桥：可以识别MAC地址，进行帧转发。能识别数据链路层协议数据单元，并根据数据链路层地址进行数据转发
• 交换机(多端口网桥)：任何一对端口之间都能进行数据转发

3、路由类型

• 直连路由ID：直接连接的网络
• 远程网络ID：不直接连接的网路
• 主机路由：到达特定主机的路由
• 默认路由：无法找到确定路由时使用的路由
• 持久路由：
• 静态路由：由用户或网络管理员手工配置的路由信息
• 随机路由：使用前向代理来收集网络中的有限全局信息即当前节点到其源节点的旅行时间，并以此来更新节点的旅行时间表
• 洪泛路由：将收到的封包，往所有的可能连结路径上递送，直到封包到达为止
• 动态路由(自适应路由)：路由器能够自动地建立自己地路由表，并且能够根据实际情况的变化适时地进行调整

4、协议类型

• POP：邮局协议，用于接收邮件，POP3端口号：110
• PGP：优良保密协议，用于信息加密、验证和应用程序，可用于加密电子邮件内容
• SMTP：简单邮件传输协议，采用ASCII编码。端口号：25
• IMAP：邮件获取协议
• MPLS：多协议标记交换，一种标记机制的包交换技术
• MIME：互联网标准，在发送邮件时可以附加多媒体数据。与安全无关
• SNMP：简单网络管理协议，用于网络管理
• SSL：传输层安全协议。依靠证书来验证服务器的身份，并为浏览器和服务器之间的通信加密(HTTPS)
• SSH：专为远程登录会话和其他网络服务提供安全性的协议
• HTTP：超文本传输协议，大多Web服务器使用但不安全，端口号：80
• HTTPS：安全超文本传输协议，端口号：443。协议命令：GET(读一个网页)、HEAD(读取网页头信息)、POST(把消息加到指定的网页上)
• ARP：网络层协议。实现IP地址与MAC地址之间的变换
• TCP：互联网中的传输层协议，使用3次握手协议建立连接
• TLS：传输层安全协议

5、计算机病毒

（1）病毒的特点：隐蔽性、传染性、潜伏性、触发性、破坏性

（2）病毒的类型：

• 多形病毒：每次感染都会改变自己的计算机病毒
• 宏病毒：破坏office文件
• 蠕虫病毒：破坏系统，如震网病毒、熊猫烧香、欢乐时光
• 引导区病毒：破坏引导盘和文件目录
• 木马病毒：控制系统，有未知程序试图建立网络连接，如X卧底

6、网络攻击

以网络为手段窃取网络上其他计算机的资源或特权，对其安全性或可用性进行破坏的行为，分为两种攻击

• 主动攻击：如窃取、篡改、假冒和破坏

• 被动攻击：系统干涉、网络窃听、截取数据包并进行分析，从中窃取重要的敏感信息

  具体类型有：

• 口令入侵：使用合法用户账号和口令登录目的主机，然后再实施攻击活动

• 放置特洛伊木马程序：向黑客通知用户的IP地址及被预先设定的端口

• 拒绝服务攻击(DOS)：使计算机或网络无法提供正常的服务

• 端口扫描：利用Socket编程与目标主机的某些端口建立TCP连接、进行传输协议的验证等

• 网络监听：主机可以接收到本网段在同一条物理通道上传输的所有信息

• 欺骗攻击：攻击者创造一个易于误解的上下文环境，以诱使受攻击者进入并且做出缺乏安全考虑的决策

• 电子邮件攻击

• ARP攻击：伪造IP地址和MAC地址，在网络中产生大量的ARP通信量使网络阻塞

• 重放攻击(重播攻击、回放攻击、新鲜性攻击)：攻击者发送一个目的主机已接受过的包，来达到欺骗系统的目的，主要用于身份认证过程、破坏认证的正确性 。时间戳可以防止

7、密钥

（1）数字证书由CA证书授权中心发行。用户获取网站数字证书后通过验证CA的签名确认其有效性，从而验证网站真伪；用户发送数据时使用网站的公钥加密，验证网站的数字签名，网站利用自身的私钥对发送的消息签名和对收到消息解密

（2）公钥体系中，私钥用于解密和签名，公钥用于加密和认证

（3）公开密钥加密(非对称加密)：一对密钥(私人密钥+公开密钥)。如RSA、ElGamal、背包算法、Rabin、ECC、DSA数字签名

（4）共享密钥加密(对称加密)：DES、三重DES、RC-5、IDEA、AES

（5）数字签名技术：数据源发送方使用自己的私钥对数据检验和其他与数据内容有关的变量进行加密处理，完成对数据的合法签名，数据接收方利用对方的公钥来解读收到的数字签名，并将解读结果用于对数据完整性的检验，以确认签名的合法性

8、命令行

cmd：提示进行命令输入的一种工作提示符

• ipconfig：显示信息
• ipconfig/all：显示详细信息
• ipconfig/renew：更新所有适配器
• ipconfig/flushdns：刷新DNS解析器缓存
• ipconfig/release：释放所有匹配的连接
• Netstat：控制台命令，用于监控TCP/IP网络，可以显示路由表、实际的网络连接以及每一个网络接口设备的状态信息
• Ping：通信协议，可以检查网络是否连通
• msconfig：系统配置实用程序

9、网络

（1）网络划分

• A类网络：1～126。缺省子网掩码255.0.0.0
  11111111·00000000·00000000·00000000(前8位为网络地址，后24位2为主机地址)
• B类网络：128~191。缺省子网掩码255.255.0.0
• C类网络：192~223。缺省子网掩码255.255.255.0

10、其他

（1）IE浏览器安全等级由高到低：
受限站点>Internet>本地Internet>可信站点

（2）关闭服务器中ICMP端口，别的计算机就不能通过ping命令测试服务器连通情况

（3）ping本地循环地址127.0.0.1，无法ping通，表明本机TCP/IP协议不能正常工作；ping通，接下来ping本机IP地址，若ping不通，则是网络适配器出现故障。ping同网段中某计算机的IP，ping不通，则表明网络线路出现故障

（4）通过默认Telnet端口连接服务器，防火墙配置时使用TCP协议，缺省下使用23端口

（5）三网合一：电信网、广播电视网、互联网

（6）MD5是一种摘要算法，输出由四个32位分组组成，级联后将生成一个128位散列值

（7）建立连接进行可靠通信在TCP/IP网络中，应该在传输层完成

（8）IPv6的地址空间是IPv4的2^96倍

（9）TCP和UDP都提供了端口寻址功能。TCP和UDP的主要区别在于UDP不一定提供可靠的数据传输

（10）CGI(公共网关接口)：外部应用程序与Web服务器之间的接口标准

（11）回送地址(127.x.x.x)：本机回送地址，即主机IP堆栈内部的IP地址，主要用于网络测试以及本地机进程间通信

（12）帧中继(FR)：为克服X.25交换网的缺陷、提高传输性能而发展起来的高速分组交换技术

（13）Windows权限由高到低
Administrators>Power users>Users>Everyone

（14）Windows IIS服务认证方式

• Passport身份验证
• 集成Windows身份验证
• 摘要式身份验证
• 基本身份验证

（15）以太网交换机根据数据链路层MAC地址进行帧交换

（16）三层交换机：一次路由、多次交换

（17）网络的可用性：网络系统、网络元素或网络应用对用户可利用的时间百分比

（18）结构化综合布线系统：基于现代计算机技术的通信物理平台，集成了语音、数据、图像和视频的传输功能，消除了原有通信线路在传输介质上的差别。分为6个子系统

• 工作区子系统
• 水平子系统
• 干线子系统
• 设备间子系统
• 管理子系统
• 建筑群子系统

（19）在ASP的内置对象中，response对象可以修改cookie中的值

（20）报文摘要：用来防止发送的报文被篡改

（21）集线器连接的主机构成一个冲突域，交换机的每个端口属于一个冲突域，路由器连接的两部分网络形成两个广播域

（22）Windows的DNS服务器通过启用循环，添加每个Web服务器的主机记录，可以确保域名解析并实现负载均衡

（23）隧道技术将两个IPv6节点通过现有的IPv4网络进行通信，翻译技术使纯IPv6节点可以与纯IPv4节点进行通信

---

多媒体

• 多媒体的基本概念
• 声音
• 图形和图像
• 动画和视频
• 多媒体网络
• 多媒体计算机系统

---

1、音频信号

（1）分量信号：单一频率的信号

（2） 复合信号：由许多频率不同的信号组成

（3）声音信号的频率：声波每秒钟变化的次数，用Hz表示

（4）带宽：描述组成声音的信号的频率范围

（5） 频率范围

• 频率小于20Hz：亚音信号(次音信号)
• 20Hz~20kHz：音频信号
• 高于20kHz：超音频信号(超声波)

（6）几个例子

• PC处理的音频信号频率范围为20Hz~20kHz
• 人的说话声音为300~3400Hz
• 乐器演奏的声音为20~20KHz
• 其他如风声、雨声、鸟叫声等为20~20kHz

2、多媒体

（1）多媒体计算机图像文件格式

• 静态图像文件格式：JPG
• 动态图像文件格式

（2）媒体分类

• 表现媒体：实现信息输入和输出的媒体，如键盘、鼠标、扫描仪、话筒、摄像头；显示器、打印机、喇叭
• 存储媒体：存储表示媒体的物理介质，如硬盘、光盘
• 传输媒体：传输表示媒体的物理介质，如光缆、电缆、电磁波
• 感觉媒体：直接作用于人的感觉器官，如图像、声音
• 表示媒体：传输噶虐媒体的中介媒体，用于数据交换的编码，如图像编码、文本编码、声音编码

（3）多媒体中媒体的两重含义

• 存储信息的实体：如手册、磁盘、光盘、磁带等
• 表达与传递信息的载体：文字、声音、图像、动画和视频等

（4）表示媒体三种类型

• 视觉类媒体：位图图像、矢量图形、图表、符号、视频和动画
• 听觉类媒体：音响、语音和音乐
• 触觉类媒体：点、位置跟踪、力反馈与运动反馈

（5）音乐合成技术

• 调频(FM)音乐合成
• 波形表(WaveTable)音乐合成：音质更好

3、图像

（1）图像深度：存储每个像素所用的位数，也用来度量图像分辨率

（2）像素深度：确定彩色图像(灰度图像)的每个像素可能有的颜色数(灰度级数)，决定彩色图像(灰度图像)中可出现的最多颜色数(最大灰度等级)。图像深度为b位，则有2^b种

（3）图像数据量计算公式

• 图像数据量=图像的总像素x图像的深度
• 光盘数量=图像的总像素x图像深度/光盘内存

（4）矢量图是用一系列计算机指令来描述和记录一副图的内容，图元是其基本组成单位；位图是用像素点来描述的图。两者相比，位图占用空间较大，处理侧重于获取和复制，显示速度快

（5）图像压缩编码及压缩标准

• JPEG
• MPEG
• H.261

（6）dpi：描述图像分辨率的单位，表示每英寸多少像素点，即组成一幅图像的像素密度

4、其他

（1）CIF视频格式的图像分辨率为352x288

（2）ISO制定的MPEG系列标准

• MPEG-7：多媒体内容描述接口标准
• MPEG-1、MPEG-2和MPEG-4：音、视频编码技术(1–VCD、2–DVD)
• MPEG-21：多媒体应用框架标准

（3）尼奎斯特取样定理：如果取样速率大于模拟信号最高频率的2倍，则可以用得到的样本中恢复原来的模拟信号

（4）计算机获取模拟视频信息的过程中首先要进行A/D变换

（5）脉冲编码调制技术(PCM)：MIC(话筒)输出音频模拟信号，声卡获取该信号后，通过模数转换器(ADC)，将声波振幅信号采样转换成一串数字信号并存储到计算机中。重放时，这些信号送到数模转换器(DAC)，以同样的采样速度还原为模拟波形，放大后送到扬声器发声

（6）分辨率

• 显示分辨率：显示器上能够显示出的像素点的数目，即显示器在横向和纵向上能够显示出的像素点数目
• 水平分辨率：显示器水平方向(横向)上显示出的像素点的数目
• 垂直分辨率：显示器垂直方向(纵向)上显示出的像素点的数目

---

数据库技术

• 基本概念
• 数据模型
• 关系代数
• 关系数据库SQL
• 关系数据库规范化
• 数据库的控制功能

---

1、数据库

（1）数据库恢复：在尽可能短的时间内把数据库恢复到故障发生前的状态

（2）数据库容灾属于系统安全和应用安全

（3）数据库体系结构一般采用三级模式结构

• 外模式(用户模式/子模式)：用户与数据库系统的接口，是用户用到的那部分数据的描述。如视图

• 内模式(存储模式)：数据库在物理存储方面的描述，定义所有内部记录类型、索引和文件的组织方式，以及数据控制方面的细节。如存储文件

• 模式(概念模式)：数据库中全部数据的整体逻辑结构的描述。如基本表

  在三级模式之间提供了两级映像

• 模式/内模式映像：存在于概念级和内部级之间，实现了概念模式到内模式之间的相互转换

• 外模式/模式映像：存在于外部级和概念级之间，实现了外模式到概念模式之间的相互转换

（4）数据库系统的安全措施

• 权限机制
• 视图机制
• 数据加密

（5）配置数据库包括开发库、受控库、产品库

（6）关系数据库的规范化

• 需求分析阶段：确定新系统功能的过程中，确定系统边界、收集支持系统目标的基础数据及其处理方法
• 逻辑设计阶段：对关系模式进一步的规范化处理

（7）数据库的关系范式：

• 第一范式(1NF)：属性不可拆分或无重复的列
• 第二范式(2NF)：完全依赖函数，即某个非主属性数据项依赖于全部关键字
• 第三范式(3NF)：消除传递依赖，即不依赖于其他非主属性
• BC范式(BCNF)：所有非主属性对每一个码都是完全依赖函数；所有的主属性对于每一个不包含它的码也是完全依赖函数；没有任何属性完全依赖于非码的任意一个组合
• 第四范式(4NF)：对于每一个X->Y，X都能找到一个候选码

2、属性和联系

（1）自然连接：两个关系种进行比较的分量必须是相同的属性组，并且在结果种将重复属性列去掉

（2）主属性：包含在任何一个候选码中的属性

（3）简单属性：原子的、不可再分的

（4）复合属性：可以细分为更小的部分(划分为别的属性)

（5）多值属性：一个属性对应一组值

（6）弱实体：某些实体对于另一些实体有很强的依赖关系，即一个实体的存在必须以另一实体的存在为前提

（7）多对多联系需要单独转换成一个关系模式，即需要建新类

3、SQL语言

（1）对数据库对象

• 创建：CREATE
• 修改：ALTER
• 删除：DROP
  （2）对基本表和视图中的数据
• 插入：INSERT
• 删除：DELETE
• 修改：UPDATE

（3）查询条件WHERE和HAVINING的区别：WHERE是针对单条记录的判断条件，HAVINING是针对分组之后的判断条件

（4）授权语句格式

GRANT INSERT ON TABLE TO XXX WITH GRANT OPTION

（5）创建视图格式
CREATE VIEW 视图名(列表名) AS SELECT 查询子句
[WITH CHECK OPTION]

4、其他

（1）数据结构模型

• 层次模型
• 网状模型
• 关系模型
• 面向对象数据模型

（2）进程控制块PCB组织方式

• 线性表方式：不论进程状态如何，将所有的PCB连续地存放在内存地系统区。适用于进程数目不多地情况
• 索引表方式：线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等
• 链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列

（3）JDBC(java数据库连接)：用于执行SQL语句的Java API，由一组用Java语言编写的类和接口组成。可以用来与数据库建立连接、发送操作数据库的语句并处理结果

（4）E-R图之间的冲突

• 结构冲突
• 属性冲突
• 命名冲突

（5）事物的ACID特性

• 原子性：事务是原子的，要么做，要么不做
• 一致性：事务执行的结果必须保证数据库从一个一致性状态变到另一个一致性状态
• 隔离性：事务相互隔离
• 持久性：事务成功提交，即使数据库崩溃，对其更新操作也永久有效

分布性：数据存储在多个不同的节点上
逻辑相关性：数据库系统内的数据在逻辑上具有相互关联的特性
场地透明性：使用分布式数据库中的数据时不需指明数据所在的位置
场地自治性：每一个单独的节点能够执行局部的应用请求

（6）视图：从一个或者多个表或视图中导出的表，其结构和数据是建立在对应表的查询基础上的。视图是一个虚拟表，查询时可以从一个或者多个基本表或视图中导出

---

数据结构

• 线性结构
• 数组、矩阵和广义表
• 树
• 图
• 查找
• 排序

---

1、 树

（1）二叉树的遍历运算

• 先序遍历：(1)根结点 (2)左子树 (3)右子树
• 中序遍历：(1)左子树 (2)根结点 (3)右子树
• 后序遍历：(1)左子树 (2)右子树 (3)根结点

（2）对二叉排序树进行中序遍历，必定得到节点关键字的有序序列

（3）插入关键字构造二叉排序树，小于根节点的值插入到左子树，大于根结点的值插入到右子树

（4）构造二叉排序树时需进行平衡处理，使每个节点左、右子树高度差的绝对值不超过1

（5）哈希表和二叉排序树可以在查找过程中动态创建，属于动态查找表

（6）平衡二叉树任意一个结点的左、右子树的高度差绝对值不超过1，如完全二叉树

（7）线索二叉树与二叉树的遍历运算相关，是一种存储结构、二叉排序树的结构与给定的初始关键码序列有关、最优二叉树(哈夫曼树)是一类带权路径长度最短的二叉树。他们都不要求是平衡二叉树

（8）二叉链表中每个节点有2个指针，一共有2k个指针。

（9）二叉树中除了根节点外，其他的节点都有一条边进入该节点，即一个指针指向该节点，二叉树中边的总个数为k-1，即非空指针为k-1个，空指针个数为k+1个

（10）任意度为2的二叉树：n0=n2+1

（11）任意度为3的二叉树：n0=2n3+n2+1

（12）哈夫曼树构造过程：将给定的序列从小到大进行排列，选择列中最小的两个数画出一个树，重复操作直至画出整个哈夫曼树

（13）哈夫曼编码属于熵编码(一致性编码)，用于数据的无损耗压缩

2、 图

（1）图的遍历运算，实质是通过边或弧找邻接点的过程

（2）两种活动网
AOV(以顶点表示活动的网)：有向图中以顶点表示活动，用有向边表示活动之间的有限关系
AOE(用边表示活动的网)：带权有向图中以顶点表示时间，以有向边表示活动，边上的权值表示该活动持续的时间

（3）拓扑排序：将AOV网中所有顶点排成一个线性序列的过程，满足AOV网中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前（入度为0，没有前驱）

（4）有n个顶点的连通图的生成树中恰好有n-1条边

（5）N顶点、E条边的简单无向图采用邻接矩阵存储结构，该矩阵中的非零元素数目为2E

（6）图的基本存储结构

• 邻接矩阵
• 邻接链表

3、查找

（1）顺序查找既适用于顺寻存储结构，也适用于链表结构

（2）二分查找需要对中间元素进行快速定位，在链表结构上无法实现

4、线性表和链表

（1）

4、其他

（1）利用McCabe度量法计算有向图G环路复杂度的公式为V(G)=m-n+2。V(G)：有向图G中的环路个数；m：G中的有向弧数；n：G中的节点数

（2）对n个结点、e条边的无向图采用邻接表访问，时间复杂度为O(n+e)；采用邻接矩阵访问，时间复杂度为O(n^2)

---

常用算法设计方法

• 算法和算法设计的基本概念
• 算法分析基础
• 分治法
• 动态规划法
• 贪心法
• 回溯法
• 分支限界法
• 概率算法
• 近似算法
• NP完全性理论

---

1、算法

符号O表示算法运行时间的上限

（1）5个基本特征

• 有穷性：任意一组合法输入值，在执行有穷步骤后一定能结束
• 确定性：每种情况下对应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径
• 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现
• 有输入
• 有输出

（2）具体算法

• 快速排序：本质是分治算法。选择一个基准元素，通过一趟排序将待排序序列分为两部分，一部分比基准小，一部分大于等于基准，此时基准元素在其排序后的正确位置，然后再递归地排序划分的两部分。适用于无序数组，最坏时间复杂度为O(n^2)，最好时间复杂度为O(nlog2n)
• 回溯法：在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。可以系统地搜索一个问题地所有解或任一解。如N-皇后问题
• 分治法：将一个难以直接解决的大问题分解成一些规模较小的相同问题，分而治之。相同子问题会被求解多次，耗费指数级时间
• 动态规划：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。子问题不独立，主要求解具有某种最优性质的问题
• 插入排序：将待排序数组分为两部分，已排好序部分和未排序部分。开始时，第一个元素在已排好序部分中，其余元素在未排序部分。然后依次从未排序部分中去除第一个元素，从后向前与排好序部分的元素进行比较并将其插入到已排好序部分的正确位置。适用于基本有序数组
• 归并排序：将待排序数组划分为子问题，对子问题求解，然后合并解
• 贪心算法：对问题求解时，总是做出在当前看来最好的选择，仅仅是在某种意义上的局部最优解
• 迪杰斯特拉算法：用于求解单源点最短路径，本质上是一种基于贪心策略的算法

---

面向对象技术

• 面向对象的基本概念
• 面向对象的程序设计
• 面向对象开发技术
• 面向对象的分析与设计方法
• 设计模式

---

1、面向对象软件开发过程

• 面向对象分析：为了获取对应用问题的理解，主要任务时抽取和整理用户需求并建立问题域精确模型
• 面向对象设计：采用协作的对象、对象的属性和方法说明软件解决方案的一种方式，强调的是定义软件对象和这些软件对象如何协作来满足需求，延续面向对象分析
• 面向对象实现：主要强调采用面向对象程序设计语言实现系统
• 面向对象测试：根据规范说明来验证系统设计的正确性

2、面向对象分析

（1）面向对象分析的目的：获得对应用问题的理解，确定系统的功能、性能要求。第一步是确定问题域

（2）面向对象分析的5个活动

• 认定对象：按自然存在的实体确定对象
• 组织对象：分析对象间的关系，将相关对象抽象成类
• 描述对象间的相互作用：描述出各对象在应用系统中的关系
• 定义对象的操作
• 定义对象的内部信息

3、面向对象设计

（1）面向对象设计中高层模块不应该依赖于底层模块

（2）**面向对象的设计模式
**采用设计模式以复用成功的设计
1）状态型模式：用于创建对象

• 工厂方法模式：
• 抽象工厂模式：提供一个创建一系列相关或相互依赖对象的接口而不许指定它们具体的类
• 单例模式：保证一个类仅能生成一个实例
• 创造者模式：
• 原型模式：

2）结构型模式：处理类或对象的组合

• 适配器模式：将已有的接口转换为系统希望的接口形式
• 装饰器模式：动态地给一个对象增加一些额外的指责，无须改变类的设计和实现
• 代理模式：通过提供与对象相同的接口来控制对这个对象的访问
• 外观模式：描述如何用单个对象标识整个子系统
• 桥接模式：将对象的抽象和其实现分离
• 组合模式：描述了如何构造一个类层次式结构
• 享元模式：共享大量细粒度的对象

3）行为型模式：描述类与对象怎样交互、怎样分配职责

• 责任链模式：将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求
• 策略模式：定义了一系列算法，并将每一个算法封装起来，使它们可以相互替换
• 模板方法模式：
• 迭代子模式：
• 责任链模式：将多个对象的请求连成一条链，并沿着这条链传递该请求，直到有一个对象处理它为止，避免请求的发送者和接收者之间的耦合关系
• 备忘录模式：
• 状态模式：
• 访问者模式：一个作用于某对象结构中的各元素的操作。对于某个对象或一组对象，不同的访问者，产生的结果不同，执行的操作也不同
• 中介者模式：
• 迭代器模式：提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象内部表示
• 命令模式：将一个请求封装为一个对象，可用不同的请求对客户进行参数化
• 解释器模式：定义一个解释器，用来根据文法表示来解释语言中的句子
• 观察者模式：定义对象间的一种一对多的依赖关系，当一个对象改变状态，则所有依赖于它的对象都会得到通知并被自动更新

4、面向对象设计原则

• 单一职责原则：设计目的的单一的类
• 开放-封闭原则(OOD)：对扩展开放，对修改封闭。模块容易扩展和修改，但不能对其他模块产生影响
• 里氏替换原则(LSP)：子类可以替换父类并出现在父类能够出现的任何地方
• 接口隔离原则：使用多个专门的接口比使用单一的总接口要好
• 依赖倒转原则(DIP)：要依赖于抽象，而不依赖于实现(要针对接口编程，不要针对实现编程)

5、面向对象开发方法

（1）面向对象开发方法

• Booch方法
• Coad方法
• OMT方法

（2）面向数据流开发方法：结构化开发方法

（3）面向数据结构开发方法：Jackson系统开发方法

6、UML

（1）UML类

• 实体类：负责数据和业务逻辑
• 边界类(接口类)：负责和用户进行交互
• 控制类：负责实体类和界面类的交互

（2）UML视图

• 用例视图：从外部参与者的角度描述系统功能
• 逻辑视图：从系统静态结构和动态行为角度显示系统内部如何实现系统功能
• 实现视图：源代码以及实际执行代码的组织结构

（3）UML图

• 类图：一组对象、接口、协作和它们之间的关系
• 对象图：一组对象以及它们之间的关系
• 用例图：一组用例、参与者以及它们之间的关系
• 序列图：场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动
• 协作图：强调收发消息的对象的结构组织
• 状态图：一个状态机，由状态、转换、事件和活动组成
• 活动图：特殊的状态图，展现了在系统内从一个活动到另一个活动的流程
• 构件图：一组构件之间的组织和依赖
• 部署图：运行处理节点以及其中的构件的配置

（4）UML类图中类与类之间的关系

• 依赖：如使用类库
• 关联
• 聚合：如当整体对象消失而部分对象依然可以存在并继续被使用(关联特殊种类)
• 组合：如当整体对象消失时，部分对象也随之消失(关联特殊种类)
• 继承

（5）UML类图用于对项目的静态设计视图建模。使用类图的3种方式

• 系统的词汇
• 简单的协作
• 逻辑数据库模式

（6）UML中关联的多重度是指一个类的实例能够与另一个类的多少个实例相关联

（7）业务用例和参与者一起描述组织或企业所支持的业务过程，业务对象模型描述业务结构以及结构元素如何完成业务用例

（8）序列图中消息定义了交互中生命线之间的特定交互，分为

• 同步消息：进行阻塞调用，调用者中止执行，等待控制权返回，需要等待返回消息。实心箭头表示
• 异步消息：调用者发出消息后继续执行，不引起调用者阻塞，也不等待返回消息。虚心箭头表示
• 返回消息

（9）接口(< < interface > >)：可用于声明对象类所需要的服务

7、面向对象特性

（1）封装：把属性和服务结合成一个独立的系统单元，并隐藏对象的内部细节

（2）继承：使得子类可以自动拥有父类的全部属性和服务

多重继承：一个类可以继承另外一个类，而另外一个类又可以继承别的类

（3）多态：是面向对象中由重载或过载机制实现的结果。在面向对象方法中，指的是客户类无需知道所调用方法得特定子类的实现，类型包括

• 参数多态：应用广泛、最纯的多态
• 包含多态：相同操作可用于一个类型及其子类型
• 强制多态：编译程序通过语义操作，把操作对象的类型强行加以变换，以符合函数或操作符的要求
• 过载多态：同一个名在不同的上下文中有不同的类型

（4）消息：是对象发出的服务请求、

8、其他

（1）类库为应用程序提供一组可以被使用的类

（2）框架除了提供类之外，还基本实现了一个可以执行的框架

（3）函数库提供被调用的函数

（4）名词短语识别对象、动词短语识别对象的操作

（5）类用来描述一组对象共有的成员属性和方法，它可以产生一个或多个对象，创建类的实例时需要分配存储空间

（6）静态成员：所修饰的成员是属于类的，而不是属于某对象的

（7）类的静态方法只能访问该类的静态数据成员

（8）绑定：把过程调用和响应调用需要执行的代码加以结合的过程

• 静态绑定：在程序编译时进行
• 动态绑定：在程序运行时进行

（9）面向对象技术中，对象具有以下特性

• 清晰的边界
• 良好定义的行为
• 可扩展性

---

标准化和软件知识产权基础知识

• 标准化基础知识
• 知识产权基础知识

---

1、我国保护计算机软件著作权的两个基本法律文件

• 《中华人民共和国著作权法》
• 《计算机软件保护条例》

2、软件许可使用

• 独占许可使用：不能授权第三方，自己不能用
• 独家许可使用：不能授权第三方，自己可以用
• 普通许可使用：既可以授权第三方又可以自己用

3、一些权利

• 软件著作权自软件开发完成之日起自动产生，职务作品的知识产权人为公司。客体包括源程序、目标程序和软件文档
• 翻译权：将原软件从一种程序语言转换成另一种程序语言的权利
• 商业秘密权：商业秘密未公开，具有实用性和保密性
• 商标权：注册商标专用权，只有依法注册后才受法律保护。不包括商标设计人的权利，主要注重商标所有人的权利

4、专利申请
（1）我国专利申请的原则

• 书面原则：办理时采用书面形式
• 先申请原则：多人申请同样专利，授予最先申请人
• 单一性原则：一申请一发明

（2）同一发明创造只能被授予一项专利，若同时申请同样的专利，解决方法有两种

• 两个申请人作为一件申请的共同申请人
• 其中一方放弃权利并从另一方得到适当的补偿

5、我国标准可分为国家标准、行业标准、地方标准和企业标准，行业代号有QJ(航天)、SJ(电子)、JB(机械)、JR(金融系统)

6、使用

• 合理使用：可以不经著作权人许可，不需要付报酬，使用其作品
• 许可使用：著作权人允许他人使用自己作品，并由此获得经济利益
• 强制许可：经行政管理部门授权使用著作权人作品，无需征得其同意，但应向其支付报酬
• 法定许可：除著作权人声明不得使用外，在不侵犯著作人合法权利下进行使用