2020年软件设计师知识点

系统可靠性分析和设计

1.串联系统

可靠性R=R1 * R2 *……*Rn，各子系统可靠度相乘。

失效率（近似）总失效率=各子系统失效率相加

2.并联系统

可靠性 R=1- （1-R1）*（1-R2）*…*(1-Rn) ，并联计算各子系统失效率，全部失效才真正失效，1-失效率

失效率 = 1- 可靠性

3.模冗余系统和混合系统

差错控制

检错和纠错

公式

描述	公式
定点整数补码和移码范围	-2^(n-1) ~ 2^(n-1) -1 （最小数再加1则为原码反码的表示范围）
定点小数补码和移码范围	-1 ~ 1-2^(-(n-1)) （原码反码的表示范围:-(1-2^(-(n-1)) ~ 1-2^(-(n-1))
对称加密	DES 3DES RC4 RC5 IDEA AES
非对称加密（公开密钥加密算法）	RSA，Rabin(RSA的特例)， DSA， ECC ，EIGamal
补码能表示的数的个数	2^n
浮点数表示	尾数 x 基数^指数
流水线理论公式	t1+..+tk+(n-1)*△t （△t 为流水线中最长执行时间）
流水线实践公式	k△t+(n-1)*△t （k为流水线的步骤数）
流水线吞吐率TP	指令条数/流水线执行时间
流水线最大吞吐率	1/△t
Cache+主存储器系统的平均周期	*ht1+(1-h)t2*
存储芯片片数	总容量/每片容量
系统可用性	MTTF/(MTTR+MTTF) * 100% （MTTF平均失效前时间，MTTR平均修复时间）
系统可靠性	MTTF/(1+MTTF)
串联系统可靠性	R1R2…Rn
并联系统可靠性	1-(1-R1)(1-R2)…(1-Rn)
海明检验码	2^r >= r+m+1 r:校验位 m：数据位
MIPS	指令条数/(执行时间10^6)主频/CPI主频IPC
系统不死锁最小资源	n >= (w-1)*m+1
逻辑地址	页号+页内地址
物理地址	页帧号+页内地址
文件物理块所在位示图的位置	(n+1)/字长，向上取整
端口号	TCP类型: POP3 110 ， SMTP 25 ，FTP 20/21 ，Telnet 23， HTTP 80 ，HTTPS 443 UDP类型:DHCP 67 ，TFTP 69 ，SNMP 161 ，DNS 53
摘要算法	MD5 128位 SHA 160位
网络安全保障	应用层：PGP HTTPS SSL表示层：SSL会话层：SSL传输层：TLS SET网络层：防火墙 IPSec数据链路层：链路加密 PPTP L2TP物理层：隔离屏蔽
风险曝光度	风险出现率*风险损失
时间复杂度排序	O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(2^n)
有无主程序开发小组，沟通路径	有主程序员 m= n -1 无程序员组：完全联通无向边图的边数 m = n *(n -1) /2
第一范式(1NF)：	关系模式S中的所有属性都是不可再分的基本数据项
第二范式(2NF)：	在第一范式的基础上，消除了非主属性对码的部分函数依赖
第三范式(3NF):	在第二范式的基础上，进一步消除了非主属性对码的传递函数依赖
BC范式(BCNF):	在第三范式的基础上，进一步消除了主属性对码的部分函数依赖和传递函数依赖
时间复杂度	O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)
有/无主程序员沟通路径	n-1（有主） n*(n-1)/2（无主）
声音频率｜ 20Hz - 20KHz
色彩空间	RGB显示器 YUV（YCBR）电视 CMY印刷 HSV 艺术

内聚与耦合

内聚（从弱到强）

偶然内聚（巧合内聚）一个模块内的各处理元素之间没有任何联系，只是偶然地被凑到一起。这种模块也称为巧合内聚，内聚程度最低。
逻辑内聚：这种模块把几种相关的功能组合在一起，每次被调用时，由传送给模块参数来确定该模块应完成哪一种功能。相关的功能也就是逻辑上的功能放在一起。如表述，我和全世界的人，比较松
时间内聚：把需要同时执行的动作组合在一起形成的模块称为时间内聚模块。仅是时间上相关的动作，如一边看书，一边听音乐，可以描述了件事情了，但还不是必须在一块执行的动作。
过程内聚：构件或者操作的组合方式是，允许在调用前面的构件或操作之后，马上调用后面的构件或操作，即使两者之间没有数据进行传递。简单的说就是如果一个模块内的处理元素是相关的，而且必须以特定次序执行则称为过程内聚。两个功能同属于一个过程中，有了在一起的理由。
例如某要完成登录的功能，前一个功能判断网络状态，后一个执行登录操作，显然是按照特定次序执行的。
通信内聚：指模块内所有处理元素都在同一个数据结构上操作或所有处理功能都通过公用数据而发生关联（有时称之为信息内聚）。即指模块内各个组成部分都使用相同的数据结构或产生相同的数据结构。两个模块需要交换数据（通信）了，才能完成某一个功能。这样在一起的理由更充分了一些。
顺序内聚：一个模块中各个处理元素和同一个功能密切相关，而且这些处理必须顺序执行，通常前一个处理元素的输出是后一个处理元素的输入。顺序虽然也代表着过程，但有本质的区别，还是体现在数据的关联上，顺序强调的是前一个输出是后一个的输入。不仅强调数据交流（通信）还限制顺序，在一起的理由就更充分了。
例如某要完成获取订单信息的功能，前一个功能获取用户信息，后一个执行计算均价操作，显然该模块内两部分紧密关联。
顺序内聚的内聚度比较高，但缺点是不如功能内聚易于维护。
功能内聚：模块内所有元素的各个组成部分全部都为完成同一个功能而存在，共同完成一个单一的功能，模块已不可再分。即模块仅包括为完成某个功能所必须的所有成分，这些成分紧密联系、缺一不可。就是为了单一的功能，不可再拆分了，必须在一起了。

耦合（从强到弱）
内容耦合：一个模块直接访问另一模块的内容，则称这两个模块为内容耦合。
若在程序中出现下列情况之一，则说明两个模块之间发生了内容耦合：

一个模块直接访问另一个模块的内部数据。
一个模块不通过正常入口而直接转入到另一个模块的内部。
两个模块有一部分代码重叠（该部分代码具有一定的独立功能）。
一个模块有多个入口。

内容耦合可能在汇编语言中出现。大多数高级语言都已设计成不允许出现内容耦合。这种耦合的耦合性最强，模块独立性最弱。

其中一个模块访问另一个模块的内部，也就是信赖另一个模块的内容

公共耦合：一组模块都访问同一个全局数据结构，则称之为公共耦合。公共数据环境可以是全局数据结构、共享的通信区、内存的公共覆盖区等。如果模块只是向公共数据环境输入数据，或是只从公共数据环境取出数据，这属于比较松散的公共耦合；如果模块既向公共数据环境输入数据又从公共数据环境取出数据，这属于较紧密的公共耦合。
公共耦合会引起以下问题：一个模块通过公共的数据与另一个模块关联，有共用的大量数据，那么还是不独立。

无法控制各个模块对公共数据的存取，严重影响了软件模块的可靠性和适应性。
使软件的可维护性变差。若一个模块修改了公共数据，则会影响相关模块。
降低了软件的可理解性。不容易清楚知道哪些数据被哪些模块所共享，排错困难。

一般地，仅当模块间共享的数据很多且通过参数传递很不方便时，才使用公共耦合。

外部耦合：一组模块都访问同一全局简单变量，而且不通过参数表传递该全局变量的信息，则称之为外部耦合。模块间通过外部的简单变量，少量的共用数据产生关联，独立性好点了。
控制耦合：模块之间传递的不是数据信息，而是控制信息例如标志、开关量等，一个模块控制了另一个模块的功能。模块间通过控制信号，肯定是外部的了，并且是开关量，共用数据更少了。独立性更好了。
标记耦合：调用模块和被调用模块之间传递数据结构而不是简单数据，同时也称作特征耦合。表就和的模块间传递的不是简单变量，而是像高级语言中的数据名、记录名和文件名等数据结果，这些名字即为标记，其实传递的是地址。标记理解为地址的话，地址里的内容可不一定是固定的，所以模块间的关系，基本开始脱离数据这么紧密的关系了，开始独立了。
数据耦合：调用模块和被调用模块之间只传递简单的数据项参数。相当于高级语言中的值传递。只是传递了个数据，如1，不用于共用数据了才行了，更加独立了。
非直接耦合：两个模块之间没有直接关系，它们之间的联系完全是通过主模块的控制和调用来实现的。耦合度最弱，模块独立性最强。

二叉树

反向构造二叉树，
对比前序，中序遍历，前序第一个是根节点，中序中的相同的字母分为左右两边，继续往下循环
树转二叉树
孩子节点-左子树节点兄弟节点-树的右子节点（从上到下，从左到右）
哈夫曼树

在权值中拿出最小两个，相加生成父节点，再将父节点放入原权值组中循环上述操作构造成树
带权路径长度=全部叶子节点权值*路径长度
树左节点为0，右子节点为1

软考中涉及到的主要开发模型：

原型开发模型（快速原型模型、演化模型、增量模型）

1）快速原型：

解释：其用途是获知用户的真正需求，一旦需求确定了，原型即被抛弃。主要用于需求分析阶段。是一种“抛弃式”的原型化方法。

特征：简化项目管理、尽快建立初步需求、加强用户参与和决策。
2）演化模型：

解释：应用于真个软件开发过程，是从最初模型逐步演化为最终软件产品的渐进过程。是一种“渐进式”的原型化方法。
3）增量模型（渐增式）

解释：主要用于设计阶段，把软件产品划分为一系列的增量构件，分别进行设计、编程、集成和测试。新的增量构件不得破坏已经开发出来的产品。

瀑布模型

解释：瀑布模型严格遵循软件生命周期各阶段的固定顺序：计划、分析、设计、编程、测试和维护，上一阶段完成后才能进入下一阶段，真个模型就像是一个飞流直下的瀑布。
      优点：以文档作为驱动，强迫开发人员采用规范的方法，严格规定了各阶段必须提交的文档；要求每一阶段结束后都要进行严格的评审。与它最相适应的开发方法是结构化方法。
      缺点：不适用户需求的改动。

螺旋模型

解释：综合了瀑布模型和原型模型中的演化模型的优点，还增加了风险分析。螺旋线第一圈的开始点可能是一个概念项目。从第二圈开始，一个新产品开发项目就开始了，新产品的演化沿着螺旋线进行若干次迭代，一直转到软件生命期结束。

喷泉模型

 解释：主要用于描述面向对象的开发过程。喷泉一词体现了面向对象开发过程的迭代和无间隙特征。

迭代软件开发技术

  Rational统一开发流程RUP是一个通用的软件流程框架，它是一个以框架为中心，用例驱动的迭代化软件开发流程。RUP是从千个软件项目的实践经验中总结出来的，对于实际的项目具有很强的指导意义，是软件开发行业事实上的行业标准。在RUP中，我们把软件开发生命周期划分为四个阶段，每个阶段的结束标志就是一个主要的里程碑。
            这四个阶段是为了达到以下阶段性的目标里程碑：
             先启（Inception）：确定项目开发的目标和范围。
             精化（Elaboration）：确定系统架构和系统功能
             构建（Construction）：实现剩余的系统功能
             产品化（Transition）：完成软件的产品化工作，将系统移交给客户
   真题再现：<br/>
   1.（2012年下）某开发小组欲开发一个规模较大、需求较明确的项目。开发小组对项目领域熟悉且该项目与小组开发过的某一项目相似，则适宜采用瀑布开发模型。<br/>
   2.（2012年上）假设某软件公司与客户签订合同开发一个软件系统，系统的功能有较清晰的定义，且客户对交付时间有严格要求，则该系统的开发最适宜采用瀑布模型。<br/>
   3.（2011年下）若全面采用新技术开发一个大学记账系统，以替换原有的系统，则宜选择采用瀑布模型进行开发。<br/>
   4.（2011年上）为了有效地捕获系统需求，应采用原型模型<br/>
   5.（2010年上）统一过程（UP）定义了初启阶段、精化阶段、构建阶段、移交阶段，每个阶段以达到某个里程碑时结束，其中，精化阶段的里程碑时生命周期架构。

下午题目

查找缺失数据流方法

1.父图子图对比
2.确定每个加工查看是否有输入输出
3.读试题描述和图做对比，查看是否有缺失。（每句话都要仔细看）

分解加工时，常见的三种错误

1.黑洞有输入无输出
2.白洞无输入有输出
3.灰洞输入不足以产生输出

添加缺失

1.将***作为外部实体，添加从加工“ ***” 到“ ***” 的数据流“***”

结构化语言

伪代码
1）从题干中抽取“动词 + 名词” 或者 “名词 + 动词”，而不是直接COPY整个句子。

2）从题干内容中提炼出IF，WHILE：比如2021上半年1题中，车辆入场和出场是想对的概念，因此是IF；比如2020下半年1题中，图像采集是一个WHILE过程。

3）利用伪代码（参考latex代码格式，参考Latex写伪代码）书写，常见语法包括：while(…) do {xxx} end while，if(…) then {xxx} end if

用例和用例之间的关系

1.包含系统用例较多，不同用例之前存在共同行为，可以将这些共同的行为提取出来，单独组成一个用例，当其他用例适用这个用例时，他们就构成了包含关系

2.扩展当用例执行过程中，可能会出现一些特殊情况，也可能再不同的分支行为中选择执行，这时可将异常行为与可选分支抽象微一个单独的扩展用例，一个用例可能有多个扩展用例

3.泛化

类图中各个图形和线条的意义

各种uml图
1.用例图
2.类图
3.对象图
4.活动图
5.状态图
6序列图（时序图）
7.协作图（通信图）
8.构建图
9.部署图
10.组件图

算法

软考中常见算法类型：分治法、回溯法、贪心法、动态规划法。

1. 分治法

将一个问题拆分为若干个小规模的子问题，通常用递归的思想求解子问题，子问题相互独立但与原问题相同，再将子问题的解合并得到原问题的解。（自下向上）

2. 回溯法

搜索问题的所有解或任一解，在搜索过程中发现不满足求解条件则回溯，尝试别的路径。

3. 贪心法

不考虑整体，只在当前做出最优的选择，求得局部最优解。（自顶向下）

4. 动态规划法

划分子问题为最优的子策略，并把子问题的解使用数组存储，利用查表查出子问题结果构造最终问题结果。与分治法不同的是子问题不独立，相同子问题可能会被求解多次。（自底向上/自下而上）

软考常见算法例题

设计模式

1.创建性模式

抽象工厂模式（Abstract Factory）:提供一个接口，可以创建一系列相关或相互依赖的对象，而无需指定它们具体的类。（一个接口创建相关对象，无需具体的类）

工厂方法模式只有一个抽象产品类，而抽象工厂模式有多个。
工厂方法模式的具体工厂类只能创建一个具体产品类的实例，而抽象工厂模式可以创建多个。

构建器模式（Builder）：将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示。（相同是构造，不同的表示）

工厂方法模式（Factory Method）：定义一个创建对象的接口，但由子类决定需要实例化哪一个类。工厂方法使得子类实例化的过程推迟。（接口，子类决定实例化具体类）

原型模式（Prototype）：用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象。（只有一个实例）

单例模式（Singleton）:保证一个类只有一个实例，并提供一个访问它的全局访问点。（只有一个实例）

2.结构型模式

适配器模式（Adapter）：将一个类的接口转换成用户希望得到的另一种接口。它使原本不相容的接口得以协同工作。（实现兼容）

桥接模式（Bridge）：将类的抽象部分和它的实现部分分离开来，使它们可以独立地变化。（抽象和实现分离开）

组合模式（Composite）：将对象组合成树型结构以表示“整体-部分”的层次结构，使得用户对单个对象和组合对象的使用具有一致性。（整体—部分）

装饰模式（Decorator）：动态地给一个对象添加一些额外的职责。它提供了用子类扩展功能的一个灵活的替代，比派生一个子类更加灵活。（动态添加）

外观模式（Facade）:定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用。（为子系统提供一致的外观）

享元模式（Flyweight）：提供支持大量细粒度对象共享的有效方法。（共享）

代理模式（Proxy）：为其他对象提供一种代理以控制这个对象的访问。（提供代理）

3.行为型模式

职责链模式（Chain of Responsibility）：通过给多个对象处理请求的机会，减少请求的发送者与接收者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求。（将对象链接起来，在链中传递请求）

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

解释器模式（Interpreter）：给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子。（有一个解释器来表示文法句子）

迭代器模式（Iterator）：提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示。（不需要暴露对象的内部）

中介者模式（Mediator）：用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互。（使用中介来调用）

备忘录模式（Memento）：在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态。（可以恢复到之前的状态）

观察者模式（Observer）：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。（一个变，其他也变）

状态模式（State）：允许一个对象在其内部状态改变时改变它的行为。（状态改变时改变它的行为）

策略模式（Strategy）：定义一系列算法，把它们一个个封装起来，并且使它们之间可互相替换，从而让算法可以独立于使用它的用户而变化。（互相替换）

模板方法模式（Template Method）：定义一个操作中的算法骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重新定义算法的某些特定步骤。（子类父类）

访问者模式（Visitor）：表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作,需要对一个对象数据结构中的对象进行很多不同的并且不相关的操作。（不改变各元素定义这些元素的新操作）

裸泳的猪

2020年软件设计师知识点整理