当前位置：首页 > news >正文

网站建设分为展示型网站建设设备

news 2025/11/20 8:24:09

网站建设分为展示型,网站建设设备,公司网站开发费用计入哪个科目,wordpress菜单图标在文字右侧前言#xff1a;全国计算机技术与软件专业技术资格#xff08;水平#xff09;考试#xff08;以下简称IT职业资格考试#xff09;是由中华人民共和国人事部主管#xff0c;国家计算机网络与信息安全管理中心主办的一项国家级、权威性的计算机职业技能水平认证考试。主要… 前言全国计算机技术与软件专业技术资格水平考试以下简称IT职业资格考试是由中华人民共和国人事部主管国家计算机网络与信息安全管理中心主办的一项国家级、权威性的计算机职业技能水平认证考试。主要为企事业单位和社会培训机构提供了一个可以测试、认证计算机和软件专业技能水平的途径。在IT职业资格考试中软件设计师考试简称软考是一个重要的考试类别资格证书被认为是软件行业人才的重要标志和职业资格证明。软考中级软件设计师是软考的一个等级属于软件工程师职业级别是一项高级软件设计和开发领域的专业资格认证是软件行业职业人员的核心能力证明之一。软考中级软件设计师考试内容包括软件开发、需求分析、软件测试、软件项目管理、软件质量保证等多个方面。通过此证书考试证明了考生在软件设计和开发方面的专业知识和实践经验能够在软件项目中发挥重要的作用为企业和组织提供高质量的软件应用解决方案。以下是学长为大家整理的软件设计师知识点希望能帮助大家取得一个好成绩~ 第 1 章计算机系统知识计算机系统由两部分组成硬件、软件。 • 计算机硬件系统五大组成部分控制器、运算器、存储器、输入设备、输出设备存储器分为内部存储器内存、容量小、速度快、存放临时数据断电消失和外部存储器硬盘、光盘、容量大、速度慢、长期数据保存输入设备、输出设备统称外设主机 CPU 主存储器 • 中央处理单元 CPU CPU 组成由运算器、控制器、寄存器组读取速度最快、内部总线组成 CPU 功能实现程序控制、操作控制、时间控制、数据处理功能运算器组成常考算数逻辑单元 ALU(Arithmetic logic unit)实现对数据的算数和逻辑运算提供一个工作区累加寄存器 AC(Accumulator): 运算结果或者源操作数的存放区数据缓冲寄存器 DR(Data Register): 暂时存放内存的指令或数据状态条件寄存器 PSW(Program Status Word): 保存指令运行结果的条件吗内容如溢出标志等运算器功能执行算数运算和逻辑运算控制器指令寄存器 IR Instruction Register : 暂存当前 CPU正在执行的指令程序计数器 PC Program Counter 存档指令执行地址地址寄存器 AR Address Register 保存当前 CPU所访问的内存地址指令译码器 ID Instruction Decoder分析指令操作码控制器功能控制整个 CPU的工作最为重要包括程序控制、时序控制程序员可以访问通用寄存器存取数据也可以访问状态寄存器和程序计数器但是不能访问指令寄存器 • 数据进制转换二进制、十六进制 0x18F、 18FH R 进制转 10 进制案例 6 进制 5043 转为十进制 36^0 46^1 06^2 56^3 1107 十进制转 R 进制案例十进制 200 转 6 进制 200/6 33 余 2 33/6 5 余 3 5/6 0 余 5 6 进制为余数的从后向前排列 532 m 进制转为 n 进制通过十进制中转 • 数的表示考得少最小数据单位 b( 比特 bit) 最小存储单位 1B(字节 byte)8b 1KB1024B; 1MB1024KB; 1GB1024MB 机器数各种数值在计算机中表示的形式特点是使用二进制计数制数的符号用 0 和 1 表示小数点隐含不占位置例如 0 0 0000000 -0(1 0000000) 其中第一位是符号为后七位表示数值位定点表示法分为纯小数与纯整数两种其中小数点不占存储位纯小数约定小数点在机器数的最高数值位之前纯整数约定小数点的位置在机器数的最低数值位之后真值机器数对应的实际数值 • 数的编码方式不怎么考原码一个数的正常二进制表示例如 0 0 0000000 -0(1 0000000) 反码正数的反码即为原码负数的反码是在原码的基础上除了符号位以外其他各位按位取反例如如上数值的反码为 0 0 0000000 -0 1 1111111 补码正数的补码即原码负数的补码是在原码基础上除了符号位以外其他各位按位取反而后在末位 1 若有进位则产生进位 0 0 0000000 -0 0 0000000 -0 的补码有溢出移码用作浮点运算的阶码无论正数负数都是将该原码的补码的首位符号位取反得到计算机系统中常采用补码来表示和运算数据原因是采用补码可以简化计算机运算部件的设计 • 浮点表示常考浮点数 N F * 2^E, 其中 E 称为阶码 ( 带符号的纯整数 ) F 称为尾数带符号的纯小数类似于十进制的科学记数法例如 101.0110.101011*2^3 浮点数所能表示的数值范围由阶码确定所表示的数值精度由尾数确定浮点数运算需要先 1. 对阶即将阶码换算成相同的后再计算小阶向大阶对接否则会损失尾数的精度》 2. 尾数计算》 3. 结果格式化浮点数存储格式 | 阶符 | 阶码 | 数符 | 尾数 | 一般尾数用补码阶码用移码规格化浮点数将尾数的绝对值限定在 [0.5, 1] 浮点数的范围 M: 尾数补码位 ( 包括数符 ) R: 阶码补码位 ( 包括阶符 ) 则最大正数 (1-2^-M1) * 2(2R-1 - 1), 最小负数 -1 * 2(2R-1 - 1) 定点表示法与浮点表示法定点表示法分为定点整数和定点小数定点表示法的小数点不需要占用存储位总位数相同时浮点表示法可以表示更大的数定点小数在机器字长为 n 的表示范围是定点整数表示范围除以 2^n-1 • 寻址立即寻址操作数包含在指令中直接寻址操作数存在内存单元中指令中给出操作数所在存储单元的地址寄存器寻址操作数存在某一个寄存器中指令中给出存放操作数的寄存器名比直接寻址要快寄存器距离 CPU 更近寄存器间接寻址操作数存在内存单元中寄存器中存放了操作数所在的内存地址指令中则存了寄存器名也就是说寻址路径指令 - 寄存器 - 内存间接寻址指令中给出操作数地址的地址寻址效率立即寻址寄存器寻址直接寻址寄存器间接寻址间接寻址采用不同寻址方式的目的扩大寻址空间提高编程灵活性 • 校验码码距指一个编码系统中两个合法编码之间至少有多少个二进制不同奇偶校验码在编码中增加一个校验位来使 1 的个数为奇数或者为偶数码距为 2奇偶校验只能校验错误不能纠正错误海明码一种利用奇偶性来纠错的校验方法码距为 3 设数据位有 n 位校验位有 k 位则 n 与 k 必须满足以下关系 2^k-1 nk 循环冗余校验码(CRC)可以检错但不能纠错码距为 2 由 k 个数据位 r个校验位组成校验码由信息码产生校验码位数越多校验能力越强求 CRC 编码时采用模二运算 • RISC 和 CISC RISC: 精简指令集计算机指令少复杂度低指令长度固定寻址方式少通用寄存器数量多支持流水线技术采用硬布线控制逻辑组合逻辑控制器 CISC 复杂指令集计算机指令多复杂指令长度变化寻址方式复杂多样通用寄存器数量一般也支持流水线技术使用微程序控制技术 • 流水线技术流水线多条指令重叠进行操作的一种准并行处理实现技术指令分为三个部分取指 - 分析 - 执行一条完整指令的执行时间取指时间分析时间执行时间流水线周期指令步骤中所花时间最长的一段例如取指 1ms - 分析 3ms - 执行 2ms 则流水线周期为 3ms表示除了第一条外后边的指令都只需要多花 3ms 就能完成流水线总共用时理论公式一条完整指令完成时间 (指令总数 - 1)*流水线周期实践公式给第一条指令充分的时间及第一条指令的每一个步骤都用一个流水线周期的时间吞吐率指单位时间内流水线所完成的任务数量计算公式指令条数 / 流水线总共用时最大吞吐率 1 / 流水线周期异步控制会延长时间降低性能每次操作结束后要发出结束信号 • 存储器按照所处位置分类内存外存按工作方式分类读 \ 写存储器 RAM只读存储器 ROM 按访问方式分类按内容访问存储器例如相连存储器按地址访问存储器按寻址访问存储器随机存储器、顺序存储器、直接存储器闪存一种只读存储器 ROM 删除时以块为单位删除类比为 U 盘虚拟存储器由主存辅存组成存储系统的层次结构由内而外 CPU 内部通用寄存器》 Cache(SRAM 静态随机存储器 ) 》主 \ 内存储器 (DRAM 动态随机存储器需要周期性刷新来保持数据 ) 》外存储器空间局部性若一个存储单元被访问则其临近的存储单元在不久的将来也很可能被访问这种特性就是空间局部性时间局部性若一个存储单元被访问则这个单元在以后也可能被再次访问这种特性就是时间局部性 • Cache 高速缓存 Cache 高速缓存位于 CPU 与主存之间用来存放当前最活跃的程序和数据主存的部分拷贝信息速度比主存块 5~10 倍对程序员来说是透明的程序员不可操作 Cache 容量越大命中率越高逐渐接近 100% 但是随着容量变大 Cache 成本和命中时间也在增大替换算法目标是使 Cache 获得更高的命中率随机替换算法先进先出算法近期最少使用算法优化替换算法 Cache 中的地址映像方法地址映像 CPU 工作时送出的主存地址而要从 Cache 中读写信息就需要将主存地址换算成 Cache 地址这种转换称为地址映像直接映像主存分区 Cache分块主存每个区有与 Cache 相同的分块主存每个区的块与 Cache 的块的对应关系时固定的硬件电路简单但是冲突率高全联映像主存不分区主存与 Cache按照相同的大小分块 Cache 的块可以对应任意的主存上的块电路设计难只适用于小容量的 Cache冲突率低组相连映像是直接相连与全联映像的折中先分组组与组之间的直接映像组内是全联映像发生冲突概率全联映像《组相连映像《直接映像 Cache 与主存之间的映射是由硬件自动完成的 • 中断中断遇到急需处理的事件时暂停当前正在运行的程序转去执行有关程序处理完后返回源程序这个过程称为中断中断向量提供中断服务程序的入口地址中断响应时间发出中断请求开始到进入中断服务程序这一段时间保存现场目的为了能正确的返回被中断的程序然后继续执行 7第 1 章计算机系统知识 • 输入输出 I/O 控制方式程序查询方式程序直接控制方式 CPU 和 I/O 只能串行工作 CPU 需要一直轮询检查状态长期处于忙等状态 CPU 利用率低一次只能读写一个字由 CPU 将数放入内存中断驱动方式 I/O 设备通过中断信号主动向 CPU 报告 I/O 操作已完成 CPU 与 I/O 外设可并行操作 CPU 利用率提升一次只能读写一个字由 CPU 将数据放入内存直接存储器存储方式 DMA方式 CPU 向 I/O 模块发出数据读写的命令然后 CPU 就可以做其他事情 I/O 模块与内存建立直接的数据通路 I/O 模块操作完成后通过中断信号告知 CPU CPU 与 I/O 外设可并行工作由外设直接将数据放入内存一次读写的单位是块而不是字仅在传输数据块的起始和结束需要 CPU 的干预 CPU 在一个总线周期结束时响应 DMA 的请求每传输一个数据都要占用一个存储周期由 I/O 设备提出的中断请求是可屏蔽中断电源掉电是不可屏蔽中断 • 总线总线链接计算机有关部件的一组信号线是计算机用来传送信息代码的公共通道总线分类数据总线地址总线控制总线 8第 1 章计算机系统知识总线的优点简化系统结构减少连接线数目便于接口设计便于故障诊断和维修同时降低了成本总线带宽计算时钟频率 * 每秒传送的字节地址总线宽度计算地址总线的宽度表明 CPU 的寻址能力与内存大小相关内存多大就需要多宽的地址总线例如内存容量为 4GB - 2^32 B - 地址总线宽度为 32 数据总线宽度计算数据总线宽度就是处理机的字长 PCI并行内总线系统总线 SCSI: 并行外总线 • 加密技术与认证技术加密解决的问题窃听认证解决的问题篡改、假冒、否认加密技术对称加密加密解密用的是同一把秘钥且只有一把秘钥加解密速度快适合大量明文数据秘钥分发有缺陷非对称加密加解密不是同一把秘钥一共有两把秘钥公钥私钥加解密速度慢秘钥分发没缺陷公钥私钥之间不可推算混合加密就是将对称加密与非对称加密混合使用先用对称加密将大量明文数据加密再用非对称公钥对“对称加密的秘钥” 加密并随着加密明文一起传给接收方接收方使用非对称的私钥解密出 “对称加密的秘钥”再用 “对称加密的秘钥” 解密明文认证技术摘要将发送的明文 Hash 算法后得到摘要放在密文后一起发送过去与接收方解密后的明文 Hash 算法的摘要结果对比一致则没有篡改数字签名在摘要的基础上对摘要进行私钥签名接收方通过公钥对数字签名进行解密可以判定是否被篡改假冒否认用来验证消息来源的真实性数字证书使用第三方机构 CA 的私钥来对用户的公钥进行数字签名来保证公钥不被篡改接收方用 CA 的公钥解密来得到发送方的公钥用数字证书来认证用户身份用数字签名来防篡改、假冒、否认加密算法对称加密算法私钥私有秘钥加密共享秘钥加密算法 DES 3DES RC-5 IDEA AES RC4 非对称加密算吗公钥公开秘钥加密 ECC RSA DSA Hash 函数、 MD5摘要算法、 SHA-1 安全散列算法 • 系统可靠性设一个系统由 N 个子系统组成子系统的可靠性分别为 R1 R2 R3 串联系统可靠性 R R1R2R3 并联的系统可靠性 R 1 - (1-R1)(1-R2)(1-R3) • 其他指令寄存器的位数取决于指令字长计算机分级存储速度依次为 CPU 内部通用寄存器》 Cache 》内存》外存安全需求物理线路安全 – 机房安全网络安全 – 入侵检测系统安全 – 漏洞补丁管理应用安全 – 数据库安全 10第 1 章计算机系统知识第 2章程序设计语言 • 低级语言与高级语言低级语言机器语言与汇编语言高级语言面向应用的各类程序设计语言例如 C JAVA Python , 与自然语言比较接近提高程序设计效率高级语言或者汇编语言编写的叫源程序源程序不能直接在计算机上执行 • 解释器解释程序翻译源程序时不生成独立的目标程序解释程序和源程序需要参与到程序的运行过程中 • 编译器编译程序翻译时将源程序翻译成独立保存的目标程序机器上运行的时与源程序等价的目标程序编译器与源程序都不参与目标程序的运行过程 • 程序设计语言的数据成分标识符由数字、字母、下划线组成的标记常量与变量按照程序运行时数据的值能否改变来区分常量存储在池中没有自己的存储单元全局量和局部量按照数据在程序代码中的作用范围来划分控制结构顺序结构、循环结构、选择结构程序中的数据具有类型的作用 1. 便于为数据分配存储单元 2. 便于对参与表达式计算的数据对象进行检查 3. 规定数据对象的取 11第 1 章计算机系统知识值范围以及能够进行的运算表达式的左结合由左向右执行例如 a b 表达式的右结合由右向左执行例如 x y z • 传值调用和传址调用函数定义函数首部返回值类型函数名 ( 形参 ) 函数体 ({}) 传值调用将实参的值传给形参实参可以是常量、变量、表达式不可以实现实参形参之间双向传递数据的效果传址调用将实参的地址传给形参实参必须有地址实参不能是常量值或者表达式可以实现实参形参之间双向传递数据的效果即改形参的值实参的值也同时改掉了 • 编译、解释程序翻译阶段编译方式各个阶段词法分析 – 语法分析 – 语义分析 – 中间代码生成可省略 – 代码优化可省略 – 目标代码生成解释方式各个阶段词法分析 – 语法分析 – 语义分析编译器与解释器都不可省略且变换顺序的阶段是词法分析、语法分析、语义分析编译器的中间代码生成和代码优化阶段不是必要的可省略 • 符号表的作用不断收集、记录和使用源程序中一些符号的类型和特征信息将其存入符号表中记录源程序中各个字符的必要信息以辅助语义的正确性检查和代码生成 12第 1 章计算机系统知识 • 词法分析将源程序看做一个多行的字符串从上到下、由左到右进行逐个字符扫描从中识别出一个个单词符号如关键字、标识符、运算符等词法分析分析出的单词常常以二元组的形式输出即单词种别和单词的值词法分析的依据是语言的词法规则词法分析输入的是源程序输出的时记号流词法分析的主要作用分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定 • 语法分析在词法分析基础上根据语言的语法规则将单词符号序列分解成各类语法单位如 ’表达式‘ ’语句‘ ’程序‘ 等如果没有语法错误语法分析后会构造出一个语法树否则指出错误给出诊断信息语法分析输入的是词法分析产生的记号流输出的时语法树语法分析主要作用对各条语句的结构进行合法性分析发现程序中的所有语法错误 • 语义分析用来检查源程序是否包含静态语义错误主要用来类型分析和检查语义分析输入的是语法分析阶段产生的语法树语义分析阶段不能发现所有的语义错误只能分析出静态的语义错误动态的语义错误要在运行时才能发现动态语义错误常见的有死循环 13第 1 章计算机系统知识 • 目标代码生成这一个阶段的任务是把中间代码变成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码目标代码生成阶段的工作与具体的机器密切相关寄存器的分配处于目标代码生成阶段 • 中间代码生成根据语义分析的输出生成中间代码是一种简单的记号系统可以有多种形式其特征是与具体的机器无关语义分析和中间代码生成所依据的时语言的语义规则常见的中间代码后缀式、三地址码、三元式、四元式、树图等形式可以将不同的高级语言编译成同一种中间代码中间代码可以跨平台中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性 • 正规式正规式是词法分析的工具大致可以类比 JS 中的正则的基本规则主要记住 * 代表的取值范围时 [0, 无穷大 ] ,然后将选项带入看看符不符合规则即可 • 有限自动机有限自动机是词法分析的工具他能正确的识别正规集状态分为初态和终态一个状态既可以是初态也可以是终态识别成功的依据是状态机的路跑的通并且跑完后的终点是终态确定的有限自动机对每一个字符来说识别字符后的转移状态是唯一 14第 1 章计算机系统知识的不确定的有限自动机对每一个字符来说识别字符后的转移状态是不唯一的区分确定的有限自动机和不确定的有限自动机在于给定一个数字或者字母它只有一条路可以跑那就是确定的反之是不确定的空串 • 上下文无关文法被广泛的用于表示各种程序设计语言的语法规则 – 上下文无关文法做题由开始符号起始推到出选项中的终结符号一个选项一个选项的尝试 • 后缀式、中缀式中缀式就是常见的表达式 1*2 后缀式的符号放在后边 12* 中缀式转后缀式按照 () 、 * /、 - 的优先级一个表达式一个表达式的转换成后缀式同等优先级的从右向左转换后缀式转中缀式使用栈的方式先进后出、后进先出语法树中缀遍历 - 生成中缀式左根右语法树后缀遍历 - 生成后缀式左右根后缀式又称逆波兰式 • 其他反编译通常不能将可执行文件还原成高级语言源代码只能转换成功能等价的汇编程序动态语言指的是程序运行时可以改变其结构指针变量变量是内存单元的抽象用于在程序中保持数据当变量 15第 1 章计算机系统知识存储的时内存单元地址时称为指针变量链表中的节点控件需要程序员申请和释放数据控件应采用堆存储分配策略可视化程序设计特点基于面向对象思想引入控件概念和事件驱动研发过程遵循先界面绘制再基于事件编写程序代码设计人员可以不用补编写或者少量编写代码编译过程中为变量分配存储单元所用的是逻辑地址程序运行时再映射为物理地址 C 中全局变量的存储空间在静态数据区语法指导翻译是一种静态语义分析方法语法分析方法递归下降分析法和预测分析法都是属于自上而下的分析法移进 - 归约分析法属于自下而上的分析法 16第 1 章计算机系统知识第 3章知识产权 • 著作权著作权分为人身权和财产权人身权分为发表权、署名权、修改权、保护作品完整权除发表权外其他权利的时限都是永久发表权的时限是终生死后 50 年知识产权的地域性在哪里授予的知识产权只在授予国家有效在外部国家不受保护 • 计算机软件著作权计算机软件著作权受《中华人民共和国著作权法》和《计算机软件保护条例》保护计算机软件著作权的主体是公民计算机软件著作权的客体的是指受保护的计算机程序源程序和目标程序和相关文档流程图、说明书、用户手册计算机软件著作人身权发表权、开发者身份权署名权、永久计算机软件著作权的保护期自软件开发完成之日起保护期为 50 年保护期满除了开发者身份权外其他权利终止《计算机软件保护条例》是国务院颁布的侵权行为鉴别未经著作权人的同意发表、登记、署名、更改、翻译、复制、出售、出租 • 职务作品职务软件作品指公民在单位任职期间为执行本单位的工作所开发的计算机软件作品 17第 1 章计算机系统知识公民在单位任职期间所开发的软件著作权属于单位。如果开发软件不是职务工作那著作权就不是单位所有但是如果用了单位设备则不能归个人享有如果是职务软件作品那开发者只有署名权 • 委托开发委托开发的作品著作权由委托方和受委托方订立的合同决定无合同约定的著作权为受委托方所有 • 商业秘密商业秘密的基本内容经营秘密和技术秘密商业秘密的构成条件具有未公开性不为公众所知悉具有实用性能给权利人带来利益具有保密性即采取了保密措施 • 专利权由书面形式申请的一份申请一项发明专利权保护期限 20 年实用新型专利是 10 年专利权就申请之日起算两人以上申请现申请先获得同一天申请由两人协商决定 • 商标权自核准之日起 10 年有效届满前可以续每次续 10 年谁先注册谁享有商标同时注册谁先使用谁享有商标同时注册都没有使用则协商或者抓阄决定 18第 1 章计算机系统知识 • 软件许可使用独占许可使用软件著作权人不能再给他人许可软件著作权人也不可使用独家许可使用软件著作权人不能再给他人许可但是软件著作权人可以使用普通许可使用软件著作权人可以再给他人许可软件著作权人也可以使用 • 软件著作权中的翻译权将软件从一种程序设计语言转化成另一种程序设计语言 19第 1 章计算机系统知识第 4章数据库知识 • 数据模型的分类概念数据模型从信息世界中抽象的数据模型独立与计算机系统一般采用实体 - 联系方法 E-R 方法来表示用于信息世界建模结构数据模型 ( 数据模型 DBSM)直接面向数据库的逻辑结构一般会考察数据模型中的关系模型和相应的关系模式 • 概念数据模型常用术语实体客观存在相互区别的事务例如一个人一个单位一个外部系统属性用来描述实体的特性例如人的姓名单位的地址码 | 键唯一标识实体的属性或属性集域属性的取值范围联系实体之间的对应关系 • 实体之间的联系分为三种一对一一个班级对应一个班长一对多一个班级对应多个学生多对多一个老师可以对应多个班级一个班级也可以有多个老师 • E-R 图实体 - 联系实体 – 矩形表示属性 – 椭圆表示联系 – 菱形表示 20第 1 章计算机系统知识使用无向边链接用 1:n, n:1, n:m 来表示联系的类型结构数据模型主要分为层次模型网状模型关系模型和面向对象模型 • 三级模式和两级映射外模式用户模式或者子模式对应外部视图和用户交互概念模式对应数据库基本表内模式存储模式实际数据库存储文件模式 - 内模式映像实现了概念模式和内模式之间的转换保持数据的物理独立性外模式 - 模式映像实现了外模式和概念模式之间的转换保持数据的逻辑独立性 • 关系模型中基本术语关系一个关系就是一个二维表元祖表中的一行就是一个元祖对应一个记录值属性表中的一个列就是一个属性列的第一行就是属性名其他为属性值域属性的取值范围关系模式对关系的描述格式实体属性 1 属性 2 …属性 n 候选码 | 候选键能够唯一标识一个元祖的属性或者属性组合主码 | 主键一个关系中可能会有多个候选码从中选择一个作为主码外码 | 外键一个关系中的属性或属性组并非该关系的码但是是别的关系中的主码则称其为该关系的外码 | 外键全码一个候选码包含关系中的所有属性则该候选码为全码超码包含候选码的属性集 21第 1 章计算机系统知识主属性候选码中的都是主属性其他的时非主属性 • 关系模型完整性约束实体完整性主键的值不能空参照完整性外键的值可以为空但是如果有值则其值一定能在对应的表中找到用户定义完整性用户定义的对某一数据的指定约束条件 • 关系代数运算 ∪ ( 并集 ) R ∪ S, R,S 所有元祖 | 记录合并删除重复记录后的结果 ( 差 ) R-S, 从 R 中删除存在于 S 中的记录 ∩ ( 交集 ) R ∩ S, R,S 中同时存在的记录组成 × ( 笛卡尔积 ): R × S, R 中每条记录与 S 中的每条记录拼接组合成新的记录 π ( 投影 ) π 1,3 ® 从关系 R 中抽取第 1 3 列属性组成新的关系其中 1 3 列号也可以用对一个属性名代替 6 (选择 ) 6 15 ® 从关系 R 中选择所有第 1 列的值等于第 5 列值的记录组成新的记录链接链接就是在两个关系的笛卡尔积中选择符合条件的行等值链接连接条件为两列值相等自然链接 || 不需要写链接条件自然链接中会选出两个表中同名属性对应值相同的记录并且生成的新关系中去除了重复的属性列左外链接 R 自然链接 S 在自然链接基础上将左侧关系 R 中在自然链接结果中丢失的记录与自然链接结过拼接的结果用空值 NULl 来填充右侧属性 22第 1 章计算机系统知识右外链接与左侧链接相反全外链接左外链接与右外链接的结果叠加 • 关系模式 R 也就是关系名属性组 , 属性的域 , 属性到域的映射 , 属性组中属性的数据依赖关系通常 D dom 可以省略例如 R{A, B, C, D}, {A-B, A-C, C-D} “-” 可以理解为 “推导出”或者“决定”的意思完整函数依赖例如 ( 学号课程 ) - 成绩但是单独的学号或者课程不能直接推导出成绩这就是完整函数依赖部分函数依赖例如学号课程号 - 姓名单独的学号也可以推导出姓名这就是部分函数依赖依赖传递 A-B , B-C , 则称 C 对 A 传递依赖属性闭包计算挑选主键由推导关系选出可以完全推导出所有属性集的某个属性或者某几个属性组合例如 R{A, B, C, D}, {A- B, A-C, C-D} 中 A 属性可以完全推导出 {A, B, C, D} A 就是主键有多个情况则可以有多个候选键冗余函数依赖例如 {A-B, B-C, A-C, C-D} 中 A-C 即为冗余因为 A-B-C 有传递依赖传递依赖优先自己的理解 • 范式 – 应试技巧 1NF - 2NF: 消除非主属性对码的部分函数依赖 2NF - 3NF: 消除非主属性对码的传递函数依赖 3NF - BCNF: 消除主属性对码的部分函数依赖和传递函数依赖 BCNF - 4NF: 消除非平凡且非函数依赖的多值依赖结题技巧一般都满足 1NF除非有类似工资基本工资加班工资实发工资这种可在细分的属性 23第 1 章计算机系统知识通过函数依赖集找到 “码”以及主属性与非主属性能被推导出的属性都不是主属性或者码判断非主属性是否对码有部分函数依赖即非主属性是否能通过码的一部分就推导出来如果是码中的成员非主属性 A - 非主属性 B 这种则不算部分函数依赖符合则至少是 2NF 看有没有传递函数依赖类似 A-B, B-C; 或者是伪传递时的某些情况 A-B, BC-D 那么可以有 AC-D符合则至少是 3NF, 查看主属性对候选码是否有部分函数依赖或者传递依赖 , 符合则至少是 BCNF 看有没有多值依赖并且多值依赖的左边是码例如 A-B,A-C, 并且 A 是码那就符合第四范式 • 判断是否为无损连接直接把分解后的关系通过“自然链接”链接看看得到的结果是否与原来一致不一致则是有损 • 判断是否为“保持函数依赖” 就看分解后的两个关系中是有原来函数依赖集的那些依赖关系如果没有就是不保持 • 数据库设计步骤用户需求分析 – 数据流图概念设计 – E-R 图逻辑设计 – 关系模式 24第 1 章计算机系统知识 • E-R 模型实体矩形表示弱实体双边矩形表示一个实体的存在必须依赖另外一个实体为前提这类实体就是弱实体联系菱形表示无向边上标明联系的类型 1:n n:1 n:m 弱实体的联系为双边菱形属性椭圆形表示简单属性不可再分的属性复合属性可以细分为更小的部分多值属性双边椭圆表示多值属性就是一个属性可以对应一组值派生属性虚线椭圆表示可以通过其他属性计算得来的属性 • E-R 图之间的冲突类型属性冲突属性的类型、取值范围、数据单位冲突命名冲突相同意义属性在不同 E-R 图中有不同命名结构冲突同一个对象在某个 E-R 图中抽象为实体在另一个 E-R 图中抽象为属性或者同一实体在不同 E-R 中有不同属性 • 关系模型转换 1:1 关系转换为关系模式把联系对应的属性放到任意一个实体中同时将另外的实体的主键也放到这个实体中 1:n 关系转换为关系模式把联系对应的属性放到 n 对应的实体中同时将另外的实体的主键也放到这个实体中 n:n 关系转换为关系模式把联系单独作为一个新的关系 , 其他实体的主键组合为这个新关系的主键关系模式规范化的要求至少满足 3NF 25第 1 章计算机系统知识 • 事务管理的特性原子性事务是原子的要么都做要么都不做一致性事务执行的结果必须保证从一个一致性状态变到另一个一致性状态隔离性事务间互相隔离多个事务并发时任意事务的变更操作知道其成功提交的整个过程对其他事务都是不可见的持久性一旦事务成功提交即使数据库崩溃其对数据库的更新操作也永久有效 • 数据库备份方法静态转储与动态转储动态指在转储期间允许对数据库的存取修改操作静态则不允许海量存储与增量存储增量是指仅转储距离上次转储更新的数据日志文件把对数据库的每次操作写入日志文件一旦发生故障则利用日志文件撤销事务回退到事务前的数据状态 • 封锁排它锁就是加了这个锁那么其他的排它锁和共享锁都不能加了直到这个锁被释放了才可以加其他的排它锁和共享锁共享锁就是加了这个锁那么不能加排它锁但是可以加共享锁直到这个锁被释放了才可以加排它锁 • 分布式数据库分片透明指不需要知道表具体是如何分块存储的复制透明采用复制技术的分布式方法时用户不需要知道复制到了那些节点和如何复制的位置透明无需知道数据存放的物理位置 26第 1 章计算机系统知识逻辑透明无需知道局部使用的时那种数据模型共享性数据存储在不同的节点数据共享自治性每个节点对本地数据独立管理可用性某一个场地故障系统可以使用其他场地的副本而不至于整个系统瘫痪分布性数据在不同场地存储 • 存储过程存储过程是在大型数据库系统中一组为完成特定功能的 SQL语句集通过提供存储过程让第三方调用将需要更新的数据传入存储过程从而避免了向第三方提供系统的表结构保证了系统的数据安全 27第 1 章计算机系统知识第 5章面向对象基础 • 面向对象基本概念如何识别是面向对象对象分类继承通过消息的通信类定义了一组大体上相似的对象是一组对象的抽象类分为三种实体类表示显示世界中的真实实体如人物等接口类边界类为用户提供一种与系统合作交互的方式例如二维码、条形码等控制类用来控制活动流充当协调者对象是基本的运行时实体一个对象中既有属性又有行为作用于数据的操作一个对象通常可由对象名、属性、方法组成消息是对象之间通信的一种构造重载是在同一个位置上一系列方法名相同但是形参类型或者个数不同的方法封装是一种信息隐蔽技术目的是使对象的使用者和生产者分离使对象的定义和实现分开继承是父类和子类之间共享数据和方法的机制一个父类可以有多个子类这些子类都是父类的特例父类描述了子类的公共属性和方法一个子类有一个父类叫单重继承一个子类有多个父类叫多重继承多重继承可能导致子类中存在二义性的成员覆盖一个继承关系中子类以更具体的方式实现从父类继承的方法称为覆盖或者重写多态收到消息是对象要予以响应不同的对象收到同一个消息可以产生完全不同的结果这个现象称为多态多态的实现受继承支持利用继承的层次关系将具有通用功能的消 28第 1 章计算机系统知识息放在高层次将不同的实现放在低层次这些低层次生成的对象能够给消息不同的响应多态的四类形式通用多态参数多态应用最广泛、包含多态常见的例子子类型化特定多态过载多态同一个名字在不同的上下文所代表含义不同、强制多态 • 静态绑定和动态绑定绑定就是一个方法的调用与调用这个方法的类连接在一起的过程静态绑定就是在程序运行前编译阶段就能够确定方法由谁调用动态绑定在运行时根据具体的对象类型进行绑定动态绑定支持继承和多态 • 面向对象设计原则单一职责原则一个类仅有一个引起他变化的原因一个类只做一种类型责任开放 - 封闭原则软件实体应该是可扩展的开放但是不可修改封闭里式替换原则子类必须要能够完全替代父类依赖倒置原则抽象不应该依赖于细节细节应该依赖于抽象高层模块不应依赖于低层模块二者都应该依赖于抽象接口分离原则接口属于客户不属于它所在的类层次结构抽象级别不应有对细节的依赖共同封闭原则一个变化如果对一个包产生影响则将对该包中的所有类产生影响而对于其他包不产生影响共同重用原则如果重用包中的一个类那么就要重用包中的所有类 29第 1 章计算机系统知识 • 面向对象分析面向对象分析的目的为了获得对应用问题的理解面向对象分析的五个活动认定对象 – 组织对象 – 描述对象间的相互作用 – 确定对象的操作 – 定义对象的内部信息认定对象用来定义问题域以自然存在的名词作为一个对象定义领域模型是面向对象分析的关键步骤之一它按照对象分类的角度来创建对象领域的描述包括定义概念、属性和重要的关联其结果用类图来组织 • 面向对象设计基于面向对象分析的结果将分析结果转化为设计模型定义系统构造蓝图面向对象设计获得对应问题的解决方案实现系统关注技术及实现层面的细节面向对象设计的五个活动识别类及对象 – 定义属性 – 定义服务 – 识别关系 – 识别包 • 面向对象程序设计实质是选用一种面向对象语言采用对象、类等相关概念所进行的程序设计 • 面向对象测试面向对象测试的四个层次算法层 – 类层 – 模板层 – 系统层 30第 1 章计算机系统知识第 6章 UML • UML 概念 UML 词汇表包含三种构造块事务对模型中最具代表性的成分抽象、关系把事务结合在一起、图聚集相关的事务 • UML 事务结构事务模型的静态部分名词描述概念或物理元素包括类、接口、用例、构件等行为事务模型的动态部分动词描述跨越时间空间的行为包括交互、状态机、活动等分组事务模型的组织部分最主要的分组事务是包结构事务、行为事务或者其他分组事务都可以放在包里注释事务模型的解释部分用来描述、说明、标注注解是最主要的注释事务 • UML 关系依赖关系是两个事务之间的语义关系一个事务独立事务发生变化会影响另一个事务依赖事务的语义 - 图形上通过虚线箭头实现 - A( 依赖事务 ) ······· B( 独立事务 ) A 依赖于 B B 事务的变化会引起 A 事务的语义变化关联关系是一种结构关系描述了一组链链是对象之间的链接通常分为聚合关系和组合关系描述了整体和部分之间的关联 - 单向关联实线箭头 A() —————— B() 它使得一个类知道另一个类的属性和方法 A 类依赖于 B 对象并把 B 作 31第 1 章计算机系统知识为 A 的一个成员变量则 A B 存在关联关系关联可以是单向的也可以是双向的双向关联不用箭头 - 双向关联实线 A —————— B 关联多重度位于实线的上方表示一个 A 类实例可以关联多少个 B 类实例一个 B 类实例又可以关联多少个 A 类实例通常多重度可以用 1 * 1 1…* 等表示 , 多对多的双向关联一般可以将关联关系提取出一个“关联类” - 聚合关系 : 实线空菱形 A( 部分 ) —————— B( 整体 ) 整体的生命周期与部分不同步整体消失部分依然可以存在 - 组合关系实线实心菱形 A( 部分 ) ——————( 实心菱形不好画用代替 ) B( 整体 ) 整体生命周期与部分同步整体消失部分也消失泛化关系是一种 “特殊” 和 “一般” 之间的关系特殊元素子的对象可以替代一般元素父的对象子元素共享了父元素的结构和行为 - 图形上通过实线空心三角箭头 - A( 特殊、子 ) ———————| B( 一般、父 ) 实现关系是类元之间的语义关系其中一个类元指定了由另一个类元保证执行的契约 - 通常的使用情况: 1. 接口和实现他们的类或构件之间 2. 用例和实现他们的协作之间 - 图形上通过虚线空心三角箭头 - A( 类 ) ········| B( 接口 ) • 类图静态类图展现了一组对象、接口、协作和他们之间的关系类图中可以包含注解和约束也可以有包或子系统类图对静态设计视图建模的三种方式 32第 1 章计算机系统知识对系统词汇建模对简单的协作建模对逻辑数据库模式建模类图中类的组成第一层类名第二层属性名 ( 属性名 1: 属性的类型 ) 第三层方法名方法名 1(): 方法返回值类型其中属性名和方法名前可以有修饰符 public 公有的 - private 私有的 # protected 受保护的 • 对象图静态对象图展现了某一时刻一组对象及他们之间的关系对象图中对象与类图中类的区别对象分为两层第一层是对象名 ( 对象名 : 类名 ) 第二层属性 • 用例图静态用例图展现了一组用例、参与者、以及他们之间的关系参与者参与者是与系统交互的外部实体可以是使用者或者参与系统交互的外部系统基础设备等用例是从用户角度描述的系统行为用例是一个类代表了一类功能而不是该功能的某一个具体实现包含关系用例与用例之间的关系图形上使用虚线箭头《 include 》表示 A 基本用例 ··· 《 include》 ··· B 被包含用例 , 箭头指向被包含的用例 A 用例包含 B 用例则 A 执行用例 B 一定也会被执行扩展关系用例与用例之间的关系图形上使用虚线箭头《 extend 》表示 A 扩展用例 ··· 《 extend 》 ··· B 被扩展用例 , 箭头指向被扩展的 33第 1 章计算机系统知识用例被扩展后的用例 B 在执行时可能会遇到特殊的情况或者可选的情况这个时候就可以用扩展用例包含关系与扩展关系区分区分包含关系使用某个用例必然会使用另外一个用例区分扩展关系当执行某个用例不一定要去执行另外一个用例 • 序列图动态序列图描述了以时间顺序组织的对象之间的交互活动序列图是对一个用例进行详细过程的分解图形上参与交互的对象放在图的上方沿水平方向排列发起交互的对象放左边然后把对象间发送和接收的消息按照时间顺序由上到下排列对象生命线由对象起始的一条垂直向下的虚线表示对象在一段时间内存在控制焦点对象生命线之上的一段瘦高的矩形表示对象执行一个动作所经历的时间段调用消息用实线箭头表示返回消息用虚线箭头表示调用消息所要执行此消息方法的是箭头指向的对象 • 通信图动态通信图也成协作图强调收发消息对象的结构组织通信图与序列图的不同在于通信图有路径、通信图有顺序号延同一个链可以展示许多消息每个消息都有唯一的顺序号通信图与顺序图是同构的可以相互转换通信图展现了对象间的消息流及其顺序 34第 1 章计算机系统知识 • 状态图动态状态图展现了一个状态机它由状态、转换、事件和活动组成状态图对系统的动态方面建模当对系统、类或用例的动态方面建模时。通常是对反应型对象建模状态任何可以被观察到的系统行为模式一个状态代表系统的一种行为模式状态分为初态实心圆终态实心圆外再加一层圆和中间状态状态图中的状态是一个圆角矩形第一层是状态名中间一层时状态变量可以没有最后一层为活动表也可以没有状态之间用带箭头的线表示 “转换迁移” 箭头线上的事件发生时转换开始一个状态图只能有一个初态可以有多个终态或者没有终态活动由 “事件名 / 动作表达式” 组成位于状态的活动表中 , 有如下三种标准事件 entry: 入口动作进入状态立即执行 do: 内部活动占用有限时间可以中断工作 exit:出口动作退出状态立即执行事件某个特定时刻发生的时间它是对引起系统做动作和一个状态转换成另一个状态的事件的抽象转换由 “事件监护条件 / 动作” 组成转换包括两个状态事件触发转换活动动作可以在状态内执行也可以在状态转换时执行监护条件是一个 boolean 表达式 “事件”发生且“监护条件为真”状态转换才发生状态转换开始后才会执行“动作” 组合状态一组状态转换作用矩形包围作为另一个状态图中的一个 35第 1 章计算机系统知识状态存在组合状态中的所有子状态完成才会走组合状态外的其他状态 • 活动图动态活动图展现了系统从一个活动到另外一个活动的流程对系统的功能建模很重要强调了对象间的控制流程活动图有起始、终止、圆角矩形组成的活动、实线箭头组成的流、并发分叉、并发汇合、分支、分支上的监护表达式组成用活动图来对工作流建模、对操作建模并发分叉后直接相连的活动可同时执行 • 构件图静态构件图也称为组件图展现了一组构件之间的组织和依赖与类图相关通常把构件映射为一个或多个类、接口或者协作构件图有特殊的标记构件图之间通过供接口空心圆和需接口圆弧对接供接口提供相应的方法实现需接口来调用这个方法 • 部署图部署图用来对系统物理层面建模部署图立体图形《 artifact 》表示制品部署图展现了系统软件和硬件间关系在实施阶段使用部署组件之间的关系类似包依赖 • 总结静态建模类图、对象图、用例图动态建模序列图、通信图、状态图、活动图物理建模构件图、部署图 36第 1 章计算机系统知识交互图序列图顺序图、时序图、通信图协作图 37第 1 章计算机系统知识第 7章设计模式 • 创造型设计模式概念创造型设计模式抽象了实例化过程帮助一个系统如何创建、组合、和表示那些对象 • 简单工厂模式定义一个工厂类可以根据传入的参数的不同返回不同类的实例这些“不同类”继承自同一个父类工厂类中创建实例的方法通常是一个静态方法因此又称为静态工厂使用者无需知道产品对象是如何创建的 • 工厂方法模式 Factory Method 在简单工厂基础上定义一个用于创建对象的工厂接口让实现这个接口的子类来决定实例化哪个类工厂方法模式使一个类的实例化延迟到了子类适用性当一个类不知道它所必须创建的对象的类的时候当一个类希望由他的子类来指定它所创建的对象的时候 • 抽象工厂模式 (Abstract Factory) 意图提供一个创建一系列相关或相互依赖对象的接口而无需指定他们具体的类可以理解为“工厂方法” 创建的是一中对象“抽象工厂” 创建的是一系列对象适用性抽工独立组合多个产品联合显示接口不实现 38第 1 章计算机系统知识一个系统要独立于它的产品创建、组合和表示时一个系统要由多个产品系列中的一个来配置时当要强调一系列相关产品对象的设计以便进行联合使用时当提供一个产品类库只想显示他们的接口而不是实现时 • 生成器模式 (Builder) 意图将一个复杂对象的构建和他的表示分离使得同样的构建过程可以创建不同的表示理解定义一个抽象的生成器再定义多个具体的生成器类封装对象复杂的算法来继承它定义一个管理者对象装配来操作生成器这样管理者与不同的生成器类组合就可以创建不同的产品表示适用性生成复杂算法构造对象不同当创建对象的复杂的算法应该独立于该对象的组成部分和装配方式时当构造过程必须允许被构造对象有不同表示时 • 原型模式 (Prototype) 意图用原型实例指定创建对象的种类通过复制这些原型创建新的对象适用性原型独立构成运行指定不同组合状态当一个系统应该独立于它的产品创建、构成和表示时当要实例化的类是在运行时刻指定的例如动态装载当一个类的实例只能有几个不同状态组合中的一种 • 单例模式 (Singleton) 意图保证一个类仅有一个实例并提供一个访问它的全局访问点适用性单例有一个实例 39第 1 章计算机系统知识当类只能有一个实例且客户从一个众所周知的访问点访问它时 • 结构型设计模式概念涉及如何组合类和对象以获得更大的结构 • 适配器模式 (Adapter) 意图将一个类的接口转换成用户希望的另一个接口使得原本由于接口不兼容不能一起工作的那些类可以一起工作适用性适配接口不符合想使用一个已存在的类但是接口不符合要求 • 桥接模式 (Bridge) 意图将抽象部分与实现部分分离使他们都可以独立的变化理解通过聚合或组合关系将一个有多种组合情况的类拆分成几个相互关联的类这个每个类各自可以独立变化适用性桥接绑定以扩充不影响不编译类层次不希望在抽象和他的实现部分之间有一个固定的绑定关系类的抽象和它的实现都可以通过生成子类的方法加以扩充对抽象的实现部分的修改应该对客户不产生影响不必重新编译有许多类要生成的类层次结构 • 组合模式 (Composite) 意图将对象组合成树型结构以表示部分–整体的层次结构使得用户对单个对象和组合对象的使用具有一致性理解以文件夹与文件间的关系去理解适用性组合部分整体使用组合对象想要表示对象的部分–整体层次结构 40第 1 章计算机系统知识希望用户忽略组合对象与单个对象间的不同统一的使用组合中的所有对象 • 装饰器模式 (Decorator) 意图动态的给一个类添加一些额外的职责适用性装饰添加和撤销职责不能扩充在不影响其他对象的情况下动态透明的方式给单个对象添加职责处理那些可以撤销的职责当不能采用生成子类的方式进行扩充时 • 外观模式 (Facade) 意图为子系统中的一组接口提供一个一致的界面定义一个高层接口使得子系统更加容易使用适用性外观子系统简单接口依赖构建层次结构入口点要为一个复杂的子系统提供一个简单的接口时客户程序与抽象类的实现部分之间存在很大的依赖性当需要构建一个层次结构的子系统时使用外观模式定义子系统每层的入口点 • 享元模式 (Flyweight) 意图运用共享技术有效的支持大量细粒度的对象理解用一个享元工厂来创建并维护实例一种实例只创建一个后续创建都是直接返回已创建的实例适用性享元大量开销外部状态取代多组对象一个应用程序使用了大量的对象由于使用了大量的对象造成了很大的存储开销 41第 1 章计算机系统知识对象的大多数状态都可以变为外部状态如果删除对象的外部状态那么可以用相对较少的共享对象取代很多组对象 • 代理模式 (Proxy) 理解为其他对象提供一种代理以控制对这个对象的访问适用性代理简单的指针在需要比较通用和复杂的对象指针代替简单的指针的时候 • 行为型设计模式概念涉及算法和对象间职责的分配描述了它们之间的通信模式使用继承机制在对象间分配行为 • 责任链模式 (Chain of Responsibility) 意图使多个对象都有机会处理请求从而避免请求的发送者和接收者之间的耦合关系将对象连城一条链沿着链传递请求直到有一个对象处理它为止适用性责任链请求自动确定不明确接收者动态指定有多个对象处理一个请求哪个对象处理该请求在运行时自动确定想在不明确指定接受者的前提下向多个对象中的一个提交请求可处理一个请求的对象集合被应动态指定 • 命令模式 (Command) 意图将一个请求封装成一个对象从而使得可以用不同的请求对客 42第 1 章计算机系统知识户进行参数化对请求排队、记录请求日志、以及支持可撤销的操作适用性命令参数化指定排列取消操作修改抽象出待执行的动作以参数化某对象在不同的时刻指定、排列和执行请求支持取消操作、修改日志 • 解释器模式 (Interpreter) 意图给定一个语言定义它的文法的一种表示并定义一个解释器解释语言中的句子适用性解释抽象语法树当一个语言需要解释执行时可将语言中的句子表现为一个抽象语法树 • 迭代器模式 (Iterator) 意图提供一种方法顺序的访问一个聚合对象中的各个元素且不需要暴露该对象的内部表示适用性迭代聚合无需暴露。多种遍历统一接口访问一个聚合对象的内容而无需暴露它的内部表示支持对聚合对象的多种遍历为遍历不同的聚合结构提供一个统一的接口 • 中介模式 (Mediator) 意图用一个中介对象来封装一系列的对象交互中介者使得各个对象不需要显示的相互引用从而使其耦合松散而且可以独立的改变它们之间的交互适用性中介复杂通信依赖难以理解一组对象定义良好但是以复杂的方式进行通信产生的相互依 43第 1 章计算机系统知识赖关系结构混乱且难以理解 • 备忘录模式 (Memento) 意图在不破坏封装性的前提下捕获一个对象的内部状态并在对象之外保存这样以后就可以将对象恢复到原先保存的状态适用性备忘录某一时刻状态破坏封装性必须保存一个对象在某一时刻的部分状态这样以后在需要时才能恢复之前的状态如果用一个接口来让其他对象直接得到这些状态将会暴露对象的实现细节并破坏对象的封装性 • 观察者模式 (Observer) 意图定义对象间的一对多的依赖关系当一个对象发生改变时所有依赖它的对象都得到通知并自动更新适用性观察者改变其他对象不是耦合的当一个对象的改变需要同时改变其他对象而不知道具体有多少对象待改变时当一个对象必须通知其他对象而它又不能假定其他对象是谁即不希望这些对象是紧耦合的 • 状态模式 (State) 意图允许一个对象再其内部状态改变时改变它的行为对象似乎修改了它的类适用性状态改变行为多分支语句依赖状态一个对象的行为决定于它的状态并且必须在运行时刻根据状态改变它的行为一个操作中含有庞大的多分支条件语句这些分支依赖于该对象 44第 1 章计算机系统知识的状态。 • 策略模式 (Strategy) 意图定义一系列算法把他们一个个封装起来并使得他们可以相互替换此模式使得算法可以独立于使用他们的客户而变化适用性策略多个行为算法变体避免暴露多条件语句许多相关的类仅仅是行为有异策略提供了一种用多个行为中的一个行为来配置一个类的方法需要使用一个算法的不同变体使用算法的客户不应该知道数据结构避免暴露一个类中定义了多种行为这些行为在这个类的操作中以多个条件语句的形式出现将相关的条件分支移入他们各自的策略类中以代替这些条件语句 • 模板方法 (Template Method) 定义一个操作中的算法骨架而将一些步骤延迟到子类中使得一个子类可以不改变一个算法的结构即可重新定义该算法的某些步骤适用性模板可变给子类避免代码重复子类扩展一次性实现一个算法的不变的部分并将可变的行为留给子类实现各子类中的公共行为应被提取出来并集中到一个公共的父类以避免代码重复控制子类扩展模板方法仅允许在特定点进行扩展 • 访问者模式 (Visitor) 意图表示一个作用于某对象结构中的各元素的操作。允许在不改变各元素类的前提下定义作用于这些元素的新操作 45第 1 章计算机系统知识适用性访问者依赖具体类不相关对象的类定义新的操作一个对象结构包含很多类对象他们有不同的接口而用户想对这些对象实施一些依赖于其具体类的操作需要对一个对象结构中的对象进行很多不同的并且不相关的操作而有不想这些操作污染这些对象的类定义对象的类很少改变但经常需要在此结构上定义新的操作 46第 1 章计算机系统知识第 8章信息安全 • 防火墙防火墙建立在内外网络边界上的过滤封锁机制认为内部网络是安全可信赖的外部网络是不安全和不可信任的防火墙对通过受控干线的任何通信进行安全处理例如控制、审计、报警、反应等 DMZ屏蔽子网防火墙位于内网与外网之间通常作为隔离区在这里可以放置一些公用服务器例如 web 服务器、 Email 、 FTP 等包过滤防火墙通过一个包过滤器根据数据的包头中各项信息来控制站点、网络之间的访问性包过滤防火墙对用户完全透明、访问速度快、低水平控制包过滤防火墙处在网络层和数据链路层之间每个 IP 字段都被检查源地址、目的地址、协议、端口缺点不能防黑客攻击、不支持应用层协议、访问控制粒度粗糙、不能处理新的安全威胁应用代理网关防火墙彻底隔绝内外网之间的直接通信内外网之间的互相访问需要经过应用层代理软件转发优点可以检查应用层、传输层、网络层的协议特征对数据包的检测能力较强缺点难以配置、处理速度较慢状态检测技术防火墙结合了包过滤防火墙和应用代理网关防火墙两者的优点即安全性和高速度 • 病毒计算机病毒特性传播性、隐蔽性、感染性、潜伏性、触发性、破坏 47第 1 章计算机系统知识性 Worm: 蠕虫病毒 Trojan: 特洛伊木马 Backdoor: 后门病毒 Macro: 宏病毒宏病毒感染对象文本文档、电子表格木马软件冰河木马感染流程通过软件下载捆绑等方式在用户主机上建立木马病毒的服务器端这个木马病毒的服务器端再与攻击者主机上的木马病毒客户端建立网络连接这样攻击者就可以借由此来盗取或者破坏用户主机数据蠕虫病毒欢乐时光、熊猫烧香、红色代码、爱虫病毒、震网 • 网络攻击拒绝服务攻击 (Dos 攻击 ) 通过不断向计算机发起请求让目标服务器没有资源去接收其他正常的请求从而达到“使计算机或者网络无法提供正常服务”的目的重放攻击攻击者发送一个目标主机已经接收过的报文来达到攻击目的主要用于身份认证过程、破坏认证正确性 ; 可通过在报文中增加时间戳来防范口令入侵攻击使用某些合法的用户账号和口令登录到目的主机然后实施攻击活动特洛伊木马用户下载了含有木马的软件后这个木马程序就会向黑客发起连接请求建立连接后黑客就可以实施攻击端口欺骗攻击采用端口扫描找到系统漏洞从而实施攻击网络监听攻击者可接口某一网段在统一物理通道上传输的所有信息截取账号和口令 IP 欺骗攻击伪造源 IP 地址冒充其他系统或发件人身份 SQL注入攻击通过注入某些 SQL查询代码获得数据库权限从而窃取及修改信息入侵检测技术专家系统、模型检测、简单匹配 48第 1 章计算机系统知识 • 网路安全 SSL( 安全套接层 ): 传输层安全协议端口号 443 TLS( 传输层安全协议 ) 也是传输层安全协议是 SSL 3.0 的后续版本 SSH: 用于终端设备与远程站点之间建立连接的安全协议建立在应用层和传输层基础上的按全协议 HTTPS: 使用 SSL 加密的 http MIME: 电子邮件扩展相关协议不具有安全性 PGP: 通过 RSA 非对称加密的邮件协议 IPSec: 对 IP 数据报文进行加密 ARP: 地址解析成物理地址协议 Telnet: 不安全的远程登录协议 WEP: 有限等效保密协议 TFTP: 简单文件传输协议 PP2P: 链路加密 RFB远程登录图形化用户界面协议 IGMP: 因特网组管理协议信息安全的五个基本要素机密性、完整性、可用性、可控性、审可查性 49第 1 章计算机系统知识第 9章计算机网络 • 网络设备物理层的互连设备中继器 (Repeater)和集线器 (Hub), 其中集线器可以看做是一种多端口的中继器数据链路层互连设备网桥 Bridge 和交换机 Switch , 其中交换机是多端口的网桥网络层互连设备路由器应用层互连设备网关物理层设备不能隔离广播域和冲突域数据链路层设备可以隔离冲突域不能隔离广播域网络层可以隔离广播域与冲突域 • TCP/IP 协议簇分类网络层协议 IP 一种尽力传送的通信协议传送的数据可能丢失 ICMP: Internet 控制信息协议利用 IP 传送报文传输层协议TCP UDP都是基于 IP 之上的应用层协议 FTP: 文件上传协议文件上传的端口是 20 控制端口为 21 SNMP 网络管理协议方便记忆 1. 名字带 IP “AP” 的都是网络层2. 应用层协议所有带 T 的除了 TFTP 都是基于 TCP的其他是基于 UDP的不带 “ T” 的只有 POP3 是 TCP 的其他都是 UDP 的 50第 1 章计算机系统知识 • 网络层协议 IP TCP UDP IP 提供的服务是无连接指没有确定目标系统在已做好接收准备前就发送数据、不可靠的目的系统不对成功接收的分组进行确认 TCP 面向连接、可靠的传输控制协议采用三次握手实现可靠性可靠传输、连接管理、差错校验、重传、流量控制可变大小滑动窗口协议、端口寻址、 UDP 无连接、不可靠的传输协议可以保证应用程序进程间的通信有助于提高传输的高效率端口寻址 • 电子邮件服务协议 SMTP: 简单邮件传输协议用来发送邮件端口 25 基于 TCP只能传输文本和 ASCII码的文件 SMTP 基于 C/S 模式即客户端 / 服务器模式来进行通信 MIME 邮件附件扩展类型 PEM 私密邮件 POP3 用来接收邮件的协议基于 TCP 端口号 110 基于 C/S 模式通信 • 地址解析 ARP RARP ARP: 地址解析协议将 IP 地址转换为物理地址 MAC 地址每个网卡唯一 RARP 反地址解析协议将物理地址转换为 IP 地址计算机间使用 ARP 通信流程 PC1向 PC2通信查询 ARP 高速缓存如果有 PC2的 IP 地址缓存则直接使用其对应的物理地址发送 51第 1 章计算机系统知识数据如果没有缓存则在局域网以广播形式发送 ARP 请求包如果局域网上某个计算机 IP 地址一致则那台计算会响应一个 ARP 应答包含对应的物理地址 ARP 将 IP 及应答的物理地址存到高速缓存中 • DHCP 动态主机配置协议集中管理分配 IP 地址使网络中的主机获得 IP 地址、网关地址、 DNS地址、 DHCP 服务器地址等 • URL 协议名 ://主机名 . 域名 . 域名后缀 . 域名分类 / 目录 / 网页文件 • DNS 域名查询次序本地 hosts 文件》本地 DNS 缓存》本地 DNS服务器》根域名服务器 • 主域名服务器在接收到请求后的查询次序本地缓存》本地 hosts 文件》本地数据库》转发域名服务器 • IP 地址和子网划分 Internet 中网络分为 5 类 A 、 B 、 C 、 D 、 E A 类网络网络地址 8 位第一位为 0 其余为主机地址 B 类网络网络地址 16 为前两位为 10 其余为主机地址 C 类网络网络地址 24 为前两位为 110其余为主机地址 52第 1 章计算机系统知识子网掩码识别报文是只存放在网络内部还是被路由转发到其他地方用 1 表示网络地址 0 表示主机地址例如 C 类掩码为 11111111.11111111.11111111.00000000 即 255.255.255.0 子网划分将一个网络划分成多个子网取部分主机号当子网号取了多少位 k 就有 2^k 个子网将多个网络合并成一个大网络去部分网络号主机号 222.125.80.128/26 中 /26 表示由 26 位的网络地址有 32-26 位的主机地址全 1 是广播地址全 0 是网络地址 • IPv6 IPv4 为 32 位 IPv6 128 位地址空间不可用完 • 无线网路无限网络中蓝牙覆盖范围最小通信距离最短 • Windows 命令 ipconfig: 显示所有网络适配器的 IP 地址、子网掩码和缺省网关值 ipconfig/release: 释放 IP 地址 ipconfig/flushdns: 清除 dns 缓存或刷新 dns ipconfig/displaydns: 显示 dns ipconfig/registerdns: DNS 客户端手工向服务器注册 ipconfig/all: 显示所有所有网络适配器的完整 TCP/IP 配置信息包括 DHCP 服务是否启动 ipconfig/renew: DHCP 客户端刷新重新申请 IP 53第 1 章计算机系统知识 • 路由五种路由类型主机路由子网掩码 255.255.255.255 直连网络远程网络默认路由目标网络和网络掩码都是 0.0.0.0 持久路由服务器接收到一个 IP 数据包时先查找主机路由在查找网络路由直连网络、远程网络、最后查找默认路由如果路由器收到关于某个目标的多条路由那么要比较各个路由的管理距离并采用管理距离最小的 • 其他网络的可用性用户可利用网络时间的百分比园区子系统链接各个建筑物的通信系统 DNS 实现负载均衡为同一个域名设置多个主机记录启用循环添加每个 web 服务器的主机记录要使得两个 IPv6 通过现有的 IPv4 网路通信需要使用“隧道技术” 要使得 IPv6 与 IPv4 通信需要使用 “翻译技术” DNS 服务器与计算机不在一个子网不会导致计算机网络不可访问只要路由可达 DNS都可以正常工作层次化局域网模型核心层的主要功能将分组从一个区域高速的转发到另一个区域默认网关要和当前 IP 地址在同一个子网段中 54第 1 章计算机系统知识第 10章操作系统 • 操作系统地位计算机系统由软件、硬件组成没有配置软件的称为裸机操作系统地位计算机硬件》操作系统》系统软件》应用软件》用户所有其他软件如编译程序、汇编程序、数据库管理系统等以及大量应用软件都是建立在操作系统之上的把操作系统看做用户与计算机之间的接口 • 进程管理进程是源分配和独立运行的基本单位进程管理重点是要研究诸进程之间的并发特性以及进程间相互合作与资源竞争产生的问题 • 前趋图有向无循环图由节点和单向边组成节点代表各个程序段的操作单向边表示前前趋关系 Pi(节点、前趋 ) -—— Pj(节点、后继 ) Pi 执行结束 Pj 才能执行前趋图有 n 个箭头就要设置 n 个信号量按照从小到大顺序写到图中箭头方向是 P 操作箭头尾部是 V 操作程序顺序执行的主要特征顺序性、封闭性独享资源、可再现性程序并发执行的主要特征失去程序封闭性、程序和机器执行程序的活动不再一一对应、并发程序之间的相互制约性 55第 1 章计算机系统知识 • 进程的三态模型在多道程序系统中进程在处理器上交替运行一般由三种状态运行就绪、阻塞运行当一个进程在处理机 CPU上运行时就是运行态就绪一个进程获得了除了处理机 CPU外的所有资源 , 一旦得到处理机即可运行这个时候就是就绪态阻塞等待、睡眠一个进程正在等待某个事件例如等待 I/O 完成发生而停止运行 • 同步与互斥同步是合作资源进程之间直接制约的问题互斥是申请临界资源进程间的间接制约问题 • 临界区管理原则有空即进临界区无进程则允许进入且只能在临界区运行有限时间无空则等临界区有进程其他进程则要等待有限等待在外等待的进程要保证在有限时间可进入让权等待进程有 CPU 没有资源时不能进入自己的临界区要立即释放 CPU 资源避免忙等 • 信号量机制信号量 S 的物理意义 S0 表示资源的可用数 S0 表示等待该资源的进程数 56第 1 章计算机系统知识 • PV 操作是实现同步和互斥的常用方法 P 表示申请一个资源 S S-1可以理解为从信号量 S 中申请出一个来使用申请后 S0 则进程转为阻塞态插入阻塞队列 V 表示释放一个资源 S S1可以理解为释放一个资源到信号量释放后 S0 则从阻塞队列唤起一个进程插入就绪队列 • PV 操作实现进程互斥令信号量 mutex 初值为 1 当进入临界区时执行 P 操作退出临界区时执行 V 操作这两就利用 PV 实现代码互斥 • PV 操作实现进程的同步单缓冲区同步 ( 缓冲区只能放一个产品 ) 分为生产者和消费者需要设置两个信号量 , S1 初值为 1 表示可放入缓冲区的产品数 S2 初值为 0 表示可从缓冲区取出的产品数每次生产产品要进行 P(S1) 和 V(S2), 每次消费产品要进行 P(S2) V(S1) 多缓冲区同步 ( 缓冲区可以放多个产品 ) 在单缓冲区的基础上增加一个信号量 S, 名为互斥信号量初始值为 1 标记缓冲区可操作的量缓冲区是个互斥资源每次生产产品及消费产品是都要增加一个 P(S1) P(S) V(S) V(S2) 操作 , S 的 PV 操作放中间 • 死锁同类资源分配不当引起的死锁若采用的资源分配策略是轮流的为每个进程分配则可能会导致分配几轮后没有一个进程达到所需的资源数这个时候每个进程都在等待资源分配形成死锁同类资源分配不当引起的死锁的解法 m 为资源总量、 n 为进程数、 k 为每个进程需要的资源满足 m n * (k-1) 1 就可以避免死锁 57第 1 章计算机系统知识 • 进程资源图 Pi 代表进程 Ri 代表资源类型每个 Ri 可以有多个资源指向进程的箭头表示分配资源指向资源的箭头表示申请资源先分配资源再申请资源经过分配申请后没有满足资源的进程即为 “阻塞” 是否可化简取决于是否可以在某个进程完成后释放资源并使得后续进程得以完成可化简的就是非死锁的 • 死锁避免死锁处理策略鸵鸟策略不理睬、预防策略、避免策略、检测与解除死锁死锁避免算法银行家算法即在每次分配资源前检测分配资源后系统是否安全是否安全取决与分配资源后系统是否可以有某种进行序列来将所有的进程都执行完资源利用率高但增加了检测的开销银行家算法题计算 1. 先算出仍需资源数 2. 在算出剩余资源数 • 线程进程在创建、撤销、切换中系统会付出较大的时空开销故系统引入的进程不易过多进程切换频率不易太高因此引入了线程线程作为调度和分配的基本单位进程作为独立分配资源的单位线程是进程中的一个实体线程与线程之间不可见但是线程与线程可以共享进程的资源 58第 1 章计算机系统知识 • 局部性原理时间局限性程序的某一条指令执行那在不久的将来该指令可能被再次执行如果某个存储单元被访问那不久的将来还可能被再次访问空间局限性程序访问了某个存储单元不久的将来其附近的存储单元也可能被访问 • 相关题型“淘汰”问题在内存中才能被淘汰先淘汰未访问过的再淘汰未修改过的 • 分页存储管理纯分页存储管理的地址结构 n 位的页号 m位的页内地址计算机的页面大小为 4k 则代表 n 位页内地址 2^n 4 * 1024 n12 页面变换表逻辑地址转物理地址逻辑地址即为纯分页存储管理的地址结构由 n 位的页号 m位的页内地址组成页内地址组成不变将页号替换成“页面变换表”中对应的物理块号即可 • 段页式存储管理段页式存储管理地址结构 n 位段号 k位段内页号 m位的页内地址 • 单缓冲区缓冲区只能有一个“作业”缓冲区为空时可以输入缓冲区有作业 59第 1 章计算机系统知识时可以传送 I/O设备 —输入 (T)— 缓冲区 —传送 (M)— 工作区 ( 处理 C) 计算 n 个作业单缓冲区所花时间 (TM)*n C • 双缓冲区缓冲区有两个每个可存一个”作业“ 计算 n 个作业双缓冲区所花时间 T*n M C • 磁盘调度算法先来先服务 FCFS : 按请求访问者的先后顺序来启动磁盘驱动器平均寻道长度大最短寻道时间优先 SSTF : 让距离当前磁道位置最短的先执行不考虑访问者的先后顺序扫描算法或者电梯调度算法 SCAN : 从磁头当前位置开始沿着磁头移动方向选择最近的柱面如果磁头移动方向无请求柱面则调转方向选择最近的循环扫描算法CSCAN : 在扫描算法的基础上调转方向后不再选择最近的柱面而是移动到最里端 • 旋转调度算法磁盘旋转不会停下磁盘旋转完一个扇区就代表读取了一个扇区的记录记录读取后的处理时间内磁盘不会停下如果是顺序处理 n 总时间 (读时间扇区一圈时间 )*(n-1) 第一个扇区的读时间第一个扇区的处理时间优化处理重排扇区让第一个扇区处理后所停在的位置在第二个记录所在扇区的起始位置所耗时 (读时间处理时间 )*n 60第 1 章计算机系统知识 • 多级索引结构直接地址索引索引从 0 开始一个地址项指向一个磁盘数据块一级间接地址索引一个地址项指向一个磁盘索引块也可以叫一级索引块一个磁盘索引块又包含很多个地址项磁盘索引块中的地址项指向一个磁盘数据块二级间接地址索引比一级间接地址索引多了一级磁盘索引块 • 文件目录为了实现按名存取系统为每个文件设置用于描述和控制的数据结构至少包含文件名和存放文件的物理地址这个结构称为文件数据块 FCB 文件目录是由文件控制块组成的用来文件检索文件控制块包含三类信息基本信息文件名、文件物理地址、文件长度、文件块数等存取控制信息文件存取权限使用信息建立日期、最后修改日期、当前使用信息目录文件的修改时发生崩溃对系统的影响很大 • 目录结构多级目录结构倒置的有根树也称为树形目录结构全路径名从根目录开始一直到文件名 D:\ 绝对路径从根目录开始最后是 / 相对路径从当前目录开始最后是 / • 位视图位视图用二进制来表示一个物理块的使用情况 0 表示空闲 1 表示使用 61第 1 章计算机系统知识位视图的大小由磁盘空间大小物理块数决定位视图描述能力强适合各种物理结构假设计算机系统 n 位那位视图第 0 个字能对应存储器上的第 0~n-1 号物理块第 1 个字能对应存储器上的第 n~2n-1 号物理块后边以此类推 • 其他可变式分区分配方案进程 P 有上邻空闲区或有下邻空闲区那么 P 进程释放后空闲区合并成一个当用户通过鼠标或键盘进入某应用系统时中断处理程序最先获得键盘或鼠标的输入信息实时操作系统的实时是指计算机对于外来信息能够以足够快的速度处理并在被控制对象允许的时间范围内做出快速响应 I/O 系统的层次结构硬件 - 》中断处理程序 - 》设备驱动程序 - 》设备无关程序 - 》用户进程 I/O 软件隐藏了 I/O操作的实现细节方便用户使用磁盘调度管理中先进行移臂调度在进行旋转访问不同柱面信息时要先移臂调度访问同一磁道只需要进行旋转 62第 1 章计算机系统知识第 11章结构化开发 • 模块化模块化是指将一个待开发的软件分解成若干个小的简单部分–模块每个模块独立开发测试 • 模块独立模块独立是指每个模块完成一个相对独立的特定子功能并且与其他模块间的联系简单衡量模块独立的标准有两个内聚性、耦合性 • 耦合耦合是模块之间相对独立性互相连接的紧密程度的度量耦合程度越高模块独立性越弱耦合的七种类型由低到高排序无直接耦合两个模块之间没有直接关系没有调用、不传递任何信息数据耦合两个模块间有调用关系传递简单的数据值值传递标记耦合有调用关系传递的是数据结构控制耦合有调用关心传递的是控制变量控制变量可以让被调用方有选择的执行某一功能外部耦合模块间通过软件之外的环境联结公共耦合通过公共数据环境相互作用的那些模块间的耦合内容耦合一个模块直接使用另一个模块的内部数据或通过非正常入口传入另一模块内部时 63第 1 章计算机系统知识 • 内聚内聚是对一个模块内部各个元素之间彼此结合紧密程度的度量内聚程度越高模块独立性越强内聚的其中类型由低到高排序偶然内聚巧合内聚模块内各元素间没有任何联系逻辑内聚指模块内执行若干个结逻辑相似的功能通过参数来确定要执行哪一个时间内聚特定时间需要同时执行的动作组合在一起形成的模块、过程内聚一个模块完成多个任务这些任务必须按照指定过程执行通信内聚模块内的处理元素都在同一个数据结构上操作顺序内聚单一功能模块内各个处理元素密切相关且需要顺序执行功能内聚模块内所有元素共同完成同一功能缺一不可 • 系统结构设计原则分解 - 协调原则大问题分解成小问题自顶向下原则抓住系统的主功能由上到下分层分解信息隐蔽 - 抽象原则上层规定下层做什么和模块间协调但不规定怎么做一致性原则统一规范、统一标准、统一的文件模式明确性原则每个模块功能明确、接口明确消除多重功能、无用接口避免病态链接、消除接口复杂度高内聚低耦合扇入扇出适中模块调用其他模块称为扇出被其他模块调用称为扇如模块规模适中过大则是分解的不充分过小则可能降低模块独立性 64第 1 章计算机系统知识模块的作用范围应该再其控制范围之内 • 系统文档系统文档是系统建设过程的”痕迹“是系统维护人员的指南是开发人员与用户的交流工具系统文档在系统开发人员、项目管理人员、系统维护人员、系统评价人员、用户之间的作用用户–系统分析人员可行性研究报告、总体规划报告、系统开发合同、系统方案说明书系统开发人员–项目管理人员系统开发计划、系统开发月报、系统开发总结报告、项目管理文件系统测试人员–系统开发人员系统方案说明书、系统开发合同、系统设计说明书、测试计划文档系统开发人员–用户用户手册、操作指南系统开发人员–系统维护人员系统设计说明书、系统开发总结报告、技术手册用户–维修人员系统运行报告、维护修改建议 • 数据流图基本图形元素外部实体矩形一般用 Ei 表示数据存储两条横线或者缺边矩形一般用 Di 表示数据流有向边起点 ———— 终点加工圆角矩形或圆一般用 Pi 表示顶层数据流图描述了系统的输入输出 0 层数据流图是对顶层数据流图的细分外部实体当前系统之外的人、物、外部系统人学生、老师、员工、主管 65第 1 章计算机系统知识物 : 传感器、控制器、车辆、采购部门外部系统支付系统、车辆交易系统、库存管理系统数据存储存储数据、提供数据存储加工后的输出数据提供加工的输入数据例如 xxx表、 xxx文件加工 : 将输入数据处理后得到输出数据一个加工至少有一个输入数据流和一个输出数据里只有输入没有输出称为”黑洞“ 只有输出没有输入称为”白洞“ 加工的数据不足以产生输出”灰洞“ 数据流数据流的起点或者重点必有一个是加工 • 父图子图平衡父图中的数据流子图中也要有其实就是根据父图去子图里一个个找看看有没有是父图里有的数据流但是子图没有找出丢失数据流的技巧父图子图平衡加工既要有输入数据里、也要有输出数据流数据守恒到题目的内容中去找图中有哪些丢失的部分数据建模 – E-R图行为建模 – UML功能建模 – 数据流图 • 数据字典数据字典为数据流图中的每个数据流、文件、加工以及组成数据流的数据项做出说明数据字典有四类条目数据流、数据存储、基本加工、数据项数据项是组成数据流和数据存储的最小元素外部实体不再字典中说明常用的加工逻辑描述方法结构化语言、判定表、判定树 66第 1 章计算机系统知识 • 结构化开发方法总的指导思想是自顶而下逐层分解从抽象到具体基本原则是功能的分解与抽象软件工程中最早提出的方法特别适合数据处理领域的问题不适合解决大规模的、特别复杂的项目难以适应需求的变化 • 结构化设计体系结构设计定义软件的主要结构元素及关系数据设计确定文件系统结构和数据库表结构接口设计描述软件使用放的外部接口及各种构件间的内部接口过程设计定义各组成部分内的算法及内部数据结构界面设计黄金原则用户操纵控制减少用户记忆负担保持界面一致构造分层数据流图时需要注意的问题适当命名图中要表示出数据流一个加工不适合过多数据流分解尽可能均匀 67第 1 章计算机系统知识第 12章软件工程 • CMM( 能力成熟度模型 ) CMM 将软件过程改进分为以下五个级别初始级杂乱无章没有明确定义的步骤可重复级建立了基本的项目管理过程和实践有必要的过程准则来重复以前在同类项目中的成功已定义级软件过程文档化、标准化已管理级制定了软件过程和产品质量的详细度量标准优化级加强了质量分析通过过程质量反馈、新观念、新技术等不断改进 • CMMI( 能力成熟度集成模型 ) 阶段式模型结构类似 CMM关注组织的成熟度初始的过程不可预测缺乏控制已管理的过程为项目服务已定义的过程为组织服务定量管理的过程已度量和控制优化的集中于过程改进连续式模型关注每个过程域的能力 CL0( 未完成的 ) 表明过程域的一个或多个目标没有被满足 CL1( 已执行的 ) 过程域特定目标完成转化可识别的输入目标产品产生可识别的输出目标产品 CL2( 已管理的 ) 已管理的过程制度化关注针对单个过程实例的能力 CL3( 已定义级 ) 已定义的过程制度化关注过程的组织标准化及部署 68第 1 章计算机系统知识 CL4( 定量管理级 ) 可定量管理的过程制度化 CL5( 优化的 ) 优化的过程制度化持续改进优化 • 瀑布模型瀑布模型是将软件生命周期中各个活动规定为依线性顺序链接的若干阶段模型需求分析》设计》编码》测试》运行与维护由前至后相互衔接的固定次序瀑布模型假设一个待开发的系统需求是完整的简明的一致的而且可以先于设计和实现之前完成以项目的阶段评审和文档控制来对开发过程进行指导优点容易理解管理成本低强调开发早期计划需求调研和产品测试适合开发需求明确的大致固定不会随意变更的系统缺点客户必须要完整的正确的清晰的表达出需求开始的两到三个阶段很难评估进度接近项目结束时出现大量的集成和测试工作项目结束之前都不能演示系统能力需求或者设计中的错误到了项目后期才能发现项目风险控制能力较弱 V 模型是瀑布模型的一个变体重点在于质量保证活动和沟通将基本问题逐步细化实际上执行了一系列测试 • 增量模型融合了瀑布模型的基本成分和原型实现的迭代特征它假设可以将需求分段为一系列的增量每一个增量可以分别开发 69第 1 章计算机系统知识第一个增量往往是核心产品客户对每个增量的使用和评估都作为下一个增量的新特征和功能每个增量均发布一个可操作版本优点具有瀑布模型的所有优点第一个可交付版本所需的成本时间很少开发由增量表示的小系统所承担的风险不大缺点如果没有对用户的变更要求有规划那么产生的初始增量可能造成后续增量的不稳定管理成本、进度、复杂性 • 演化模型演化模型是迭代的过程模型使得软件开发人员能够逐步的开发出更完整的软件版本演化模型特别适合对软件需求缺乏准确认识的情况典型的演化模型有原型模型和螺旋模型演化模型与增量模型区别增量每次开发的时小的功能模块演化每次开发整个产品 • 原型模型原型模型比较适合用户需求不清、需求经常发生变化的情况当系统规模不是很大也不太复杂时采用比较合适一个原型不必满足目标软件的所有约束其目的是能快速、低成本的构建原型迅速的开发出一个看得见摸得着的系统框架步骤交流沟通》快速计划》快速设计方式建模》构建原型》部署交付和反馈 – 完成后继续循环步骤原型始于沟通其目的是为了定义软件的总体有效的捕获用户需求 70第 1 章计算机系统知识原型模式不适合大规模的系统开发 • 螺旋模型螺旋模型将瀑布模型和演化模型相结合加入了两个模型都忽略了的风险分析每个螺旋周期和瀑布模型大致相符合每个螺旋周期分为四个步骤制定计划确定软件目标制定实施方案明确项目开发的限制条件风险分析识别风险、消除风险实施工程软件开发、验证阶段性产品用户评估提出修正建议制定下一周期开发计划螺旋模型的特点是加入了风险分析适合大规模、高风险、需求变化的系统缺点过多的迭代次数会增加开发成本延迟提交时间 • 喷泉模型喷泉模型是一种以用户需求为动力以对象作为驱动的模型适合与面向对象的开发方法喷泉模型克服了瀑布模型不支持软件重用和多项开发活动集成的局限性喷泉模型的开发过程具有迭代性和无间隙性无间隙是指在开发活动分析、设计、编码之间不存在明显边界允许活动交叉、迭代进行优点软件开发效率高节省开发时间缺点开发阶段重叠需要大量开发人员管理成本高 71第 1 章计算机系统知识需要严格的管理文档审核难度大 • 统一过程模型 UP 是一种用例和风险驱动以架构为中心迭代并增量的开发过程每次迭代有 5 个核心工作流统一过程的四个技术阶段及里程碑起始阶段专注于项目初创里程碑生命周期目标精化阶段需求分析和架构演进里程碑生命周期架构构建阶段关注系统的构建产生实现模型里程碑初试运作功能移交阶段关注软件提交方面的工作产生软件增量里程碑产品发布 • 敏捷开发总体目标是尽可能早、持续地对有价值的软件交付敏捷开发使用户能够在开发周期的后期增加或改变需求极限编程 (XP) XP 是一种轻量级敏捷、高效、低风险、柔性、可预测、科学的软件开发方式 XP 的四大价值观沟通、简单性、反馈、勇气 5 个原则快速反馈、简单性假设、逐步修改、提倡更改和优质工作 12 个最佳实践计划游戏、小型发布、隐喻、简单设计、测试先行、重构、结对编程、集体代码所有制、持续集成、每周 40h、现场客户和编码标准水晶法 (Crystal) 每一个不同的项目都需要一套不同的策略、约定和方法论并列征求法 (Scrum)使用迭代的方法每 30 天一个冲刺按需求 72第 1 章计算机系统知识级别来实现产品自适应软件开发(ASD) 6 个基本原则有一个使命作为指导特征被视为客户价值的关键点 ”重做“与”做“同样关键变化不被视为改正而是 ”调整“ 交付时间迫使考虑每一个生产版本的关键需求风险包含敏捷统一过程 AUP : 采用 ”在大型上连续在小型上迭代 “的原理来构建每个 AUP 执行以下活动建模、实现、测试、部署、配置及项目管理、环境管理 • 需求分析软件需求指用户对目标软件在功能、行为、性能、设计约束等方面的期望功能需求 : 考虑系统做什么、何时做性能需求用户或人因素用户理解使用系统难度、错误操作的可能性环境需求硬件或软件环境机型操作系统平台界面需求考虑来自其他系统输入输出数据格式存储介质规定文档需求文档针对那些读者数据需求接收发送数据格式资源使用需求运行所需计算机资源维护所需人力安全保密需求数据隔离系统备份可靠性需求隔离错误出错重启等待软件成本消耗和开发进度其他非功能性需求 73第 1 章计算机系统知识 • 概要设计设计软件系统的总体结构将复杂系统按功能分成模块并确定模块的功能、调用关系、接口、结构和质量数据结构及数据库设计数据库设计概念设计 E-R、逻辑设计、物理设计编写概要设计文档概要设计说明书、数据库设计说明书、用户手册、修订测试计划评审 • 详细设计对每个模块进行详细的算法设计对模块内的数据结构进行设计对数据库进行物理设计其他设计编写详细设计说明书评审 • 系统测试系统测试的意义为了发现错误而执行程序的过程成功的测试就是发现了至今为发现的错误测试的目的以最小的人力和时间发现潜在的各种错误和缺陷测试的基本原则尽早和不断的测试贯穿整个开发阶段避免由原开发人员进行测试测试时要有预期的输出结果与测试结果作比较关心不合理的输入或操作造成的结果不仅要检查程序是否做了该做的事还要检查程序是否做了不该 74第 1 章计算机系统知识做的事严格按照计划测试避免随意性妥善保存测试用例及相关文档后续测试以前次测试的基础上修改系统测试的测试目标来源于需求分析阶段 • 单元测试单元测试又称为模块测试在模块编写完成且没有编译错误后开始执行单元测试侧重于模块内部的处理逻辑与数据结构单元测试检查模块的 5 个特征模块接口保证测试模块的数据流可以正常输入输出测试形参与实参是否匹配全局变量使用 I/O格式 , 文件处理等局部数据结构测试变量定义及使用重要的执行路径出错处理边界条件单元测试过程由于模块不是独立运行的各模块之间存在调用与被调用关系因此测试时需要开发两种模块  驱动模块相当于一个主程序接收测试用例的数据将数据输入到被测试模块输出测试结果  桩模块存根模块用来代替被测试模块所调用的子模块检测测试模块的输入高内聚可以简化单元测试 • 集成测试集成测试就是将模块按照系统说明书组合起来测试旨在发现与接口 75第 1 章计算机系统知识相关错误集成后可能出现的问题穿过模块的数据丢失一个模块的功能对其他模块造成有害影响模块集成后没有达到预期功能全局数据结构出现问题模块组合后误差累积自顶向下集成测试属于增量方法模块集成顺序从主控模块开始沿着控制层次逐步向下不用编写驱动模块需要编写桩模块自底向上集成测试模块集成顺序从底层原子模块开始沿着控制层次逐步向上不用编写桩模块需要编写驱动模块 • 回归测试软件发生变更可能会使原来正常的功能产生问题这时需要回归测试重新执行一下已经测试过的某些子集确保没有传播不期望的副作用回归测试有助于保证不引入无意识的行为或者额外的错误 • 冒烟测试将已经转换为代码的软件构件集成到构件中设计一系列测试以暴露影响构建正确的完成其功能的错误 • 测试方法静态测试被测程序不在机器上运行采用人工检测和计算机辅助静态分析来对程序进行检测动态测试通过运行程序发现错误可以采用黑盒测试和白盒测试测试用例由测试的输入数据和预期输出结果组成设计用例时应包 76第 1 章计算机系统知识含合理的输入条件和不合理的输入条件 • 黑盒测试不考虑软件内部结构和特性把软件当做和黑盒子测试软件的外部特性常用的黑盒测试技术等价类划分将程序输入输出划分为若干等价类然后每个等价类中取一个代表性数据作为测试用例测试时需要同时测试有效等价类和无效等价类边界值分析输入的边界比中间更容易发生错误应测试边界值和刚刚超过边界值的值错误推测基于经验推测因果图通过因果图转换判定表 • McCabe 度量法通过定义环路复杂度建立程序复杂度的度量它基于一个程序模块的程序图中环路的个数计算公式为 V(G) m - n 2 ; G 表示程序图 V(G) 表示程序图的环路复杂度 m 表示有向弧的个数 n 表示节点的个数也可以通过查找图中有多少个闭合区域 k , 然后 V(G) k 1 • 白盒测试白盒测试也称结构测试根据程序的内部结构来设计测试用例白盒测试的常用技术是逻辑覆盖、循环覆盖、基本路径测试白盒测试原则程序模块中的所有独立路径至少执行一次逻辑判断中取”真“ 和 ”假“的情况都至少执行一次 77第 1 章计算机系统知识每个循环都要在边界条件和一般条件下各执行一次测试程序内部数据结构的有效性逻辑覆盖语句覆盖选择足够的测试数据使得被测试程序中每条语句至少执行一次只要保证每条语句执行因此可能错过一些判断逻辑分支语句覆盖对程序执行逻辑的覆盖程度很低是很弱的逻辑覆盖判定覆盖设计足够的测试用例是的测试程序的每个判定表达式至少获得一次 ”真“值和”假“值每个取”真“和”假“的分支都至少跑一次因此也称为分支覆盖条件覆盖创造一组测试用例是的每一个判断语句中的每个逻辑条件的各种可能的值都至少满足一次判定 / 条件覆盖需要同时满足判定覆盖和条件覆盖的要求条件覆盖组合在判定 / 条件覆盖的要求前提下判定表达式的所有真假不同组合都要测试一遍例如 A0 b0 就要测试四种 TT, FF, TF, FT 路径覆盖指测试用例要覆盖程序中所有可能路径  路径覆盖每一条路径可能都要有  如何覆盖所有路径只要能把路径都走一遍就行如果有伪代码则先将其转换成流程图然后计算 • 运行和维护软件维护是软件生命周期最后一个阶段不属于系统开发过程系统可维护性评价指标可理解性、可测试性、可修改性文档是软件可维护性的决定因素可维护性在开发阶段就需要考虑到此后的每个阶段也都需要考虑 78第 1 章计算机系统知识 • 软件文档编写高质量的文档可以提高软件开发质量文档也是软件产品的一部分没有文档的软件不能称之为软件软件文档的编制在软件开发中占有突出的地位和相当大的工作量高质量的文档对软件产品的效益有着重要意义总的来说软件文档只好不坏 • 软件维护内容正确性维护改正在系统开发和测试阶段未发现的问题适应性维护适应行业环境变化和管理需求而做出的修改完善性维护为扩充功能和改善性能而做出的修改预防性维护为了适应未来的软硬件环境变化而主动做出的预防 • 软件可靠性、可用性、可维护性公式可靠性给定时间间隔、给定条件下无失效运作的概率 MTTF/ (1MTTF) MTTF: 平均无故障时间可用性给定时间系统正确运作的概率 MTBF/(1MTBF) MTBF: 平均失效间隔时间可维护性给定时间使用规定的过程和资源完成维护活动的概率 1/(1MTTR) MTTR: 平均修复时间 • 沟通路径计算 n 个程序员无主程序员 (n-1)*n/2 n 个程序员一个主程序员 n-1 79第 1 章计算机系统知识 • 软件项目估算 COCOMO 估算模型精确的易于使用的成本估算模型按精细程度分为基本 COCMO、中级 COCOMO 、详细 COCOMO 基本 COCOMO 模型 : 静态单变量模型中级 COCOMO 模型静态多变量模型将系统模型分为系统和部件两个层次详细 COCOMO 模型将软件系统模型分为系统、子系统和模块三个部分 COCOMOII 估算模型层级结构的估算模型分为三个阶段应用组装模型软件开发的前期阶段使用使用对象点估算早期设计阶段模型在需求已经稳定并且基本的软件体系结构已经建立的时期使用使用功能点估算体系结构阶段模型软件构造过程中使用使用代码行估算 • Gannt 图甘特图一种简单的水平条形图以日历为基准描述项目任务水平轴展示日历时间线每个横条表示一个任务水平条的起点终点对应日历时间表示任务的开始和结束其长度代表任务持续时间同一时间段的多个水平条间是并发关系优点清晰描述任务的开始结束时间任务进展情况和任务间的并行关系缺点不能清晰的反应出任务间的依赖关系不能反映项目的关键不能反应计划中有潜力的部分 • PERT 图 PERT 图是一个有向图图中的箭头表示”任务“箭头上的时间表示完成”任务“所需时间 80第 1 章计算机系统知识图中的节点表示”事件“表示指向当前节点的”任务“结束。并且由当前节点指出的”任务“开始当流入该节点的所有任务都结束时由当前节点指出的任务才会开始事件本身不消耗时间和资源仅表示一个时间点 ”事件“节点由三部分组成事件号、出现事件的最早时刻、最迟时刻开始节点没有流入的任务的节点可以有多个开始节点的最早时刻为 0 结束节点没有流出的任务的节点只能有一个结束节点的最迟时刻等于其自身的最早时刻最早时刻计算要从开始节点向结束节点推算最晚时刻要从结束节点向开始节点推算最早时刻能开始该事件节点出发的后续任务的最早时刻有多个流入的任务时则选择计算后的最大的那个节点的最早时刻计算流入的任务的所需时间流入前一个节点的最早时刻最迟时刻从此节点出发的任务必须在此时刻前开始否则工程不能如期完成有多个流出的任务时则选择计算后最小的那个节点的最迟时刻计算流出任务指向的节点的最晚时刻 - 流出任务所需时间松弛时间在不影响工期的前提下完成该任务有多少机动余地是挂在任务下的松弛时间计算链接任务的两个节点中箭头指向的节点的最迟时刻 - 任务的耗时 - 箭头尾部的节点的最早时刻关键路径从开始节点到结束节点松弛时间都是 0 的路径 PERT 图优点给出任务开始结束时间还能给出任务建的依赖关系、关键路径 PRET 图缺点不能反映出任务键的并行关系 81第 1 章计算机系统知识 • 项目活动图与 PERT 图类似其中顶点表示里程碑链接定点的变表示活动边上的数字表示活动所需时间除了图形及命名与 PERT 图不一样其他计算方面基本相似 • 软件配置管理软件配置管理主要目标变更标识、变更控制、版本控制、确保变更正确的实现、变更报告软件配置管理内容版本管理、配置支持、变更支持、过程支持、团队支持、变化报告、审计支持软件配置管理内容第二版软件配置标识、变更管理、版本控制、系统建立、配置审核、配置状态报告配置数据库分为三类 : 开发库、受控库、产品库 • 风险管理软件风险的特性不确定性可能发生也可能不发生和损失如果发生就会产生恶性后果软件风险的分类项目风险拖延项目进度、增加项目成本。例如预算、进度、人员、资源、项目复杂度、规模及结构不确定技术风险质量和交付时间。例如设计、实现、接口、维护等方面的问题商业风险威胁软件生存能力 • 风险识别系统的指出对项目计划估算、进度、资源分配等的威胁识别出已知风险和可预测风险后项目管理者要回避这些风险必要时控制 82第 1 章计算机系统知识这些风险识别风险的一种方法是建立 ”风险条目检查表“ 风险条目检查表格式列出每一种类型的有关特性最终给出一组风险因素和驱动因子及发生概率风险因素包含性能、成本、支持、进度 • 风险预测又称风险估计通过两个方面进行评估 1. 风险发生概率 2. 风险发生后果风险预测活动建立一个尺度或者标准反应风险发生的可能性描述风险产生的后果估算风险对项目和产品的影响标注风险预测的精确度以免产生误解风险预测技术建立风险表影响风险产生后果的三个因素风险的本质、范围、时间整体风险显露度风险发生的概率 * 风险发生给项目带来的成本风险评估一种对风险评估很有用的技术是定义风险参照水准 • 风险控制风险控制的目的辅助项目组建立处理风险的策略风险避免应对风险的最好办法就是主动的避免风险风险监测项目管理者应监控某些因素这些因素可以提供风险是否正在变低或者变高的指示 RMMM 计划将所有风险分析工作文档化并由项目管理者作为整个项目计划的一部分来使用风险缓解是一种问题规避活动风险监测是一种项目跟踪活动 83第 1 章计算机系统知识风险监测的另一个任务就是找到“起源” • 软件质量 ISO/IEC 9126 软件质量模型由三层组成质量特性》质量子特性》质度量指标功能性满足规定或隐含需求的那些功能适应性是否适合有关的软件属性准确性能够得到正确的结果互用性与其他系统进行交互的能力依从性服从有关标准、法规安全性避免非授权访问和意外访问可靠性一定时间内软件维持性能水平的能力成熟性软件故障引起失效的频率容错性在软件错误或违反指定接口的情况下维持指定的性能水平易恢复性故障后回复的能力易使用性是否容易使用使用付出学习成本易理解性易学性易操作性效率软件性能水平和所占资源时间特性响应处理时间资源特性所使用的资源量可维护性易分析性诊断所需要的成本易改变性缺陷改正成本稳定性不发生风险的能力 4. 易测试性可移植性 84第 1 章计算机系统知识适应性软件转移到不同环境耗时和成本易安装性指定环境下安装软件成本一致性不同环境安装后软件能力一致易替换性 • 软件评审低概率考设计质量设计的规格说明书符合用户要求程序质量程序按照规格说明书所规定的情况正确执行设计质量评审内容评价软件的规格说明是否符合用户要求评审可靠性即是否能避免输入异常评审保密措施实施情况评审性能实现情况评审软件可修改性、可扩充性、可互换性、和可移植性评审软件可测试性评审软件复用性程序质量评审内容从开发者角度进行评审与开发技术直接相关着眼于软件本身结构功能结构功能的通用性模块的层次模块结构控制流结构、数据流结构、模块结构与功能结构之间的对应关系处理过程的结构与运行环境的接口与硬件的接口、与用户的接口完成质量评估的中心活动是技术评审目的是揭露质量问题 85第 1 章计算机系统知识 • 软件容错技术对无可避免的差错使其影响减到最小容错软件的定义对自身错误具有屏蔽能力的软件一定程度上能从错误状态恢复到正常状态的软件发生错误仍能完成预期任务的软件一定程度上具有容错能力容错的一般方法实现容错的主要手段是冗余冗余是指对于实现系统功能的多余的那部分资源 • 四类冗余技术结构冗余静态冗余、动态冗余、混合冗余信息冗余为检测或纠正信息在运算或传输中的错误而外加的一部分信息时间冗余重复执行程序或指令来先出瞬时错误的影响冗余附加技术屏蔽硬件错误的附加技术 1. 关键程序和数据的冗余存储。 2. 检测、表决、切换、重构、纠错、复算屏蔽软件错误的附加技术 1. 冗余备份程序的存储及调用。 2. 实现错误检查和错误恢复。 3. 实现容错软件所需的固化程序 • 软件工具软件开发工具需求分析工具设计工具编码与排错工具测试工具 86第 1 章计算机系统知识软件维护工具版本控制工具文档分析工具开发信息库工具逆向工程工具再工程工具 • 其他高质量文档特性针对性、精确性、清晰性、完整性、灵活性、可追溯性软件工程基本要素方法、工具和过程数据处理领域不太复杂的软件适合结构化开发方法软件调试方法试探法猜测问题所在位置通过输出语句获得错误线索回溯法从发现问题的位置开始沿着程序的控制流程往回跟踪代码对分查找法通过缩小错误范围找出问题归纳法收集正确的与不正确的数据分析他们之间的关系提出假想的错误原因演绎法列出所有可能的错误原因排除、尝试 87第 1 章计算机系统知识第 13章数据结构与算法 • 复杂度大 O 表示法以算法中基本操作重复执行的次数频度作为算法时间点的度量一般只要大致的计算出数量级即可 O(1) O(log2 n) O(n) O(nlog2 n) O(n^2) O(n^3) O(n!) O(n^n) 常数阶对数阶线性阶线性对数阶平方阶立方阶阶乘阶 n 次方阶复杂度计算规则多项相加保留最高项多项相乘都保留加乘混合则按照计算规则系数化为 1 时间复杂度与循环相关空间复杂度看有没有开辟新空间比如数组 • 渐进符号 O(g(n)): 表示渐进上界 10n^24n2 O(n^2) 是成立的因为渐进上界括号内的复杂度要大于等于等式左边的计算结果 Ω(g(n)): 表示渐进下界 10n^24n2 O(n^3) 是不成立的因为渐进下界括号内的复杂度要小于等于等式左边的计算结果 Θ(g(n)): 表示渐进紧致界 10n^24n2 O(n^3) 是不成立的因为渐进紧致界括号内的复杂度要等于等式左边的计算结果 • 递归的时间空间复杂度递归的时间复杂度递归的次数 * 每次递归的时间复杂度递归的空间复杂度如果递归中有变量声明赋值则相当于长度为递归次数的数组 88第 1 章计算机系统知识递归式主方法假如题目给了一个递归式的表达式长得像 T(n) aT(n/b) f(n) 那么可以按照下边方法尝试一下比如给了个题目 T(n) 2T(n/2) nlgn 让求复杂度那么按照公式换算得出 a2; b2; f(n) nlgn; 如果 f(n) 中有 lg 相关那么就套这个公式 f(n) Θ(n^(logb a)lgk n); 将换算的数据代入即 nlgn (n^(log2 2)lgk n); 得到 k 1; 然后再代入到这个公式 T(n) Θ(n^(logb a)lgk1 n) 得出 T(n) 复杂度为 nlg2n 若果 f(n) 中没有 lg 则直接代入到 T(n) Θ(n^(logb a)) • 线性表线性关系具有单一前趋和后继的数据关系元素一个接一个的排列线性表最简单基本常见的线性数据结构通常表示为 (a1,a2,…an) 线性表特点‘第一个元素’、‘最后一个元素’都是唯一且只有一个的除第一个元素只有后继最后一个元素只有前趋外其余元素都含有前趋和后继线性表顺序存储指用一组连续的存储单元一次存储线性表中的数据也就是说物理位置相邻优点可随机存取表中元素查询效率高缺点插入和删除需要移动元素删除插入效率低表长为 n, 插入新的值平均移动 n/2; 删除值平均移动 (n-1)/2 顺序表插入元素时间复杂度顺序表最后插入 O(1); 顺序表首位插入 O(n);平均复杂度 O(n) 顺序表删除元素时间复杂度顺序表最后一位删除 O(1); 顺序表首位删除 O(n); 平均复杂度 O(n) 查找元素时间复杂度直接根据数组下标查询所以为 O(1) 89第 1 章计算机系统知识 • 线性表链式存储通过指针链接起来节点来存储数据元素分为数据域指针域数据元素的节点地址不是连续的节点空间在需要的时候才申请若节点只有一个指针域则成为线性链表或单链表头节点不存储数据 (!!也可以存储链表长度 ) 只存储链表第一个节点的地址头指针、尾指针有了尾指针就可以直接从尾部遍历查找有了尾指针时间复杂度会有变化连式存储插入元素时间复杂度首位插入 O(1); 末位插入 O(n); 平均复杂度 O(n) 连式存储删除元素时间复杂度首位删除 O(1); 末位删除 O(n); 平均复杂度 O(n) 连式存储查找元素时间复杂度首位查找 O(1); 末位查找 O(n); 平均复杂度 O(n) 循环单链表就是在单链表的基础上尾部节点的指针指向头部节点时间复杂度与单链表一致双链表每个节点指针不但指向后驱节点还会指向前趋节点也就是一个节点即知道前一个节点地址也知道后一个节点的地址 • 栈栈的定义只能通过访问它的一端来实现数据存储和检索的一种线性数据结构栈的修改按照先进后出后进先出的原则进行插入和删除操作的一端称为栈顶 Top, 另外一端称为栈底不含元素的称为空栈理解可以将栈想象成一个杯子先进先出与递归的执行过程类似栈的链式存储用链表作为存储结构的栈也称为链栈不必设置头指针链表的头指针就是栈顶指针 90第 1 章计算机系统知识 • 队列队列的定义一种先进先出的线性表只允许在表的一端插入值在另一端删除元素顺序队列使用顺序存储的队列需要设置队头指针和队尾指针循环队列可处理顺序队列中插入值溢出越界只需要改变队头和队尾指针即可避免采用线性表插值导致的遍历 • 队列链式存储双端队列入队出队在两端都可以进行两个栈可以模拟一个队列但是两个队列无法模拟一个栈 • 串串是一种特殊的线性表其数据元素为字符是由字符构成的有限序列例如 ‘ abc’ 空串长度为零不包含字符子串串中任意长度的连续子串构成的序列 ‘ abc’ 的子串可以是 ‘ ab’ 但不能是 ‘ ac’ 串比较两个串比较时以字符的 ASCII 码值作为依据串的模式匹配可以理解为 JS 中所要的效果 a.indexOf(b) 复杂度主串长度 n , 子串长度 m 最好情况首位即匹配成功复杂度 O(m) | O(1) 最坏请款比较到最后 m 位复杂度 O(nm) (n-m1)m 平均复杂度 O(nm) • 串的模式匹配 KMP 算法串的前缀包含第一个字符但是不包含最后一个字符的子串串的后缀包含最后一个字符但是不包含第一个字符的子串 91第 1 章计算机系统知识 KMP可以提高串的模式匹配效率时间复杂度为 O(nm) KMP next 的数值计算第 i 个字符的 next 值第 i 个字符前的字符串中”串前缀串后缀“最长的那个的长度 1其中 next[1] 0 • 一维数组 LOC: 表示第一个元素的首地址 L: 表示每个元素的大小计算数组中某个元素 i 的地址 ai LOC i*L • 二维数组二维数组的存储会将将第二行在第一行后边连续存储列优先存储则第二列在第一列存储之后连续存储 LOC: 表示第一个元素的首地址 L: 表示每个元素的大小 ; N: 行数 ; M: 列数计算二维数组 i 的地址 LOC (i 前有多少个元素 ) * L 行优先存储 LOC (i*M j) * L 列优先存储 LOC (j*N i) * L N M 且 i j 时按行还是按列的地址都是一样的偏移量也是一样的 • 对称矩阵矩阵内任意元素具有 Ai,j Aj,i 的特点按照主对角线对称分为上三角区和下三角区存储时只需要存储下三角区主对角线即可一般使用一个一维数组存储按行存储 i j 时 Ai,j (i1)i/2 j 1; i j 时因为 92第 1 章计算机系统知识是主对角线堆成则可以改为计算 Aj,i • 三对角矩阵只有主对角线两侧紧邻区域有值其他区域都是 0 存储时只存中间区域的值不存 0 的位置存到一个一维数组中按行存储 Ai,j 2ij1 • 稀疏矩阵矩阵很大但是存的非 0 元素很少压缩存储方式使用三元组顺序表存储 [i, j, data] [行 , 列值 ] 另一种压缩方式十字链表 • 树一种非常重要的非线性结构一个元素可以有 0 个或多个的后继元素树是 n 个节点的有限结合 n0 时称为空树有且只有一个根节点兄弟节点具有相同父节点的节点节点的度一个节点的子树的个数计为该节点的度叶子节点终端节点没有子节点的节点度为 0 的节点内部节点分支节点度不为 0 的节点节点的层次根为第一层跟的子为第二层以此类推树的高度一棵树最大的层数计为树的高度或者树的深度树的度树中所有节点度的最大值 • 树的性质树中节点总数所有节点的度数之和 1 93第 1 章计算机系统知识度为 m 的树中第 i 层上最多有 m^(i-1) 个节点最多的情况就是每层都有 m 个节点高度为 h 的度为 m 的树最多有 (m^h - 1)/(m-1) 个节点最多的情况就是每层都有 m 个节点一共 h 层具有 n 个节点度为 m 的树的最小高度为 logm (n(m-1) 1) 要想高度最小那还是每层都要有 m 个节点 • 二叉树 n 个节点的有限集合 n0 时为空树或者是由一个根节点及两个不想交的且分别称为左右子树的二叉树组成树和二叉树的区别二叉树中子树分为左子树和右子树即使只有一个子树也要区分左右二叉树中节点最大度数为 2 • 二叉树的性质二叉树第 i 层最多有 2^(i-1) 个节点实际就是树的公式中国将度 2 后代入高度为 h 的二叉树最多有 2^h - 1 个节点最多的情况下每一层的节点数都是前边所有层的节点数 1 任意一个二叉树度数为 0 的叶子节点个数度数为 2 的节点个数 1由 ”树中节点总数所有节点的度数之和 1“ 推断出来的有 n 个节点的完全二叉树的高度为 (log2 n 1)的向下取整或者 (log2 (n1)) 的向上取整 94第 1 章计算机系统知识 • 满二叉树高度为 k 的二叉树如果有 2^k -1 个节点那就是满二叉树可以从上往下从左往右编号 • 完全二叉树除最后一层外其他层都是”满的“最后一层的节点也是从左至右依次放置这个情况下完全二叉树中的每一个节点都能与同样深度的满二叉树一一对应 • 卡特兰数 n 个节点的二叉树有多少种 : (C2n n)/(n1); 其中 (Cn m) n!/m!*(n-m)! • 二叉树的顺序存储用一组连续的存储单元存储二叉树中的节点树节点与编号 i 间关系求父节点 i1, 则为根节点根节点没有父节点若 i1 则该节点的父节点为 i/2 的向下取整求左子节点 2in 则该节点左子节点编号为 2i, 否则无左子节点求右子节点 2i1n 则该节点右子节点编号为 2i1, 否则无右子节点顺序存储对完全二叉树比较合适对普通二叉树来说则为了保持关系会有很多”虚节点“ 单支树除了叶子节点其他节点的度都为 1 95第 1 章计算机系统知识 • 二叉树链式存储二叉链表存储每个二叉链表节点存储 [ 当前节点的数据元素 , 左子节点指针右子节点指针 ] 如果没有对应的子节点则存 NULL 二叉链表存储中的有效指针域数量即为树结构中的有效关联数量每个子节点都仅有一个父节点 ( 除了根节点 ) 因此有效的数量总的节点数 - 1 个三叉列表在二叉链表的基础上增加了一个指向父节点的指针域 • 二叉树的遍历先序遍历按照根左右的次序遍历中序遍历按照左根右的次序遍历后序遍历按照左右根的次序遍历层次遍历从根节点开始每一层从左往右访问 • 还原二叉树单独一种遍历结果没法还原出树先序遍历和层次遍历的的首位就是根节点后序遍历的末位也是根节点因此中序遍历与其他任意一种遍历结合就能还原二叉树 • 平衡二叉树二叉树中任意节点的左右子树高度只差不大于 1 完全二叉树一定是平衡二叉树 • 二叉排序树又称二叉检查树根节点关键字就是根节点的值 96第 1 章计算机系统知识根节点的关键字大于左子树的所有节点关键字根节点的关键字小于右子树的所有节点关键字左右子树也是二叉排序树依次递归二叉排序树的中序遍历是一个有序序列计算题会给一个关键字序列关键字序列的收个元素就是根节点后边数字比根大就放右边比根小就放左边节点为空就直接插入不为空就与其比较后向下层插入其他的元素依次判断插入二叉排序树中即可二叉排序树查找的效率是受查找的层数相关的层数越高效率越差 • 最优二叉树又称哈弗曼树它是一类带权路径长度最短的树路径从树的一个节点到另一个节点之间的通路路径长度路径上的分支数目几条线树的路径长度从根节点到每一个叶子节点路径长度之和乘以权值则代表树的带权路径长度 • 最优二叉树构造题将一个权值集合例如 {1,3,3,4} 构造成一个二叉树构造方法从前往后找两个权值最小的这两个里边小的作为左子树大的作为右子树构造新的二叉树这个二叉树的根的权值等于两者相加将计算后的根加入权值集合末尾继续上述步骤直到集合中只剩下一个权值大的距离根节点近权值小的距离根节点远最优二叉树只有度为 0 的节点和度为 2 的节点总节点个数 (权值数量 * 2) - 1 97第 1 章计算机系统知识 • 哈夫曼编码等长编码对每个字符编制相同长度的二进制码例如英文 26 个字符需要 2^5 即需要 5 位二进制串表示哈夫曼编码不是等长编码接收方按照 5 位一组将电文进行分割后通过对应实现译码题一般会给一串字符并说明字符的权重我们根据权重画出哈夫曼树并将节点替换为相应的字符根节点与左子节点的连线为 0 与右子节点的连线为 1 将每条节点间连线标出某个字符的编码就是从根节点开始到当前字符节点所经过路径上的 0,1 组成哈夫曼编码压缩比即每个字符从等长编码到哈夫曼编码的压缩情况哈夫曼编码是基于贪心策略的 • 线索二叉树普通二叉树采用二叉链表做存储结构则链表中会有空指针域利用这个空指针域来存放节点的前驱后继信息 • 图图中任意两个节点之间都可能有关系一个节点可能有多个前趋或者多个后继图标记为 G(V,E) V 表示顶点的非空有限集合 E 是图中边的有限集合有向图每个边是有方向的那么顶点关系用 v1 是起点 v2 是终点无向图每个边是无方向的那么顶点关系用 (v1,v2) 完全图每个顶点都与其他顶点有一个边则称为完全图 98第 1 章计算机系统知识假设无向完全图有 n 个顶点那完全图的边一共有 n(n-1)/2 有向完全图的边总数则为 n(n-1) 因为每两个顶点间有来回两条边无向图顶点的度关联于该顶点的边的数量有向图的出度与入度出度–从该顶点指出去的边的数量入度–指向该顶点的边的数量总度数出度入度图的总度数边数 * 2 路径就是通过那几条边的组合实现从一个顶线到另一个顶点路径长度就是路径上边或弧的数目第一个顶点和最后一个顶点相同的路径称为回路或者环简单路径路径上除了起点和终点可以相同外其余顶点都不相同的路径 • 连通图连通图无向图中任意两个顶点间都有至少一条的路径可以连通则称为连通图对于 n 个顶点的无向图最少有 n-1条边就可以实现连通最多 n(n-1)/2 强连通图有向图中任意两个顶点间都有来回的两条路径连通称为强连通图对于 n 个顶点的有向图最少有 n 条边就可以实现连通最多 n(n-1) • 图的存储结构邻接矩阵表示法使用一个矩阵来表示图中顶点间的关系有 n 个定点的图其邻接矩阵就是 n 阶的矩阵中值为 1 表示有边为 0 表示无边无向图的邻接矩阵是对称的有向图则不一定是 99第 1 章计算机系统知识无向图邻接矩阵计算某个定点的度数定点 vi 的度数就是第 i 行非 0 元素的个数有向图邻接矩阵计算某个定点的度数定点 vi 的出度–第 i 行非 0 元素的个数 ; 入度第 i 列非 0 元素的个数邻接链表表示法为图的每个节点建一个单链表具体的还得看图这里不做详解有向图的邻接链表有几个指出来的表结点就有几条边无向图的邻接链表有 n 指出来的表结点就有 n/2条边稠密图和稀疏图边多的就是稠密图边少的就是稀疏图邻接矩阵表示法适合稠密图邻接链表适合稀疏图网边或弧带有权值的图称为网网的邻接矩阵中有边的会用权值表示没有边的用 oo 无穷表示 • 图的遍历深度优先搜素从一个顶点 A 按照出度向另一个顶点 B B 在按照出度向顶点 C, 这样先从路径的起始遍历到路径的末尾然后在通过回溯换一个路径遍历深度优先搜素的时间复杂度 n 表示顶点数 e 表示边数邻接矩阵存储的复杂度为 O(n^2) 邻接链表的时间复杂度 O(ne) 用栈的方式广度优先搜索先遍历一个顶点 A 的所有出度的节点在遍历出度节点的所有出度节点以此类推相当于一层层遍历广度优先搜素的时间复杂度 n 表示顶点数 e 表示边数邻接矩阵存储的复杂度为 O(n^2) 邻接链表的时间复杂度 O(ne) 用队列的方式 • 拓扑排序 AOV 网一种有向无环图 100第 1 章计算机系统知识 AOV 网中弧的尾部是前趋弧指向的是后继前趋对后继有制约关系拓扑排序是 AOV 网中所有定点排出的线性序列并且网中任意路径的前后顶点在这个线性序列中 vi 排在 vj 前假设 AOV 图是一个工程的计划那 AOV网的一个拓扑排序就是工程顺利完成的可行方案拓扑排序计算方式在 AOV 网中选择一个入度为 0 的顶点且输出它在网中删除该顶点及与该顶点相关的所有弧重复上述两步直到不存在入度为 0 的顶点为止例如得到 614325 这个拓扑序列那么对于 6 与 4 来说可能存在弧6-4;不可能存在弧 4-6;可能存在 6-4 的路径一定不存在 4-6 的路径 • 查找查找表由同一类型元素构成的集合集合元素之间存在着完全松散的关系静态查找表只进行以下两种操作查询某个特定元素是否在查找表中检索某个特定元素的各种属性动态查找表除了静态查找表的功能还进行如下操作在查找表中插入一个数据从查找表中删除一个数据关键字是数据元素某个数据项的值可以用来标记数据元素静态查找表有顺序查找、二分查找、分块查找动态查找表有二叉排序树、平衡二叉树、 B_ 树、哈希表查找的基本操作将记录的关键字与给定的值进行比较顺序查找就是从左向右查找不需要有序适用于顺序存储和链式存储方式平均查找长度为 (n1)/2 101第 1 章计算机系统知识 • 二分查找又称折半查找就是将给定的值与查找表中间的值进行比较下标求中间值比较值中间值为小数则向下取整比较后舍弃中间值进行下一轮比较例如 10 个值则依次取 (110)/2 5 (610) 8; (910)/2 9; (1010)/2 10; 需要顺序存储且要有序存储二分查找成功时给定值的比较次数最多为 [log2 n) 1 向下取整二分查找的平均查找长度为 (log2 (n1)) - 1 • 哈希表哈希表通过计算一个已记录的关键字为自变量的函数哈希函数来得到该记录的存储地址根据设定的哈希函数 H(key) 和处理冲突的方法将一组关键字映射到一个有限的连续地址集上对于一个哈希函数两个不同的关键字经过哈希函数查找后的地址相同时称为冲突具有相同哈希函数值的关键词称为同义词一般情况下冲突可以尽可能的减少而不能避免要减少冲突就要尽可能均匀的将关键字映射到存储区的各个存储单元对于哈希表来说主要考虑两个问题一个是如何构造哈希函数一个是如何解决冲突哈希函数构造方法构造哈希函数时一般都会对关键字进行计算尽可能的使得关键字的所有成分都起作用除留余数法 H(key) key % m 地址求关键字 key 的余数作为地址其中 m 是一个接近 n 但不大于 n 的质数 n 是散列表的长度地址一般从 0 开始 102第 1 章计算机系统知识解决冲突的方法解决冲突就是在冲突时给冲突的关键字再找个地址存储线性探测法如果 H(key) 冲突了那就按照 Hi (H(key) i) % m 再计算一个地址其中 i1,2,3,... 表示再次计算如果还是冲突就加码再次计算直到不冲突为止二次探测法如果 H(key) 冲突了那就按照 Hi (H(key) di) % m再计算一个地址其中 i1^2,-1^2,2^2,-2^2,... 表示再次计算如果还是冲突就就按照 1^2,-1^2,2^2,-2^2,... 的方式依次尝试直到不冲突为止 , 与线性探测法相比是在 H(key) 地址的左右来回试探装填因子 a 表中装入的记录树 / 哈希表长度 a 代表哈希表的装满程度 a 越大冲突概率越大 • 堆 n 个关键码构成的序列 {k1,k2,…kn}满足以下关系称为堆小顶堆 ki k2i ki k(2i1) 即根节点比子节点小的二叉树层次遍历的结果大顶堆 ki k2i ki k(2i1) 即根节点比子节点大的二叉树层次遍历的结果将一个序列调整为一个大顶堆或者小顶堆先按照层次遍历的结果将其还原成一个二叉树从叶子节点开始向上依次判断比如说要还原成一个小顶堆就要使得局部根节点的值比子节点要小不符合的就互换一下 • 排序通过排序使得关键字满足递增或者递减的关系稳定的原序列中有 Ri 和 Rj 的关键字相同且 Ri 在 Rj 之前经过排序算法后还能保持 Ri 在 Rj 之前那就是稳定的 103第 1 章计算机系统知识否则是不稳定的归位在排序时能确定最终排序位置比如 Ri 排序后应该放在位置 3 那在计算时如果开始没将它放在 3 这个位置就是不归位 • 直接插入排序新序列中以 R1 开始遍历原序列 R, 每个 Ri, 依次与新序列中从后开始的关键字相比较大的直接插入到后边小的继续往前判断直到插入直接插入排序稳定、不归位平均复杂度 O(n^2), 最大复杂度 O(n^2), 最小复杂度 O(n), 空间复杂度 O(1) 适用于基本有序的情况 • 希尔排序是直接插入排序算法的改进方法设定一个增量序列例如 5 3 1 按照增量序列依次将原序列切割成多段比如增量为 5 时将第 0, 5, 10 位置的元素分为一组 1 6, 11 分为一组以此类推每组间元素进行直接插入排序排序后的值互换位置插入回原序列按照增量序列依次处理直到增量为 1 希尔排序不稳定、不归位平均复杂度 O(n^1.3), 最大复杂度 O(n^2), 最小复杂度 O(n), 空间复杂度 O(1) • 计数排序适合比较少数据量的排序 104第 1 章计算机系统知识就是将把要排序的数统计一下每种数据有多少个然后依次添加到序列中 • 简单选择排序从首位开始依次用后边的关键字与当前的关键字比较选出最小的那个与当前位替换顺序直到最后一位为止简单选择排序 : 不稳定、归位平均复杂度 O(n^2), 最大复杂度 O(n^2), 最小复杂度 O(n^2), 空间复杂度 O(1) • 堆排序先将原序列按照层级遍历成一个二叉树然后构造一个大根堆或者小根堆将堆的根与堆的末位进行交换然后再次构造大根堆或者小根堆重复进行操作直到整个堆变成一个新的序列堆排序不稳定、归位平均复杂度 O(nlog2 n), 最大复杂度 O(nlog2 n), 最小复杂度 O(nlog2 n), 空间复杂度 O(1) • 冒泡排序从原序列首位开始分别进行 ki 与 k(i1) 位的比较如果如果 ki 更大则交换顺序这样直到交换到最后一位可以保证最后一位是最大的重复进行冒泡排序稳定、归位平均复杂度 O(n^2), 最大复杂度 O(n^2), 最小复杂度 O(n), 空间复杂度 O(1) • 快速排序基于分治的思想通过一趟排序将待排序的记录分为两个部分前半区、后半区前半区的关键字都不大于后半区的关键字然后载分别对两部分进行快速排序依次递归操作 105第 1 章计算机系统知识基本有序序列的快速排序效率最低时间复杂度最大 O(n^2) 快速排序不稳定、归位平均复杂度 O(nlog2 n), 最大复杂度 O(n^2), 最小复杂度 O(nlog2 n), 空间复杂度 O(log2 n) • 归并排序基于分治的思想将一个序列一分为二每一半再一分为二如此递归直到每一项为 1 个在从从底向上每两项间进行比较、每四项间进行比较如此向上递归直到最外层归并排序稳定、归位平均复杂度 O(nlog2 n), 最大复杂度 O(nlog2 n), 最小复杂度 O(nlog2 n), 空间复杂度 O(n) • 回溯法 N 皇后问题给定 N * N 的棋盘要在棋盘上摆放 N 个皇后皇后中的任意两个都不处于同一行同一列同一对角线上判断是否同一列 Qi 列 Qj列判断是否在一个对角线 |Qi 行 - Qj 行 | |Qi 列 - Qj 列 | 代码求解 N 皇后问题非递归循环、迭代递归深度优先主要考的是下午 C 语言计算题放弃。。。 • 分治法用递归来实现的递归是指自己调用自己或者间接的自己调用自己有两个基本要素 1. 需要有边界条件递归出口 2. 递归模式递归体分治法的基本思想 106第 1 章计算机系统知识规模越小解题所需时间越少越容易处理将一个难以解决的大问题分解成一些规模较小的相同问题以便各个击破分而治之分治算法三个步骤 3. 分解原问题分解为子问题 4. 求解递归求解各个子问题 5. 合并子问题的解合并成原问题的解 • 动态规划法与分治法类似基本思想都是将问题分解为若干个子问题然后求解子问题在通过子问题的解得到原问题的解不同点适合动态规划法的问题分解为的子问题往往不是独立的有相同的子问题操作上将动态规划法会用一个表记录所有已解决的子问题答案在后续计算中如果有相同的问题则直接找出已求解的答案避免重复计算动态规划算法通常用来求解某种最优性质的问题全局最优解适合动态规划法求解的问题的两个特征最优子结构一个问题的最优解中包含其子问题的最优解需要注意贪心算法也有这个特性重叠子问题原问题的递归算法可反复的解同样的子问题对每个子问题只解一次保存在表中需要时查表 • 0-1 背包问题问题详情表 n 个物品第 i 个物品价值为 vi, 重量 wi, 背包容量 W 如何装使得背包物品价值最大 0-1 表示物品要么装入要么不装入代码实现放弃~~~ 107第 1 章计算机系统知识背包问题时间复杂度 O(n * w); 空间复杂度 O(n * w) • 矩阵连乘由动态规划法实现时间复杂度 O(n^3); 空间复杂度 O(n^2) 计算方法 : 矩阵 A(mn) 与 B(np) 相乘所需的乘法次数为 m * n * p 相乘后的结果可以类似表示为 AB(mp) 再次与 C(pk) 相乘则所需乘法次数为 m * p * k 因此 A(mn), B(np), C(p*k) 三者相乘的乘法次数可以为 m * n * p m * p * k 多个矩阵连乘最优的计算次序是先将 m, n, p, k 中最大的那个乘以消除掉 • 贪心法贪心法与动态规划法类似也用来解决最优化问题但是在解决问题的策略上贪心法不是从整体最优上考虑而是局部最优适合贪心法求解的问题的两个特征最优子结构 : 一个问题的最优解中包含其子问题的最优解需要注意贪心算法也有这个特性贪心选择性质问题的整体最优解可以通过一系列局部最优的选择即贪心选择来实现部分背包问题在 0-1 背包问题基础上物品可以部分装入背包 • 分支限界法类似于回溯法也是一种在问题的解空间树 T 上搜索问题解的方法 108第 1 章计算机系统知识用来找出满足约束条件的一个解搜索方式上采用广度优先或以最小消耗优先

查看全文

http://www.dnsts.com.cn/news/114254.html