软件设计师考试笔记

考试软考的时候,整理的一些笔记

[toc]

内容

系统开发和运行

软件生存周期

可行性分析, 项目开发计划, 需求分析, 设计(概要设计和详细设计), 编码, 测试, 维护

软件开发模型

瀑布模型 : 提供了有效的管理模式, 文档驱动 : 主要用于结构化的软件开发 : 缺乏灵活性, 无法通过开发活动来明确需求

演化模型 : 构建原型 : 对软件需求缺乏准确认识

螺旋模型 : 综合了瀑布模型和演化模型的优点 : 增加了风险分析 : 适合大型复杂系统

喷泉模型 : 面向对象开发过程 : 具有迭代和无间隙特性

V模型 : 强调软件开发的协作和速度 : 实现和验证结合 : 保证质量缩短周期

软件开发方法

结构化方法

由结构化分析,结构化设计,结构化程序设计构成
是一种面向数据流的开发方法.
使用DFD图来建立系统的功能模型.
指导思想是 自顶向下,逐层分解.基本原则是功能的分解与抽象.
适用于数据处理领域,不适合解决大规模的,特别复杂的项目,且难以适应需求的变化

Jackson 方法

是一种面向数据流的开发方法.
JSP(Jaskon Structure Programming) 方法 以数据结构为驱动,适合于小规模项目. JSD 是 JSP 的扩充.

原型化方法

开发原型,征求意见,修改原型.
适用于用户需求不清,业务不确定,需求经常变化的情况.也可用于不复杂的小规模项目.

面向对象开发方法

包括面向对象分析,面向对象设计和面向对象实现.

面向对象开发方法: Booch,Coad,OMT.
UML 是面向对象标准建模语言.

风险分析

包括 风险识别, 风险预测, 风险评估, 风险控制

风险识别 : 建立风险条目检查表

风险预测 : 风险发生的可能性或概率,风险发生所产生的后果

风险评估 : $(r_i,l_i,x_i)$,r为风险,l为概率,x为影响 : 建立参照

风险控制 : 风险避免,风险监控, 风险管理及意外事件计划

进度管理

Gantt 图

可以反映并行关系 不能反映依赖关系,难以确定项目的关键所在,不能反映计划中有潜力部分

PERT 图

可以反映依赖关系,确定关键,反映潜力 不能反映并行

关键路径是松弛时间为 0 的任务完成过程所经历的路径.没有松弛时间则是耗时最长路径.

软件配置管理

标识变更,控制变更,确保变更,版本控制

软件过程管理

软件过程能力评估的意义 : 是改进软件过程和降低软件风险的需要

软件能力成熟度模型 / CMM

初始级 : 无序的,混乱的,对过程没有定义,成功取决于个人

可重复级 : 有基本的项目管理过程来跟踪费用,进度,功能特性.有过程纪律,能重复早先类似的成功

已定义级 : 将软件管理和工程的过程文档化,标准化,综合成该组织的标准软件过程.项目使用经批准,裁剪的标准软件过程来开发和维护软件.

已管理级 : 收集对软件过程和产品质量的详细度量,对软件过程和产品都有定量的理解和控制

优化级 : 过程的量化反馈和先进的新思想,新技术促使过程不断改进.

统一过程

统一过程(UP)模型是一种 "用例和风险驱动,以构架为中心,迭代并且增量"的开发过程.

分为五个阶段:

--
初始阶段生命周期目标
精化阶段生命周期构架
构建阶段初始运作功能(Beta 版产品)
移交阶段产品发布

RUP

RUP(Rational Unified Process) 是 UP 的商业扩展.

角色 : 描述个人或小组的行为职责

活动 : 有明确目的的工作单元

工件 : 是活动生成,创建或修改的一段信息.

敏捷方法

是 "尽可能早的,持续的对有价值的软件的交付"使客户满意

典型方法: 极限编程,水晶法,并列征求法,自适应软件开发

极限编程

4个价值观 : 沟通,简单性,反馈和勇气

5个原则 : 快速反馈, 简单性假设, 逐步修改, 提倡更改和优质工作

12个最佳实践 : 计划游戏,小型发布,隐喻, 简单设计, 测试先行, 重构, 结对编程, 集体代码所有制, 持续集成, 每周工作40个小时,现场客户和编码标准.

软件质量特性

ISO/IEC 9126 软件质量模型由三个层次构成: 质量特性,质量子特性, 度量指标

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

软件质量保证

包括7个主要活动相关的各种任务:

  • 应用技术方法
  • 进行正式的技术评审
  • 测试软件
  • 标准的实施
  • 控制变更
  • 度量
  • 记录保存和报告

代码复杂性

  • 代码行度量法
  • McCabe 度量法
    又称为环度量法,认为复杂性主要取决于控制复杂性.

系统设计的基本原理

抽象, 模块化, 信息隐蔽, 模块独立

软件测试策略

单元测试 : 也称为模块测试. : 特征: 模块结构,局部数据结构, 重要的执行路径,出错处理,边界条件

组装测试 : 也称为集成测试 : 方法: 1.分别测试各模块,在组装起来整体测试,即非增量测试. 2.模块组合到已测试好的模块中,完成后组合下一个模块,即增量测试

确认测试 : 确认功能和性能是否和用户要求的一样. : 先进行有效性测试及软件配置审查,然后进行验收测试和安装测试,完成后交付给用户

系统测试 : 将软件放入到实际环境中,进行各种组装测试和确认测试. : 常见的系统测试 恢复测试,安全性测试,强度测试, 性能测试,安装测试,可靠性测试

测试方法

分为静态测试和动态测试

静态测试分为 人工检测和计算机辅助静态分析

动态测试分为 黑盒测试和白盒测试

黑盒测试用例

也称为功能测试.不考虑内部结构和特性的情况下进行外部特性测试.

常用的测试技术:

  • 等价类划分
  • 边界值分析
  • 错误推断
  • 因果图

白盒测试用例

也称为结构测试

测试方法:

  • 逻辑覆盖
  • 循环覆盖
  • 基本路径测试

调试

常用的调试方法: 试探法,回溯法, 对分查找法,归纳法,演绎法

系统文档

人员文档
用户-系统分析人员 规划分析可行性研究报告,总体规划报告,系统开发合同,系统方案说明书
系统开发人员-项目管理人员系统开发计划,系统开发月报,系统开发总结
系统测试人员-系统开发人员系统方案说明书,系统开发合同,系统设计说明书,测试计划
系统开发人员-用户 运行期间用户通过开发人员撰写的文档运行系统
系统开发人员-系统维护人员系统设计说明书,系统开发总结报告
用户-维护人员 运行维护期间用户记载运行问题,形成运行报告和修改建议.维护人员依次进行维护

系统维护

可维护性 : 维护人员理解,改正,改动和改进这个软件的难易度.

系统的可维护性指标 : 可理解性,可测试性,可修改性

维护与文档 : 文档是软件可维护性的决定因素.分为用户文档和系统文档

系统维护的内容及类型

维护的费用是生存周期全部费用的 60% ~ 80%

  • 硬件维护
  • 软件维护
  • 数据维护

软件维护的分类

  • 正确性/改正性 维护. 17%~21%
    交付后,运行时,诊断和改正错误
  • 适应性维护. 18%~25%
  • 完善性维护. 50%~60%
    扩充功能和改善性能.
  • 预防性维护. 4%
    改进以适应未来的软硬件环境,增加新的功能,使其不被淘汰.

算法

原码 : +0=00000000 : -0=10000000

反码 : +0=00000000 : -0=11111111

补码 : +0=-0=00000000

移码 : =$n^{ n-1 }+X\quad X 为纯整数,且 (-2^{ n-1 }\le\quad X\quad<\quad 2^{n-1})$ : =$1+X \quad X为纯小数,且(-1 \le X < 1)$ : 移码主要用于表示浮点数的阶码, 在浮点数运算中有优势.

浮点数 : 表示 $N=M \cdot R^{E}$ : M 尾数 R 基数 E 阶码 : IEEE754 表示 $(-1)^{S}2^{E}(b0b_1\cdots b{P-1})$

cache性能分析

$$ t_a\quad = \quad Ht_c + (1 - H ) t_m $$

$$ r=t_m/t_a $$

H 为 cache 命中率,
$t_c $为cache 存取时间,
$t_m$为主存访问时间,
$t_a$ cache等效访问时间,
r 为使用 cache 提高的速度倍数

磁盘容量

$$ 非格式化容量 = 面数 \times (磁道数/面)\times 内圆周长\times 最大位密度 $$

$$ 格式化容量 = 面数 \times (磁道数/面)\times (扇区数\times 道)\times (字节数/扇区) $$


吞吐率


可靠性

$$ R(t) = e^{-\lambda t} $$

$\lambda$ 失效率
t 时间 R(t) t这段时间能正常运行的概率

$$ MTBF= 1/\lambda $$

$$ A = \frac{MTBF}{MTBF + MTRF} $$

MTBF 平均无故障时间
MTRF 平均故障修复时间

可靠性模型

串联系统 : $R=R_1R_2\cdots R_N$ : $\lambda = \lambda_1 + \lambda_2 + \cdots +\lambda_N$

并联系统 : $R = 1 - (1-R1)\times(1-R_2)\times\cdots\times(1-R_N)$ : $\mu =\frac { 1 }{ \frac { 1 }{ \lambda } \sum { j=1 }^{ N }{ \frac{1}{j} } } $

N模冗余系统 : $ R=\sum _{ i=n+1 }^{ N } \begin{pmatrix} j \ N \end{pmatrix} \times R_0^j(1-R_0)^{N-1} $

计算机性能

$$ T = \sum_{i=1}^{n} \times (\omega_i \times t_i) $$

T 等效指令时间
i 某类指令
n 指令种类数
$\omega_i$ 指令i在程序中占的比例
$t_i$ 指令i 执行时间

McCabe 度量法

$$ V(G) = m - n + 2p $$

V(G) 为有向图 G 中的环路数
m 为图 G 中弧的个数
n 为节点个数
p 为 G 中的强连通分量个数

完全二叉树叶子节点数量

除最外层,其余层上的节点数目都达到最大值,而第 h 层上的节点集中存放在左侧树

n0 度为0的节点数
n1 度为1的节点数
n2 度为2的节点数
n0 = n2 + 1
n = n0 + n1 + n2
n0 = (n+1)/2 或 n0 = n/2

Misc

$$ 平均作业周转时间 = (\sum{i=1}^{n}{\sum{j=1}^{i}} t_j)/n $$

n 为作业的数量
ti 为作业 i 的时间


$$ ASL/平均查找长度 = \sum{i=1}^nP_iC_i $$ n 记录个数
Pi 对表中第 i 个记录进行查找的概率 且 $\sum
{i=1}^nP_i = 1$



芯片数 = 总容量/芯片容量
地址线数 = 片选地址数 + 片内地址数 = log(芯片数) + log(芯片容量)
注意: 地址是按字节编址的

Cheat Sheet

耦合类型

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

UML

视图主要概念
结构静态视图类图类,关联,泛化依赖关系,实现,接口
用例视图用例图用例,参与者,关联,扩展,包括,用例泛化
实现视图构件图构件,接口,依赖关系,实现
部署视图部署图节点,构件,依赖关系,实现
动态状态机视图状态机图状态,事件,转换,动作
活动视图活动图状态,活动,完成转换,分叉,结合
交互视图顺序图交互,对象,消息,激活
协作图协作,交互,写作角色.消息
模型管理模型管理视图类图包,子系统,模型
可扩展性,所有所有约束,构造性,标记值

依赖 : 两个事物之间的语义关系,一个事物的变化会影响另一个

关联 : 一种结构关系, 描述了一组链式对象之间的连接.

聚集 : 是一种特殊的关联,描述了整体和部分之间的结构关系.

泛化 : 是一种 特殊/一般 关系

实现 : 是类元之间的语义关系

包含 : 把几个用例的公共步骤分离成一个单独的被包含用例.

扩展 : 把新行为插入到已有的用例中的方法.

边界类 : 描述的是系统外部环境和系统内部的交互,工作在外部环境和系统之间,边界对象表示一个窗口.

实体类 : 存储和管理系统内部信息,可以有行为,但必须和他所表示的对象密切相关 : 实体类是独立于系统外部环境的

控制类 : 主要描述特点的 UseCase 的控制行为,与特定的 UseCase, 实现密切相关 : 可以有效的降低边界类和实体类的耦合, 使系统对于外部环境的变化,能更好适应.

哈夫曼树的定义

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

带权路径长度 = 权值 * 该节点到根节点的长度

FTR 指导原则

  1. 软件评审是评审软件产品,不要涉及对软件生产者能力的评价
  2. 评审前要制定严格的评审计划,并严格遵守预计的日程安排
  3. 对评审中出现的问题要记录在案,不要过多的讨论解决问题,把问题解决留给生产者
  4. 要限制参与人数,并要求参加评审的人员在评审会之前仔细阅读文档,做好充分准备

数据库范式

1NF : 每一个分量是不可再分的数据项 : 问题
1. 冗余度大 2. 引起修改操作不一致 3. 插入异常 4. 删除异常

2NF : 每一个非主属性完全依赖于码 : 即 消除了非主属性对码的部分函数依赖

3NF : 消除非主属性对码的传递函数依赖

BCNF : 消除主属性对码的部分和传递函数依赖 : 即: : 所有非主属性对每一个码都是完全依赖 : 所有非主属性对每一个不包含它的码,也是完全函数依赖 : 没有任何属性完全函数依赖于非码的任何一组属性

ACID/Atomicity, Consistency, Isolation, Durability : 事务的特性: 原子性 一致性 隔离性 持久性

分解应具有的特性 : 分解具有无损连接性 : 分解要保持函数依赖 : 分解既要有无损连接性,又要保持函数依赖

设 $R(U)$ 是一个属性集 $U$ 上的关系模式, $X$ 和 $Y$ 是 $U$ 的子集.

函数依赖 : 若对 $R(U)$ 的任意可能关系 $r$ : $r$ 中不存在两个或以上元组在 $X$ 上的属性相等 而在 $Y$ 上不等 : 则称 $X$ 函数决定 $Y$ 或 $Y$ 函数依赖于 $X$, 记做 $X \rightarrow Y$

如果 $X \rightarrow Y$

非平凡函数依赖 : 且$X \not\subset Y$

平凡函数依赖 : 且$X \subset Y$

完全函数依赖 : $\forall X' \subsetneq X$,都有 $X \not\rightarrow Y$ : 记做 $X \xrightarrow{\quad _f \quad } Y$

部分函数依赖 : $\exists X' \subsetneq X$,有 $X \not\rightarrow Y$ : 记做 $X \xrightarrow{\quad _p \quad } Y$

数据库的键

候选键/Candidate Key : 关系中能唯一的标识一个元组的某一属性或属性组

主码/Primary Key : 如果关系中有多个候选码,则选定一个作为主码

主属性/Primary Attribute : 在候选码中的属性

外码/Foreign Key : 属性是其他关系的码

全码/All-Key : 关系中所有属性组是该关系的候选码

超键/Super Key : 能唯一标识元组的属性集

设计模式 概括

桥接模式/Bridge : 将抽象部分和它的实现部分分离, 使他们都可以独立的变化 : 对一个抽象的实现部分的修改应该对使用它不产生影响

中介模式/Mediator : 可以使各个对象间的耦合松散,只需关心和Mediator的关系 : 使多对多的关系变成了一对多的关系,降低系统的复杂性,提高可修改性和扩展性

OOA 的步骤

  1. 分析问题域,建立用例模型
  2. 发现和定义对象和类
  3. 识别对象的内部特征
  4. 识别对象的外部特征
  5. 识别对象之间的交互

5个活动 : 认定对象,组织对象,描述对象间的相互作用,定义对象的操作,定义对象的内部信息

OMT 概述

OMT/Object Modeling Technique/ 对象建模技术 : 三种模型: 对象模型, 动态模型, 功能模型 : 四个步骤: 分析, 系统设计, 对象设计和实现

对象模型 : 描述系统对象的 静态结构,对象之间的关系,对象的属性,操作 : 表示静态的,结构上的,系统的 数据 特征

动态模型 : 描述与时间和操作顺序有关的系统特征----激发事件,事件序列,确定事件先后关系 以及事件和状态的组织 : 表示瞬时的,行为上的, 系统的 控制 特征

功能模型 : 描述与值的变换有关的系统特征----功能,映射,约束和函数依赖 : 使用数据流图来表示

排序算法的适用性

  • 待排序的记录数据 n 较小时, 可采用插入排序和选择排序
  • 待排序基本有序, 选择直接插入排序或冒泡排序
  • 当 n 很大且关键字位数少,选择链式基数排序
  • 当 n 很大, 则采用时间复杂度为 O(nlogn)的排序方法----快速排序,堆排序,归并排序

排序算法的分类

分类包含
交换排序冒泡排序 快速排序
插入排序插入排序 希尔排序 二叉查找树排序
选择排序选择排序 堆排序
归并排序归并排序
分布排序基数排序

设计模式分类

分类包含
创建抽象工厂 构造器 工厂方法 原型 单例模式
结构适配器 桥接 组合 装饰 外观 享元 代理
行为职责链 命令 翻译器 迭代器 仲裁器(Mediator) 回忆(Memento) 观察者 状态机 策略 模板方法 参观者(Visitor)

乔姆斯基文法类型

类型说明
0型相当于图灵机,任何 0型 语言都是递归可枚举的
1型上下文有关文法,相当于线形界限自动机,对非终结符替换时不考虑上下文,不允许替换为空串
2型上下文无关文法, 相当于非确定的下推自动机
3型右线性文法,等价于正规式, 也称为正规文法

文法描述语言的能 : 0型文法最强 3型最弱

3型文法必是2型文法

Tips

正规式只能表示给定结构的固定次数的重复或者没有指定次数的重复
对于每个非确定的有限自动机,都有一个与其等价的正规式
上下文无关文法可以表示次数不固定的重复

中断响应有两种方式 : 精确断点法 和 不精确断点法

精确断点法 : 立即响应中断 : 不影响中断反应时间,影响程序的正确执行

不精确断点法 : 流水线中指令执行完后再响应中断 : 影响中断反应时间,影响程序的正确执行

广义表 : 由零个或多个单元素或子表组成的有限序列 : 长度值元素个数,深度指展开后所含括号的最大层数 : 非空广义表表尾必定是一个表

CCIR/无线电咨询委员会 : 制定了广播级质量数字电视编码标准, CCIR601

算法的特征 : 有穷性: 在有穷步和有限时间内完成 : 确定性: 无二义,唯一的执行路径,同样测输入产生同样的输出 : 可执行性: 算法中描述的操作是通过已经实现的基本操作通过有限次执行实现的 : 正确性: 满足具体需求 : 可读性 : 健壮性: 能处理错误数据 : 效率与低存储需求

SIMD 中 : I 是指指令流 D 是指数据流

三类常用的空闲块管理方法 : 位图向量法, 空闲块链表链接法 和 索引法

死锁的四个必要条件

  • 互斥条件
  • 请求和保持条件
  • 不剥夺条件
  • 环路等待条件

标准

标准名描述
ISO/IEC 9126Software engineering — Product quality/软件工程 质量管理
ISO/TC 176Quality management and quality assurance
GB904-91商品条码结构
GB7590-87第四辅助集
--
国际标准ISO,IEC
行业标准IEEE
区域标准CEN(欧洲标准化委员会)
已公布的行业代号QJ(航天), SJ(电子), JB(机械), JR(金融系统)
企业标准的编号行业标准代号+[/T]+标准发布顺序号(5位)+/+标准发布年代号(4位)

排序算法时间复杂度

排序方法最优时间复杂度平均时间复杂度最差时间复杂度最差空间辅助稳定
插入排序O(n)O(n2)O(n2)O(n)O(1)Yes
选择排序-O(n2)-O(n)~No
冒泡排序O(n)O(n2)O(n2)O(n)~Yes
希尔排序-O(nlog2n)-O(n)~No
快速排序O(nlogn)O(nlogn)O(n2)-O(nlogn)No
堆排序-O(nlogn)-O(n)O(1)Yes
归并排序(wiki:O(n))O(nlogn)-O(n)O(n)Yes
基数排序-O(d(n+rd))--O(rd)Yes
基数排序1-O(kN)-O(k+N)
二叉查找树-O(logn)-O(n)

注 : 1 : 指维基上的结果 : ~ : 和上一个值相同