[toc]

软件设计师笔记_科目一_精简考点

科目一：综合知识（选择题）。满分75分，需要达到45分才能合格。

科目一知识点分布

知识点	分数	说明	比例
软件工程基础知识	13	开发模型、设计原则、测试方法、质量特性、CMM、Pert图、风险管理	17.33%
面向对象	11	面向对象基本概念、面向对象分析与设计、UML、设计模式	14.67%
数据结构与算法	9	数组、栈、队列、树与二叉树、图、查找与排序、常见算法	12%
程序设计语言	6	文法、有限自动机、正规式、语句的作用、语句的语义、程序的控制结构、函数调用的参数传递、各种程序语言的特点比较	8%
计算机硬件基础	6	浮点数运算、溢出、算术、逻辑运算、计算机体系结构分类、指令系统基础、CISC与RISC、流水线、Cache存储器可靠性分析、校验方法	8%
操作系统	6	进程状态转换图、信号量与PV操作、死锁问题、银行家算法、段页式存储、页面置换算法、磁盘调度、树形文件系统	8%
数据库系统	6	E-R模型、关系代数、元组演算、规范化理论（键、范式、模式分解）、并发控制	8%
计算机网络	5	OSI模型、TCP/IP协议族、子网划分、常用的网络命令	6.6%
信息安全知识	5	加密解密技术、网络安全、计算机病毒	6.6%
知识产业与标准化	3	作品保护时间、侵权判定、知识产权归属、标准的分类、标准代号	4%
专业英语	5	专业英语填空	6.6%

软件设计师笔记01_计算机系统知识概述_精简考点

科目一考试中占2-8分左右。

计算机系统硬件基本组成

计算机的基本硬件系统主要由运算器、控制器、存储器、输入设备和输出设备五大部件组成。

运算器和控制器集成在一起统称为中央处理单元（CPU）。
存储器是计算机系统中的记忆设备，分为内部存储器（速度高，容量小）和外部存储器（速度慢，容量大）。
输入设备和输出设备合称为外部设备（简称外设）

中央处理单元CPU

中央处理单元（CPU）是计算机系统的核心部件，它负责获取程序指令，对指令进行译码并加以执行。除此之外，CPU 还需要对系统内部和外部的中断（异常）做出响应，进行相应的处理。

CPU 主要由运算器、控制器、寄存器组和内部总线等部件组成。

运算器的组成：

1）算术逻辑单元（ALU）：负责对数据的算术运算和逻辑运算。
2）累加寄存器（AC）：是一个通用寄存器。负责暂存算术运算或逻辑运算的中间运算结果。
3）数据缓冲寄存器（DR）：写内存时，暂存指令或数据字或操作数。
4）状态条件寄存器（PSW）：保存指令执行后的状态。

控制器的组成：

程序计数器PC：存储下一条要执行指令的地址。
指令寄存器IR：存储即将执行的指令。
指令译码器：对指令中的操作码字段进行分析。
时序部件：提供时序控制信号。

进制转换

非十进制数转换为十进制数

在软考中，非十进制数（如二进制、八进制、十六进制）转换为十进制数的方法是按位权展开相加法。

二进制转十进制

方法：从右往左，将二进制数每一位的值（0 或 1）乘以对应位权（2 的幂次），然后求和。
位权计算：从右往左，第一位为 2^0^ ，第二位为 2^1^ ，依此类推。

例子：

二进制数 1011 转换为十进制：1 x 2^0^ + 1 x 2^1^ + 0 x 2^2^ + 1 x 2^3^ = 1 + 2 + 0 + 8 = 11

八进制转十进制

方法：从右往左，将八进制数每一位的值（0-7）乘以对应位权（8 的幂次），然后求和。
位权计算：从右往左，第一位为 8^0^ ，第二位为 8^1^ ，依此类推。

例子：

八进制数 35 转换为十进制：5 x 8^0^ + 3 x 8^1^ = 5 + 24 = 29

十六进制转十进制

方法：从右往左，将十六进制数每一位的值（0-9，A-F 表示 10-15）乘以对应位权（16 的幂次），然后求和。
位权计算：从右往左，第一位为 16^0^ ，第二位为 16^1^ ，依此类推。

例子：

十六进制数 0xA3 转换为十进制：3 x 16^0^ + A x 16^1^ = 3 + 10 x 16^1^ = 160 + 3 = 163

带小数的非十进制数转换十进制数

方法：整数部分和小数部分,分别按位权展开再相加。

整数部分：从右往左，位权为基数^0^ ，第二位为基数^1^ ，依此类推。
小数部分：从左往右，位权为基数^-1^ ，第二位为基数^-2^ ，依此类推。

示例：二进制数 101.11 转换为十进制

整数部分：1 x 2^0^ + 0 x 2^1^ + 1 x 2^2^ = 1 + 0 + 4 = 5
小数部分：1 x 2^-1^ + 1 x 2^-2^ = 0.5 + 0.25 = 0.75
总和：5 + 0.75 = 5.75

十进制数转换为非十进制数

在软考中，十进制数转换为非十进制数（如二进制、八进制、十六进制）的方法是除基取余法（整数部分）和乘基取整法（小数部分）。

十进制整数转非十进制

步骤1 除基取余：将十进制整数不断除以目标进制的基数（二进制为 2，八进制为 8，十六进制为 16），记录每次的余数。
步骤2 逆序排列余数：直到商为 0，将余数从最后一次到第一次依次排列，即为转换结果。

十进制小数转非十进制

乘基取整：将十进制小数不断乘以目标进制的基数，记录每次乘积的整数部分。
顺序排列整数部分：直到小数部分为 0 或达到所需精度，将整数部分从第一次到最后一次依次排列，即为转换结果。

十进制数（包含整数和小数）转非十进制

整数部分：用除基取余法转换。
小数部分：用乘基取整法转换。
合并结果：将整数部分和小数部分用小数点连接。

各个进制的加减法

在进行不同进制（如二进制、八进制、十进制、十六进制等）的加减法时，核心原理与十进制运算类似，但需注意"逢基数进一"（加法）和"借一当基数"（减法）的规则。

加法规则

从右向左逐位相加（低位到高位）
若本位数字之和小于基数：直接写结果
若本位数字之和大于等于基数：则向高位进1位，然后再继续计算。

减法规则

从右向左逐位相减（低位到高位）
若被减数本位数字大于等于减数本位数字：直接相减
若被减数本位数字小于减数本位数字。则需要从高位借1位（高位减1），然后再继续计算。

十进制（基数 10）

加法示例：计算 1011 + 110

bash

  1 0 1 1  
+   1 1 0  
----------  
  1 1 2 1  （步骤：从右向左逐位相加，遇10进1）

二进制（基数 2）

加法示例：计算 1011 + 110

bash

  1 0 1 1  
+   1 1 0  
----------  
1 0 0 0 1  （步骤：从右向左逐位相加，遇2进1）

八进制（基数是8）

加法示例：计算 35 + 27

bash

  3 5  
+ 2 7  
------  
  6 4  （步骤：5+7=12，12=1×8+4→本位写4，进位1；3+2+1=6→本位写6）

十六进制（基数是16）

十六进制中，每个位上的数字可以是 0-9 和 A-F（分别表示 10-15）。

加法示例：计算 A3 + 2F

bash

  A 3  
+ 2 F  
------  
  D 2  （步骤：3+15=18，18=1×16+2→本位写2，进位1；10+2+1=13→本位写D）

原码，反码，补码，移码

原码：在一串二进制机器数中，数的最高位是符号位。其中0为正符号位，1为负符号位。其余位是绝对值部分。原码主要用于早期计算机中，现在已经淘汰了。
反码：正数的反码与原码相同。负数的反码中绝对值部分相比原码是按位取反的。
补码：正数的补码与原码相同，负数的补码等于其对应反码的末尾加1。
移码：只要将补码的符号位取反，就可以得到对应的移码表示。

浮点数

规格化浮点数的数值范围如下

如果浮点数的阶码(包括1位阶符)用R位的移码表示，尾数(包括1位数符)用M位的补码表示，则这种浮点数所能表示的数值范围如下。

校验码

奇偶校验码可以检错，但不能纠错。码距为2
循环冗余校验码CRC 可以检错，但不能纠错。由两部分组成，左边为信息码（数据）。
海明码可以检错也可以纠错。奇偶校验码和CRC循环冗余校验码方法可以检错，但不能纠错。

海明码通过在数据位n之间的特定位置上插入k个校验位，通过扩大码距来实现检错和纠错。

海明码公式： 2^k^ >= n+k+1 其中数据位是n，校验位是k

三种校验码的区别

寻址方式

立即寻址：操作数在指令中的寻址方式。
寄存器寻址：操作数在寄存器中的寻址方式。
直接寻址：操作数的地址在指令中的寻址方式。
寄存器间接寻址：操作数的地址在寄存器中的寻址方式。
间接寻址：操作数的地址的地址在指令中的寻址方式。

存储器中各个寻址方式的速度对比：

立即寻址 > 寄存器寻址 > 直接寻址 > 寄存器间接寻址 > 间接寻址

指令系统

CISC与RISC

CISC 全称为Complex Instruction Set Computing 复杂指令集。

指令种类多
指令复杂度高
寻址方式复杂
通用寄存器数量一般
不支持流水线技术
采用微程序控制技术实现译码。

RISC 全称为Reduced Instruction Set Computer，精简指令集。

指令种类少
指令复杂度低
寻址方式固定
通用寄存器数量大量
支持流水线技术
采用硬布线控制逻辑来实现译码。

流水线

流水线是为了模仿工业生产过程的流水线(如汽车装配线)而提出的一种指令控制方式。

流水线执行指令时间的公式 T = NT + (K-1)t

NT是第一条指令执行的完整时间。
t 是流水线中耗时最长的哪个部分的时间。
k 是流水线中一共需要执行的指令数。

流水线的吞吐率公式 = 总的指令数 / (流水线执行指令时间) = 总的指令数 / ( NT + (K-1)t )

存储系统

高速缓存（Cache）

在计算机的存储系统体系中，Cache是（除寄存器以外）访问速度最快的。主要解决CPU与主存之间速度容量不匹配问题。

高速缓存（Cache）的各种地址映像方法

由于高速缓存Cache中的内容是与主存的内容是一一映像的。因此有多种地址映像方法。

直接映像：是指主存的块与Cache块的对应关系是一一对应的。优点是硬件电路设计简单，缺点是Cache块冲突率高。
全相联映像：允许主存的任一块可以调入Cache存储器的任何一个块的空间中。优点是Cache块冲突率低、灵活性好。缺点是访问速度慢、硬件电路设计成本太高。
组相联映像：是前两种方式的折中方案，即组采用直接映像方式、块采用全相联映像方式。

注意：主存和高速缓存Cache之间的地址映射是由硬件直接完成的。

发生块冲突从少到多的顺序：全相联映射-->组相联映射-->直接映射。

多级Cache：在多级Cache计算机中分为一级(L1Cache)，二级(L2Cache)等。

Cache的命中率与Cache容量的关系是：容量越大，命中率越高。

内存编址计算 *****

存储单元个数 = 最大地址 - 最小地址 + 1

编制内容：

按字编址: 存储体的存储单元是字存储单元，即最小寻址单元是一个字。
按字节编址：存储体的存储单元是字节存储单元，即最小寻址单元是一个字节。

总容量 = 存储单元个数 * 编制内容。

根据存储器中要求的容量和选定存储芯片的容量。就可以计算出存储器中所需要芯片的个数。

总的芯片数 = 存储器的总容量 / 每个存储芯片的容量

输入输出技术

输入/输出（I/O）控制方式有三种，分别是程序控制方式、程序中断方式和直接存储器方式（DMA）。

程序控制方式：程序控制方式是指 CPU 主动通过执行程序来查询外设的状态，判断外设是否准备好。从而为外设设备提供输入/输出服务。方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。
程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。
直接存储器存取方式（DMA）：DMA方式是指通过DMA硬件来控制内存和设置的数据交换，这种方式可以不需要CPU处理。即绕过了CPU来进行数据交换的方式。

直接内存存取 DMA

DMA全称是直接内存存取。DMA方式是为了在主存与外设之间，添加一个DMA硬件，从而实现高速、批量数据交换。

DMA方式比程序控制方式与中断方式都高效。这种方式可以不需要CPU处理。即绕过了CPU来进行数据交换的方式。

总线

一般来说，任何连接两个以上电子元器件的导线都可以称为总线。总线一般分为三类，分别是数据总线、地址总线、控制总线。

数据总线：用于传输数据的，双向的。
地址总线：用于传输CPU发出的地址数据的，是单向的。
控制总线：用于传输控制信号的，双向的。

加密技术

加密技术是最常用的安全保密手段，数据加密的技术分为对称加密和非对称加密。

对称加密：是指加密密钥和解密密钥是相同的。
非对称加密：是指加密密钥和解密密钥是不同的。

常见的对称加密算法包括：DES，3DES，RC-5，AES等

常见的非对称加密算法包括：RSA，ECC等。

常见摘要算法：MD5，SHA-1，SHA-256等。

系统可靠性

可靠性是指一个系统对于给定的时间间隔内、在给定条件下无失效运作的概率。

串联系统的可靠性：各个子系统的可靠性乘积。即 R = R1 * R2 * ....Rn
并联系统的可靠性：1减去各个子系统的不可靠性的乘积。即 R = 1 -（1-R1）（1-R2）...(1-Rn)

其中R1为子系统1的可靠性。

可靠性公式

可靠性是指一个系统对于给定的时间间隔内、在给定条件下无失效运作的概率。

记忆：可靠性公式 = t / (1+t) 其中t为平均无故障时间。

可用性公式

可用性是在给定的时间点上，一个系统能够按照规格说明正确运作的概率。

记忆：可用性公式 = t / (1+t) 其中t为平均失效间隔时间。

可维护性公式

可维护性是在给定的使用条件下，在规定的时间间隔内，使用规定的过程和资源完成维护活动的概率。

记忆：可维护性公式 = t / (1+t) 其中t为平均修复时间。

软件设计师笔记02_程序设计语言基础_精简考点

科目一考试中占6分左右。

程序语言

低级语言：机器语言，如汇编语言。
高级语言：常见的有Java，C，C++，PHP，Python，Delphi等。

汇编程序

汇编程序的作用是将汇编语言所编写的源程序翻译成机器指令程序。

汇编程序一般需要两次扫描源程序才能完成翻译过程。

第一次扫描：检查语法错误，确定符号名字；建立使用的全部符号名字表；每一符号名字后跟一个对应值（地址或数）。
第二次扫描：在第一次扫描的基础上，将符号地址转换成真地址（代真）；利用操作码表将助记符转换成相应的目标码。

解释和编译

编译程序是将源程序编译完之后,生成一个独立的可执行文件。然后再运行这个可执行文件。因此运行效率高。
解释程序不生成可执行文件，它是一边解释源程序，然后一边运行解释后的目标程序。因为解释程序一边解释一边运行，因此执行速度慢，效率低。

编译过程

注意：词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 代码优化 -> 目标代码生成。前后顺序不可更换。

速记

词法分析：扫描源程序，将一个个字符识别为一个个单词。
语法分析：将一个个单词组成一个个表达式。并分析是否有语法错误。
语义分析：将一个个表达式根据上下文环境，分析是否有语义错误。只能分析出静态语义错误，不能分析出动态语义错误。
中间代码生成：此阶段与具体机器无关。将语法分析阶段生成的语法树，转换为中间代码。
代码优化：对中间代码进行优化，提高程序的执行效率。
目标代码生成：此阶段与具体机器硬件紧密相关。将优化后的中间代码转换为与具体机器硬件相关的目标代码。

词法分析阶段

词法分析阶段是编译过程的第一个阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号（记号），并分析一个个符号是否符合程序语言的规定。

输入：源程序。
输出：记号流。

语法分析阶段

语法分析阶段是在词法分析的基础上，根据语法规则将一个个单词符号分解成各个语法单位，如“表达式”“语句”等,并分析是否符合语法规则。

输入：记号流。
输出：语法树。
语法分析阶段可以发现程序中所有的语法错误。

语法错误包含：单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误。

语法分析的几种方法
- 自上而下语法分析：最左推导，从左至右。给定文法G和源程序串r。从G的开始符号s出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出r。
- 递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法。
- 自下而上语法分析：最右推导，从右至左。从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号S。
- 移进-规约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想。

语义分析阶段

根据语法分析的结果，分析各个表达式，各个语句。检查是否包含静态语义错误,不能发现程序中所有的语义错误。

输入：语法树。

语义分析阶段可以发现静态语义错误。但不能发现动态语义错误，动态语义错误运行时才能发现。有语义错误是可以编译成功的，例如a/0；这是符合语法的，也符合静态语义，编译器检验不出来这个是错的，只有运行才会报错，也就是动态语义，动态语义错误常见的有死循环。

静态语义错误：一般是指运算符与运算对象类型不合法等错误。

动态语义错误：发生程序运行时，也叫动态语义错误。包括死循环、变量取零时做除数、引用数组元素下标越界等错误。

中间代码生成阶段

此阶段与具体机器无关。根据语义分析的结果，将源程序转换为一种中间表示形式。

例如将源程序 “int a = 5 + 3;” 转换为中间代码形式可能是 “t1 = 5 + 3; a = t1;” 利于后续处理。

代码优化阶段

代码优化阶段对中间代码进行等价变换，旨在提高目标代码的运行效率，减少运行时间和空间开销。

目标代码生成阶段

此阶段与具体机器硬件紧密相关。把中间代码转换为特定机器上的代码。例如将中间代码转换为 x86 架构下的机器指令，从而让程序能在对应硬件上运行。

注意：编译方式中的中间代码生成和代码优化不是必要的，可省略。

解释过程

如图是解释程序实现高级语言的三种方式

解释过程直接执行源程序（词法分析、语法分析、语义分析过程是有的，但是没有中间代码生成，也没有目标机器码代码），其最大的特点是不产生目标程序代码，并且程序每执行一次就要解释一次，运行效率低。

总结

编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。
解释方式：词法分析、语法分析、语义分析。

编译和解释都不可省略词法分析、语法分析、语义分析且顺序不可交换。

背诵点

语法错误：单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误。
静态语义错误：一般是指运算符与运算对象类型不合法等错误。
动态语义错误：发生程序运行时，也叫动态语义错误。包括死循环、变量取零时做除数、引用数组元素下标越界等错误。

符号表

符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地査找、插入、修改和删除等操作。

符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段

正规式

正规文法，表示的语言集合是正规集，正规集的规律可以用正规式表示。

案例1

2018年上半年

下图所示为一个不确定有限自动机(NFA)的状态转换图。该NFA识别的字符串集合可用正规式（）描述。

A ab*a
B (ab)*a
C a*ba
D a(ba)*

正确答案：A

解析：

A. (ab^*a)：表示一个a，接着0个或多个b，再一个a，与 NFA 路径规律完全一致。
B. ((ab)^*a)：表示ab重复多次后接a（如(abab\cdots a)），但 NFA 中b可单独重复，并非固定ab组合重复，不符合。
C. (a^*ba)：开头允许a出现多次，但 NFA 中开头是一个a，并非多次，不符合。
D. (a(ba)^*)：表示a后接ba多次重复（如(ababa\cdots)），与 NFA 路径不匹配，不符合。

案例2

某有限自动机的状态转换图如下图所示，与该自动机等价的正规式是（）。

A (0|1)*
B (0|10)*
C 0*(10)*
D 0*(1|0)*

正确答案：B

分析选项 A：((0|1)^*) 表示任意 0 和 1 的组合（包括空串）。但自动机中，若输入 11，从 (q_0) 输入 1 到 (q_1)，再输入 1 无转换路径，无法识别，排除。
分析选项 B：((0|10)^*) 表示由 0 或 10 重复任意次组成。输入 0 时，在 (q_0) 循环，可识别。输入 10 时，1 使状态从 (q_0) 到 (q_1)，0 使状态从 (q_1) 回到 (q_0)，可识别。对于 0 或 10 的任意组合（如 010、100、1010 等），均可通过自动机状态转移识别，符合。
分析选项 C：(0^(10)^) 表示先有任意个 0，然后是任意个 10。但自动机可识别如 101（1 到 (q_1)，0 回 (q_0)，再 1 到 (q_1)），而该正规式不允许中间有单独的 1，排除。
分析选项 D：(0^(1|0)^) 类似 A，表示任意 0 和 1 的组合，存在如 11 无法被自动机识别的情况，排除。

案例3

由字符a、b构成的字符串中，若每个a后至少跟一个b，则该字符串集合可用正规式表示为（）。

A （b|ab）*
B （ab*）*
C （ab）*
D （a|b）

正确答案为 A

选项 A：((b|ab)^)ab 表示 “a 后紧跟一个 b”，b 表示单独的 b。((b|ab)^) 表示由 b 或 ab 重复任意次组成，确保每次出现 a 时，后面必有 b，符合题意。
选项 B：((ab^)^)(ab^*) 表示 “a 后接零个或多个 b”，可能出现 a 后无 b 的情况（如 a 单独出现），不满足 “每个 a 后至少跟一个 b”，排除。
选项 C：((a^b^)^)(a^) 表示零个或多个 a，(b^*) 表示零个或多个 b，可能出现连续 a 后无 b 的情况（如 aa），排除。
选项 D：((a|b))仅表示单个 a 或单个 b，无法表示任意长度的字符串，排除。

有限自动机

有限自动机是词法分析的一个工具，它能正确地识别正规集。

如图所示 ruankao_20250507110854654

主要有五个符号集，由上图示例，可知用状态来表示十分清晰，由s输入一个0，可得出B，依次类推.

一般考试，给出一个状态图，问能否构造出001这样的字符串，解决方法就是从起始s到终点f之间是否有一条路，权值为001。本质就是有向图从起点到终点的遍历。

确定的有限自动机(DFA):对每一个状态来说识别字符后转移的状态是唯一的
不确定的有限自动机(NFA):对每一个状态来说识别字符后转移的状态是不唯一的

确定的有限自动机和不确定的有限自动机的区别

输入一个字符，看是否能得出唯一的后继，若能，则是确定的有限自动机。否则若得出多个后继，则是不确定的有限自动机。

案例1

[2018年下半年] 下图所示为一个不确定有限自动机（NFA）的状态转换图。该NFA可识别字符串（）。

A 0110 B 0101 C 1100 D 1010

正确答案：A

主要考查点如下：不确定有限自动机（NFA）的状态转换：要求考生理解 NFA 状态转换图中节点（状态）和边（状态转换条件，包括输入字符和(\varepsilon)转换）的含义。根据输入字符串，依据状态转换规则在图中进行状态转移，判断能否从初始状态到达终态。

(\varepsilon)转换的处理：(\varepsilon)转换是 NFA 的一个特性，即不需要输入字符就可以进行状态转移。考生需要掌握在状态转移过程中如何处理(\varepsilon)转换，这是准确判断 NFA 识别字符串能力的关键。

解题思路

对于选项 A（0110）：从初始状态0开始，输入字符0，根据状态转换图可转移到状态1。接着有(\varepsilon)转换，可从状态1转移到状态2。输入字符1，从状态2转移到状态3。又有(\varepsilon)转换，从状态3转移到状态4。再输入字符1，仍在状态4（因为状态4输入1无明确转移，可认为保持在状态4 ），之后有(\varepsilon)转换到状态4 。最后输入字符0，从状态4转移到终态5 ，所以该 NFA 能识别字符串0110 。
对于选项 B（0101）：按照上述状态转移方式，当输入到最后一个字符1时，无法从当前状态转移到终态5 ，所以该 NFA 不能识别此字符串。
对于选项 C（1100）：从初始状态0开始，输入第一个字符1时，没有从状态0输入1的转移路径，所以该 NFA 不能识别此字符串。
对于选项 D（1010）：同样，从初始状态0开始，输入第一个字符1时，没有从状态0输入1的转移路径，该 NFA 不能识别此字符串。

记忆方法图形化理解：把 NFA 的状态转换图当作地图，状态是地点，边是路径，输入字符是沿着路径行走的指令。(\varepsilon)转换就像是不需要特定指令就能走的 “秘密通道”。这样形象化的理解有助于记忆状态转移规则。

案例2

[2016年上半年] 某确定的有限自动机（DFA）的状态转换图如下图所示（A是初态，C是终态），则该DFA能识别（）。

A aabb B abab C baba D abba

解题思路

对于选项 A（aabb）：从初始状态A开始，输入第一个字符a，根据状态转换图，转移到状态B。输入第二个字符a，在状态B下，输入a又回到状态B。输入第三个字符b，从状态B转移到状态C。输入第四个字符b，在状态C下，没有输入b的转移路径，所以该 DFA 不能识别字符串aabb。
对于选项 B（abab）：从初始状态A开始，输入第一个字符a，转移到状态B。输入第二个字符b，从状态B转移到状态C。输入第三个字符a，在状态C下，输入a转移回状态B。输入第四个字符b，从状态B转移到状态C，最终到达终态C，所以该 DFA 能识别字符串abab。
对于选项 C（baba）：从初始状态A开始，输入第一个字符b，在状态A下没有输入b的转移路径，所以该 DFA 不能识别字符串baba。
对于选项 D（abba）：从初始状态A开始，输入第一个字符a，转移到状态B。输入第二个字符b，从状态B转移到状态C。输入第三个字符b，在状态C下，没有输入b的转移路径，所以该 DFA 不能识别字符串abba。

函数调用传值

当在一个函数中需要使用另一个函数时，称为函数调用。函数调用分为值调用和引用调用。

传值调用：将实参的值传递给形参，实参可以是变量、常量和表达式。不可以实现形参和实参之间的双向传递数据。
传引用（地址）调用：将实参的地址传递给形参，形参必须有地址，实参不能是常量（值）、表达式。可以实现形参和实参间双向传递数据的效果，即改变形参的值同时也改变了实参的值。

文法

一般的程序设计语言属于上下文无关文法。

文法案例题1

[2013年下半年] 己知文法G: S→A0|B1，A→S1|1, B→S0|0,其中S是开始符号。从S出发可以推导出（）。

A 所有由0构成的字符串 B 所有由1构成的字符串 C 某些0和1个数相等的字符串 D 所有0和1个数不同的字符串

正确答案：C

本题考点：要求考生掌握根据给定的文法产生式（如本题中 (S \to A0|B1)、(A \to S1|1)、(B \to S0|0) 这些产生式规则）进行推导，通过不断替换非终结符（S、A、B 为非终结符）来得到终结符组成的字符串（由 0 和 1 组成）。语言与文法关系理解：理解文法所定义的语言，即从开始符号 S 出发，通过推导能够得到的所有字符串的集合。考生需要分析推导过程中字符串的特征，从而判断文法所产生的语言类型。

解题思路

对选项 A 分析：若要得到仅由 0 构成的字符串，从给定文法推导，由于产生式中有 A 相关产生式会引入 1（如 (A \to S1|1) ），B 相关产生式也会引入与 1 相关的推导路径（因为 (B \to S0|0) 且 S 可推导到含 1 的式子），所以无法只推导出全是 0 的字符串，A 选项错误。
对选项 B 分析：同理，因为有产生式会引入 0（如 (B \to S0|0) ），所以不能只推导出全是 1 的字符串，B 选项错误。
对选项 C 分析：例如 (S \to A0)，(A \to 1) 时得到 10 ；(S \to B1)，(B \to 0) 时得到 01 ；还可以进一步推导如 (S \to A0)，(A \to S1)，(S \to B1)，(B \to 0) ，得到 0110 等，能推导出一些 0 和 1 个数相等的字符串，C 选项正确。
对选项 D 分析：由前面 C 选项的推导可知，能得到 0 和 1 个数相等的字符串，并非所有 0 和 1 个数不同的字符串，D 选项错误。

记忆方法：把文法推导想象成一种规则游戏，产生式就是游戏规则，非终结符是可替换的 “牌”，通过不断按照规则替换 “牌”（非终结符）得到最终的 “牌面”（终结符字符串）。这样能帮助理解推导过程，而不是死记硬背规则。

表达式

在考试当中，该知识点的考查，通常形式是给出一个表达式的中缀表达形式（或前缀、后缀），让考生将其转换为前缀或后缀表达形式。

记忆背诵方法如下

记住 “前缀运算符在前，中缀运算符在中，后缀运算符在后” 这个关键区别。
也要注意运算符的优先级。

中缀表达式

中缀表达式：运算符位于操作数中间，是人们常用的算术表示方法，如 “(3 + 4) × 5 - 6”。

前缀表达式

前缀表达式：运算符位于操作数之前，也称为波兰式。如 “- × + 3 4 5 6” 是前缀表达式，等价于中缀表达式 “(3 + 4) × 5 - 6”。

推导过程：

“(3 + 4) × 5 - 6”
“(+34)x5-6”
“x(+34)5-6”
“-x(+34)56”
“-x+3456”

后缀表达式

运算符位于操作数之后，也称为逆波兰式。如 “3 4 + 5 × 6 -” 是后缀表达式，等价于中缀表达式 “(3 + 4) × 5 - 6”。

推导过程：

“(3 + 4) × 5 - 6”
“(34+)x5-6”
“(34+)5x-6”
“(34+)5x6-”
“34+5x6-”

真题

在 Python 语言中，语句x=（1）不能定义一个元组。x=(1,)可以定义为一个元组。
关于 Python 语言的叙述中，不正确的是（可以用if...else和switch...case语句表示选择结构）
某python程序中定义了X=【1，2】，那么X*2的值为（【1，2，1，2】）
Python 中采用（ type（））方法来获得一个对象的类型。
在Python语言中，（ tuple（元组））是一种不可变的、有序的序列结构，其中元素可以重复
Python语言的特点不包括（编译型）。Python属于解释型而非编译型程序设计语言。
在Python3中，表达式list（ range （）【10:0:-2】的值为（ [10,8,6,4,2] ）。
Java语言符合的特征有（采用即时编译，对象在堆空间分配）和自动的垃圾回收处理。
在运行时将调用和响应调用所需执行的代码加以结合的机制是（动态绑定）。
对布尔表达式a or ((cb<c) and d)求值时，（ a为true ）时可进行短路计算。
以下关于程序设计语言的叙述中，错误的是（程序中局部变量的值在运行时不能改变）。
更适合用来开发操作系统的编程语言是（ C/C++ ）。
在高级语言源程序中，常需要用户定义的标识符为程序中的对象命名，常见的命名对象有（ ②变量③函数④数据类型）
以下关于传值调用与引用调用的叙述中，正确的是（在传值调用方式下，实参可以是变量，也可以是常量和表达式。在引用调用方式下，可以实现形参和实参间双向传递数据的效果）。
（ Lisp ）是一种函数式编程语言。
己知文法G: S→A0|B1，A→S1|1, B→S0|0,其中S是开始符号。从S出发可以推导出（某些0和1个数相等的字符串）。
在仅由字符a、b构成的所有字符串中，其中以b结尾的字符串集合可用正则表达式为（ (a|b)*b ）。
用C/C++语言为某个应用编写的程序，经过（预处理、编译、汇编、链接）后形成可执行程序。
C程序中全局变量的存储空间在（静态数据区）分配。
在程序运行过程中，（将整型变量与浮点型变量相加）时涉及整型数据转换为浮点型数据的操作。
在对高级语言源程序进行编译的过程中，为源程序中变量所分配的存储单元的地址属于（逻辑地址）。
在程序的执行过程中，系统用（栈）实现嵌套调用(递归调用)函数的正确返回。
以下关于可视化程序设计的叙述中，错误的是（可视化程序设计使开发应用程序无需编写程序代码）。
面向对象程序设计语言C++、JAVA中，关键字（ this ）可以用于区分同名的对象属性和局部变量名。
某些程序设计语言中，在运行过程中当一个对象发送消息请求服务时，根据接收对象的具体情况将请求的操作与实现的方法进行连接，称为（动态绑定）。
绑定是一个把过程调用和响应调用所需要执行的代码加以结合的过程。在一般的程序设计语言中，绑定在编译时进行，叫做（静态绑定）；而（动态绑定）则在运行时进行，即一个给定的过程调用和执行代码的结合直到调用发生时才进行。
多态分为参数多态、包含多态、过载多态和强制多态四种不同形式，其中（包含）多态在许多语言中都存在，最常见的例子就是子类泛型化。
采用继承机制创建子类时，子类中（可以有新的属性和行为）。
聚合对象是指一个对象（包含其它对象）。
同一消息可以调用多种不同类的对象的方法，这些类有某个相同的超类，这种现象是（多态）。
以下关于实现高级程序设计语言的编译和解释方式的叙述中，正确的是（在编译方式下产生源程序的目标程序，在解释方式下不产生）。
计算机执行程序时，内存分为静态数据区、代码区、栈区和堆区。其中（栈区）一般在进行函数调用和返回时由系统进行控制和管理，（堆区）由用户在程序中根据需要申请和释放。
移进—归约分析法是编译程序（或解释程序）对高级语言源程序进行语法分析的一种方法，属于（自底向上（或自下而上））的语法分析方法。
编译过程中进行的语法分析主要是分析（程序语句的结构是否合法）。
将高级语言程序翻译为机器语言程序的过程中，常引入中间代码，其好处是（利于进行与机器无关的优化处理）。
以下关于语言L={anbn|n>=1}的叙述中，正确的是（不能用正规式表示，也不能通过有限自动机识别）。
对高级语言源程序进行编译的过程中，有限自动机(NFA或DFA)是进行（词法分析）的适当工具。
己知文法G: S→A0|B1，A→S1|1, B→S0|0,其中S是开始符号。从S出发可以推导出（某些0和1个数相等的字符串）。
对于大多数通用程序设计语言，用（上下文无关文法）描述其语法即可。
运行下面的C程序代码段 int k=0;for(;k<100;);{k++;}，会出现（动态语义错误）错误。
在某C/C++程序中，整型变量a的值为0且应用在表达式“c=b/a”中，则最可能发生的情形是（运行时产生异常）。
语法制导翻译是一种（静态语义分析）方法。
在C程序中有些变量随着其所在函数被执行而为其分配存储空间，当函数执行结束后由系统回收。这些变量的存储空间应在（栈区）分配。
许多程序设计语言规定，程序中的数据都必须具有类型，其作用不包括（便于定义动态数据结构）。
语言L={ambn|m≥0,n≥1}的正规表达式是（ abb ）

软件设计师笔记03_数据结构_精简考点

科目一考试中占5分左右。

线性表

线性表常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动 (n-1)/2 个元素。
当线性表进行顺序存储时，逻辑上相邻的元素，其物理位置也相邻。此时查询元素的时间复杂度为O(1)，也就是常量级。此时插入元素就需要移动一些元素了，因此插入元素的时间复杂度为O(n)，其中n为线性表的长度。
当线性表进行链式存储时，逻辑上相邻的元素，其物理位置不要求相邻。此时查找元素和插入元素的时间复杂度都为O(n)。

单向循环链表由于指针方向是单向的。因此访问其直接后继的运算时间复杂度为O(1)，访问其直接前驱的运算时间复杂度为O(n)。

栈

栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此实现函数或过程的递归调用及返回处理时必须用栈。
表达式采用逆波兰式(后缀式)表示时，利用（栈）进行求值。

存放操作数的栈的容量

如何计算存放操作数的栈的至少容量：

先将表达式转换为后缀式。
然后看后缀式中的第一个运算符号前的操作数个数。那就是存放操作数的栈的至少容量。

例题

当利用栈对算术表达式10*(40-30/5)+20求值时，存放操作数的栈(初始为空)的容星至少为__,才能满足暂存该表达式中的运算数或运算结果的要求。

解法

先将表达式转换为后缀式 10 40 30 5 / - * 20 +
然后看后缀式中的第一个运算符号前的操作数个数。那就是存放操作数的栈的容量。
后缀式 10 40 30 5 / - * 20 + 中第一个运算符号前的操作数个数是4个。

则存放该操作树的栈的容量为4

队列

循环队列中求队头元素的指针的计算公式为：(rear-len+1+M) % M 其中rear是队尾指针，len是队列长度，M是队列存储容量。
必须采用队列结构的是打印序列。

真题案例1

输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出，如下图所示，若有e1,e2,e3,e4依次进入输出受限的双端队列，则得不到输出序列（）。

A e4,e3,e2,e1
B e4,e2,e1,e3
C e4,e3,e1,e2
D e4,e2,e3,e1

正确答案是D

选项 A：e4,e3,e2,e1 输入过程：让e1、e2、e3、e4依次从左端输入队列。输出过程：由于只能从一端输出，此时队列中元素顺序从左到右为e4 e3 e2 e1。按照先进后出原则，依次输出e4、e3、e2、e1，该输出序列可以得到。
选项 B：e4,e2,e1,e3输入过程：先让e1、e2从左端输入，e3 从右端输入 e4再从左端输入。此时队列中元素顺序从左到右为e4 e2 e1 e3。按照先进后出原则，依次输出e4,e2,e1,e3。该输出序列可以得到。
选项 C：e4,e3,e1,e2输入过程：让e1、e2从左端输入，e3、e4从右端输入。此时队列中元素顺序从左到右为e4,e3,e1,e2。按照先进后出原则，依次输出e4,e3,e1,e2。该输出序列可以得到。
选项 D：e4,e2,e3,e1输入过程：尝试各种从两端输入元素的方式。若要先输出e4，e4需最后进入队列且在队尾（输出端）。矛盾分析：若e4在队尾，当输出e4后，接下来要输出e2，由于只能从一端输出，在e4输出后，要输出e2，则e2需在队尾，但此时若e2在队尾，e3就无法在e2之前输出，所以无法得到该输出序列。

二维数组

二维数组的特点如下：

数据元素数目固定。
数据元素具有相同的类型。
数据元素的下标关系具有上下界约束且下标有序。

一个m行n列的数组表示如下

数组存储地址的计算公式

假设每个数组元素占用内存长度为len，起始地址为a，存储地址计算如下：

案例1

在一个二维数组A中，假设每个数组元素的长度为3个存储单元，行下标i为0-8，列下标j为0-9，从首地址SA开始连续存放，在这种情况下，元素A[8][5]的起始地址为（）。

A SA+141
B SA+144
C SA+222
D SA+255

正确答案：D

二维数组按行优先存储，即先存储完一行的所有元素，再存储下一行。

那么元素A[8][5]是二维数组中的第86个元素。

元素A[8][5]的起始地址 SA + 85 * 3 = SA + 255

矩阵

三对角矩阵公式如图所示

真题范例1

设有n阶三对角矩阵A，即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上，现对该矩阵进行按行压缩存储，若其压储空间用数组B表示，A的元素下标从0开始，B的元素下标从1开始。已知A[0,0]存储在B[1]，A[n-1,n-1]存储在B[3n-2]，那么非零元素A[i，j](0≤i<n，0≤j<n，|i-j|≤1)存储在B[（）]。

A 2i+j-1 B 2i+j C 2i+j+1 D 3i-j+1

正确答案：C

n阶三对角矩阵如下图所示。

在元素ai,y之前共有i行（行号从0到i-1 )，除了第一行外，其余每行都是3个元素, 因此这i行上的元素个数为(3*i-1);在行号为i时，排列在ai,y之前的元素个数为j-i+1, 合计2i+j个元素，因此元素ai,y存储在B[]中的下标为2i+j+1(因数组B是从下标1开始存放元素的）。

真题范例2

某n阶的三对角矩阵A 如下图所示，按行将元素存储在一维数组M中，设a1,1存储在M[1]，那么ai,j (1<=i，j<=n且ai,j位于三条对角线中)存储在M（）。

A i+2j B 2i+j C i+2j-2 D 2i+j-2

按行存储时，aij之前有i-1行，除了第一行外，每行有3个元素，在第i行上，其之前有j-i+1个元素，因此aij之前共有(i-1)*3-1+j-i+1=2i+j-3个元素，由于ai,1存储在M[1]，所以 ai,j存储在M[2i+j-3+1]。

树

树的基本概念

树的深度。一棵树的最大层数为该树的深度（或高度）。
结点的度。一个结点拥有子树的个数称为该结点的度。
叶子结点。叶子结点是指度为 0 的结点。
结点的层次。该结点所在树中的层次，即为该结点的层次。
有序/无序树。如果树中各结点的各个子树是从左到右有序排列且不能交换时，则称该树为有序树。否则称为无序树。

二叉树

二叉树与普通树的区别在于，每个节点最多只有两个孩子结点。二叉树中结点的子树分为左子树和右子树。

二叉树的性质

一个深度为k的二叉树最多有 2^k^-1 个结点（k>=1）。
在二叉树的第i层上最多有个 2^(i-1)^ 个结点(i>=1)。
对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。即度为0的结点数比度为2的结点数多1个。

特殊的二叉树

满二叉树

如果一个二叉树的层数为 K，结点总数为 2^k^ - 1 个，则它就是满二叉树，如图a所示。

完全二叉树

在一个深度为 h 的完全二叉树中，除第 h 层外（最后一层），其他各层都是满的。第 h 层所有的结点都必须从左到右依次放置，不能留空，如图 b 所示。则这样的二叉树为完全二叉树。

平衡二叉树

平衡二叉树：树中任一结点的左右子树高度之差不超过1。

查找二叉树

查找二叉树：又称之为排序二叉树。任一结点的权值，大于其左孩子结点，小于其右孩子结点。中序遍历结果有序。

二叉树的存储结构

顺序存储

二叉树的顺序存储结构：顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。

在采用顺序存储时，完全二叉树与一般的二叉树相比节省了空间，这是因为一般二叉树需要添加一些“虚结点”而造成了空间的浪费，如图所示。

链式存储

二叉树的链式存储结构：一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针。每个二叉链表节点存储一个二叉树节点，头指针则指向根节点

在采用链式存储时，二叉树的链式存储可以分为二叉链表和三叉链表的存储结构，如图所示

对于完全二叉树，若某个节点在数组中的存储位置为i，则其左孩子的存储位置为2i，右孩子的存储位置为2i+1。

二叉树的遍历

二叉树是一个非线性结构，而对二叉树的遍历本质上是对一个非线性结构进行线性访问的过程。通过这种遍历，可以将二叉树这种非线性结构的数据转换为线性结构的数据，从而方便存储或处理等操作。

二叉树的遍历可以分为前序、中序、后序和层次遍历四种形式。这四种遍历方式产生的结果如图所示。

先序（前序）遍历：根左右
中序遍历：左根右
后序遍历：左右根
层次遍历：按层次，从上到下，从左到右

二叉树的构造（通过遍历的序列）

单独一个序列无法确定一个二叉树。唯有根据先序遍历和中序遍历或后序遍历和中序遍历才能唯一确定一个二叉树。

必须是中序遍历搭配其他序列才能唯一确定一个二叉树。

根据先序遍历和中序遍历构造二叉树

根据先序遍历和中序遍历构造二叉树的过程如下：

先序遍历的第一个节点就是根节点
在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
递归地对左子树和右子树进行构造

根据后序遍历和中序遍历构造二叉树

根据后序遍历和中序遍历构造二叉树的过程如下：

后序遍历的最后一个节点就是根节点
在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
递归地对左子树和右子树进行构造

根据层序遍历和中序遍历构造二叉树

根据层序遍历和中序遍历构造二叉树的过程如下：

层序遍历的第一个节点就是根节点
在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
递归地对左子树和右子树进行构造

最优二叉树（哈夫曼树）

哈夫曼树又称为最优二叉树，是一种带权路径长度最短的二叉树。

所谓树的带权路径长度，就是树中所有的叶子结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶子结点到根结点的路径长度为叶子结点的层数）。

基本概念

权：节点代表的值
路径是从树中一个结点到另一个结点之间的通路，路径上数目称为路径长度。
结点的路径长度：路径上的分支数目
结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值
树的带权路径长度：根节点到达每一个叶子节点之间的带权路径长度之和

树的带权路径长度（WPL）：树中所有叶子节点的带权路径长度之和。

真题范例1

对下面的二叉树进行顺序存储(用数组MEM表示)，已知结点A、B、C在MEM中对应元素的下标分别为1、2、3，那么结点D、E、F对应的数组元素下标为（）。

A 4、5、6 B 4、7、10 C 6、7、8 D 6、7、14

正确答案D

二叉树顺序存储规则：对于完全二叉树，若根节点下标为i（本题中根节点A下标为1 ），则其左孩子节点下标为2i，右孩子节点下标为(2i + 1) 。

节点D：节点C下标为3，D是C的左孩子，根据规则，D的下标为 2x3=6。
节点E：E是C的右孩子，其下标为 2x3+1=7。
节点F：F是D的右孩子，D下标为6，所以F的下标为 2x6+1=14。
综上，节点D、E、F对应的数组元素下标为6、7、14，答案选 D。

构造最优二叉树（哈夫曼算法）

如何构造最优二叉树？构造最优二叉树的哈夫曼算法步骤如下。

假设有一组给定的权值集合 F，集合 F 里面包含一些权值节点。（比如{w₁, w₂, ..., wₙ}）。我们需要用这些权值节点构建一个最优二叉树。
第一步：
- 从集合F 中选择两个权值最小的节点。将它们作为左、右子树构造一棵新的二叉树，新树的根节点的权值为这两个节点的权值之和。
- 把集合F 中删除这两个节点。并将新树根节点的权值加入到集合 F 中。
第二步：
- 从集合 F 剩下的节点中再次选择两个权值最小的节点，将它们作为新树的左、右子树，新树的根节点的权值为这两个节点的权值之和。
- 把集合F 中删除这两个节点。并将新树根节点的权值加入到集合 F 中。
重复上面步骤，直到所有节点都被合并为一棵树。

注意：

在构造新树的过程中，对于选出的两个权值节点，哪个作为左子树、哪个作为右子树并没有明确规定。这就导致：对于相同的一组权值，可能会构造出不同形状的最优二叉树。不过，不管形状如何变化，这些树的带权路径长度（WPL值）都是相同的，这是由权值本身决定的。
建议，每次选择两个权值最小的节点时，先选择权值较小的节点作为左子树，权值较大的节点作为右子树。

图

图是比树结构更复杂的一种非线性结构。

图的种类

无向图：图的顶点之间连接线是没有箭头的，不分方向。如图所示。
有向图：图的顶点之间连接线是箭头，表示从一个节点到另一个节点。如图所示。
无向完全图：在无向图中，若每个顶点都与其他顶点之间都有一条边相连，则称该图为无向完全图。无向完全图的n个结点的连线数为(n-1)+(n-2)+...+1 = n(n-1) / 2;
有向完全图：在有向图中，若每个顶点都与其他顶点之间都有两条有向边互相相连，则称该图为有向完全图。即顶点两两之间都有互通的两个箭头，则 n个节点有向完全图的的连线数为n(n-1)

图的基础概念

度：顶点的度是关联与该顶点的边的数目。若在有向图中，一个顶点的度为该顶点的出度和入度之和。
出度是以该顶点为起点的有向边的数目。
入度是以该顶点为终点的有向边的数目。
路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的。

连通图：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。

连通分量：无向图G中的极大连通子图称为其连通分量。

强连通图：针对有向图。若有向图任意节个顶点间都互相存在路径即存在v到u，也存在u到v的路径，则称为强连通图。

强连通分量：有向图G中的极大连通子图称为强连通分量。

网：若图中的边带有权值，则称该图为网。

图的遍历特点

深度优先遍历

深度优先遍历：从任一顶点出发，遍历到底，直至返回。再选取任一其他节点出发，重复这个过程直至遍历完整个图。

如图所示

深度优先遍历的时间复杂度

当图使用邻接矩阵表示时，深度优先搜索遍历该图的时间复杂度为O(n^2^)
当图使用邻接链表来表示时，深度优先搜索遍历该图的时间复杂度为O(n+e)。其中n为节点数，e为边数。

广度优先遍历

广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

广度优先遍历的时间复杂度

广度优先遍历和深度优先搜索遍历图的时间复杂度相同，其不同之处仅仅在于对顶点的访问次序不同。

查找

顺序查找的平均查找长度为 (n+1) / 2。

排序

稳定的排序方法：冒泡排序，直接插入排序。

常见排序方法对比如图所示

软件设计师笔记04_操作系统_精简考点

科目一考试中占7分左右。

基本概念

操作系统的定义

操作系统定义：能有效地组织和管理系统中的各种软硬件资源；合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。

操作系统的作用

通过资源管理提高计算机系统的效率
改善人机界面向用户提供友好的工作环境

操作系统的特征

操作系统的4个特征是并发性、共享性、虚拟性和不确定性。

操作系统的功能

操作系统的功能可分为进程管理、存储管理、文件管理、设备管理、作业管理。

操作系统的分类

批处理操作系统
分时操作系统（轮流使用CPU工作片）
实时操作系统（快速响应）
网络操作系统
分布式操作系统（物理分散的计算机互联系统）
微机操作系统（Windows）
嵌入式操作系统

计算机的启动流程

计算机启动的基本流程为：BIOS——>主引导记录——>操作系统

进程管理

基本概念

进程是系统进行资源分配和调度的一个独立单位。

进程的组成

进程通常由程序块，数据块，进程控制块（PCB）组成。

进程控制块PCB（是进程的唯一标志）
程序块（描述进程要做什么）
数据块（存放进程执行时所需数据）

进程的基础状态模型-三态图

进程一般有3中基础状态：运行，就绪和阻塞。

就绪：一个进程获得了除CPU以外的所有资源，一旦得到CPU资源就可以运行。此时的进程处于就绪状态。
运行：当一个进程得到了CPU资源时，则表示该进程正在系统上运行。此时的进程处于运行状态。
阻塞：阻塞也称等待或睡眠状态。一个进程正在等待某一事件发生（例如正在请求其他资源）而暂时停止运行，这时即使把CPU资源分配给进程也无法运行，故称该进程处于阻塞状态。

注意：运行可以直接转换为就绪或阻塞。就绪状态只能转换为运行状态，阻塞状态只能转换为就绪状态。

进程的复杂状态模型-五态图

事实上，对于一个实际的系统，进程的状态及其转换更为复杂。如图所示，引入新建状态和终止状态。

新建：对应一个进程刚刚被创建时没有被提交的状态，并等待系统完成创建进程的所有必要信息。
终止：对应一个进程运行完毕的状态。

注意：运行可以直接转换为就绪或等待或终止，就绪只能转换为运行，等待只能转化为就绪。

进程调度

进程调度方式分为可剥夺和不可剥夺两种。
- 可剥夺式是指当有更高优先级的进程到来时，强行将正在运行进程的 CPU分配给高优先级的进程；
- 不可剥夺式是指当有更高优先级的进程到来时，必须等待正在运行进程自动释放占用的CPU，然后将CPU分配给高优先级的进程。

进程调度算法

常用的进程调度算法有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。

先来先服务调度算法：是指按照进程到达的先后顺序进行调度，先到达的进程先执行，后到达的进程后执行。
时间片轮转调度算法：是指给每个进程分配一个固定的时间片，在该时间片内进程执行。时间片结束后则将CPU资源分配给其他进程。
优先级调度算法：是指给每个进程分配一个优先级。优先级高的进程先执行，优先级低的进程后执行。
多级反馈调度算法：该算法是将时间片轮转调度算法和优先级调度算法相结合。将进程分为多个队列，每个队列有不同的优先级，进程可以在不同队列之间进行迁移，根据进程的行为和优先级进行调度。

真题示例

在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4 (假设进程按此顺序到达)，其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。若P1 时间片到了，则P1、P2、P3和P4的状态应分别为（）。

A 等待、就绪、等待和等待 B 运行、就绪、运行和等待 C 就绪、运行、等待和等待 D 就绪、就绪、等待和运行

解题思路：

P1 状态：因为时间片到了，P1 不能继续占用 CPU ，它从运行状态转变为就绪状态，等待下一次被调度执行。
P2 状态：在先来先服务调度算法下，P2 在就绪队列中等待，且 P1 时间片到了释放了 CPU ，按照先来先服务的规则，P2 将获得 CPU 进入运行状态。
P3 和 P4 状态：P3 等待打印机，P4 等待扫描仪，它们所等待的资源未得到满足，依然处于等待状态。

真题示例

在单处理机计算机系统中有1台打印机、1台扫描仪，系统采用先来先服务调度算法。假设系统中有进程P1、P2、P3、P4,其中P1为运行状态，P2为就绪状态，P3等待打印机，P4等待扫描仪。此时，若P1释放了扫描仪，则进程P1、P2、P3、P4的状态分别为（）。

本题解题关键在于理解进程状态以及先来先服务调度算法的特点，具体思路如下：

分析 P1 状态：P1 释放扫描仪，只是释放了占用的资源，它本身仍在运行，所以 P1 还是运行状态。
分析 P2 状态：系统采用先来先服务调度算法，P2 处于就绪状态且在就绪队列中等待，在 P1 未结束运行且无更高优先级抢占情况下，P2 只能继续等待，状态依旧是就绪。
分析 P3 状态：P3 等待打印机，P1 释放的是扫描仪，与 P3 等待的资源无关，所以 P3 仍处于等待打印机的等待状态。
分析 P4 状态：P4 等待扫描仪，P1 释放了扫描仪，满足 P4 等待的资源条件，P4 从等待状态变为就绪状态，等待被调度执行

进程通信

进程间的同步与互斥

进程同步与互斥

即通过信号量协调进程间的执行顺序，保证进程按正确的先后顺序执行。通过前驱图确定进程之间的先后关系，然后利用 PV 操作来实现这种同步关系。

信号量机制是一种用于控制进程间同步和互斥的机制。

PV操作是用来操作信号量的方式。

信号量（⭐⭐⭐）

信号量是一种用于控制进程间同步和互斥的机制。

信号量是一个整型变量（通常用S表示），用于描述系统中某类资源的可用数量或某个事件的状态。其值的含义如下：

S > 0：表示当前可用的资源数量（或可继续执行的进程数）；
S = 0：表示资源已耗尽（或事件未发生）；
S < 0：表示等待该资源的进程数（绝对值为等待队列中的进程数）。

信号量S的物理意义：当 S ≥ 0 时表示某资源的可用数量，若 S < O，则表示其绝对值表示阻塞队列中等待该资源的进程数量。

PV操作（⭐⭐⭐）

PV 操作是对信号量的原子操作（不可中断的操作），用于实现进程的同步与互斥：

P 操作：表示申请一个资源；
V 操作：表示释放一个资源。

PV 操作的具体逻辑

P(S) 操作
- 1. 将信号量S的值减 1（S = S - 1）, 即先申请并锁定资源；
- 1. 若S ≥ 0：表示资源够，则该进程可继续执行（成功获取资源）；
- 1. 若S < 0：表示资源不够，则该进程进入等待队列（该线程转为阻塞状态，等待资源释放）。
V(S) 操作
- 1. 将信号量S的值加 1（S = S + 1）, 即先释放资源；
- 1. 若S > 0：无等待进程，继续执行；
- 1. 若S ≤ 0：从等待队列中唤醒一个进程（使其就绪）。

P操作的定义：S=S-1。当某个资源的信号量S >= 0时，执行P操作，将该资源的信号量S减1；当某个资源的信号量S < 0时，由于该资源的信号量S为负数，说明该资源当前不可用，需要等待其他进程释放资源。

V操作定义: S=S+1。若S>0，则执行V操作的进程继续执行;若S ≤ 0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

前趋图与PV操作

在前趋图中，针对箭线标注信号量，箭线的起点位置是V操作（即前趋活动完成后以V操作通知后继活动）；箭线的终点位置是P操作（即后继活动开始前以P操作检查前趋活动是否完成）。

真题示例

解题思路：

先在前趋图中给每个箭头画上P操作和V操作。其中箭头起点为V操作，箭头终点为P操作。
然后对前趋图中的箭头，按从左到右，从上到下的顺序。依次标注上信号量。

分析进程间的依赖关系：从前驱图可知，P1 执行完后 P2 才能执行，P2 执行完后 P3 和 P4 才能执行，P3 和 P4 执行完后 P5 才能执行。

根据前驱图，P1进程运行完需要V(S1)操作通知P2进程，所以空①应填V(S1)。
P2进程运行完需要利用V(S2)、V(S3)操作分别通知P3、P4进程，所以空②应填V(S2)V(S3)。
根据前驱图，P3进程运行完需要利用V(S4)、V(S5)操作分别通知P4、P5进程，故空③应为填写V(S4)V(S5)。
P4需要等待P2和P5进程的通知，需要执行2个P操作，由于P4进程的程序中执行前有1个P操作P(S4)，故空④应为填写P(S3)。
根据前驱图，P4进程执行完需要通知P5进程，故P4进程应该执行1个V操作，即空⑤应填V(S6)。
P5进程运行前需要等待P3和P4进程的通知，需要执行2个P操作，故空⑥应填写P(S5)和P(S6)。

真题示例3

解题思路：

先在前趋图中给每个箭头画上P操作和V操作。其中箭头起点为V操作，箭头终点为P操作。
然后对前趋图中的箭头，按从左到右，从上到下的顺序。依次标注上信号量。

解题分析：

根据前驱图，P1进程运行完需要利用V操作V(S1)、V (S2)分别通知P2、P3进程，所以空①应填V (S2)。
P2进程需要等待P1进程的通知，故需要利用P(S1)操作测试P1进程是否运行完，由于P3进程执行前已经用P(S2)，所以空②应填P (S1)。
根据前驱图，P3进程需要等待P1和P2进程的通知，需要执行2个P操作，即P (S2)、P (S3)。由于P3进程的程序中执行前有1个P操作P (S2)，故空③应为填写P (S3)。
P3进程运行结束需要利用1个V操作通知P5进程，故空④应为1个V操作V (S5)。
根据前驱图，P4进程执行完需要通知P5进程，故P4进程应该执行1个V操作，即空⑤应填V (S6)。
P5进程运行前需要等待P3和P4进程的通知，需要执行2个P操作，故空⑥应填写P(S5)和P(S6)。

死锁

死锁，是指两个以上的进程互相都要求对方已经占有的资源，从而导致双方进程都无法继续运行下去的现象。

产生死锁的4个必要条件是互斥条件、请求保持条件、不可剥夺条件和环路条件。

资源互斥
每个进程占有资源并等待其他资源
系统不能剥夺进程资源
进程资源图是一个环路

死锁计算问题

若系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*(R-1)。其不发生死锁的最小资源数为n*(R-1)+1。

发生死锁的最大资源数 = n*(R-1)
不发生死锁的最小资源数 = n*(R-1)+1

死锁的处理方法

死锁的处理策略主要有4种:鸵鸟策略(即不理睬策略)、预防策略、避免策略和检测与解除死锁。

其中死锁避免就是银行家算法，即提前计算出不会产生死锁的资源分配方法。

真题范例

某计算机系统中互斥资源R的可用数为8，系统中有3个进程P1、P2和P3竞争R，且每个进程都需要i个R，该系统可能会发生死锁的最小i值为（ 4 ）。

根据公式 8 >= 3*（i-1）+1 。当i=4时公式不成立,可能会发生死锁。

真题范例

正确答案C 图①可化简，图②不可化简

解析：

在图①中，R1的可用资源数=1，R2的可用资源数=0，进程P1是非阻塞节点，可以运行完毕: P1释放其占用的资源后，R1的可用资源数=2，R2的可用资源数=1，P2、P3都是非阻塞节点,因为P2申请2个R1资源、P1申请1个R2资源的请求均可以满足而运行完毕。可见进程资源图①是可化简的。图②中，R1和R2的可用资源数都为0，P1、P2和P3都是阻塞节点，所以图②是不可化简的。

真题范例

假设某计算机系统中资源R的可用数为6，系统中有3个进程竞争R，且每个进程都需要i个资源R，该系统可能会发生死锁的最小i值是（ 3 ）。若信号量S的当前值为-2，则R的可用数和等待R的进程数分别为（ 0、2 ）。

解题思路：

资源R的可用数为6，系统中有3个进程竞争R，当每个进程分配2个进程数的适合，不会发送死锁。一旦大于2就会发生死锁。

本题由于信号量S的当前值为-2,则意味着系统中资源R的可用个数M=0, 等待资源R的进程数N=2。

真题范例

某系统中有3个并发进程竞争资源R，每个进程都需要5个R，那么至少有（ 13 ）个R，才能保证系统不会发生死锁。

解题思路：

根据公式不发生死锁的最小资源数 >= 进程数 *（单个进程所需资源数-1）+1

即不发生死锁的最小资源数 >= 3(5-1)+1

线程

同一个进程当中的各个线程，可以共享该进程的各种资源，如内存地址空间、代码、数据、文件等，线程之间的通信与交流非常方便。

但每个线程都有自己独立的CPU运行上下文和栈，这是不能共享的（程序计数器、寄存器和栈不能共享）。

存储管理

存储管理的主要目的是解决多个用户同时使用主存的问题。

页式存储的淘汰原则

页面淘汰时，主要依据原则（考试中默认按照此原则进行淘汰）：先淘汰最近未被访问的（访问位为0），其次多个页面访问位为0时，则淘汰未被修改的（即修改位为0，因为修改后的页面淘汰时代价更大）。

分页式存储管理

将进程空间分为一个个页，每次将需要运行的逻辑页装入物理块中，运行完再装入其他需要运行的页，就可以分批次运行完进程，而无需将整块逻辑空间全部装入物理内存中

优点：利用率高、碎片小(只在最后一个页中有)、分配及管理简单
缺点：增加了系统开销,可能产生抖动现象

分段式存储管理

将进程空间分为一个个段，每段也有段号和段内地址，与分页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的。

优点：程序逻辑完整，修改互不影响
缺点：内存利用率低，内存碎片浪费大

段页式存储

段页式存储管理既具有分页式存储能有效地提高主存利用率的优点，又具有分段式存储能很好地满足用户需要的长处，显然是一种比较有效的存储管理方式。

段页式存储管理核心思想就是对进程空间先分段，后分页。

优点：空间浪费小、存储共享容易、能动态连接
缺点：由于管理软件的增加，复杂性和开销也增加，执行速度下降

真题示例

某操作系统采用分页存储管理方式，下图给出了进程A和进程B的页表结构。如果物理页的大小为1K字节，那么进程A中逻辑地址为1024 (十进制)用变量存放在（）号物理内存页中。假设进程A的逻辑页4与进程B的逻辑页5要共享物理页4，那么应该在进程A页表的逻辑页4和进程B页表的逻辑页5对应的物理页处分别填（）。

因为逻辑地址是从0开始编址的，物理页的大小为1KB，而进程A逻辑地址为1024 的变量的逻辑页号为1，对应的物理页号为3。

根据题意，进程A的逻辑页4与进程B的逻辑页5要共享的物理页4,那么应该在进程A页表的逻辑页4对应的物理页处填4,进程B页表的逻辑页5对应的物理页处也填4。

真题示例

(26)试题分析: 页内地址为13位，页号地址为11位，段号地址为8位。

根据公式，可以分别计算段号、页号和页内地址最大的寻址空间。存储管理系统中的地址长度均表示为最大的寻址空间。

所以最多有 2^8^ = 256 段,每段最大有 2^11^ = 2048 页,页的大小为 2^13^ = 8*1024 = 8K。

答案:(26)B

位数决定寻址上限，是 “最大有”，而非 “均为”。

设备管理

设备管理是操作系统中最繁杂而且与硬件紧密相关的部分。

I/O 软件

I/O软件是一个用于专门管理设备的软件，它提供了程序与设备的交互。通过I/O软件，用户可以方便地管理和使用设备，从而不必关心设备的具体实现细节。

I/O设备管理软件一般分为4层:中断处理程序、设备驱动程序、与设备无关的系统软件和用户级软件。

如图所示

磁盘调度

常用的磁盘调度算法如下

先来先服务（FCFS）算法
最短寻道时间优先（SSTF）算法
扫描（SCAN）算法
单向扫描调度（CSCAN）算法

真题

某磁盘有100个磁道，磁头从一个磁道移至另一个磁道需要6ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和20ms，则读取一个100块的文件需要（）ms。

步骤一：计算寻道时间

每次寻道移动10个磁道，每个磁道移动时间6ms，则每次寻道时间为 10x6=60ms 。
100块文件，每块都需先寻道，所以寻道总时间为 100x60=6000ms 。

步骤二：计算旋转延迟时间

每块的旋转延迟时间为 100ms，一共有 100块文件。那么旋转延迟总时间为100×100=10000ms

步骤三：计算传输时间

每块的传输时间为20ms ，文件共100块。所以传输总时间为 100x20=2000ms 。

步骤四：计算读取文件的总时间

将寻道时间、旋转延迟时间和传输时间相加，可得总时间为 6000+10000+2000=18000ms

真题

假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间为10μs，由缓冲区送至用户区的时间是5μs，系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区，并送至用户区进行处理，那么采用单缓冲区需要花费的时间为（）μs；采用双缓冲区需要花费的时间为（）μs。

当第一块数据送入用户工作区后，缓冲区是空闲的，可以传送第二块数据。这样第一块数据的处理C1与第二块数据的输入T2是可以并行的。

依次类推，每一块数据的处理时间为10+5=15。则采用单缓冲区需要花费的时间为 15*10+2

若采用双缓冲区，则可使系统不必等待设备输入。每一块数据的处理时间为10,采用双缓冲需要花费的时间为10*10+5+2=107。

文件管理

位示图

位示图的大小需要多个字 = 磁盘中物理块的数量 / 一个字可记录的物理块数量。

真题示例

由于物理块是从0开始编号的，所以 16385号物理块是第16386块。16386/32=512.0625，所以 16385 号物理块的使用情况在位示图中的第513个字中描述。

磁盘的容量为 1000GB，物理块的大小为4MB，则磁盘共有(1000x1024/4)个物理块，一个字对应 32 个物理块，位示图的大小为1000 x 1024/(32x4) =8000 个字。答案:C、D

真题1

某文件管理系统在磁盘上建立了位示图(bitmap) ，记录磁盘的使用情况。若计算机系统的字长为32 位，磁盘的容量为300GB ，物理块的大小为4MB ，那么位示图的大小需要（）个字。

根据题意，计算机系统中的字长为32位，每位可以表示一个物通块的“使用”还是“未用”，一个字可记录32个物理块的使用情况。又因为磁盘的容量为300GB，物理块的大小为4MB，那么该磁盘有300*1024/4=76800个物理块，位示图的大小为76800/32=2400个字

真题2

某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024GB，物理块的大小为4MB，那么位示图的大小需要（）个字。

根据题意计算机系统中的字长为64位，每位可以表示一个物理块的“使用”还是“未用”，一个字可记录64个物理块的使用情况。又因为磁盘的容量为1024GB，物理块的大小为4MB，那么该磁盘有1024X1024/4=262144个物理块，位示图的大小为262144/64=4096个字。

真题3

某文件管理系统采用位示图.(bitmap)来记录磁盘的使用情况，若计算机系统的字长为64位，磁盘容量为512GB，物理块的大小为4MB，那么位示图的大小为（）个字.

512G=5121024M。所以5121024/4/ 64=2048，位示图的大小为2048个字.

例子

某文件系统采用多级索引结构，若磁盘块的大小为512B，每个块号需占3B，那么根索引采用一级索引时的文件最大长度为（） KB：采用二级索引时的文件最大长度为（） KB。

根据题意，磁盘块的大小为512B，每个块号需占3B，因此一个磁盘物理块可存放512/3=170个块号。

根索引采用一级索引时的文件最大长度为： 170X512/1024=87040/1024=85KB
根索引采用二级索引时的文件最大长度为： 170X170X512/1024=28900X512/1024=14450KB

真题

在计算机系统中，若P1进程正在运行，操作系统强行撒下P1进程所占用的CPU，让具有更高优先级的进程P2运行，这种调度方式称为（可剥夺方式）。
在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4 (假设进程按此顺序到达)，其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。若P1时间片到了，则P1、P2、P3和P4的状态应分别为（就绪、运行、等待和等待）。
假设系统采用PV操作实现进程同步与互斥，若有n个进程共享一台扫描仪，那么当信号量S的值为-3时，表示系统中有（ 3 ）个进程等待使用扫描仪。
假设某分时系统采用简单时间片轮转法，当系统中的用户数为n、时间片为q时，系统对每个用户的响应时间T= （ n*q ）。
在单处理机计算机系统中有1台打印机、1台扫描仪，系统采用先来先服务调度算法。假设系统中有进程P1、P2、P3、P4,其中P1为运行状态，P2为就绪状态，P3等待打印机，P4等待扫描仪。此时，若P1释放了扫描仪，则进程P1、P2、P3、P4的状态分别为（运行、就绪、等待、就绪）。
假设系统中有n个进程共享3台扫描仪，并采用PV操怍实现进程同步与互斥。若系统信号量S的当前值为-1，进程P1、P2又分别执行了1次P（S）操作，那么信号量S的值应为（ -3 ）。
假设系统有n (n≥5) 个进程共享资源R，且资源R的可用数为5。若采用PV操作，则相应的信号量S的取值范围应为（ -(n-5)~5 ）。
PV操作是操作系统提供的具有特定功能的原语。利用PV操作可以（实现资源的互斥使用）。
在支持多线程的操作系统中，假设进程P创建了线程T1、T2和T3，那么以下叙述中错误的是（线程T1、T2可以共享P进程中T3的栈指针）。

软件设计师笔记05_软件工程基础_精简考点

科目一考试中占2-5分左右。

软件工程概述

软件工程的基本要素：方法、工具、过程。

软件生存周期

一个软件产品或软件系统要经历孕育、诞生、成长、成熟、衰亡等阶段，一般称为软件生存周期。

软件生存周期包括以下七个方面：

可行性分析与项目开发计划。这个阶段主要确定软件的开发目标及其可行性。参与该阶段的人员有用户、项目负责人、系统分析师。产生的文档有可行性分析报告、项目开发计划。
需求分析。该阶段的任务不是具体的解决问题，而是要确定软件系统要做什么，确定软件系统的功能、性能、数据和界面等要求，从而确定系统的逻辑模型。参与该阶段的人员有用户、项目负责人、系统分析师。产生的文档主要是软件需求说明书。
概要设计。该阶段开发人员把确定的各项功能需求转换成需要的体系结构。概要设计就是设计软件的结构，明确软件由哪些模块组成，这些模块层次结构是怎样的，调用关系是怎样的，每个模块的功能是什么。参与该阶段的人员有系统分析师、软件设计师。产生的文档主要是概要设计说明书。
详细设计。该阶段的主要任务是对每个模块的功能进一步详细、具体的描述。参与该阶段的人员有软件设计师、程序员。产生的文档主要是详细设计文档。
编码。把每个模块的控制结构转换成计算机可接受的程序代码，即写成某种特定程序设计语言表示的源程序清单。
测试。测试是保证软件质量的重要手段。参加测试的人员通常是另一部门（或单位）的软件设计师或系统分析师。产生的文档主要是软件测试计划、测试用例、测试报告。
维护。软件维护是软件生存周期中时间最长的阶段。软件已交付且正式投入使用后，便进入维护阶段。对软件进行修改的原因包括：①运行中发现隐含的错误而需要修改；②为了适应变化的（或变化后的）工作环境而修改；③需要对软件功能进行扩充、增强而进行的修改；④为将来软件维护活动做预先准备。

能力成熟度模型（CMM）

能力成熟度模型（CMM）是对软件组织进化阶段的描述，随着软件组织定义、实施、测量、控制和改进其软件过程，软件组织的能力经过这些阶段逐步提高。

通过该能力成熟度模型可以较容易地确定软件过程的成熟度并识别其软件过程执行中的薄弱环节，确定对软件质量和过程改进最为关键的几个问题，从而形成对其过程的改进策略。

能力成熟度模型（CMM）将软件过程的改进分为五个成熟度级别。

速记

初始级：制度缺乏，混乱无序，依赖个人管理。
可重复：建立基本管理制度。
已定义：文档化，标准化。
已管理：有对应的测量指标。
优化级：基于工具，持续改进软件过程，质量稳步改进。

能力成熟度模型集成（CMMI）

CMMI 是若干过程模型的综合和改进，是支持多个工程学科和领域的、系统的、一致的过程改进框架，能适应现代工程的特点和需要，能提高过程的质量和工作效率。

CMMI 提供了两种表示方法：阶段式模型和连续式模型。

阶段式模型。结构类似于 CMM，它关注组织的成熟度。
连续式模型。关注每个过程域的能力，一个组织对不同的过程域可以达到不同的过程域能力等级（简称 CL）。

CMMI 中包括六个过程域能力等级。

CL0（未完成的）：过程域未执行或未得到CL1中定义的所有目标。
CL1（已执行的）：其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标。
CL2（已管理的）：其共性目标是集中于已管理的过程的制度化。所有工作任务和工作产品都被监控、控制、和评审。
CL3（已定义级的）：其共性目标集中于已定义的过程的制度化。过程是按照组织的裁剪指南从组织的标准过程中裁剪得到的，还必须收集过程资产和过程的度量，并用于将来对过程的改进。
CL4（定量管理的）：其共性目标集中于可定量管理的过程的制度化。使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的质量目标作为管理准则。
CL5（优化的）：使用量化（统计学）手段改变和优化过程域，以满足客户的改变和持续改进计划中的过程域的功效。

软件开发方法

原型化开发方法：适合需求不清晰，需求变化大且规模不太大时采用。
结构化开发方法：适合需求明确或需求变化不大。
面向对象开发方法：更好的复用性，关键在于建立一个全面、合理、统一的模型，分析、设计、实现三个阶段界限不明确。

软件过程模型

典型的软件过程有瀑布模型、增量模型、演化模型（原型模型、螺旋模型）、喷泉模型、基于构件的开发模型和形式化方法模型等。

瀑布模型

瀑布模型的开发流程如同瀑布一般，一步一步的走下去，直到最后完成项目开发。

瀑布模型包括需求分析、设计、编码、测试、运行与维护共5个阶段。

如图所示

瀑布模型的优点：容易理解、成本低、强调开发的阶段性早期计划及需求调查和产品测试
瀑布模型的缺点：只适用于需求明确或者二次开发(需求稳定)，当需求不明确时，最终开发的项目容易产生错误，有很大的缺陷。

V 模型

V模型是瀑布模型的一个变体。如图所示。

V 模型的特点是增加了很多轮测试，并且这些测试贯穿于软件开发的各个阶段，不像其他模型都是软件开发完成后测试，很大程度上保证了项目的准确性。

增量模型

增量模型：首先开发核心模块功能，而后与客户确认。之后再开发次核心模块的功能，即每次开发一部分功能，并与客户需求确认。最终完成项目开发，优先级最高的服务最先交付

增量模型也具有瀑布模型所有的优点。

增量模型的优点：可交付的第一个增量版本所需要的成本和时间很少，所承担的风险不大。由于很快发布了第一个版本，因此可减少客户需求的变更。
增量模型的缺点：若客户需求不像早期思考的那样稳定和完整，那么一些增量就可能需要重新开发或重新发布；管理发生的成本、进度和配置的复杂性可能会超出组织的能力。

演化模型

在开发过程中，软件开发人员需要一种专门应对不断演变的软件产品的过程模型。而演化模型是迭代的过程模型，特别适用于对软件需求缺乏准确认识的情况。

典型的演化模型有原型模型和螺旋模型等。

原型模型

原型模型：即快速原型开发，原型模型针对的就是需求不明确的情况，首先快速构造一个功能模板，演示给客户看，并按用户要求及时修改，中间再通过不断的演示与客户沟通，最终设计出项目，就不会出现与客户要求不符合的情况，采用的是迭代的思想。

原型模型如图所示。

螺旋模型

螺旋模型是将瀑布模型和演化模型结合起来，加入了两种模型均忽略的风险分析，弥补了这两种模型的不足。

因此螺旋模型是针对需求不明确的项目，与原型模型类似，但是增加了风险分析，这也是其最大的特点。

螺旋模型强调风险分析，使用户、开发人员对演化层出现的风险有所了解，从而作出反映。因此，螺旋模型适合用于庞大、复杂、高风险的系统。

螺旋模型如图所示。

螺旋模型将开发过程分为几个螺旋周期，每个螺旋周期大致和瀑布模型相符合，每个螺旋周期分为如下4个工作步骤。

制订计划：确定软件目标，选定实施方案，明确项目开发的限制条件。
风险分析：对所选方案进行分析，识别风险，消除风险。
实施工程：实施软件开发，验证阶段性产品。
用户评估：评价开发工作，提出修正建议，建立下一个周期的开发计划。

喷泉模型

喷泉模型：是一种以用户需求为动力，以对象作为驱动的模型，适合于面向对象的开发方法。使开发过程具有迭代性和无间隙性。

喷泉模型如图所示。

优点：喷泉模型的各个阶段没有明显的界线，开发人员可以同步进行。其优点是可以提高软件项目的开发效率，节省开发时间。
缺点：这种模型要求严格管理文档，使得审核的难度加大。

各个软件过程模型总结

瀑布模型：需求明确，如同瀑布一般，按阶段一步一步完成。

V模型：瀑布模型的变体。在瀑布模型的各个阶段上添加多轮测试。很大程度上保证了软件的准确性。强调测试贯穿项目始终，而不是集中在测试阶段。是一种测试的开发模型。

增量模型：瀑布模型的变体。先开发核心功能，后开发附加功能。一个增量一个增量的开发。特点是可以很快发布了第一个版本。

演化模型：针对的就是需求不明确的情况。

原型模型：采用快速迭代的思想。只适合小型软件系统的开发。
螺旋模型：在原型模型的基础上加上了风险分析。适合用于庞大、复杂、高风险的系统。

喷泉模型：适合于面向对象的开发方法,可复用。使开发过程具有迭代性和无间隙性。

统一过程模型

统一过程的四个技术阶段及其产品：

（1）起始阶段：专注于项目初创活动。
（2）精化阶段：在理解了最初领域范围之后，需要进行需求分析和架构演进。
（3）构建阶段：关注系统的构建，产生实现模型。
（4）移交阶段：关注软件提交方面的工作，产生软件增量。

敏捷开发

敏捷开发的总体目标是通过“尽可能早地、持续地对有价值的软件的交付”使客户满意。通过在软件开发过程中加入灵活性，敏捷方法使用户能够在开发周期的后期增加或改变需求。

敏捷开发方法，包括极限编程（XP）、水晶法（Crystal）、并列争球法（Scrum:）和自适应软件开发（ASD）等。

总结

极限编程XP 是一种轻量级的软件开发方式。由价值观、原则、实践和行为4个部分组成。
水晶法Crystal 认为每一个不同的项目都需要一套不同的策略、约定和方法论。
并列争球法Scrum 使用迭代的方法，并按需求的优先级来实现产品。
敏捷统一过程(AUP)采用“在大型上连续”以及在“在小型上迭代”的原理来构建软件系统。

系统设计

概要设计主要包括:

①软件系统总体结构设计;
②数据结构及数据库设计;
③编写概要设计文档(概要设计说明书、数据库设计说明书、用户手册及修订测试计划);
④评审。

详细设计主要包括:

①对每个模块进行详细设计;
②对模块内部的数据结构进行设计;
③对数据库进行物理设计，即确定数据库的物理结构:
④其他设计(代码设计、输入/输出设计、用户界面设计);
⑤编写详细设计说明书;
⑥评审。

项目活动图里程碑

真题案例

2018年下半年

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间（天），则完成该项目的最少时间为（）天。活动FG的松驰时间为（）天。

A 20
B 37
C 38
D 46

完成该项目的最少时间由活动图中的最长路径决定。

其中路径 A-D-F-H-J ：10+8+18+10=46 。因此完成该项目的最少时间为46天。

某个活动的松弛时间 = 最长路径的天数 - 包含该活动的最长路径的天数。

活动 FG 所在路径中的最长路径为A-D-F-G-J ，其长度为 10+8+3+7=28 （天）。

完成该项目的最少时间为46天。所以活动 FG 的松弛时间为 46 - 28 = 18 （天）。

真题案例

2023年上半年

下图是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示活动，则里程碑（）在关键路径上,关键路径长度为（）

关键路径就是完成该项目的最长路径，也是完成该项目的最少时间的路径。

如图可知：A-C-E-H-J-K 所在路径是最长路径。该路径完成时间为23天。因此里程碑E在关键路径上。关键路径长度为23

软件测试

白盒测试技术的各种覆盖方法中，（语句覆盖）具有最弱的错误发现能力。
软件产品的 Alpha 测试和 Beta 测试属于（确认测试）。

单元测试

单元测试也称模块测试，在模块编写完成且编译无误后进行，侧重于模块中的内部处理逻辑和数据结构。

单元测试环境如图所示。

集成测试

集成测试就是把模块组合起来进行测试。即使所有的模块都通过了测试，在集成之后，仍然可能出现问题。

另外，单个模块的误差可以接受，但模块组合后，可能会出现误差累积，最后累积到不能接受的程度。

集成测试通常有以下两种方法：

（1）非增量集成：分别测试各个模块，再将这些模块组合起来进行整理测试。
（2）增量集成：以小增量的方式逐步进行构造和测试。

常用的增量集成策略包括：自顶向下集成测试、自底向上集成测试、回归测试、冒烟测试等

测试方法

软件测试的测试方法分为静态测试和动态测试。

静态测试：是指被测程序不在机器上运行，采用人工检测和计算机辅助静态分析的手段对程序进行测试，包括人工检测、计算机辅助静态分析。
- 人工检测：是指通过人工阅读、分析程序代码、设计测试用例等方式，发现程序中的错误和缺陷。
- 计算机辅助静态分析：是指利用计算机程序对程序代码进行分析，发现程序中的错误和缺陷。
动态测试：是指通过运行程序发现错误，一般采用黑盒测试和白盒测试。
- 黑盒测试：也称功能测试，在不考虑软件内部结构和特性的情况下，测试软件的外部特性。
- 白盒测试：也称结构测试，根据程序的内部结构和逻辑来设计测试用例，对程序的路径和过程进行测试，检查是否满足设计的需要。

黑盒测试

黑盒测试又称功能测试。完全不考虑（或不了解）软件的内部结构和处理算法，它只检查软件功能是否能按照软件需求说明书的要求正常使用。

常用的黑盒测试技术包括等价类划分、边界值分析、错误推测和因果图等。

白盒测试

白盒测试按照程序内部逻辑测试程序，检验程序中每条通路是否按预定要求正确工作。

典型的白盒测试方法包括：静态测试、动态测试。其中静态测试包括：代码检查法、静态结构分析法、静态质量度量法。

语句覆盖测试和路径覆盖测试

语句覆盖：语句覆盖是指设计足够的测试用例，使得程序中的每条语句至少被执行一次。语句就是代码。
路径覆盖：路径覆盖是指设计足够的测试用例，覆盖程序中所有可能的判断条件路径。路径就是判断条件。

项目管理

甘特图（Gantt Chart）

Gantt图：又称为横道图，横轴表示时间，纵轴表示活动，以时间顺序表示活动，能反应活动间的并行关系，但无法反应活动之间的依赖关系。

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

PERT图

PERT图：类似于前趋图，是有向图，反应活动之间的依赖关系，有向边上标注活动运行的时间，但无法反应活动之间的并行关系

PERT图不仅给出了每个任务的开始时间、结束时间和完成该任务所需的时间，还给出了任务之间的关系，即哪些任务完成后才能开始另外一些任务，以及如期完成整个工程的关键路径。

图中的松弛时间则反映了完成某些任务时可以推迟其开始时间或延长其所需完成的时间。但是，PERT图不能反映任务之间的并行关系。

软件维护

更正性维护：针对真实存在并已经发生的错误进行的维护行为。
预防性维护：针对真实存在但还未发生的错误进行的维护。
适应性维护：指使应用软件适应信息技术变化和管理需求变化而进行的修改。企业的外部市场环境和管理需求的不断变化也使得各级管理人员不断提出新的信息需求。
完善性维护：扩充功能和改善性能而进行的修改。对已有的软件系统增加一些在系统分析和设计阶段中没有规定的功能与性能特征。

软件风险管理

风险的特性：具有不确定性，可能会造成损失。

风险的类别：

项目风险涉及到各种形式的预算、进度、人员、资源以及客户相关的问题，并且可能导致项目损失。
技术风险涉及到技术相关的可能会导致项目损失的问题。
商业风险与市场因素相关。
社会风险涉及到政策、法规等因素。

风险曝光度的公式 = 错误出现率(风险出现率) X 错误造成损失(风险损失)。

软件质量

ISO/IEC9126 软件质量模型

在 ISO/IEC9126软件质量模型中，软件质量模型由三个层次组成，第一层为质量特性，第二层为质量子特性，第三层为度量指标。

如图所示

ISO/IEC 9126模型中，基本特性为6个：功能性、可靠性、易使用性、效率、可维护性和可移植性。

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

常考知识点

软件维护的工作量比开发阶段的工作量大
在ISO/IEC软件质量模型中，易使用性的子特性不包括（易分析性）。
软件可维护性是一个系统在特定的时间间隔内可以正常进行维护活动的概率。用MTTF和MTTR分别表示平均无故障时间和平均故障修复时间，则软件可维护性计算公式为（ 1/(1+MTTR) ）
系统的可维护性指标：可理解性、可测试性和可修改性。

McCabe度量法

McCabe环路复杂度。有两种方式求出。
- 公式法：先将程序的流程图转换为有向图。然后使用公式 V(G)= m - n + 2 。其中 m 是程序图中边的数量，n 是节点数量。
- 区域法：先数出图中封闭环的个数。环形复杂度等于封闭环个数+1。

真题案例

若采用McCabe度量法计算环路复杂性，则对于下图所示的程序图，其环路复杂度为（）。

考点：McCabe 度量法计算环路复杂度。

解法1 公式法

解题思路：McCabe 度量法计算环路复杂度公式为 (V(G)=e - n + 2) ，其中 e 是程序图中边的数量，n 是节点数量。

由于图为有向图，因此从图中数出节点数 (n = 9) ，边数 (e = 11) ，代入公式可得 (V(G)=11 - 9 + 2 = 4) 。

解法2 区域法

程序图的环路数等于由程序图中封闭的区域数量加上 1。

如图图中封闭的区域数量为3。因此环路复杂度 = 3 + 1 = 4

真题案例

对下图所示的程序流程图采用McCabe度量法计算其环路复杂度为（）。

解法1 公式法

先将程序流程图转换为有向图。然后根据公式 V(G)= m - n + 2 。m为边数，m为节点数。得到环路复杂度。

如图 V(G)= 15 - 12 + 2 = 5

解法2 区域法

如图程序流程图的封闭环路数量为 6.因此该图的环路复杂度为6+1=7

真题案例

采用McCabe度量法计算下列程序图的环路复杂性为（）。

环形度量采用封闭环个数+1的方式进行计算最简单也是最保险的方式。上图可以直接看出存在3个封闭环回路，整个环形复杂度就是3+1 = 4

注意：封闭环个数不计算重叠的。

真题

以下软件产品中，属于图像编辑处理工具的软件是（ Photoshop ）。
某个项目在开发时采用了不成熟的前沿技术，由此而带来的风险属于（技术）风险。
软件开发过程中，需求分析阶段的输出不包括（软件体系结构图）。
由8位成员组成的开发团队中，一共有（ 28 ）条沟通路径.
- 如果是采用有主程序员的沟通方式，只要7条路径。
- 如果是无主程序员的沟通方式。计算7+6+5+4+3+2+1，结果是28。
软件详细设计阶段的主要任务不包括（模块之间的接口设计）。
信息系统的文档是开发人员与用户交流的工具。在系统规划和系统分析阶段,用户与系统分析人员交流所使用的文档不包括（用户使用手册）。
正式技术评审的目标是（发现软件中的错误）。
以下关于各类文档撰写阶段的叙述中，不正确的是（测试计划必须在测试阶段撰写）。
下列活动，（针对系统特点，考虑并确定系统开发平台与程序设计语言）不属于需求开发活动的范畴。
能力成熟度模型集成（CMMI）是若干过程模型的综合和改进。连续式模型和阶段式模型是CMMI提供的两种表示方法，而连续式模型包括6个过程域能力等级，其中（ CL5（优化的））使用量化（统计学）手段改变和优化过程域，以应对客户要求的改变和持续改进计划中的过程域的功效。
能力成熟度模型集成(CMMI)是若干过程模型的综合和改进。连续式模型和阶段式模型是CMMI提供的两种表示方法。连续式模型包括6个过程域能力等级( Capability Level,CL)，其中（ CL1(已执行的) ）的共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品,以实现支持过程域的特定目标。
若用户需求不清晰且经常发生变化，但系统规模不太大且不太复杂，则最适宜采用（原型化）开发方法，对于数据处理领域的问题，若系统规模不太大且不太复杂，需求变化也不大，则最适宜采用（结构化）开发方法。
统一过程模型是一种“用例和风险驱动，以架构为中心，迭代并且增量”的开发过程，定义了不同阶段及其制品，其中精化阶段关注（需求分析和架构演进）。
关于螺旋模型，下列陈述中不正确的是（可以快速的提供一个初始版本让用户测试）。
（瀑布）开发过程模型最不适用于开发初期对软件需求缺乏准确全面认识的情况。
喷泉模型是一种适合于面向（对象）开发方法的软件过程模型。该过程模型的特点不包括（开发活动之间存在明显的界限）。
某企业拟开发一个企业信息管理系统，系统功能与多个部门的业务相关。现希望该系统能够尽快投入使用，系统功能可以在使用过程中不断改善。则最适宜采用的软件过程模型为（演化（迭代）模型）。
以下关于快速原型模型优点的叙述中，不正确是（适用于大型软件系统的开发）。
（很容易将客户需求划分为多个增量）不是增量式开发的优势。
螺旋模型综合了__瀑布模型和演化模型___的优点，并增加了这两种模型忽略的风险分析。
确定软件的模块划分及模块之间的调用关系是（概要设计）阶段的任务。
敏捷开发方法Scrum的步骤不包括（ Refactoring ）。
以下关于极限编程(XP) 中结对编程的叙述中，不正确的是（编码速度更快）。
以下关于极限编程（XP）的最佳实践的叙述中，不正确的是（编写完程序之后编写测试代码）。
优化模块结构时，（使模块功能完整，消除重复功能，改善软件结构，避免或减少模块之间的病态连接）是适当的处理方法。
在软件开发过程中，系统测试阶段的测试目标来自于（需求分析）阶段。
白盒测试技术的各种覆盖方法中，（语句覆盖）具有最弱的错误发现能力。
在设计测试用例时，应遵循（不仅要设计有效合理输入，也要包含不合理、失效的输入）原则。
在软件系统交付给用户使用后，为了使用户界面更友好，对系统的图形输出进行改进，该行为属于（改善性）维护。
以下关于软件测试的叙述中，正确的是（一个成功的测试能发现至今未发现的错误）。
以下关于进度管理工具Gantt图的叙述中，不正确的是（能清晰地确定影响进度的关键任务）。
针对“关键职员在项目未完成时就跳槽”的风险，最不合适的风险管理策略是（临时招聘具有相关能力的新职员）。
在进行软件开发时，采用无主程序员的开发小组，成员之间相互平等;而主程序员负责制的开发小组，由一个主程序员和若干成员组成，成员之间没有沟通。在一个由8名开发人员构成的小组中，无主程序员组和主程序员组的沟通路径分别是（ 28和7 ）。
- 无主程序员组的开发小组，每两十开发人员之间都有沟通路径，因此，8人组成的开发小组沟通路径为完全连通无向图的边数，即 7+6+5+4+3+2+1
- 主程序员组中，除了主程序员外的每个开发人员只能和主程序员沟通，因此8人组成的开发小组的沟通路径8-1=7。
工作量估算模型COCOMO II的层次结构中,估算选择不包括（用例数）。

软件质量

按照 ISO/IEC 9126 软件质量度量模型定义，一个软件的可靠性的子特性包括（容错性和易恢复性）。
软件可维护性是一个系统在特定的时间间隔内可以正常进行维护活动的概率。用MTTF和MTTR分别表示平均无故障时间和平均故障修复时间，则软件可维护性计算公式为（ 1/(1+MTTR) ）。
在ISO/IEC软件质量模型中，可移植性是指与软件可从某环境行移到另一环境的能力有关的一组属性，其子特性不包括（测试性）。
在对程序质量进行评审时，模块结构是一个重要的评审项，评审内容中不包括（数据结构）。
在ISO/IEC9126软件质量模型中，软件质量特性（功能性）包含质量子特性安全性。
在IS0/IEC软件质量模型中，易使用性是指与使用所需的努力和由一组规定或隐含的用户对这样使用所作的个别评价有关的一组属性，其子特性不包括（易分析性）。
在ISO/IEC 9126软件质量模型中，可靠性质量特性是指在规定的一段时间内和规定的条件下，软件维持在其性能水平有关的能力，其质量子特性不包括（安全性，可移植性）。
（易理解性）不属于软件质量特性中的可移植性。
（功能与模块之间的对应关系）不属于软件设计质量评审。
在设计中实现可移植性设计的规则不包括（可使用特定环境的专用功能）
软件质量属性中，（吞吐量）是指软件每分钟可以处理多少个请求。
系统可维护性的评价指标不包括（可移植性）。
系统可维护性是指维护人员理解、改正、改动和改进软件系统的难易程度，其评价指标不包括（一致性）。
将每个用户的数据和其他用户的数据隔离开，是考虑了软件的（功能性）质量特件。

软件设计师笔记05_软件工程基础_精简考点

科目一考试中占2-5分左右。

软件工程概述

软件工程的基本要素：方法、工具、过程。

软件生存周期

一个软件产品或软件系统要经历孕育、诞生、成长、成熟、衰亡等阶段，一般称为软件生存周期。

软件生存周期包括以下七个方面：

可行性分析与项目开发计划。这个阶段主要确定软件的开发目标及其可行性。参与该阶段的人员有用户、项目负责人、系统分析师。产生的文档有可行性分析报告、项目开发计划。
需求分析。该阶段的任务不是具体的解决问题，而是要确定软件系统要做什么，确定软件系统的功能、性能、数据和界面等要求，从而确定系统的逻辑模型。参与该阶段的人员有用户、项目负责人、系统分析师。产生的文档主要是软件需求说明书。
概要设计。该阶段开发人员把确定的各项功能需求转换成需要的体系结构。概要设计就是设计软件的结构，明确软件由哪些模块组成，这些模块层次结构是怎样的，调用关系是怎样的，每个模块的功能是什么。参与该阶段的人员有系统分析师、软件设计师。产生的文档主要是概要设计说明书。
详细设计。该阶段的主要任务是对每个模块的功能进一步详细、具体的描述。参与该阶段的人员有软件设计师、程序员。产生的文档主要是详细设计文档。
编码。把每个模块的控制结构转换成计算机可接受的程序代码，即写成某种特定程序设计语言表示的源程序清单。
测试。测试是保证软件质量的重要手段。参加测试的人员通常是另一部门（或单位）的软件设计师或系统分析师。产生的文档主要是软件测试计划、测试用例、测试报告。
维护。软件维护是软件生存周期中时间最长的阶段。软件已交付且正式投入使用后，便进入维护阶段。对软件进行修改的原因包括：①运行中发现隐含的错误而需要修改；②为了适应变化的（或变化后的）工作环境而修改；③需要对软件功能进行扩充、增强而进行的修改；④为将来软件维护活动做预先准备。

能力成熟度模型（CMM）

能力成熟度模型（CMM）将软件过程的改进分为五个成熟度级别。

速记

初始级：制度缺乏，混乱无序，依赖个人管理。
可重复：建立基本管理制度。
已定义：文档化，标准化。
已管理：有对应的测量指标。
优化级：基于工具，持续改进软件过程，质量稳步改进。

能力成熟度模型集成（CMMI）

CMMI 提供了两种表示方法：阶段式模型和连续式模型。

阶段式模型。结构类似于 CMM，它关注组织的成熟度。
连续式模型。关注每个过程域的能力，一个组织对不同的过程域可以达到不同的过程域能力等级（简称 CL）。

CMMI 中包括六个过程域能力等级。

CL0（未完成的）：过程域未执行或未得到CL1中定义的所有目标。
CL1（已执行的）：其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标。
CL2（已管理的）：其共性目标是集中于已管理的过程的制度化。所有工作任务和工作产品都被监控、控制、和评审。
CL3（已定义级的）：其共性目标集中于已定义的过程的制度化。过程是按照组织的裁剪指南从组织的标准过程中裁剪得到的，还必须收集过程资产和过程的度量，并用于将来对过程的改进。
CL4（定量管理的）：其共性目标集中于可定量管理的过程的制度化。使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的质量目标作为管理准则。
CL5（优化的）：使用量化（统计学）手段改变和优化过程域，以满足客户的改变和持续改进计划中的过程域的功效。

软件开发方法

原型化开发方法：适合需求不清晰，需求变化大且规模不太大时采用。
结构化开发方法：适合需求明确或需求变化不大。
面向对象开发方法：更好的复用性，关键在于建立一个全面、合理、统一的模型，分析、设计、实现三个阶段界限不明确。

软件过程模型

典型的软件过程有瀑布模型、增量模型、演化模型（原型模型、螺旋模型）、喷泉模型、基于构件的开发模型和形式化方法模型等。

瀑布模型

瀑布模型的开发流程如同瀑布一般，一步一步的走下去，直到最后完成项目开发。

瀑布模型包括需求分析、设计、编码、测试、运行与维护共5个阶段。

如图所示

瀑布模型的优点：容易理解、成本低、强调开发的阶段性早期计划及需求调查和产品测试
瀑布模型的缺点：只适用于需求明确或者二次开发(需求稳定)，当需求不明确时，最终开发的项目容易产生错误，有很大的缺陷。

V 模型

V模型是瀑布模型的一个变体。如图所示。

增量模型

增量模型也具有瀑布模型所有的优点。

增量模型的优点：可交付的第一个增量版本所需要的成本和时间很少，所承担的风险不大。由于很快发布了第一个版本，因此可减少客户需求的变更。
增量模型的缺点：若客户需求不像早期思考的那样稳定和完整，那么一些增量就可能需要重新开发或重新发布；管理发生的成本、进度和配置的复杂性可能会超出组织的能力。

演化模型

典型的演化模型有原型模型和螺旋模型等。

原型模型

原型模型如图所示。

螺旋模型

螺旋模型是将瀑布模型和演化模型结合起来，加入了两种模型均忽略的风险分析，弥补了这两种模型的不足。

因此螺旋模型是针对需求不明确的项目，与原型模型类似，但是增加了风险分析，这也是其最大的特点。

螺旋模型强调风险分析，使用户、开发人员对演化层出现的风险有所了解，从而作出反映。因此，螺旋模型适合用于庞大、复杂、高风险的系统。

螺旋模型如图所示。

螺旋模型将开发过程分为几个螺旋周期，每个螺旋周期大致和瀑布模型相符合，每个螺旋周期分为如下4个工作步骤。

制订计划：确定软件目标，选定实施方案，明确项目开发的限制条件。
风险分析：对所选方案进行分析，识别风险，消除风险。
实施工程：实施软件开发，验证阶段性产品。
用户评估：评价开发工作，提出修正建议，建立下一个周期的开发计划。

喷泉模型

喷泉模型：是一种以用户需求为动力，以对象作为驱动的模型，适合于面向对象的开发方法。使开发过程具有迭代性和无间隙性。

喷泉模型如图所示。

优点：喷泉模型的各个阶段没有明显的界线，开发人员可以同步进行。其优点是可以提高软件项目的开发效率，节省开发时间。
缺点：这种模型要求严格管理文档，使得审核的难度加大。

各个软件过程模型总结

瀑布模型：需求明确，如同瀑布一般，按阶段一步一步完成。

增量模型：瀑布模型的变体。先开发核心功能，后开发附加功能。一个增量一个增量的开发。特点是可以很快发布了第一个版本。

演化模型：针对的就是需求不明确的情况。

原型模型：采用快速迭代的思想。只适合小型软件系统的开发。
螺旋模型：在原型模型的基础上加上了风险分析。适合用于庞大、复杂、高风险的系统。

喷泉模型：适合于面向对象的开发方法,可复用。使开发过程具有迭代性和无间隙性。

统一过程模型

统一过程的四个技术阶段及其产品：

（1）起始阶段：专注于项目初创活动。
（2）精化阶段：在理解了最初领域范围之后，需要进行需求分析和架构演进。
（3）构建阶段：关注系统的构建，产生实现模型。
（4）移交阶段：关注软件提交方面的工作，产生软件增量。

敏捷开发

敏捷开发方法，包括极限编程（XP）、水晶法（Crystal）、并列争球法（Scrum:）和自适应软件开发（ASD）等。

总结

极限编程XP 是一种轻量级的软件开发方式。由价值观、原则、实践和行为4个部分组成。
水晶法Crystal 认为每一个不同的项目都需要一套不同的策略、约定和方法论。
并列争球法Scrum 使用迭代的方法，并按需求的优先级来实现产品。
敏捷统一过程(AUP)采用“在大型上连续”以及在“在小型上迭代”的原理来构建软件系统。

系统设计

概要设计主要包括:

①软件系统总体结构设计;
②数据结构及数据库设计;
③编写概要设计文档(概要设计说明书、数据库设计说明书、用户手册及修订测试计划);
④评审。

详细设计主要包括:

①对每个模块进行详细设计;
②对模块内部的数据结构进行设计;
③对数据库进行物理设计，即确定数据库的物理结构:
④其他设计(代码设计、输入/输出设计、用户界面设计);
⑤编写详细设计说明书;
⑥评审。

项目活动图里程碑

真题案例

2018年下半年

A 20
B 37
C 38
D 46

完成该项目的最少时间由活动图中的最长路径决定。

其中路径 A-D-F-H-J ：10+8+18+10=46 。因此完成该项目的最少时间为46天。

某个活动的松弛时间 = 最长路径的天数 - 包含该活动的最长路径的天数。

活动 FG 所在路径中的最长路径为A-D-F-G-J ，其长度为 10+8+3+7=28 （天）。

完成该项目的最少时间为46天。所以活动 FG 的松弛时间为 46 - 28 = 18 （天）。

真题案例

2023年上半年

下图是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示活动，则里程碑（）在关键路径上,关键路径长度为（）

关键路径就是完成该项目的最长路径，也是完成该项目的最少时间的路径。

如图可知：A-C-E-H-J-K 所在路径是最长路径。该路径完成时间为23天。因此里程碑E在关键路径上。关键路径长度为23

软件测试

白盒测试技术的各种覆盖方法中，（语句覆盖）具有最弱的错误发现能力。
软件产品的 Alpha 测试和 Beta 测试属于（确认测试）。

单元测试

单元测试也称模块测试，在模块编写完成且编译无误后进行，侧重于模块中的内部处理逻辑和数据结构。

单元测试环境如图所示。

集成测试

集成测试就是把模块组合起来进行测试。即使所有的模块都通过了测试，在集成之后，仍然可能出现问题。

另外，单个模块的误差可以接受，但模块组合后，可能会出现误差累积，最后累积到不能接受的程度。

集成测试通常有以下两种方法：

（1）非增量集成：分别测试各个模块，再将这些模块组合起来进行整理测试。
（2）增量集成：以小增量的方式逐步进行构造和测试。

常用的增量集成策略包括：自顶向下集成测试、自底向上集成测试、回归测试、冒烟测试等

测试方法

软件测试的测试方法分为静态测试和动态测试。

静态测试：是指被测程序不在机器上运行，采用人工检测和计算机辅助静态分析的手段对程序进行测试，包括人工检测、计算机辅助静态分析。
- 人工检测：是指通过人工阅读、分析程序代码、设计测试用例等方式，发现程序中的错误和缺陷。
- 计算机辅助静态分析：是指利用计算机程序对程序代码进行分析，发现程序中的错误和缺陷。
动态测试：是指通过运行程序发现错误，一般采用黑盒测试和白盒测试。
- 黑盒测试：也称功能测试，在不考虑软件内部结构和特性的情况下，测试软件的外部特性。
- 白盒测试：也称结构测试，根据程序的内部结构和逻辑来设计测试用例，对程序的路径和过程进行测试，检查是否满足设计的需要。

黑盒测试

黑盒测试又称功能测试。完全不考虑（或不了解）软件的内部结构和处理算法，它只检查软件功能是否能按照软件需求说明书的要求正常使用。

常用的黑盒测试技术包括等价类划分、边界值分析、错误推测和因果图等。

白盒测试

白盒测试按照程序内部逻辑测试程序，检验程序中每条通路是否按预定要求正确工作。

典型的白盒测试方法包括：静态测试、动态测试。其中静态测试包括：代码检查法、静态结构分析法、静态质量度量法。

语句覆盖测试和路径覆盖测试

语句覆盖：语句覆盖是指设计足够的测试用例，使得程序中的每条语句至少被执行一次。语句就是代码。
路径覆盖：路径覆盖是指设计足够的测试用例，覆盖程序中所有可能的判断条件路径。路径就是判断条件。

项目管理

甘特图（Gantt Chart）

Gantt图：又称为横道图，横轴表示时间，纵轴表示活动，以时间顺序表示活动，能反应活动间的并行关系，但无法反应活动之间的依赖关系。

PERT图

PERT图：类似于前趋图，是有向图，反应活动之间的依赖关系，有向边上标注活动运行的时间，但无法反应活动之间的并行关系

图中的松弛时间则反映了完成某些任务时可以推迟其开始时间或延长其所需完成的时间。但是，PERT图不能反映任务之间的并行关系。

软件维护

更正性维护：针对真实存在并已经发生的错误进行的维护行为。
预防性维护：针对真实存在但还未发生的错误进行的维护。
适应性维护：指使应用软件适应信息技术变化和管理需求变化而进行的修改。企业的外部市场环境和管理需求的不断变化也使得各级管理人员不断提出新的信息需求。
完善性维护：扩充功能和改善性能而进行的修改。对已有的软件系统增加一些在系统分析和设计阶段中没有规定的功能与性能特征。

软件风险管理

风险的特性：具有不确定性，可能会造成损失。

风险的类别：

项目风险涉及到各种形式的预算、进度、人员、资源以及客户相关的问题，并且可能导致项目损失。
技术风险涉及到技术相关的可能会导致项目损失的问题。
商业风险与市场因素相关。
社会风险涉及到政策、法规等因素。

风险曝光度的公式 = 错误出现率(风险出现率) X 错误造成损失(风险损失)。

软件质量

ISO/IEC9126 软件质量模型

在 ISO/IEC9126软件质量模型中，软件质量模型由三个层次组成，第一层为质量特性，第二层为质量子特性，第三层为度量指标。

如图所示

ISO/IEC 9126模型中，基本特性为6个：功能性、可靠性、易使用性、效率、可维护性和可移植性。

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

常考知识点

软件维护的工作量比开发阶段的工作量大
在ISO/IEC软件质量模型中，易使用性的子特性不包括（易分析性）。
软件可维护性是一个系统在特定的时间间隔内可以正常进行维护活动的概率。用MTTF和MTTR分别表示平均无故障时间和平均故障修复时间，则软件可维护性计算公式为（ 1/(1+MTTR) ）
系统的可维护性指标：可理解性、可测试性和可修改性。

McCabe度量法

McCabe环路复杂度。有两种方式求出。
- 公式法：先将程序的流程图转换为有向图。然后使用公式 V(G)= m - n + 2 。其中 m 是程序图中边的数量，n 是节点数量。
- 区域法：先数出图中封闭环的个数。环形复杂度等于封闭环个数+1。

真题案例

若采用McCabe度量法计算环路复杂性，则对于下图所示的程序图，其环路复杂度为（）。

考点：McCabe 度量法计算环路复杂度。

解法1 公式法

解题思路：McCabe 度量法计算环路复杂度公式为 (V(G)=e - n + 2) ，其中 e 是程序图中边的数量，n 是节点数量。

由于图为有向图，因此从图中数出节点数 (n = 9) ，边数 (e = 11) ，代入公式可得 (V(G)=11 - 9 + 2 = 4) 。

解法2 区域法

程序图的环路数等于由程序图中封闭的区域数量加上 1。

如图图中封闭的区域数量为3。因此环路复杂度 = 3 + 1 = 4

真题案例

对下图所示的程序流程图采用McCabe度量法计算其环路复杂度为（）。

解法1 公式法

先将程序流程图转换为有向图。然后根据公式 V(G)= m - n + 2 。m为边数，m为节点数。得到环路复杂度。

如图 V(G)= 15 - 12 + 2 = 5

解法2 区域法

如图程序流程图的封闭环路数量为 6.因此该图的环路复杂度为6+1=7

真题案例

采用McCabe度量法计算下列程序图的环路复杂性为（）。

环形度量采用封闭环个数+1的方式进行计算最简单也是最保险的方式。上图可以直接看出存在3个封闭环回路，整个环形复杂度就是3+1 = 4

注意：封闭环个数不计算重叠的。

真题

以下软件产品中，属于图像编辑处理工具的软件是（ Photoshop ）。
某个项目在开发时采用了不成熟的前沿技术，由此而带来的风险属于（技术）风险。
软件开发过程中，需求分析阶段的输出不包括（软件体系结构图）。
由8位成员组成的开发团队中，一共有（ 28 ）条沟通路径.
- 如果是采用有主程序员的沟通方式，只要7条路径。
- 如果是无主程序员的沟通方式。计算7+6+5+4+3+2+1，结果是28。
软件详细设计阶段的主要任务不包括（模块之间的接口设计）。
信息系统的文档是开发人员与用户交流的工具。在系统规划和系统分析阶段,用户与系统分析人员交流所使用的文档不包括（用户使用手册）。
正式技术评审的目标是（发现软件中的错误）。
以下关于各类文档撰写阶段的叙述中，不正确的是（测试计划必须在测试阶段撰写）。
下列活动，（针对系统特点，考虑并确定系统开发平台与程序设计语言）不属于需求开发活动的范畴。
能力成熟度模型集成（CMMI）是若干过程模型的综合和改进。连续式模型和阶段式模型是CMMI提供的两种表示方法，而连续式模型包括6个过程域能力等级，其中（ CL5（优化的））使用量化（统计学）手段改变和优化过程域，以应对客户要求的改变和持续改进计划中的过程域的功效。
能力成熟度模型集成(CMMI)是若干过程模型的综合和改进。连续式模型和阶段式模型是CMMI提供的两种表示方法。连续式模型包括6个过程域能力等级( Capability Level,CL)，其中（ CL1(已执行的) ）的共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品,以实现支持过程域的特定目标。
若用户需求不清晰且经常发生变化，但系统规模不太大且不太复杂，则最适宜采用（原型化）开发方法，对于数据处理领域的问题，若系统规模不太大且不太复杂，需求变化也不大，则最适宜采用（结构化）开发方法。
统一过程模型是一种“用例和风险驱动，以架构为中心，迭代并且增量”的开发过程，定义了不同阶段及其制品，其中精化阶段关注（需求分析和架构演进）。
关于螺旋模型，下列陈述中不正确的是（可以快速的提供一个初始版本让用户测试）。
（瀑布）开发过程模型最不适用于开发初期对软件需求缺乏准确全面认识的情况。
喷泉模型是一种适合于面向（对象）开发方法的软件过程模型。该过程模型的特点不包括（开发活动之间存在明显的界限）。
某企业拟开发一个企业信息管理系统，系统功能与多个部门的业务相关。现希望该系统能够尽快投入使用，系统功能可以在使用过程中不断改善。则最适宜采用的软件过程模型为（演化（迭代）模型）。
以下关于快速原型模型优点的叙述中，不正确是（适用于大型软件系统的开发）。
（很容易将客户需求划分为多个增量）不是增量式开发的优势。
螺旋模型综合了__瀑布模型和演化模型___的优点，并增加了这两种模型忽略的风险分析。
确定软件的模块划分及模块之间的调用关系是（概要设计）阶段的任务。
敏捷开发方法Scrum的步骤不包括（ Refactoring ）。
以下关于极限编程(XP) 中结对编程的叙述中，不正确的是（编码速度更快）。
以下关于极限编程（XP）的最佳实践的叙述中，不正确的是（编写完程序之后编写测试代码）。
优化模块结构时，（使模块功能完整，消除重复功能，改善软件结构，避免或减少模块之间的病态连接）是适当的处理方法。
在软件开发过程中，系统测试阶段的测试目标来自于（需求分析）阶段。
白盒测试技术的各种覆盖方法中，（语句覆盖）具有最弱的错误发现能力。
在设计测试用例时，应遵循（不仅要设计有效合理输入，也要包含不合理、失效的输入）原则。
在软件系统交付给用户使用后，为了使用户界面更友好，对系统的图形输出进行改进，该行为属于（改善性）维护。
以下关于软件测试的叙述中，正确的是（一个成功的测试能发现至今未发现的错误）。
以下关于进度管理工具Gantt图的叙述中，不正确的是（能清晰地确定影响进度的关键任务）。
针对“关键职员在项目未完成时就跳槽”的风险，最不合适的风险管理策略是（临时招聘具有相关能力的新职员）。
在进行软件开发时，采用无主程序员的开发小组，成员之间相互平等;而主程序员负责制的开发小组，由一个主程序员和若干成员组成，成员之间没有沟通。在一个由8名开发人员构成的小组中，无主程序员组和主程序员组的沟通路径分别是（ 28和7 ）。
- 无主程序员组的开发小组，每两十开发人员之间都有沟通路径，因此，8人组成的开发小组沟通路径为完全连通无向图的边数，即 7+6+5+4+3+2+1
- 主程序员组中，除了主程序员外的每个开发人员只能和主程序员沟通，因此8人组成的开发小组的沟通路径8-1=7。
工作量估算模型COCOMO II的层次结构中,估算选择不包括（用例数）。

软件质量

按照 ISO/IEC 9126 软件质量度量模型定义，一个软件的可靠性的子特性包括（容错性和易恢复性）。
软件可维护性是一个系统在特定的时间间隔内可以正常进行维护活动的概率。用MTTF和MTTR分别表示平均无故障时间和平均故障修复时间，则软件可维护性计算公式为（ 1/(1+MTTR) ）。
在ISO/IEC软件质量模型中，可移植性是指与软件可从某环境行移到另一环境的能力有关的一组属性，其子特性不包括（测试性）。
在对程序质量进行评审时，模块结构是一个重要的评审项，评审内容中不包括（数据结构）。
在ISO/IEC9126软件质量模型中，软件质量特性（功能性）包含质量子特性安全性。
在IS0/IEC软件质量模型中，易使用性是指与使用所需的努力和由一组规定或隐含的用户对这样使用所作的个别评价有关的一组属性，其子特性不包括（易分析性）。
在ISO/IEC 9126软件质量模型中，可靠性质量特性是指在规定的一段时间内和规定的条件下，软件维持在其性能水平有关的能力，其质量子特性不包括（安全性，可移植性）。
（易理解性）不属于软件质量特性中的可移植性。
（功能与模块之间的对应关系）不属于软件设计质量评审。
在设计中实现可移植性设计的规则不包括（可使用特定环境的专用功能）
软件质量属性中，（吞吐量）是指软件每分钟可以处理多少个请求。
系统可维护性的评价指标不包括（可移植性）。
系统可维护性是指维护人员理解、改正、改动和改进软件系统的难易程度，其评价指标不包括（一致性）。
将每个用户的数据和其他用户的数据隔离开，是考虑了软件的（功能性）质量特件。

软件设计师笔记06_结构化开发方法_精简考点

科目一考试中占2分左右，但是科目二占一道大题。

知识点结构图如下

系统分析概述

系统分析是一种问题求解技术，它将一个系统分解成各个组成部分，目的是研究各个部分如何工作、交互，以实现其系统目标。

系统分析的目的和任务

简而言之，系统分析就是调查，收集资料，分析，并给出系统分析报告（系统方案说明书）。

系统分析的主要步骤

系统分析的主要分为以下五步：

对当前系统进行详细的调查，收集数据。
建立当前系统的逻辑模型。
对现状进行分析，提出改进意见和新系统应达到的目标。
建立新系统的逻辑模型。
编写系统方案说明书

系统结构设计原则

为保证总体结构设计顺利完成，应遵循以下几条原则。

(1)分解-协调原则。
(2)自顶向下的原则。
(3)信息隐蔽、抽象的原则。
(4)一致性原则。
(5)明确性原则。
(6)模块之间的耦合尽可能小，模块的内聚度尽可能高。
(7)模块的扇入系数和扇出系数要合理。
(8)模块的规模适当。

系统设计的基本原理

(1)抽象。 (2)模块化。 (3)信息隐蔽。 (4)模块独立:低耦合、高内聚。

耦合性和内聚性

衡量模块独立程度的标准有两个:耦合性和内聚性。应尽量做到高内聚、低耦合，提高模块的独立性。

耦合性

耦合性是指模块与模块之间的联系紧密程度。一般模块之间的耦合性有7种类型。

耦合种类如图所示

每种耦合类型介绍如图所示

内聚性

内聚性是指模块内部元素之间联系的紧密程度。一个内聚程度高的模块应该只完成一个相对独立的特定子功能，而不是完成多个不同的功能。

内聚种类如图所示

每种内聚类型介绍如图所示

子系统划分的原则

(1)子系统要具有相对独立性。
(2)子系统之间数据的依赖性尽量小。
(3)子系统划分的结果应使数据冗余较小。
(4)子系统的设置应考虑今后管理发展的需要。
(5)子系统的划分应便于系统分阶段实现。
(6)子系统的划分应考虑到各类资源的充分利用。

模块设计原则

保持模块的大小适中。
尽可能减少调用的深度。
多扇入，少扇出。
单入口，单出口。
模块的作用域应该在模块之内【作用域在控制域内】。
功能应该是可预测的。

结构化分析

结构化分析的输出包括数据流图、数据字典和加工逻辑。

其中数据字典用来描述DFD中的每个数据流、文件以及组成数据流或文件的数据项，包括4类条目：数据流、数据项、数据存储和基本加工。

数据流图 DFD

数据流图用于描述数据在系统中如何被传送或变换，以及如何对数据流进行变换的功能或子功能，主要用于对功能建模。

数据流图建模应遵循（自顶向下、从抽象到具体）的原则。

数据流图中的基本图形元素包括数据流、加工、数据存储和外部实体。

外部实体: 是指存在于软件系统之外的人员、组织或其他系统;
数据流: 是由一组固定成分的数据组成，表示数据的流向;
加工: 是指输入数据流到输出数据流之间的变换;
数据存储: 用来表示存储数据。

加工

加工表示数据的处理。

加工描述了输入数据流到输出数据流之间的变换，也就是输入数据流经过什么处理后变成了输出数据流。

一个加工可以有多个输入数据流和多个输出数据流，但至少有一个输入数据流和一个输出数据流。

加工错误的情况

当一个加工有输入数据流但是没有输出数据流时，称之为“黑洞”加工。
当一个加工输入数据流不足以产生输出数据流时，称之为“灰洞”加工。

数据字典（DD）

数据流图描述了系统的分解，但没有对图中各成分进行说明。

数据字典就是为数据流图中的每个数据流、文件、加工，以及组成数据流或文件的数据项做出说明。

数据流图基本设计原则

数据守恒原则：对任何一个加工来说，其所有输出数据流中的数据必须能从该加工的输入数据流中直接获得，或者说是通过该加工能产生的数据
守恒加工原则：对同一个加工来说，输入与输出的名字必须不相同，即使它们的组成成分相同。
对于每个加工，必须既有输入数据流，又有输出数据流
外部实体与外部实体之间不存在数据流
外部实体与数据存储之间不存在数据流
数据存储与数据存储之间不存在数据流
父图与子图的平衡原则：子图的输入输出数据流同父图相应加工的输入输出数据流必须一致，此即父图与子图的平衡。父图与子图之间的平衡原则不存在于单张图
数据流与加工有关，且必须经过加工

真题

某考试系统的部分功能描述如下，审核考生报名表，通过审核的考生登录系统，系统自动为其生成一套试题，考试中心提供标准答案，问卷老师问卷，提交考生成绩，考生查看自己的成绩。若用数据流图对该系统进行建模，则（试题）不是外部实体。
结构化分析的输出不包括（结构图）。
某医院预约系统的部分需求为：患者可以查看医院发布的专家特长介绍及其就诊时间：系统记录患者信息，患者预约特定时间就诊。用DFD对其进行功能建模时，患者是（外部实体）；用ERD对其进行数据建模时，患者是（实体）。
以下关于数据流图中基本加工的叙述，不正确的是（加工规格说明需要给出实现加工的细节）
绘制分层数据流图(DFD)时需要注意的问题中，不包括（图中要表示出控制流）。
结构化分析方法中，数据流图中的元素在（数据字典）中进行定义。
数据流图建模应遵循（自顶向下、从抽象到具体）的原则。
某零件厂商的信息系统中，一个基本加工根据客户类型、订单金额、客户信用等信息的不同采取不同的行为，此时最适宜采用（判定表）来描述该加工规格说明。
模块A提供某个班级某门课程的成绩给模块B，模块B计算平均成绩、最高分和最低分，将计算结果返回给模块A ，则模块B在软件结构图中属于（变换）模块。
某航空公司拟开发一个机票预订系统，旅客预订机票时使用信用卡付款。付款通过信用卡公司的信用卡管理系统提供的接口实现。若采用数据流图建立需求模型，则信用卡管理系统是（外部实体）。
下列关于结构化分析方法的数据字典中加工逻辑的叙述中，不正确的是（加工逻辑必须描述实现加工的数据结构和算法）。
在采用结构化方法进行系统分析时，根据分解与抽象的原则，按照系统中数据处理的流程，用（数据流图）来建立系统的逻辑模型，从而完成分析工作。
结构化开发方法中，（过程设计）主要包含对数据结构和算法的设计。
结构化设计方法中使用结构图来描述构成软件系统的模块以及这些模块之间的调用关系。结构图的基本成分不包括（控制）。
在软件设计阶段进行模块划分时，一个模块的（作用范围应该在其控制范围之内）。

软件设计师笔记07_面向对象技术_精简考点

科目一考试大概有11分左右，科目二考试有一道大题。

基本概念

对象：对象是一个基本实体，包括数据（属性）和操作（方法）。
消息和消息通信：对象之间进行通信的一种方式叫做消息。消息是异步通信的。
类：类是对象的模板，它定义了对象的属性和方法。
继承：继承是父类与子类之间共享数据和方法的机制。这是类之间的一种关系。
重置/覆盖：在子类中重新定义父类中已经定义的方法。
重载：一个类可以有多个同名而参数类型不同的方法。
动态绑定：根据接收对象的具体情况将请求的操作与实现的方法进行连接（运行时绑定）。
多态：不同对象收到同样的消息产生不同的结果（软设一般只涉及过载多态。即同一个名字在不同的上下文中所代表的含义不同）。

类的类型

类可以分为三种类型，分别是实体类、边界类和控制类。

实体类：代表实体对象
控制类：描述一个用例所具有的事件流控制行为，控制一个用例中的事件顺序。通常情况下，控制类没有属性，但一定有方法。
边界类：描述外部参与者与系统之间的交互。常见的边界类有窗口、通信协议、打印机接口、传感器和终端等。

类图关系

类与类之间的关联关系可分为依赖、关联、聚合、组合和继承5种

依赖关系：若类A的方法中仅仅使用了类B的对象，那么类A依赖于类B。
泛化关系：泛化是一个类与它的一个或多个细化类之间的关系，表达一般与特殊的关系。
关联关系：关联是类与类之间，对象与对象之间的一种结构关系。
聚合关系：整体与部分的生命周期不同。购物车与商品是整体与部分的关系，购物车包含了商品，但是商品可以脱离购物车独立存在，这是一种聚合关系。
组合关系：整体与部分的生命周期相同。网店与商品之间是一种整体与部分的关系，商品是网店的一部分，如果网店不存在了，那么网店中的商品也不存在，它们之间是组合关系。
实现关系：接口与类之间的关系。
聚集关系：若其中一个较大的整体类包含一个或多个较小的部分类；则大类和小类是聚集关系。

组合是一种很强的"拥有"关系，"部分"和"整体"的生命周期通常一样。整体对象完全支配其组成部分，包括它们的创建和销毁等;

聚合同样表示"拥有"关系，但"部分"对象的生命周期也可以与"整体"对象不同，甚至"部分"对象可以脱离"整体"对象而单独存在。

面向对象

单一职责原则:设计目的单一的类。
开放封闭原则:对扩展开放，对修改封闭。
里氏替换原则:子类可以替换父类。
依赖倒置原则:要依赖于抽象，而不是具体实现;要针对接口编程，不要针对实现编程。
接口分离原则:不强迫客户依赖于他们不用的方法。
共同封闭原则：包中的所有类对于同一类性质的变化应该是共同封闭的。一个变化若对一个包产生影响，则将对该包中的所有类产生影响，而对于其他的包不造成任何影响。
共同重用原则：一个包中的所有类应该是共同重用的。如果重用了包中的一个类，那么就要重用包中的所有类。

多态

多态有不同的形式，分为参数多态、包含多态、过载多态和强制多态四种。

参数多态通过给出不同的类型参数，使得一个结构有多种类型;
包含多态是指同样的操作可用于一个类型及其子类型，即子类型化:
过载多态是指同一个名字在不同上下文中可代表不同的含义；
强制多态是指通过语义操作把一个变量的类型加以变换。

UML

UML由3个要素构成

UML的基本构造块
支配这些构造块如何放置在一起的规则和运用
整个UML语言的一些公共机制

UML的3种基本构造块

事物（对模型中最具有代表性的成分的抽象）
关系（把事物结合在一起）
图（聚集了相关的事物）

UML中的事物

UML 中有4种事物:结构事物、行为事物、分组事物和注释事物。

结构事物是指 UML 模型的静态部分，是模型中的名词，用来描述概念。如类、接口、用例、构件等。

行为事物是指 UML 模型的动态部分，是模型中的动词，用来描述行为。如交互、活动等。

分组事物是指 UML 模型的组织部分。最主要的分组事物是包，包是把元素组织在一起的一种机制。

注释事物是指 UML 模型的解释部分，用来描述，说明模型中的元素。

UML中的关系

UML 中有4种关系:依赖、关联、泛化和实现。

依赖

依赖是两个事物间的语义关系，其中一个事物(独立事物)发生变化会影响另一个事物(依赖事物)的语义。在图形上，把一个依赖画成一条可能有方向的虚线

关联

关联是一种结构关系，它描述了一组链，链是对象之间的连接。

聚集是一种特殊类型的关联，它描述了整体和部分间的结构关系。

其中关联分为组合和聚合,都是部分和整体的关系，其中组合之间关系更强。

聚合体现的是整体与部分、拥有的关系，即has-a的关系，此时整体与部分之间是可分离的。
组合同样体现整体与部分间的关系，是一种con-tains-a的关系，这种关系比聚合更强。它但此时整体与部分是不可分的。

关联和聚集如图所示。

泛化

泛化是一种特殊/一般关系，即子元素的对象可替代父元素的对象。用这种方法，子元素共享了父元素的结构和行为。

在图形上，把一个泛化关系画成一条带有空心箭头的实线，它指向父元素。

实现

实现是类元之间的语义关系，其中一个类元指定了由另一个类元保证执行的契约。

在两种情况下会使用实现关系:

一种是在接口和实现它们的类或构件之间;
另一种是在用例和实现它们的协作之间。

在图形上，把一个实现关系画成一条带有空心箭头的虚线，如图所示

UML中的关系总结

依赖关系：一个事物发生变化影响另一个事物。
泛化关系：特殊/一般关系。
关联关系：描述了一组链，链是对象之间的连接。
聚合关系：整体与部分生命周期不同。
组合关系：整体与部分生命周期相同。
实现关系：接口与类之间的关系。

UML中的图

类图：描述系统中的对象、接口、类之间的关系，是系统的静态设计视图。
对象图：描述对象之间的关系。对象图描述了在类图中所建立的对象的静态快照。
用例图：描述系统与外部系统及用户的交互。从用户使用系统的角度对系统进行了划分；
序列图：描述了对象如何通过消息互相交互，说明了消息如何在对象之间被发送和接收以及发送的顺序。。
通信图：不强调时间顺序，只强调事件之间的通信。
状态图：用于对一个特定对象的动态行为建模，说明了一个对象的生命周期——对象可以经历的各种状态，以及引起对象从一个状态向另一个状态转换的事件。
活动图：是一种特殊的状态图，描述一个业务过程或者一个用例的活动的顺序流。
构件图：描述系统的物理结构，它可以用来显示程序代码如何分解成模块。
部署图：描述系统中硬件和软件的物理架构，它描述构成系统架构的软件构件、处理器和设备。
顺序图：是一种交互图，它由一组对象或参与者以及它们之间可能发送的消息构成。顺序图是强调消息的时间次序的交互图。

UML图中

关联关系是普通直线。
依赖关系是虚线。
聚集关系是黑色方块线。
组合关系是黑色三角线。
泛化关系是白色三角线。

设计模式

设计模式的要素

设计模式的核心在于提供了相关问题的解决方案，使得人们可以更加简单方便地复用成功的设计和体系结构。

设计模式的四个基本要素：

模式名称
问题：问题描述了应该在何时使用模式。
解决方案：解决方案描述了设计模式的具体内容
效果：描述了设计模式应用的效果以及使用设计模式需要权衡的问题。

简而言之,每一个设计模式都集中于一个特定的面向对象设计问题或设计要点，描述了什么时候使用它，在另一些条件下是否还能使用，以及使用的效果和如何取舍。

设计模式的类别

创建型模式：主要抽象了实例化过程,用于帮助系统如何创建对象。
结构型模式：主要处理类和对象的组合
行为型模式：主要涉及算法和对象间职责的分配。行为设计模式不仅描述对象或类的模式，还描述了它们之间的通信模式。

各个设计模式的应用场景

装饰器模式：无法对已有的类进行扩充的时候，可以动态的给对象添加一些额外的功能。
桥接模式：将抽象部分与它的实现部分分离，使它们都可以独立地变化。
外观模式：为复杂系统提供简化接口（隐藏内部细节，对外暴露单一入口）
组合模式：处理树形结构（整体与部分可统一操作，如文件夹与文件）
观察者模式：处理一对多关系（一个主题变化，多个观察者自动更新）
代理模式：控制对对象的访问权限（如远程访问、权限校验、延迟加载）
命令模式：将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作。
策略模式：多个算法 / 策略（如排序算法、支付方式），需动态切换
责任链模式：让多个对象依次处理请求（每个对象决定自己处理或传递给下一个）
享元模式：由于大量对象造成很大开销的时候，可以运用共享技术支持大量相似对象的复用。
适配器模式：若接口不符合需求时，将该类接口转换为想要的接口。
中介者模式：用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互。如使一个后端数据模型能够被多个前端用户界面连接，采用此模式最合适。

创建型设计模式的应用场景结构型设计模式应用场景行为型设计模式应用场景

真题

在面向对象设计时，如果重用了包中的一个类，那么就要重用包中的所有类，这属于（共同重用）原则。
在领域类模型中不包含（领域对象）。
在面向对象方法中，两个及以上的类作为一个类的父类时，称为（多重继承），使用它可能造成子类中存在（二义性）的成员。
（泛化）是一个类与它的一个或多个细化类之间的关系，即一般与特殊的关系。
在面向对象的系统中，对象是运行时实体，其组成部分不包括（消息）；一个类定义了一组大体相似的对象，这些对象共享（属性和行为）。
采用面向对象方法进行系统开发时，以下与新型冠状病毒有关的对象中，存在“一般-特殊’关系的是（确诊病人和治愈病人）。
对象的（状态）标识了该对象的所有属性(通常是静态的)以及每个属性的当前值(通常是动态的)。
在面向对象方法中，支持多态的是（动态绑定）。
（过载）多态是指操作（方法）具有相同的名称、且在不同的上下文中所代表的含义不同。
采用面向对象方法进行系统开发时，需要对两者之间关系创建新类的是（医生和病人）。
对采用面向对象方法开发的系统进行测试时，通常从不同层次进行测试。测试类中定义的每个方法属于（算法）层。
在下列机制中，（动态绑定）是指过程调用和响应调用所需执行的代码在运行时加以结合；而（静态绑定）是过程调用和响应调用所需执行的代码在编译时加以结合。
采用面向对象方法进行软件开发，在分析阶段，架构师主要关注系统的（行为）。
进行面向对象系统设计时，修改某个类的原因有且只有一个，即一个类只做一种类型的功能，这属于（单一责任）原则。
在面向对象方法中,多态指的是（客户类无需知道所调用方法的特定子类的实现）。
以下关于面向对象继承的叙述中，错误的是（继承仅仅允许单重继承，即不允许一个子类有多个父类）。

UML

在UML用例图中，参与者表示（人、硬件或其他系统可以扮演的角色）。
UML中关联是一个结构关系，描述了一组链。两个类之间（可以有多个由不同角色标识的）关联。
在UML图中，（部署）图用于展示所交付系统中软件组件和硬件之间的物理关系。
对一个复杂用例中的业务处理流程进行进一步建模的最佳工具是UML （活动图）。
UML包图展现由模型本身分解而成的组织单元及其依赖关系，以下关于包图的叙述中，不正确的是（一个元素可以被多个包拥有）。
UML构件图(component diagram)展现了一组构件之间的组织和依赖，专注于系统的静态（实现）视图，图中通常包括构件、接口以及各种关系。

设计模式

为图形用户界面（GUI）组件定义不同平台的并行类层次绩构，适合采用（抽象工厂）模式。
（策略）模式定义一系列的算法，把它们一个个封装起来，并且使它们可以相互替换，使得算法可以独立于使用它们的客户而变化。
以下关于单例模式的描述中，正确的是（它能够保证一个类只产生唯一的一个实例）。
（观察者）设计模式能使一个对象的状态发生改变时通知所有依赖它的监听者。
在发布-订阅消息模型中，订阅者订阅一个主题后，当该主题有新消息到达时，所有订阅者都会收到通知。（观察者）设计模式最适合这一模型。
（命令）设计模式将一个请求封装为一个对象，从而使得可以用不同的请求对客户进行参数化，对请求排队或记录请求日志，以及支持可撤销的操作。
欲使一个后端数据模型能够被多个前端用户界面连接，采用（中介者）模式最适合。
某旅游公司欲开发—套软件系统，要求能根据季节，节假日等推出不同的旅行定价包，如淡季打折、一口价等。实现该要求适合采用（策略）模式，该模式的主要意图是（定义一系列的算法，把它们一个个封装起来，并且使它们可以相互替换）
因使用大量的对象而造成很大的存储开销时，适合采用（享元）模式进行对象共享，以减少对象数量从而达到较少的内存占用并提升性能。
某公司欲开发一个软件系统的在线文档帮助系统，用户可以在任何一个查询上下文中输入查询关键字，如果当前查询环境下没有相关内容，则系统会将查询按照一定的顺序转发给其他查询环境。基于上述需求，采用（责任链模式）最为合适。
- 在责任链模式中，很多对象由每一个对象对其下家的引用而连接起来形成一条链。请求在这个链上传递，直到链上的某一个对象决定处理此请求。

软件设计师笔记08_算法设计与分析_精简考点

科目一考试有4分左右。

知识点结构图

基本概念

设计算法时，通常应考虑以下原则：首先说设计的算法必须是"正确的"，其次应有很好的"可读性"，还必须具有"健壮性"，最后应考虑所设计的算法具有"高效率与低存储量"。

一个算法还具有下列5个重要特性。即有穷性、确定性、可行性、输入、输出。

有穷性。一个算法必须总是在执行有穷步之后结束，且每步都可在有穷时间内完成。
确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

一个“好”算法的要求

正确性、健壮性、高效性

复杂度

复杂度是指算法执行所需要的时间和空间资源的量。分为时间复杂度和空间复杂度。

如图是一些不同数量级的复杂度，复杂度由小到大排列。

时间复杂度

算法的时间复杂度分析主要是分析算法重复执行的次数，即算法从开始到结束所需要的执行次数作为算法的时间度量。

一般不必要精确计算出算法的时间复杂度，只需要大致计算出响应的数量级即可，例如O(1)、O(n)、O(n^2^)等。

空间复杂度

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

分治法贪心法回溯法动态规划法

判断此类题目，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的。

分治法：

分治法：将大问题分解为各个小问题，各个小问题相对独立，然后分开解决各个小问题。常见分治法：递归。

动态规划法（全局最优）

动态规划法：与分治法类似的思想，也是将大问题分解为各个小问题，然后分开解决各个小问题。但是此处的各个小问题是互相关联的，因此需要记录下各个小问题的解，然后从中找出最优解。

动态规划法与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。

贪心法（局部最优）

贪心法和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

即贪心法中它所做的每一步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。一般可以快速得到相对满意的解，但得不到全局最优解。

回溯法

回溯法：可以系统地搜索一个问题的所有解或任一解。一般用于解决迷宫类的问题。

真题案例

已知算法A的运行时间函数为T(n)=8T(n/2)+n2，其中n表示问题的规模，则该算法的时间复杂度为（）。另已知算法B的运行时间函数为T(n)=XT(n/4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为（）。

A 15 B 17 C 63 D 65

正确答案：C

解题思路：使用主定理来求解算法的时间复杂度。主方法适用于形如(T(n) = aT(n / b)+f(n))的式子。

第一问：求算法 A 的时间复杂度

对于算法A，其运行时间函数(T(n)=8T(n / 2)+n^{2}) ，因此这里的(a = 8)，(b = 2) ，(f(n)=n^{2}) 。

计算(\log_{b}a)：根据对数运算法则，(\log_{b}a=\log_{2}8 = 3) 。

比较(f(n))与(n^{\log_{b}a})：(n^{\log_{b}a}=n^{3}) ，(f(n)=n^{2}) ，根据主方法的第一种情况，时间复杂度(T(n)=\Theta(n^{\log_{b}a})=\Theta(n^{3})) ，所以第一问答案是 D。

第二问：求算法 B 中X的最大值

同样使用主方法分析算法 B：算法B的运行时间函数(T(n)=XT(n / 4)+n^{2}) ，其中(a = X)，(b = 4) ，(f(n)=n^{2}) ，(\log_{b}a=\log_{4}X) 。

若算法B和算法A效率一样，即算法B的时间复杂度也为(\Theta(n^{3})) ，根据主方法，当(\log_{4}X = 3) 时，可通过对数运算求解X，即(X = 4^{3}=64) 。

确定X的最大值：要使算法B比算法A快，那么算法B的时间复杂度要低于(\Theta(n^{3})) ，即(\log_{4}X<3) ，所以(X < 4^{3}=64) ，那么X的最大值为63 。

真题案例

本题可使用主定理（Master Theorem）来求解算法的时间复杂度。

主定理适用于形如(T(n)=aT(n / b)+f(n))（(a\geq1)，(b > 1)，(f(n))是渐近正函数）的递推式。

由主定理式可知 (a = 6)，(b = 5)，(f(n)=n) 。计算(\log_{b}a)，即(\log_{5}6) 。

比较(f(n))与(n^{\log_{b}a}) ，因此(T(n)=\Theta(n^{\log_{5}6})) 。

真题

算法

以下关于字符串的叙述中，正确的是（字符串的长度是指串中所含字符的个数）。
通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系，是（顺序存储）的特点。
某个算法的时间复杂度递归式T(n)=T(n-l)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（ n^2 ），若问题的规模增加了16倍，则运行时间增加（ 256 ）倍。
在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（动态规划）算法设计策略;若定义问题的解空间，以深度优先的方式搜索解空间，则采用（回溯）算法设计策略。

线性表

对于线性表，相对于顺序存储，采用链表存储的缺点是（数据元素之间的关系需要占用存储空间，导致存储密度不高）。
以下关于线性表存储结构的叙述，正确的是（线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级）。
当函数调用执行时，在栈顶创建项目用来支持被调用函数执行的一段存储空间称为活动记录或栈帧，栈帧中不包括（全局变量）。
若一个栈初始为空，其输入序列是1，2，3，…，n-1，n，其输出序列的第一个元素为k(1≤k≤「n/2」)，则输出序列的最后一个元素是（不确定的）。
队列的特点是先进先出，若用循环单链表表示队列，则（入队列和出队列操作都不需要遍历链表）。
采用循环队列的优点是（入队和出队操作都不需要移动队列中的其他元素）。

矩阵

（三元组顺序表和十字链表）是对稀疏矩阵进行压缩存储的方式。
对于一个n阶的对称矩阵A,将其下三角区域(含主对角线)的元素按行存储在一维数组S中,设元素A[i][j]存放在S[K]中，且S[1]=A[0][0]，则k与i、j (i≤j)的对应关系是（）。

树

已知树T的度为4，且度为4的结点数为7个、度为3的结点数5个、度为2的结点数为8个、度为1的结点数为10个，那么T的叶子结点个数为（ 40 ）。(注：树中节点个数称为结点的度，结点的度中的最大值称为树的度。）
当二叉数中的结点数目确定时，（完全二叉树）的高度一定是最小的。
- 完全二叉树是让二叉树的每一层的结点都尽可能全满，除了最底层，此时树的高度一定是最小的。
二叉树的高度是指其层数，空二叉树的高度为0，仅有根结点的二叉树高度为若某二叉树中共有1024个结点，则该二叉树的高度是整数区间（ [11, 1024] ）中的任一值。
具有3个结点的二叉树有5种，可推测出具有4个结点的二叉树有（ 14 ）种。
已知某二叉树的先序遍历序列为A B C D E F、中序遍历序列为B A D C F E，则可以确定该二叉树（高度为4（即结点分布在4层上））。
某二叉树的中序、先序遍历序列分别为{20,30,10,50,40}、{10,20,30,40,50}，则该二叉树的后序遍历序列为（ 30,20,50,40,10 ）。
设m和n是某二叉树上的两个结点，中序遍历时，n排在m之前的条件是（ m在n的右边）。
- 对于二叉树的中序遍历，是先遍历根结点的左子数，再访问根结点，最后遍历根结点的右子树。所以结点n排在结点m之前的条件是n在m的左边，也就是m在n的右边。、
设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含k个节点时，其二叉链表节点中必有（ k+1 ）个空的孩子指针。
某二叉树的先序遍历序列为ABCDEF ，中序遍历序列为BADCFE ，则该二叉树的高度(即层数)为（ 4 ）。
若一棵二叉树的高度（即层数）为h，则该二叉树（最多有2h-1个结点）。
以下关于哈夫曼树的叙述，正确的是（哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近）。
具有3个结点的二叉树有（ 5 ）种形态。
设由三棵树构成的森林中，第一棵树、第二棵树和第三棵树的结点总数分别为n1、 n2和n3。将该森林转换为—棵二叉树，那么该二叉树的右子树包含_（ n2+n3 ）个结点。
一个高度为h的满二叉树的结点总数为2h-1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4，5，6，7，依此类推。那么，在一棵满二叉树中，对于编号为m和n的两个结点，若n=2m+1,则（ n是m的右孩子）。

图

某图G的邻接表中共有奇数个表示边的表结点，则图G（是有向图）。
若无向图G有n个顶点e条边，则G采用邻接矩阵存储时，矩阵的大小为（ n2 ）。
对有向图G进行拓扑排序得到的拓扑序列中，顶点Vi在顶点Vj之前，则说明G中（一定不存在有向弧 <vj, vi> ）。
在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（可能存在vi到vj的路径，而不可能存在Vj到vi的路径）。
以下关于无向连通图G的叙述中，不正确的是（ G中任意两个顶点之间均有边存在）。
设一个包含n个顶点、e条弧的简单有向图采用邻接矩阵存储结构（即矩阵元素A[i][j]等于1或0，分别表示顶点i与顶点j之间有弧或无弧）,则该矩阵的非零元素数目为（ e ）。
某简单无向连通图G的顶点数为n，则图G最少和最多分别有（ n-1,n*(n-1)/2 ）条边。

算法

对长度为n的有序顺序进行折半查找(即二分查找)的过程可用一棵判定树表该判定树的形态符合（平衡二叉树）的特点。
在线性表L中进行二分查找，要求L（序存储，元素有序排列）。
对某有序概序表进行折率查找《二分查找》时，进行比较的关键字序列不可能是（ 90,85,61,77,42 ）
在55个互异元素构成的有序表A[1..55]中进行折半查找（或二分查找，向下取整）。若需要找的元素等于A[19]，则在查找过程中参与比较的元素依次为（ A[28]、A[14]、A[21]、A[17] ）、A[19]。
对于有序表(8,15, 19, 23, 26, 31, 40, 65, 91)，用二分法进行查找时，可能的关键字比较顺序为（ 26,40,65 ）。
以下关于哈希(Hash,散列)查找叙述中，正确的是（构造哈希函数时应尽量使关键字的所有组成部分都能起作用）。
对于一个初始无序的关键字序列，在下面的排序方法中，（ ②③④⑤ ）第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。 ①直接插入排序②冒泡排序③简单选择排序④堆排序⑤快速排序⑥归并排序
归并排序算法在排序过程中，将待排序数组分为两个大小相同的子数组，分别对两个子数组采用归并排序算法进行排序,排好序的两个子数组采用时间复杂度为O(n)的过程合并为一个大数组。根据上述描述，归并排序算法采用了（分治）算法设计策略。归并排序算法的最好和最坏情况下的时间复杂度为（）。
下列排序算法中，占用辅助存储空间最多是（归并排序）。

软件设计师笔记09_数据库技术基础_精简考点

科目一考试有6分左右。科目二考试占一道大题。

知识点结构图

基本概念

数据库管理系统的分类

关系型数据库系统（RDBS）：是指采用关系模型作为数据组织的数据库系统，如MySQL、Oracle、SQL Server等。
面向对象的数据库系统（OOBS）：是指采用面向对象模型作为数据组织的数据库系统，如ObjectDBMS、VisualFoxPro等。
对象关系数据库系统（ORDBS）：是指采用对象关系模型作为数据组织的数据库系统，如PostgreSQL、Oracle等。

数据库三级模式两级映像

数据库体系结构大多采用"三级模式和两级映像"。

如图所示

三级模式

外模式-视图；概念模式-基本表；内模式-物理文件。

概念模式（也称模式）。它是数据库中全体数据的逻辑结构和特征的描述，它由若干个概念记录类型组成，只涉及类型的描述，不涉及具体的值。概念模式反映的是数据库的结构和特征。
外模式（也称用户模式或子模式）。它是用户与数据库系统的接口，是用户用到的那部分数据的描述，由若干个外部记录类型组成。用户使用数据操作语言对数据进行操作，实际上是对外模式的外部记录进行操作。
内模式（也称存储模式），它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式，定义所有的内部记录类型、索引和文件的组织方式以及数据控制方面的细节。

简而言之，外模式是对接用户的，内模式是对接数据库系统的，而概念模式连接这两者的中间层，它是是用户和数据库系统之间的桥梁。

两级映像

外模式-概念模式映射，保证数据逻辑独立性，即数据的逻辑结构发生变化后，用户程序也可以不修改。只需要修改外模式和概念模式之间的映像。
概念模式-内模式映射，保证数据物理独立性，即当数据的物理结构发生改变时，应用程序不用改变。只需要修改概念模式和内模式之间的映像。

数据模型

数据模型是对现实世界数据特征的抽象。

数据模型的三要素是数据结构、数据操作、数据的约束条件。

数据结构：是所研究的对象类型的集合，是对系统静态特性的描述。
数据操作：是对数据库中各种对象(型)的实例(值)允许执行的操作集合，包括操作及操作规则。例如操作有检索、插入、删除和修改，操作规则有优先级别等。
数据的约束条件：是一组完整性规则的集合。也就是说，对于具体的应用数据必须遵循特定的语义约束条件，以保证数据的正确、有效、相容。

E-R 模型图

E-R 模型图

E-R模型图，所采用的3个主要概念是实体、联系和属性。

实体：用矩形表示，每个实体由一组属性表示，包括主键、候选键、外键。
联系：用菱形表示，分为一对一（1:1）、一对多（1:n）、多对多（m:n）。
属性：用椭圆表示，是实体某方面的特性。E-R 模型中的属性分为：①简单和复合属性；②单值和多值属性；③null 属性；④派生属性

两个不同实体集之间的3种联系类型

如图所示

两个以上不同实体集之间的联系类型

两个以上不同实体集之间存在 1:1:1、1:1:n、1:m:n 和 r:m:n 的联系。

如图表示了3个不同实体集之间的联系。例如图(b)表示病房、病人和医生之间一对多对多(1∶n:m)的联系，联系名为PD。表示了一个病房有多个病人和多个医生，一个医生只负责一个病房，一个病人只属于一个病房的语义

例题：假设学校有若干个系，每个系有若干名教师和学生;每个教师可以担任若干门课程,并参加多个项目;每个学生可以同时选修多门课程。请设计该学校教学管理系统的E-R模型，要求给出每个实体、联系的属性。

解题：该学校教学管理系统的E-R模型应该有5个实体，即系、教师、学生、项目和课程。

(1)设计各实体属性如下:
- 系(系号，系名，主任名)
- 教师(教师号，教师名，职称)
- 学生(学号，姓名，年龄，性别)
- 项目(项目号，名称，负责人)
- 课程(课程号，课程名，学分)
(2)各实体之间的联系如下:
- 教师担任课程的 1∶n“任课”联系;
- 教师参加项目的 n:m“参加”联系;
- 学生选修课程的n:m“选修”联系;
- 教师、学生与系之间所属关系的1:n:m“领导”联系。其中“参加”联系有一个排名属性,“选修”联系有一个成绩属性。

则对应的E-R模型图如下所示。

关系模型

关系模型是最常用的数据模型之一。

属性和域

属性：在现实世界中，要描述一个事物，常常取其若干特征来表示。这些特征称为属性。
域：每个属性的取值范围的集合，称为该属性的域。

关系的三种类型

基本关系(又称基本表、基表)：这是实际存在的表，它是实际存储数据的逻辑表示。
查询表：它是查询结果对应的表。
视图表：它是由基本表或其他视图表导出的表。由于它本身不独立存储在数据库中，数据库中只存放它的定义，所以常称为虚表。

5种基本的关系代数运算

5种基本的关系代数运算分别为并，差，笛卡尔积，投影，选择。其他运算包括可以通过基本的关系运算导出。

自然连接关系运算符

属性列数 = 二者之和 - 重复的列数

范式

（1）1NF：每个分量（属性）不可分割。
（2）2NF：满足 1NF，而且消除非主属性对候选键的部分依赖。
（3）3NF：满足 2NF，而且消除非主属性对候选键的传递依赖。

第一范式（1NF）：原子性

第一范式要求表中的所有字段值都是不可分解的原子值，即每个字段都是最小的数据单位，不可再分。

第二范式（2NF）：唯一性

在满足第一范式的基础上，第二范式进一步要求表中的每个字段都必须与主键完全相关，而不能仅与主键的一部分相关。这主要针对联合主键的情况，即一个表中只能保存一种数据类型，不可以将多种数据类型保存在同一张表中。

第三范式（3NF）：独立性

第三范式要求表中的每个字段都必须直接与主键相关，而不能间接相关。也就是说，非主键字段之间不能存在依赖关系，它们必须直接依赖于主键。

SQL语言

普通查询

分组查询

GROUPBY子句：在WHERE子句后面加上GROUPBY子句可以对元组进行分组，保留字GROUPBY后面跟着一个分组属性列表。最简单的情况是，FROM子句后面只有一个关系，根据分组属性对其元组进行分组。SELECT子句中使用的聚集操作符仅用在每个分组上。
HAVING子句：假如元组在分组前按照某种方式加上限制，使得不需要的分组为空，则在GROUPBY子句后面跟一个HAVING子句即可。

当元组含有空值时，应注意以下两点：

a、空值在任何聚集操作中都被忽略。它对求和、求平均值和计数都没有影响，也不能是某列的最大值或最小值
b、NULL值可以在分组属性中看作一个一般的值。

SQL访问控制（授权与收回权限）

SQL访问控制是指控制用户对数据访问的权限。应具有以下功能：

通过 GRANT 和 REVOKE 将授权通知系统，并存入数据词典。
当用户提出请求时，根据授权情况检查是否执行操作请求。

GRANT 授权语句

REVOKE 收回权限语句

事务并发

事务特性

事务具有原子性、一致性、隔离性和持久性。这4个特性也称事务的 ACID 性质。

原子性(Atomicity)：一个事务中的所有操作在数据库中要么全做，要么全都不做
一致性(Consistency)：一个事务执行的结果必须保证数据库从一个一致性状态变到另一个一致性状态。
隔离性(Isolation)：事务与事务之间相互隔离。当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程，对其他事务都是不可见的。
持久性(Durability)：一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也将永久有效。

事务恢复的3个步骤

反向扫描文件日志，查找该事务的更新操作
对事务的更新操作执行逆操作
继续反向扫描日志文件，查找该事务的其他更新操作，并做同样的处理，直到事务的开始标志

数据库故障和备份

数据库一般遭遇的故障类型如下

事务内部故障：事务内部的故障有的可以通过事务程序本身发现。例如运算故障，事务发生死锁等。
系统故障：通常称为软故障，是指造成系统停止运行的任何事件，使得系统要重新启动。例如系统崩溃、操作系统死机等。
介质故障：通常称为硬故障，如磁盘损坏、磁头碰撞和瞬时强磁干扰。此类故障发生的几率小，但破坏性最大
计算机病毒：是一种人为的故障和破坏，是在计算机程序中插入的破坏，计算机功能或者数据可以繁殖和传播的一组计算机指令或程序代码。

数据库的备份方法

恢复的基本原理是“建立冗余数据”(重复存储)。建立冗余数据的方法是进行数据转储和登记日志文件。

数据的转储分为静态转储和动态转储、海转储和增量转储、日志文件。

静态转储和动态转储：
- 静态转储是指在转储期间不允许对数据库进行任何存取、修改操作
- 动态转储是指在转储期间允许对数据库进行存取、修改操作
海量转储和增量转储：
- 海量转储是指每次转储全部数据
- 增量转储是指每次只转储上次转储后更新过的数据
日志文件。在事务处理的过程中，把对数据库的插入，删除和修改的每一次操作写入日志文件。一旦发生故障，利用日志文件回退到事务的初始状态。

数据库的并发控制的问题

并发操作带来的数据不一致性有三类:丢失修改、不可重复读和读脏数据。如图 9-30 所示。

丢失修改

如图 9-30(a)所示，事务T1、T2都是对数据 A 做减1操作。事务 T1 在时刻t5 把 A 修改后的值 15 写入数据库，但事务T2 在时刻t7再把它对 A 减1后的值 15 写入。两个事务都是对A的值进行减1操作并且都执行成功，但 A 中的值却只减了 1。

例如火车售票系统，T1与T2各售出了一张票，但数据库里的存票却只减了一张，造成数据的不一致。原因在于T1事务对数据库的修改被T2事务覆盖而丢失了，破坏了事务的隔离性。

不可重复读

如图 9-30(b)所示，事务T1 读取 A、B 的值后进行运算，事务T2在 t6 时刻对 B的值做了修改以后，事务T1又重新读取 A、B的值再运算，同一事务内对同一组数据的相同运算结果不同，显然与事实不相符。同样是事务T2干扰了事务T1的独立性。

读脏数据。

如图 9-30(c)所示，事务T1 对数据C 修改之后，在t3时刻事务T2读取修改后的 C 值做处理，之后事务 T1 回滚，数据C恢复了原来的值，事务T2对C所做的处理是无效的，它读的是被丢掉的垃圾值。

在上面的例子中，在事务并行处理的过程中对相同数据进行访问会导致了数据的不一致性，解决该问题可以从保证事务的隔离性入手。

并发控制技术

有多种技术用来解决并发操作带来的数据不一致性问题，主要有封锁等。

并发控制的主要技术是封锁。封锁的类型有排它锁(简称X锁或写锁)和共享锁(简称S锁或读锁)。

封锁的类型

排他锁（X/写锁）。若事务T对数据对象 A加上X锁，则只允许事务T读取和修改 A，其他事务都不能再对 A 加任何类型的锁，直到事务T释放 A上的锁。
共享锁（S/读锁）。若事务T对数据对象 A 加上S锁，则只允许事务T读取 A，但不能修改 A，其他事务只能再对A加S锁，直到事务T释放A 上的S锁。这就保证了其他事务可以读 A，但在事务 T 释放A上的S锁之前不能对A进行任何修改。

三级封锁协议

（1）一级：修改数据前先加 X 锁，事务结束后释放，可解决丢失修改问题。
（2）二级：在一级基础上，读数据之前加 S 锁，读完后释放即可解决读脏数据问题。
（3）三级：在一级基础上，读数据之前加 S 锁，直到事务结束后释放 S 锁，即可解决丢失修改、读脏数据、不可重复读三个数据不一致的问题。

真题

采用三级模式结构的数据库系统中，如果对一个表创建聚簇索引，那么改变的是数据库的（内模式）。
数据的物理独立性和逻辑独立性分别是通过修改（模式与内模式之间的映像、外模式与模式之间的映像）来完成的。
数据库系统通常采用三级模式结构：外模式、模式和内模式。这三级模式分别对应数据库的视图、基本表和存储文件。
以下关于数据库两级映像的叙述中，正确的是（模式/内模式映像实现了概念模式到内模式之间的相互转换）。
采用三级结构/两级映像的数据库体系结构，如果对数据库的一张表创建聚簇索引，改变的是数据库的（内模式）。

软件设计师笔记10_网络与信息安全基础知识_精简考点

科目一考试有3-7分左右。

知识点结构图

计算机网络概述

计算机网络的功能：数据通信、资源共享、负载均衡、高可靠性。

计算机网络按照数据通信和数据处理的功能分为两层：内层通信子网和外层资源子网

计算机网络的分类

计算机网络的分类方式很多,按照不同的分类原则,可以得到各种不同类型的计算机网络。

按通信距离可分为广域网、局域网和城域网

如图所示

网络的拓扑结构

常见的网络拓扑结构包括总线型结构、星型结构、环型结构、树型结构、分布式结构，如图所示。

总线型结构（线路利用率低、干扰大、但是价格低）
星型结构(交换机形成的局域网、中央单元负荷大）
环型结构（流动方向固定、效率低,扩充难）
树型结构（总线型的扩充、分级结构）
分布式结构（任意节点连接、管理难、成本高)

注意：广域网与局域网所使用的网络拓扑结构有所不同，广域网多用分布式或树型结构，而局域网常使用总线型、环型、星型或树型结构。

OSI参考模型

ISO/OSI 的参考模型一共有七层，如图所示。由低层至高层分别为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

应用层:实现具体的应用功能。
表示层:数据的格式与表达、加密、压缩。
会话层:建立、管理和终止会话。
传输层:端到端的连接。
网络层:分组传输和路由选择。
数据链路层:传送以帧为单位的信息。
物理层:二进制传输。

ISO/OSI 参考模型的信息流向

假设 A 系统的用户要向 B 系统的用户传送数据。流向如下

A 系统用户的数据先送入应用层，该层给它附加控制信息 AH(头标)后，送入表示层。
表示层对数据进行必要的变换并加头标 PH 后送入会话层。
会话层也加头标 SH 送入传输层。
传输层将长报文分段后并加头标 TH 送至网络层。
网络层将信息变成报文分组，并加组号 NH 送数据链路层。
数据链路层将信息加上头标和尾标(DH 及 DT)变成帧，经物理层按位发送到对方(B 系统)。

B 系统接收到信息后,按照与 A 系统相反的动作,层层剥去控制信息,最后把原数据传送给B系统的用户。

可见，两系统中只有物理层是实通信，其余各层均为虚通信。因此图中只有两物理层之间有物理连接，其余各层间均无连线。

ISO/OSI 参考模型中各层对应的网络设备

中继器是物理层设备，其作用是对接收的信号进行再生放大，以延长传输的距离。
网桥是数据链路层设备，可以识别MAC地址，进行帧转发。
交换机是由硬件构成的多端口网桥，也是一种数据链路层设备。
路由器是网络层设备，可以识别IP地址，进行数据包的转发。

ISO/OSI 参考模型中的各个协议

简单网络管理协议SNMP，它的传输层协议是UDP。即该协议的报文封装在（ UDP ）。

常见协议功能

邮件相关的

SSL是为网络通信提供安全及数据完整性的一种安全协议，在传输层对网络连接进行加密。在设置电子邮箱时使用SSL协议，会保障邮箱更安全。
HTTPS协议是由HTTP加上TLS/SSL协议构建的可进行加密传输、身份认证的网络协议，主要通过数字证书、加密算法、非对称密钥等技术完成互联网数据传输加密，实现互联网传输安全保护。
PGP是一套用于消息加密、验证的应用程序。PGP加密中每个公钥均绑定唯一的用户名和/或者E-mail地址。
MIME是设定某种扩展名的文件用一种应用程序来打开的方式类型。它是一个互联网标准，扩展了电子邮件标准。

文件相关的

FTP是一种用于在不同设备之间传输文件的协议。但是FTP传输的数据是明文形式的，不安全。
TFTP是FTP协议的简化版本，没有安全机制，仅仅支持读写文件。
SFTP 协议基于SSH协议，提供了加密和认证机制，可以保证传输的数据是安全的。SFTP使用的TCP端口号默认是22。
ICMP 协议是一种用于在IP网络中发送控制消息的协议，常用于网络故障排除。ICMP本身不传输数据，不适用于文件传输。

安全相关的

TCP是可靠的传输层协议，与安全无关。
TLS安全传输层协议用于在两个通信应用程序之间提供保密性和数据完整性。
SSH 是建立在应用层和传输层基础上的安全协议。SSH 是目前较可靠，专为远程登录会话和其他网络服务提供安全性的协议。

Telnet 协议提供了访问远程主机的功能，使本地用户可以通过TCP连接登录到远程主机上，像使用本地主机一样使用远程主机的资源。Telnet协议使用TCP端口23号，但是未经加密，因此是不安全的。

TCP和UDP

目前主要的传输层协议为TCP和UDP。

TCP协议的是现较为复杂，采用3次握手建立连接，传输过程中能实现可靠传输、流量控制以及拥塞控制，因而也带来了较大开销。
UDP协议主要通过端口号实现传输层级的寻址，开销也小。

TCP和UDP协议均提供了端口寻址的功能。但是连接管理、差错校验和重传以及流量控制均为TCP的功能。

HTTP的一次请求过程

当在Web浏览器的地址栏中输入某URL,并按下回车，则处理过程如下：

(1)对URL进行DNS域名解析，得到对应的IP地址；
(2)根据这个IP，找到对应的服务器，发起TCP连接，进行三次握手；
(3)建立TCP连接后发起HTTP请求；
(4)服务器响应HTTP请求，浏览器得到HTML代码；
(5)浏览器解析HTML代码，并请求HTML代码中的资源.如js、css图片等；
(6)浏览器将页面呈现给用户；
(7)通信完成，断开TCP连接。

浏览器和服务器

在HTTPS中，浏览器和服务器之间的通信需要进行加密，以保证数据传输的安全性。

HTTPS使用SSL/TLS协议来实现加密通信。SSL/TLS协议使用了公钥加密和对称加密两种加密方式。

在握手阶段，浏览器和服务器会协商出一个会话密钥，用于后续的通信加密。这个会话密钥是使用公钥加密传输的，以保证传输过程中的安全性。
后续的通信就会使用对称加密方式，使用会话密钥进行加密和解密。

安全措施

设备防雷击属于物理线路安全措施
入侵检测和流量控制属于网络安全措施
漏洞发现与补丁管理属于系统安全措施。

网络攻击

跨站脚本是一种安全攻击，其中攻击者在看上去来源可靠的链接中恶意嵌入译码。它将代码注入到网页上，其他用户在观看网页时就会受到影响。

拒绝服务，对信息或其它资源的合法访问被无条件地阻止，会让服务器拒绝提供服务。

信息篡改，指主动攻击者将窃听到的信息进行修改之后再将信息传送给原本的接受者。

口令猜测，攻击者常常把破译用户的口令作为攻击的开始。只要攻击者能猜测或者确定用户的口令，他就能获得机器或者网络的访问权，并能访问到用户能访问到的任何资源。

SQL注入攻击，就是通过把SQL命令插入到 Web表单提交或输入域名或页面请求的查询字符串，最终达到欺骗服务器执行恶意的SQL命令。其首要目的是获取数据库访问权限。

对用户输入做关键字过滤、Web应用防火墙、定期扫描系统漏洞并及时修复都可以有效防御SQL注入攻击，入侵检测系统无法防御SQL注入。

IP 地址

实际上，Internet 中的主机地址是用IP地址来唯一标识的。这是因为Internet中所使用的网络协议是TCP/IP协议，故每个主机必须用IP地址来标识。

IPv6地址由128位二进制表示。故IPv6地址空间是IPv4地址空间的2^96倍。

IPv6的地址为128位，地址空间为2^128;
IPv4的地址为32位，地址空间为2^32;

域名和IP地址是一一对应的，域名易于记忆、便于使用，因此得到比较普遍的使用。

当用户和Internet上的某台计算机交换信息时，只需要使用域名，网络会自动地将其转换成IP地址，从而找到该台计算机。

Internet 中的IP地址可以分为五类：A 类、B 类、C 类、D 类和 E 类，各类地址分配方案如图所示。

A类网络地址占有1个字节(8位)，定义最高位为0来标识此类地址，余下7位为真正的网络地址，支持1~126个网络。后面的3个字节(24位)为主机地址,一共提供2^24^ - 2个端点的寻址。A类网络地址第一个字节的十进制值为000~127。
B类网络地址占有两个字节(16位)，使用最高两位为10来标识此类地址，其余14位为真正的网络地址，主机地址占后面的两个字节(16位)，所以B类全部的地址有(2^14^ - 2)X (2^16^ - 2)= 16382X65534个。B类网络地址第一个字节的十进制值为128~191。
C类网络地址占有3个字节，它是最通用的Internet地址。使用最高三位为110来标识此类地址，其余21位为真正的网络地址，因此C类地址支持221-2个网络。主机地址占最后1个字节，每个网络可多达28-2个主机。C类网络地址第一个字节的十进制值为192~223。
D类地址是相当新的。它的识别头是1110，用于组播，例如用于路由器修改。D类网络地址第一个字节的十进制值为224~239。
E 类地址为实验保留,其识别头是1111.E类网络地址第一个字节的十进制值为240~255。

例题1

IP地址块155.32.80.192/26包含了（）个主机地址，以下IP地址中，不属于这个网络的地址是（）。

答：

155.32.80.192/26表示32位长度的IP地址中，前26位是网络前缀，后6位是主机号，因此包含的主机地址个数为2^6^-2=62

因此主机地址范围为155.32.80.193～155.32.80.254，显然155.32.80.191不属于这个网络。

例题2

IP地址块222.125.80.128/26包含了（）个可用主机地址,其中最小地址是（）, 最大地址是（）。

答案:

IP地址块222.125.80.128/26留给主机的地址码只有6位，2^6^-2=62。

这些地址都采用222.125.80.10xxxxxx 的形式，其中最小的地址是 222.125.80.10000001，即 222.125.80.129，最大的是 222.125.80.10111110，即222.125.80.190。

网络安全威胁

一般认为，目前网络存在的威胁主要表现在以下5个方面。

(1)非授权访问:没有预先经过同意，就使用网络或计算机资源则被看作非授权访问。
(2)信息泄露或丢失:指敏感数据在有意或无意中被泄露出去或丢失。
(3)破坏数据完整性:以非法手段窃得对数据的使用权，删除、修改、插入或重发某些重要信息
(4)拒绝服务攻击:它不断对网络服务系统进行干扰，改变其正常的作业流程，执行无关程序使系统响应减慢甚至瘫痪
(5)利用网络传播病毒:通过网络传播计算机病毒，其破坏性大大高于单机系统，而且用户很难防范。

防火墙

防火墙的分类

防火墙技术经历了包过滤、应用代理网关和状态监测三个发展阶段。

包过滤防火墙。包过滤防火墙工作在网络层，对数据包的源及目的 IP 具有识别和控制作用，对于传输层，也只能识别数据报是 TCP 还是 UDP 及所用的端口信息。包过滤防火墙的处理速度较快，也易于配置。
- 包过滤防火墙的优点是防火墙对每条传入和传出网络的包实行低水平控制：①每个 IP 包的字段都被检查，如源地址、目的地址、协议和端口等；②可以识别和丢弃带欺骗性的源 IP 地址的包；③两个网络之间访问的唯一来源；④通常被包含在路由器数据报中，所以不必额外的系统来处理这个特征。
应用代理网关防火墙。应用代理网关防火墙的优点是可以检查应用层、传输层和网络层的协议特征，对数据包的检测能力较强，其缺点是难于配置、处理速度非常慢。
状态监测防火墙。状态监测防火墙结合了代理防火墙的安全性和包过滤防火墙的高速度等优点，在不损失安全性的技术上将代理防火墙的性能提高了 10 倍。

包过滤型防火墙是在网络层对数据包进行分析、选择，选择的依据是系统内设置的过滤规则（访问控制表）。通过检查每个数据包的源地址、目的地址、端口和协议状态等因素，确定是否允许该数据包通过。

防火墙通常分为内网、外网和DMZ三个区域。

安全级别最高的LAN Area 内网
安全级别中等的DMZ区域
安全级别最低的Internet区域（外网）。

防火墙的工作层次是决定防火墙效率及安全的主要因素。一般来说，工作层次越低，则工作效率越高，但安全性就低了；反之，工作层次越高，工作效率越低，则安全性越高。

多媒体

传输媒体指传输表示媒体的物理介质，如电缆、光缆、电磁波等；
表示媒体指传输感觉媒体，如声音、图像等的中介媒体，即用于数据交换的编码，如文本编码、声音编码和图像编码等；
表现媒体是指进行信息输入和输出的媒体，如键盘、鼠标、话筒以及显示器、打印机、喇叭等；
存储媒体指用于存储表示媒体的物理介质，如硬盘、光盘等。

声音

频率范围为20Hz~20kHz 的声波信号称为音频信号；
频率小于20Hz声波信号称为亚音信号(也称次音信号);
频率高于20kHz的信号称为超音频信号，也称超声波。

云

公有云通常指第三方提供商为用户提供的能够使用的云。
私有云是为一个客户单独使用而构建的。
社区云一般是由几个组织共享的云端基础设施。
混合云：将公有云和私有云进行混合和匹配，达到了既省钱又安全的目的。

URL

URL由三部分组成:资源类型、存放资源的主机域名、资源文件名。

URL语法: protocl://hostname[:port]/path/[;parameters][?query]#fragment

蓝牙

蓝牙民用实现中通信距离30米以内，是通信距离最短的。

802.15.1蓝牙是覆盖范围最小无线网络技术。

真题

在网络设计和实施过程中要采取多种安全措施，其中（漏洞发现与补丁管理）是针对系统安全需求的措施。
以下媒体中（声音编码）是表示媒体，（喇叭）是表现媒体。
云计算有多种部署模型。若云的基础设施是为某个客户单独使用而构建的，那么该部署模型属于（私有云）。
下列无线通信技术中，通信距离最短的是（蓝牙）。
在OSI参考模型中，负责对应用层消息进行压缩、加密功能的层次为（表示层）。
在OSI参考模型中，（数据链路层）在物理线路上提供可靠的数据传输。
TCP/IP的四层模型中，每一层都提供了安全协议，下列属于数据链路层安全协议的是 PPTP 。
IP规定每个C类网络最多可以有（ 254 ）台主机或路由器。
为了攻击远程主机，通常利用（端口扫描）技术检测远程主机状态。
包过滤防火墙对（网络层）的数据报文进行检查。
下列协议中，与电子邮箱服务的安全性无关的是（ MIME ）。
下列协议中，可以用于文件安全传输的是（ SFTP ）。
使用电子邮件客户端向服务器发送邮件的协议是（ SMTP ）。
以下协议中属于应用层协议的是（SNMP），该协议的报文封装在（ UDP ）。
下列协议中，属于安全远程登录协议的是（ SSH ）。
PKI体系中，由SSL/TSL实现HTTPS应用.浏览器和服务器之间用于加密HTTP消息的方式是（会话密钥+公钥加密）
利用报文摘要算法生成报文主要的目的是（防止发送的报文被篡改）。
下列攻击类型中，（拒绝服务）是以被攻击对象不能继续提供服务为首要目标。
SQL是一种数据库结构化查询语言，SQL注入攻击的首要目标是（获得数据库的权限）。
SQL注入是常见的web攻击，以下不能够有效防御SQL注入的手段是（部署入侵检测系统阻断攻击）。
IPv6地址长度为（ 128 ）bit。
采用DHCP动态分配IP地址，如果某主机开机后没有得到DHCP服务器的响应。则该主机获取的IP地址属于网络（ 169.254.0.0/16 ）。
- 169.254.0.0/16这个地址段就是local link address(链路本地地址)。
Telnet协议是一种（基于TCP ）的远程登录协议。
防火墙通常分为内网、外网和DMZ三个区域，按照受保护程度，从低到高正确的排列次序为（外网、DMZ和内网）。
使用漏洞扫描系统对信息系统和服务器进行定期扫描可以（发现高危风险和安全漏洞）。
web应用防火墙无法有效保护（流氓软件）
- 流氓软件属于系统内部，不是防火墙处理范围

软件设计师笔记11_标准化和软件知识产权基础知识_精简考点

基本概念

《中华人民共和国著作权法》和《计算机软件保护条例》是构成我国保护计算机软件著作权的两个基本法律文件。

《计算机软件保护条例》第八条第一款第八项规定的软件著作权中的翻译权将原软件由（一种自然语言文字转换成另一种自然语言文字）的权利。

标准化基础知识

标准是标准化活动的产物，其目的和作用都是通过制定和贯彻具体的标准来体现的。

标准化不是一个孤立的事物，而是一个活动过程。

标准化活动过程一般包括标准产生、标准实施和标准更新等。

标准的分类

标准的分类如图所示

标准的代号和编号

标准的代号和编号如图所示

知识产权基础知识

知识产权是指民事权利主体（公民、法人）基于创造性的智力成果。
根据国际公约，知识产权的保护对象包括：
- ①文学、艺术和科学作品；
- ②表演艺术家的表演，以及唱片和广播节目；
- ③人类一切活动领域的发明；
- ④科学发现；
- ⑤工业品外观设计；
- ⑥商标、服务标记、商业名称和标志；
- ⑦制止不正当竞争；
- ⑧在工业、科学、文学艺术领域内由于智力创造活动而产生的一切其他权利。

根据世贸协议，知识产权还包括“未披露过的信息专有权”，即商业秘密。

知识产权的分类如图所示

另外计算机软件和实用艺术品受著作权保护的同时，权利人还可以通过申请发明专利和外观设计专利获得专利权（工业产权）。

知识产权的特点如下

无形性（智力成果）、双重性（多权并存）、确认性（依法审查）、独占性（权利人的相对性）、地域性、时间性。

知识产权人确定-职务作品判定

保护范围和保护对象

专利

若两个申请人分别就相同内容的计算机程序的发明创造，先后向专利行政部门提出申请，先申请人可以获得专利申请权。

同一天申请的情况处理方式如下:

①两个申请人作为一件申请的共同申请人:
②其中一方放弃权利并从另一方得到适当的补偿。
③如果双方协商不成，则两件申请都不授专利权。

商标权

商标权的保护期是可以延长的。

商标权确定知识产权人的过程。第一原则是：谁先申请谁获得。其次，同时申请时，谁先使用谁获得。

若A和B公司都是同一天申请商标的情况：

初步审定并公告使用在先的，驳回其他人的申请
若双方均未使用或无法证明的，各自协商
不愿协商或协商不成的，抽签决定。
不抽签的，视为放弃。

侵权判断的特殊要求

中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权。

开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。

著作权法不适用于下列情形：

法律、法规或其他具有立法、行政、司法性质的文件，及其官方正式译文；
时事新闻；
历法、通用数表、通用表格和公式。

真题

王某是一名软件设计师，按公司规定编写软件文档，并上交公司存档。这些软件文档属于职务作品，且（其著作权由公司享有）。

甲软件公司受乙企业委托安排公司软件设计师开发了信息系统管理软件，由于在委托开发合同中未对软件著作权归属作出明确的约定，所以该信息系统管理软件的著作权由（甲）享有。

以下关于某委托开发软件的著作权归属的叙述中，正确的是（若无书面合同或合同中未明确约定，则该软件的著作权由受托人享有）。

刘某完全利用任职单位的实验材料、实验室和不对外公开的技术资料完成了一项发明。以下关于该发明的权利归属的叙述中，正确的是（原则上应归单位所有，但若单位与刘某对成果的归属有特别约定时遵从约定）。

有可能无限期拥有的知识产权是（商标权）。

以下有关计算机软件著作权的叙述中，正确的是（非法进行拷贝、发布或更改软件的人被称为软件盗版者）。

国际上为保护计算机软件知识产权不受侵犯所采用的主要方式是实施（版权法）

甲、乙两个申请人分别就相同内容的计算机软件发明创造，向国务院专利行政部门门提出专利申请，甲先于乙一日提出，则（甲获得该项专利申请权）。

甲、乙两互联网公司于2020年7月7日就各自开发的库存管理软件分别申请“宏达”和“鸿达”商标注册，两个库存管理软件相似，甲第一次使用时间为2019年7月，乙第一次使用时间为2019年5月，此情景下，（ “鸿达” ）能获准注册。

软件设计师笔记12_软件系统分析与设计_精简考点

结构化分析与设计

总结

结构化分析的对象包括数据（实体对象的属性和关系）和处理（对信息的加工和处理）。
数据流图（DFD）是面向数据流建模的工具。
进行结构化分析的步骤：①确定系统边界，绘制系统环境图；②绘制各层数据流图（自顶向下）；③定义数据字典；④定义加工（处理）说明；⑤将图、字典和加工组成分析模型。
系统总体设计模型反映模块间的调用关系，可以采用层次图、HIPO 图和机构图进行表达。
数据流图分为变换型数据流图和事务型数据流图。事务型数据流图的处理为条件判断式，根据不同输入数据的类型对应不同的处理动作。
详细设计可以采用程序流程图、N-S 图、PAS 图和 PDL 语言等工具进行表达。
结构化分析的最终结果：数据流图、数据字典和加工处理说明。

数据库分析与设计

数据库设计的策略

数据库设计的一般策略有两种:自顶向下(Top Down)和自底向上(Bottom Up)。

这两种方法各有优缺点。在实际的数据库设计开发过程中，常常把这两种方法综合起来使用。

数据库设计的步骤

数据库应用系统的生命周期分为六个阶段：数据库规划、需求描述与分析、数据库设计与应用程序设计、实现、测试、运行与维护。

其中：

需求描述与分析是以用户的角度进行的。
应用程序设计包括事务设计和用户界面设计。
DDL（数据定义语言）用于建立数据库。

数据库设计的四个主要阶段有：用户需求分析、概念结构设计、逻辑结构设计、物理结构设计。

面向对象分析与设计

面向对象分析与设计的步骤

面向对象分析包括四个活动：建模系统功能、定义领域模型、定义交互行为和状态、定义设计类图。
通过用例建模系统功能的步骤：①确定参与者；②确定需求用例；③构造用例模型；④记录需求用例描述。

建模对象状态

建模状态图应遵循的指导原则如下：①状态名称简单但具有描述性；②避免黑洞（有进无出）；③避免奇迹（有出无进）；④符合状态需对子状态集进行建模；⑤为复杂的实体创建分层的状态图

软件设计师笔记_科目一_精简考点 ​

软件设计师笔记01_计算机系统知识概述_精简考点 ​

计算机系统硬件基本组成 ​

中央处理单元CPU ​

进制转换 ​

非十进制数转换为十进制数 ​

带小数的非十进制数转换十进制数 ​

十进制数转换为非十进制数 ​

各个进制的加减法 ​

十进制（基数 10） ​

二进制（基数 2） ​

八进制（基数是8） ​

十六进制（基数是16） ​

原码，反码，补码，移码 ​

浮点数 ​

校验码 ​

寻址方式 ​

指令系统 ​

CISC与RISC ​

流水线 ​

存储系统 ​

高速缓存（Cache） ​

内存编址计算 ***** ​

输入输出技术 ​

直接内存存取 DMA ​

总线 ​

加密技术 ​

系统可靠性 ​

可靠性公式 ​

可用性公式 ​

可维护性公式 ​

软件设计师笔记02_程序设计语言基础_精简考点 ​

程序语言 ​

汇编程序 ​

解释和编译 ​

编译过程 ​

解释过程 ​

总结 ​

符号表 ​

正规式 ​

案例1 ​

案例2 ​

案例3 ​

有限自动机 ​

案例1 ​

案例2 ​

函数调用传值 ​

文法 ​

文法案例题1 ​

表达式 ​

中缀表达式 ​

前缀表达式 ​

后缀表达式 ​

真题 ​

软件设计师笔记03_数据结构_精简考点 ​

线性表 ​

栈 ​

存放操作数的栈的容量 ​

队列 ​

二维数组 ​

数组存储地址的计算公式 ​

矩阵 ​

树 ​

树的基本概念 ​

二叉树 ​

特殊的二叉树 ​

二叉树的存储结构 ​

二叉树的遍历 ​

二叉树的构造（通过遍历的序列） ​

根据先序遍历和中序遍历构造二叉树 ​

根据后序遍历和中序遍历构造二叉树 ​

根据层序遍历和中序遍历构造二叉树 ​

最优二叉树（哈夫曼树） ​

构造最优二叉树（哈夫曼算法） ​

图 ​

图的种类 ​

图的基础概念 ​

图的遍历特点 ​

深度优先遍历 ​

广度优先遍历 ​

软件设计师笔记_科目一_精简考点

软件设计师笔记01_计算机系统知识概述_精简考点

计算机系统硬件基本组成

中央处理单元CPU

进制转换

非十进制数转换为十进制数

带小数的非十进制数转换十进制数

十进制数转换为非十进制数

各个进制的加减法

十进制（基数 10）

二进制（基数 2）

八进制（基数是8）

十六进制（基数是16）

原码，反码，补码，移码

浮点数

校验码

寻址方式

指令系统

CISC与RISC

流水线

存储系统

高速缓存（Cache）

内存编址计算 *****

输入输出技术

直接内存存取 DMA

总线

加密技术

系统可靠性

可靠性公式

可用性公式

可维护性公式

软件设计师笔记02_程序设计语言基础_精简考点

程序语言

汇编程序

解释和编译

编译过程

解释过程

总结

符号表

正规式

案例1

案例2

案例3

有限自动机

案例1

案例2

函数调用传值

文法

文法案例题1

表达式

中缀表达式

前缀表达式

后缀表达式

真题

软件设计师笔记03_数据结构_精简考点

线性表

栈

存放操作数的栈的容量

队列

二维数组

数组存储地址的计算公式

矩阵

树

树的基本概念

二叉树

特殊的二叉树

二叉树的存储结构

二叉树的遍历

二叉树的构造（通过遍历的序列）

根据先序遍历和中序遍历构造二叉树

根据后序遍历和中序遍历构造二叉树

根据层序遍历和中序遍历构造二叉树

最优二叉树（哈夫曼树）

构造最优二叉树（哈夫曼算法）

图

图的种类

图的基础概念

图的遍历特点

深度优先遍历

广度优先遍历