[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%

---

原码，反码，补码，移码

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

校验码

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

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

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

三种校验码的区别

系统可靠性

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

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

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

流水线

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

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

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

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

表达式

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

记忆背诵方法如下

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

中缀表达式

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

前缀表达式

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

推导过程：

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

后缀表达式

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

推导过程：

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

编译过程

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

速记

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

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

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

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

项目活动图 里程碑

真题

解析

真题

试题分析:

先找出关键路径为 ABDGIKL ，其长度为22，所以最短工期为22天。

BD是关键路径上的活动，其总时差为0，不能耽搁，所以BD最多延误0天不会影响总工期。

答案:(15)C (16)A

真题案例

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 B
• B E
• C G
• D I

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

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

分页式存储

真题示例

某操作系统采用分页存储管理方式，下图给出了进程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

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

真题示例

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

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

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

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

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

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

真题

(27)试题分析:

P(S)操作是申请资源，是减量操作;V(S)操作是释放资源，是增量操作。所以执行两次P(S)后S的值是-3。

答案:(27)B

真题示例

解题思路：

• 先在前趋图中给每个箭头画上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)。

真题

解题思路：

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

试题分析

真题

解析

正规式

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

案例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，无法表示任意长度的字符串，排除。

有限自动机

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

如图所示

主要有五个符号集，由上图示例，可知用状态来表示十分清晰，由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。

磁道中的读取文件耗时

真题

试题分析: (6msX10个磁道 + 100ms + 20ms) x 100块 = 18000

磁盘 位示图的大小

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

真题

某字长为 32 位的计算机的文件管理系统采用位示图(bitmap)记录磁盘的使用情况。若磁盘的容量为 300GB，物理块的大小为1MB，那么位示图的大小为( )个字

A.1200 B.3200 C.6400 D.9600

试题分析：

300G 的磁盘有 300×1024 = 307200 个物理块，因此总共需要 307200 位，307200/32 = 9600 字（32位系统的字长就是 32 位）。 即位示图的大小为 9600 个字。

真题示例

由于物理块是从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

真题

试题分析:

2053/32=64.156，并且位示图是从0开始的，所以选择C选项。

McCabe度量法

McCabe环路复杂度。有两种方式求出。

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

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

真题案例

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

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

解法1 公式法

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

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

解法2 区域法

程序图的环路数等于由程序图中封闭的区域数量加上 1。注意：封闭环个数不计算重叠的。

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

真题案例

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

解法1 公式法

先将程序流程图转换为有向图。然后根据公式V(G) = E - N + 2 。其中 E 是程序图中边的数量，N 是节点数量。

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

解法2 区域法

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

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

真题案例

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

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

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

真题

试题分析:

环形复杂性计算公式为V(G) = E - N + 2，其中 E是流图中边(Edge)的条数，N是节点(Node)的个数。所以，V(G)=E-N+2=11-10+2=3。

答案: C

测试的覆盖用例计算

试题分析:

覆盖两条路径就能达到语句覆盖的要求，用两个测试用例即可。

路径覆盖需要把程序中的所有路径均覆盖一遍，需要四个用例。

整个程序流程图转化为节点图之后，一共11个节点、13条边，根据环路复杂度公式有 13-11+2=4。

答案:(35)B (36) D

各个软件过程模型总结

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

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

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

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

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

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

UML 图

设计模式

• 装饰器模式：无法对已有的类进行扩充的时候，可以动态的给对象添加一些额外的功能。

• 桥接模式：将抽象部分与它的实现部分分离，使它们都可以独立地变化。

• 外观模式：为复杂系统提供简化接口（隐藏内部细节，对外暴露单一入口）

• 组合模式：处理树形结构（整体与部分可统一操作，如文件夹与文件）

• 观察者模式： 处理一对多关系（一个主题变化，多个观察者自动更新）

• 代理模式：控制对对象的访问权限（如远程访问、权限校验、延迟加载）

• 命令模式：将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作。

• 策略模式：多个算法 / 策略（如排序算法、支付方式），需动态切换

• 责任链模式： 让多个对象依次处理请求（每个对象决定自己处理或传递给下一个）

• 享元模式：由于大量对象造成很大开销的时候，可以运用共享技术支持大量相似对象的复用。

• 适配器模式：若接口不符合需求时，将该类接口转换为想要的接口。

• 中介者模式：用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互。如使一个后端数据模型能够被多个前端用户界面连接，采用此模式最合适。

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

敏捷开发

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

各个敏捷开发方法

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

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号，但是未经加密，因此是不安全的。

死锁

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

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

1. 资源互斥
2. 每个进程占有资源并等待其他资源
3. 系统不能剥夺进程资源
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时公式不成立,可能会发生死锁。

真题范例

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

解题思路：

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

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

真题范例

正确答案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。

耦合性和内聚性

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

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

图片像素

真题

使用图像扫描仪以300DPI的分辨率扫描一幅3X4英寸的图片，可以得到( )像素的数 字图像。

A.300X300 B.300X400 C.900x4 D.900X1200

试题分析:

DPI为像素/英寸，可以得到(300X3)X(300X4)=900X1200。

软件质量

如图所示

常考知识点

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

树

树的基本概念

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

二叉树

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

二叉树的性质

• 一个深度为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。

二叉树的遍历

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最优二叉树（哈夫曼树）

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

所谓树的带权路径长度，就是树中所有的叶子结点的权值乘上其到根结点的路径长度（若根结点为 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。

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

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

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

注意：

• 在构造新树的过程中，对于选出的两个权值节点，哪个作为左子树、哪个作为右子树并没有明确规定。这就导致：对于相同的一组权值，可能会构造出不同形状的最优二叉树。不过，不管形状如何变化，这些树的带权路径长度（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为边数。

广度优先遍历

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

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

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