20xx-20xx年软件设计师知识点汇总

20xx-20xx年软件设计师知识点汇总内容摘要：

模式。 两级映射 ：模式到内模式（数据的物理独立性）、外模式到模式（数据的逻辑独立性） 数据模型的三要素： 数据结 构、数据操作、数据的约束条件。 目或度 n:R 上的 n 元关系，元数：属性的个数，基数：元组的个数记录数，候选码：唯一标识一个元组，主码：关键字， 20 主属性：全部候选码，全码：所有属性都是候选码。 三类完整性约束条件 ：实体的（主属性不空）、参照的即引用的、用户定义的完整性。 五个基本运算 ：并∪、 2－差、 3笛卡儿积 from、 4 投影п select、 5 选择σ where 扩展运算 ： 1 交∩ R∩ S＝ R－ (RS)， 2 连接◇， 3 除 规范化 1NT:没有表中表， 2NT 消除了 1NT 中非主属性对码的部分函数依赖即每一个非主属性 完全依赖于全部的码（ XY 即 Y 依赖 X）、 3NT 消除了非主属性对码传递依赖、BCNF 消除了主属性对码的部分和传递依赖、 4NT 表中没有多值依赖 事务的四个特征 ：原子性、一致性（数据不会因事务而破坏）、隔离性（事务独立运行）、持久性（事务一旦提交）。 BEGIN TRANSACTION。 COMMIT。 ROLLBACK 并发控制 的主要技术是封锁，三级封锁协议： 1 级可解决丢失更新问题； 2 级可解决读脏数据； 3 级防止丢失更新、不读脏数据、防不可重复读 建立冗余数据的方法是数据转储和登记日志文件。 8 数据结构 栈 ：先 进后 出 ； 队 列 ： 尾 进头 出 循 环对 列 F ＝(R+1+Memory_Length) mod M 串 ： (主串 n 模式串 m)朴素的模式匹配算法即布鲁特－福斯 21 算法 :最好情况平均比较次数＝ (n+m)/2 最坏＝ m(n+m)/2 二叉树 ： i 层至多 2i1个结点；深度为 k 的二叉树最多 2k1 个结点；具有 n 个结点的完全二叉树的深度为└ log2n ┘ + 1；森林和树的转换利用树的孩子兄弟表示法。 哈夫曼树即最优二叉树 ，是带权路径最短的树。 图 ： N 个顶点的无向完全图有 n(n1)/2 条边；任何图的边＝顶点总度数 /2； 连通图 是指无向图 任两顶点连通，最大的连通子图叫连通分量； 生成树 是极小连通图； n 个顶点 e 条边的无向图的邻接链表需要 n 个头结点和 2e 个表结点。 求最小生成树有普里姆算法 prim 和克鲁斯卡尔算法 Kruskal； AOV 网 ：工程可行性； AOV 的拓扑排序（选入度为 0 的输出、删） AOE 网 ：工程需时和关键活动；关键路径是最长路径。 最短路径 ：迪杰斯特拉算法 查找 ：①顺序查找平均查找次数 ASL＝ (n+1)/2；②折半 ASL＝ (n+1)/2 * log2(n+1) 1 ；③分块 (s 是每块的个数 )块内块间都顺序 ASL＝ (n/s + s )/2 +1 块内顺序块间折半 ASL= log2(n/s+1) + s/2 二叉排序树 即二叉查找树 左小于右；平衡二叉树 AVL 树左右深度差不超过一； m 阶 B－树 根至少有两棵子树其他非叶至少有 m/2 进位取整棵 哈希表 散列表 ：构造方法有直接定址法、数字分析法、平 22 均取中法、折叠法、随机数法、除留余数法；冲突处理方法有开放地址法、链地址法、再哈希法、建公共溢出区法；装填因子＝表中记录数 /哈希表长度。 排序 ：堆排序 建堆从最后一个非叶开始（一直往下）一个个往前筛选。 直接插入 好 O(n) 均 O(n2) 坏 O(n2) 辅 O(1) 稳定 直接选择 O(n2) O(n2) O(n2) O(1) 不稳 冒泡排序 O(n) O(n2) O(n2) O(1) 稳定 希尔排序 ――― O() 不稳 缩小增量排序 快速排序 O(nlogn) O(nlogn) O(n2) O(nlogn)不稳后往前找小交换 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳 归并排序 O(nlogn) O(nlogn)O(nlogn) O(1) 稳定 两两排序归并 基数排序 O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd) 稳定 r=10,d位数 线性表的第 i 个元素存储位置为 loc(a1)+(i1)*L ； 线性表的平均移动次数 (n1)/2； 线性表的顺序查找平均长度为 (n+1)/2； 判断循环队列满：==(+1)%m m 为队列最大长度 ； 判断循环队列满： == 23 指令流水线计算时间公式 NT+(n1)T T 是流水线的周期， N是流水线的段数， n是有多少条流水 线指令 系统可靠性计算方法： 串联系统 可靠性 R = R1*R2*R3 失效率 y = y1 + y2 + y3 并联系统 可靠性 R = 1 (1 R1)*(1 R2)*(1 R3) 平均无故障时间 MTBF = 1/u = 指令流水线计算方法； 第一类是各指令段 ,有同步时间 ,即有指令流操作周期 .当某指令段执行完毕后 ,必须等到下一个操作周期来临时 ,才能执行下一条指令的相同段 .其计算公式是 : (指令所分段数 1)*指令流操作周期 +指令数 *指令流操作周期 . 同指令的段数 *操作周 期 +(总的指令数 1)*操作周期 . 第二类是各指令段 ,没有同步时间 ,每段执行完毕 ,不需要等待 ,直接执行下一条执令相同的段 .其计算方法。 第一条指令执行时间 +(指令数 1)*各指令段执行时间中最大的执行时间 CPI = 所有的指令执行时间 /指令总数 MIPS = 机器频率 /CPI 9 常用算法 算法的五特性： 有穷性、确定性、可行性、输入、输出 24 好的算法的目标 ：正确性、可读、健壮、效率与低存储需求 迭代法： 求方程近似根 ，对分法和梯度法。 穷举搜索法。 递推法。 递归法： 执行过程分递推和回归两阶段。 背包问 题。 回溯法即试探法。 贪心法： 不求最优但求快速有解， 哈夫曼算法 装箱问题 马的遍历 0/1 背包。 分治法： 大问题分成小问题解决 快速排序 比赛日程。 动态规划法 ：求两字符串中最长公共字符序列。 10 面向对象技术 面向对象技术 面向对象 ＝对象＋分类＋继承＋通过消息的通讯。 对象有对象名（标识）、属性和操作（方法）组成。 对象是类的实例。 类解决数据保护问题，继承是父子共享数据和方法的机制。 注意类中的静态变量，该变量可以通过 类名：：静态成员名访问 ，类的所有对象共享该静态成员变 量。 对于静态成员变量的初始化方式： 类型类型 类名 ::静态数据成员名 = 值 Smalltalk全面支持面向对象概念， eiffel是全面的静态类型化也支持全面的面向对象概念。 “类的层次结构”指导编译程序进行类的实例化过程。 多态 ：是不同对象收到同一消息产生不同结果。 通用多态有参数多态（最纯的、类属），包含多态（子类型化）； 特定多态有 过载多态（同一变量被用来表示不同功能）、强制多态。 类属 (模版类 )是一种参数多态机制。 25 好的 OOP 必须支持 ：被封装的对象、类和实例的概念、继承性、多态。 程序设计的 发展： 过程程序设计、模块化、函数、逻辑、面向对象。 面向对象的好处 ：对象技术解决了产品质量和生产率间的平衡；继承机制使系统具有很高的灵活性和易扩充性；面向对象是一个能管理复杂性并增强伸缩性的工具；从概念模型化到分析设计编码可以无缝传递；封装有助于建立安全的系统。 面向对象的概念 ：对象、类、方法、实例变量、消息、子类、继承 类的访问控制符 ： Private 类内 Protected 类及友元 Public 消息传递机制和对象自身引用 将方法与特定的对象动态地联系在一起，使得不同对象在执行同样的方法体时可因对象的状态不 同而产生不同的行为，从而使方法对具体地对象具有个性。 衡量开发人员 ：能否最好地发挥已有类库地优点、将已有类库与新问题紧密匹配地能力、不得不另外编写地代码最少。 面向对象分析方法 OOA：将数据和功能合在一起考虑，把系统地行为和信息间地关系表示为迭代构造特征。 五个活动 ：认识对象、组织对象、对象间地相互作用、基于对象地操作。 面向对象设计 OOD：设计分析模型和实现源代码。 构件是 26 功能和数据的封装。 面向对象测试 ：单元测试－综合测试－系统测试；算法层－类层－模板层－系统层。 常采用回归测试和自动测试。 面向对象的分析和设 计方法： 1） Peter Coad 的 OOA 模型 的五个层次：主题层、对象类层、结构层、属性层、服务层；两种结构分类结构（一般和特殊）和组装结构（整体和部分）。 OOD 的四个活动：设计问题域部件、设计人机交互部件、设计任务管理部件、设计数据管理部件。 2） Booch 的 OOD：认为软件开发是螺旋的，每个周期包括标识类和对象、确定他们的含义、标识他们的关系、说明每一个类的界面和实现。 3）对象建模技术 OMT： 三个模型即对象模型（链和关联、泛化、聚集、模块）、动态模型（与时间和操作顺序有关的特征，用状态图表示）、功能模型（描 述与值变换有关的特征 用数据流图表示）。 4）统一建模语 UML： UML 三要素（ UML 的基本构造块、支配这些构造块如何存放的规则、运用与整个语言的一些公共机制）。 三种构造块 （事物、关系、图）。 四种事务 ：结构事物 (静态部分类 接口 协作 用例 主动类 构件 结点 )、行为事物（交互和状态机）、分组事物（包 是概念性的仅在开发时存在）、注释事物。 四种关系 ： 依赖（事物间语义关系）、关联（结构关系）、聚集（特殊的关联 整体和部分）、泛化（一般和特殊）、实现（类元之间的语义关系）。 27 五类 9 种图： ①用例图 （用户角度描述系统 功能，用于对系统的语境和需求建模）、 ②静态图 （类图、对象图；定义类之间关系和类内结构）、 ③行为图 （状态图由状态转换事件和活动组成；活动图用于工作流建模和对操作建模）、 ④交互图 （顺序图 合作图：描述对象间的交互关系）、 ⑤实现图（构件图：描述代码部件的物理结构及各部件之间的关系； 配置图即部署图：定义系统中软硬件关系。 ） 11 标准化知识 国际标准化组织 ISO 和 IEC。 统一是标准化的本质， 目的 是建立最佳秩序和获得最佳效益。 标准复审（ 5 年次）要确保其有效性、先进性、适用性。 按性质分类 ：技术标准、管理标准、工作标准。 采用国际和国外先进标准的方法 ：认可法、封面法、完全重印法、翻译法、重新制定法、包括引用法。 采用程度 ：等同 idt、等效 eqv、非等效采用 neq。 标准化条码 EAN，共有 13 位： 3 位前缀表示国家、 4 位厂商代码、 5位商品代码、 1 位效验码。 ISO9000： 是质量管理和质量保证的标准，按照全面质量管理的 PDCA 模式工作。 ISO9000： 2020 现有 13 项标准，有 4个核心标准（基础和术语 用概念图描述、要求、业绩改进指南、审核指南）。 标准确认的 8 项原则：以顾客为中心、领导作用、全员参与、过程方法（ 4 大过程即管理职责、资源管理、产品实现、测量分析和改进）、管理的系统方法、 28 持续改进、基于实事的决策方法、互利的供求关系。 标准化对象有技术标准、管理标准和工作标准。 计算机软件产品编制开发指南是国家批准的标准，所以是推荐性的国家标准。 信息产业部批准的标准应该是行业标准，因为该部门是国家的行政管理部门。 IEC 国际电工委员会 国际电信联盟 ITU指定了 X和 V系列标准， V系列建议是针对电话通信、 X系列是针对网络接口和公用网络例如 定了分组交换网络接口标准， 准。 IEEE 美国电气电子工程师学会 制 定了 802局域网标准。 CMM 成熟度模型 1)初始级 ――软件过程的特点是无秩序的，有时甚至是混乱的。 软件过程定义几乎处于无章法可循的状态，软件产品所取得的成功往往依赖极个别人的努力和机遇。 2)可重复级 ――已建立了基本的项目管理赛程，可用于对成本、进度和功能特性进行跟踪。 对类似的应用项目，有章可循并能重复以往所取得的成功。 3)已定义级 ――用于管理的和工程的软件过程均已文档化、标准化，并形成了整修软件组织的标准软件过程。 全部项目均采用与实际情况相吻合的、适当修改后的标准软件过程来进行操作。 4) 已管理级 ― ―软件过程和产品质量有详细的度 29 量标准。 软件过程和产品质量得到了有效的认识和控制。 5)优化级 ――通过对来自过程、新概念和新技术等方面的各种有用信息的有效分析，能够不断地、持续性地对过程进行改进。 12 知识产权知识 《民法通则》保护。 知识产权 分为两类工业产权和著作权。 特点：无形性、双重性、确认性、独占性、地域性、时间性（专利 20 年，实用新型和外观 10 年，到期前 6。