软件设计师（中级）
2021-05-24 10:42:14 4 举报AI智能生成
中级软件设计师知识点总结（重要考点内容）
作者其他创作
大纲/内容
计算机网络
开放系统互联参考模型☆☆
OSI/RM七层模型
7、应用层
实现具体的应用功能
5-7层
POP3、FTP、HTTP、Telnet、SMTP、DHCP、TFTP、SNMP、DNS
6、表示层
数据的格式与表达、加密、压缩
5、会话层
建立、管理和终止会话
4、传输层
端到端的连接——报文
TCP、UDP
3、网络层
分组传输和路由选择——包
三层交换机、路由器
ARP、RARP、IP、ICMP、IGMP
ARP、RARP、IP、ICMP、IGMP
2、数据链路层
传输以帧为单位的信息——帧
网桥、交换机（多端口网桥）、网卡
PPTP、L2TP、SLIP、PPP
PPTP、L2TP、SLIP、PPP
1、物理层
二进制传输——bit
中继器、集线器（多端口中继器）
载波监听多路访问协议（CSMA/CD）、令牌环网协议（Token Ring）
载波监听多路访问协议（CSMA/CD）、令牌环网协议（Token Ring）
TCP/IP协议簇
POP3：110端口，邮件收取
SMTP：25端口，邮件发送
FTP：20数据端口/21控制端口，文本传输协议
HTTP：80端口，超文本传输协议，网页传输
DHCP：67端口，IP地址自动分配
SNMP：161端口，简单网络管理协议
DNS：53端口，域名解析协议，记录域名与IP的映射关系
TCP：可靠的传输控制协议
UDP：用户数据报协议——不可靠的传输层协议
ICMP：因特网控制信息协议，Ping命令来自该协议
IGMP：组播协议
ARP：地址解析协议，IP地址转换为Mac地址
RARP：反向地址解析协议，Mac地址转IP地址
TCP/IP协议☆☆☆☆
TCP/IP模型
应用层（对应7层模型的上三层）
应用层
表示层
会话层
传输层
传输层
网际层
网络层
网络接口层(对应7层模型中的前2层)
数据链路层
物理层
IP地址与子网划分☆☆☆☆☆
子网划分
1、子网掩码：网络地址全为1，主机号部分全为0
2、将一个网络划分为多个子网（取部分主机号当子网号）
3、将多个网络合并成一个大的网络（取部分网络号当主机号）
IP地址
A类：0打头，网络地址8位，主机号24位
B类：10打头，网络地址16位，主机号16位
C类：110打头，网络地址24位，主机号8位
D类：1110打头，组播地址
E类：1110打头，保留为以后使用
网络规划与设计☆
需求分析
网络功能需求
网络的性能要求
网络运行环境的要求
网络的可扩充性和可维护性要求
网络规划原则
实用性原则
开放性原则
先进性原则
经济
网络设计与实施原则
可靠性原则
安全性原则
高效性原则
可扩展性原则
层次化网络设计（三层交换机）
核心层
汇聚层
接入层
计算机网络分类
按分布范围分
局域网
城域网
广域网
因特网
按拓扑结构分
总线型
星型
环型
网络接入技术
有线接入
公用交换电话网络（PSTN）
数字数据网（DDN）
综合业务数字网（ISDN）
非对称数字用户线路（ADSL）
同轴光纤技术（HFC）
无线接入
IEEE 802.11（WIFI）
IEEE 802.15（蓝牙）
红外（IreDA）
3G与4G标准☆☆
3G
WCDMA——联通
CDMA2000——电信
TD-SCMA——移动
wireless MAN（802.16）（WIMAX）
4G
FDD-LTE
TD-LTE
wirelessMAN（802.16m）(WiMAX)
HTML语言☆☆
信息安全
对称加密与非对称加密☆☆☆
对称加密
使用同一套的密钥
特点：加密强度不高，但效率高；秘钥分发困难
常见的对称加密算法：DES、3DES（三重DES），RC-5，IDEA算法
非对称加密
密钥必须成对使用（公钥加密，相应的私钥解密）
特点：加密速度慢，但强度高
常见的非对称加密算法：RSA，ECC
信息摘要与数字签名☆☆
数字签名
用发送方的私钥签名，接收方用发送方的公钥来验证数字签名
信息摘要
由单向散列函数加密固定长度的散列值（不可逆的过程）
常用的信息摘要算法有MD5，SHA等，市场上广泛使用的MD5，SHA算法的散列值分别为128和160位，
由于SHA通常采用的密钥长度较长，因此安全性高于MD5
由于SHA通常采用的密钥长度较长，因此安全性高于MD5
主动攻击与被动攻击
被动攻击
监听
消息内容获取
业务流分析
主动攻击
中断（可用性）
篡改（完整性）
伪造（真实性）
数字证书☆☆
网络安全协议☆☆☆
防火墙技术与网络攻击☆☆☆
防火墙
网络级
包过滤
状态监测
应用级
双穴主机
屏蔽主机
屏蔽子网
安全防范体系
物理环境的安全性
操作系统的安全性
网络的安全性
应用的安全性
管理的安全性
计算机病毒与木马☆☆☆
木马
计算机木马是一种后门程序，常被黑客用作控制远程计算机的工具（窃取信息）
病毒
编制或者在计算机程序中插入破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或程序代码
系统开发基础
开发模型☆☆☆☆☆
瀑布模型
V模型
喷泉模型
面向对象的开发方法
原型化模型
演化模型
螺旋模型
统一过程
敏捷方法
极限编程XP
CockBurn水晶方法
开放式源码
Scrum
软件开发方法☆
结构化方法
面向数据流的方法，自顶向下，逐步分解(求精)，不适合大型的项目
原型法
面向对象方法
复用性好，分析、设计、实现三个阶段界限不明确【喷泉模型】
面向服务的方法
SOA
面向数据结构的开发方法
Jackson
需求分析☆
需求的任务
需求的过程
问题识别
分析与综合
编制需求分析文档
需求分析与评审
需求的分类
功能需求
非功能需求
设计约束
应用的工具
数据流图DFD
数据字典DD
判定表
基本条件项、条件项
基本动作项、动作项
基本动作项、动作项
判定树（决策树）
软件设计☆☆
软件设计的任务与活动
模块设计原则：高内聚、低耦合
内聚：从上到下内聚性越来越低，独立性越来越弱
1、功能内聚
模块内的所有元素都共同作用完成一个功能，缺一不可
2、顺序内聚
一个模块中的各个处理元素都密切相关于同一功能且必须顺序执行，前一个功能元素的输出就是下一个功能元素的输入
3、通信内聚
模块内的所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或产生相同的输出数据
4、过程内聚
指一个模块完成多个任务，这些任务必须按指定的过程执行
5、时间内聚
把需要同时执行的动作组合在一起形成的模块
6、逻辑内聚
指模块内执行若干个逻辑上相似的功能，通过参数确定该模块完成哪个功能
7、偶然内聚（巧合内聚）
一个模块内的各处理元素之间没有任何联系
耦合：从上到下耦合性越来越强，独立性越来越弱
1、无直接耦合
指的是两模块之间没有直接的关系，通过主模块的调用来实现的
2、数据耦合
两个模块之间有调用关系，传递的是简单的数据参数
3、标记耦合
两个模块之间传递的是数据结构
4、控制耦合
指一个模块调用另一个模块时，传递的是控制变量，被调用的模块通过该控制变量的值有选择地执行模块内的某一功能
5、外部耦合
模块间通过软件之外的环境联结（如I/O将模块耦合到特定的设备、格式、通信协议上）
6、公共耦合
通过一个公共数据环境相互作用的那些模块间的耦合
7、内容耦合
当一个模块直接使用另一个模块的内部数据，或通过非正常入口转入另一个模块内部
应用的工具
IPO图：输入处理输出图
PDL：程序描述语言
PAD：问题分析图
程序流程图
N/S盒图
软件测试
动态测试
黑盒测试
等价类划分
尽可能多的覆盖有效类、设计用例覆盖一个无效类
边界值分析
错误推测
因果图
白盒测试
语句覆盖
判定覆盖
条件覆盖
条件判定覆盖
路径覆盖
灰盒测试
静态测试
桌前检查
代码审查
代码走查
测试类型
单元测试
模块接口、局部数据结构、边界条件、独立的路径、错误处理
集成测试
模块间的接口和通信
系统测试
恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试
验收测试
（用户主导）有效性测试、软件配置审查、验收测试
回归测试
负载测试
压力测试
McCabe复杂度（环路复杂度）
有向图环路复杂度公式：V(G)=m-n+2
其中V(G)是有向图中的环路个数，m是G中的有向弧数，n表示的是G中农的节点数
其中V(G)是有向图中的环路个数，m是G中的有向弧数，n表示的是G中农的节点数
封闭区域数+1=环路复杂度
子主题
面向对象技术
面向对象的基本概念
对象：属性（数据）+方法（操作）+对象ID
类：（实体类/控制类/边界类）
继承与泛化：复用机制
封装：隐藏对象的属性和实现细节，仅对外公开接口（方法）
多态：不同对象收到同样的消息产生不同的结果
接口：一种特殊的类，他只有方法定义没有实现
重载：一个类可以有多个同名而不同参数类型不同的方法
模板类
消息和消息通道：消息是异步通信的
面向对象设计的7大原则
单一职责原则：设计目的的单一的类
开放-封闭原则：对扩展开放，对修改封闭
李氏（Liskov）替换原则：要依赖于抽象，而不是具体实现
容易被重写打破
依赖倒置原则：要依赖于抽象，而不是具体的实现；针对接口编程，不要针对实现编程
容易被重写打破
接口隔离原则：使用多个专门的接口比使用单一的总接口要好
组合重用原则：要尽量使用组合，而不是继承关系达到重用目的
迪米特（Demeter）原则（最少知识法则）：一个对象应当对其他对象尽可能少的了解
UML
结构图
类图
对象图
包图
组合结构图（UML2.0新增）
构件图
部署图：软硬件之间映射
制品图
行为图
用例图：系统与外部参与者的交互
顺序图：强调按时间顺序
通信图（协作图）
定时图（UML2.0新增）
状态图
活动图：类似程序流程图，并行行为
交互概览图
设计模式（23个）
创建型模式
工厂方法（Factory Method）模式
定义一个创建对象的接口，但由子类决定需要实例化哪一个类，工厂方法使得子类实例化的过程推迟
动态生成对象
抽象工厂（Abstract Factory）模式
提供一个接口，可以创建一系列相关或相互依赖的对象，而无需指定他们具体的类
生产成系列对象
原型（Prototype）模式
用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象
克隆对象
单例（singleton）模式
保证一个类只有一个实例，并提供一个访问它的全局访问点
单实例
构建器（Builder）模式
将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示
复杂对象构造
结构型模式
适配器（Adapter）模式
将一个类的接口转换成用户希望得到的另一种接口，它使原本不相容的接口得以协同工作
转换接口
桥接（Bridge）模式
将类的抽象部分和实现部分分离开，使它们可以独立地变化
组合（Composite）模式
将对象组合成树形结构以表示“整体.部分”的层次结构，使得用户对每个对象和组合对象的使用具有一致性
树型目录结构
装饰（decorator）模式
动态地给一个对象增加一些额外的职责。它提供了用子类扩展功能的一个灵活的替代，比派生一个子类更加灵活
增加职责
外观（facade）模式
定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用
对外统一接口
享元（flyweight）模式
提供支持大量细粒度对象的有效方法
文章共享文字对象
代理（proxy）模式
为其他对象提供一种代理以控制这个对象的访问
行为型模式
职责链（chain of responsibility）模式
通过给多个对象处理请求的机会，减少请求的发送者与参与者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求
传递职责
命令（command）模式
将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作
日志记录，可撤销
解释器（interpreter）模式
给定一种语言，定义它的文法表示，并定义一个解释器，该解释器是用来根据文法表示来解释语言中的句子
虚拟机的机制
迭代器（iterator）模式
提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示
数据库数据集
中介者（mediator）模式
用一个中介对象来封装一系列的对象交互，它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互
不直接引用
备忘录（memento）模式
在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态
观察者（observer）模式
定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有的依赖于它的对象得到通知并自动更新
联动
状态（state）模式
允许一个对象在其内部状态改变时改变它的行为
状态变成类
策略（strategy）模式
定义一系列算法，把它们一个个封装起来，并且使它们之间可相互替换，从而让算法可以独立于使用它的用户而变化
多方案切换
模板方法（template method）模式
定义一个操作中的算法骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重新定义算法的某些特定步骤
访问者（visitor）模式
表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作
计算机组成与体系结构(6分)
数据的表示——4☆
R进制数
R进制转十进制
按权展开法
十进制转R进制
短除法
二进制转八进制、十六进制
码制
原码
n位机器数来表示，最高位是符号位，其余的n-1位表示数值的绝对值，0表示正数，1表示负数
正数的原码、反码、补码都相同
反码
负数的反码是在除符号位以外的数分别取反
补码
负数的补码是在反码的基础上+1
通过负数的补码，求原码是：除符号位其他的位数取反，再+1
用补码来计算加减法
移码
在补码的基础上，符号位取反
浮点的运算
N=尾数*基数的指数
运算过程：对阶>尾数计算>结果格式化
特点
1、一般尾数用补码，阶数用移码
2、阶码的位数决定数的表示范围，位数越多范围越大
3、尾数的位数决定数的精度，位数越多精度越高
4、对阶时，小数向大数看齐
5、对阶是通过较小数的尾数算术右移实现的
运算器与控制器——4☆
运算器
算术逻辑单元——ALU
处理数据，实现对数据的算术运算和逻辑运算
累加寄存器——AC
通用寄存器——当运算器的算数逻辑单元执行算术运算或逻辑运算时，为ALU提供一个工作区，用来暂存数据
每一个CPU中至少要有一个累加器
每一个CPU中至少要有一个累加器
数据缓冲寄存器——DR
写内存时，暂存指令或数据
状态条件寄存器——PSW
保存由算术指令和逻辑指令运行或测试的结果建立的各种条件码内容，主要分为状态标志和控制标志。
通常一个操作数产生一个运算结果，一个逻辑操作产生一个判决。
(争议：有时候也属于控制器的一部分）
通常一个操作数产生一个运算结果，一个逻辑操作产生一个判决。
(争议：有时候也属于控制器的一部分）
控制器
程序计数器——PC
寄存信息和计数，保存将要执行的下一条指令的地址
指令寄存器——IR
指令从存储器中读出来，放到指令寄存器中暂存，存储即将要执行的指令
地址寄存器——DR
保存当前CPU所要访问的内存单元的地址
指令译码器——ID
对指令中的操作码字段进行分析解释
指令包括操作码和地址码
指令包括操作码和地址码
时序部件
为每条指令按时间顺序提供应有的控制信号
Flynn分类法
单指令流单数据流——SISD
一个控制部分
一个处理器
一个主存模块
一个处理器
一个主存模块
代表：但处理器系统
单指令流多数据流——SIMD
一个控制模块
多个处理器
多个存储模块
多个处理器
多个存储模块
特性：各处理器以异步的形式执行同一条指令
代表：并行处理机、阵列处理机、超级向量处理机
多指令流单数据流——MISD
多个控制模块
一个处理器
一个存储模块
一个处理器
一个存储模块
特性：被证明不可能，至少是不实际
代表：目前没有，有文献称流水线计算机为此类
多指令流多数据流——MIMD
多个控制模块
多个处理器
多个存储模块
多个处理器
多个存储模块
特性：能够实现作业、任务、指令等各级全面并行
代表：多处理机系统、多计算机
指令相关概念
指令就是机器语言的一个语句，是一组有意义的二进制代码
指令：操作码字段+地址码字段
操作码：加法、减法、取数、村数
按照地址码的结构可分为：三地址指令、二地址指令、一地址指令、零地址指令
寻址方式
立即寻址方式
特点：操作数直接在指令中，速度快，灵活性差
直接寻址方式
特点：指令中存放的是操作数的地址
间接寻址方式
特点：指令中存放了一个地址，这个地址对应的内容是操作数的地址
寄存器寻址方式
特点：寄存器存放操作数
寄存器间接寻址
特点：寄存器内存放的是操作数的地址
CISC与RISC
复杂指令集系统CISC
指令数量多，使用频率差别大，可变格式
支持多种寻址方式
微程序控制技术（微码）
研发周期长
精简指令集系统RISC
指令数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有load/store操作内存
支持的寻址方式少
增加了通用寄存器（累加器）；硬布线逻辑控制为主，适合采用流水线
优化编译，有效支持高级语言
流水线技术——4☆
概念
流水线周期：1条指令在执行阶段中执行时间最长的一段t
流水线执行时间：
理论公式：（n-1）*t+（t1+t2+...+tk）
实践公式：k*t+(n-1)*t
吞吐率
单位时间内流水线所完成的任务数量或输出的结果数量
吞吐率（TP）=（指令条数）/（流水线执行时间）
最大吞吐率=1/t
存储系统——4☆
层次化存储结构
CPU内部通用寄存器
最快，容量小，成本高
Cache（高速缓存）
按内容存取
Cache概念
在计算机的存储体系中，Cache的访问速度最快（仅次于CPU）
使用Cache改善系统性能的依据是程序的局部性原理【例如改善抖动】
时间局部性
空间局部性
Cache访问命中率
CPU要访问的内容恰好在Cache中，即为命中，否则没有命中
t1为Cache的周期时间，t2表示主存储器周期时间，h表示命中率，则【Cache+主存储器】的平均周期=h*t1+(1-h)*t2
Cache映像
直接相连映像
硬件电路比较简单，单冲突率很高
全相连映像
电路难于设计和实现，只适用于小容量的Cache，冲突率较低
组相连映像
直接相连与全相连的折中
地址映像
将主存与Cache的存储空间划分为若干大小相同的页（块）
主存储器（内存）
随机存储器（RAM）和只读存储器（ROM）
主存——编址与计算
按字编址
存储体的存储单元是字存储单元，即最小寻址单位是一个字
按字节编址
存储体的存储单元是字节存储单元，即最小寻址单位是一个字节
外存（辅存）
速度慢。硬盘、光盘、U盘
总线系统
一条总线同一时刻仅允许一个设备发送，但允许多个设备接收
总线的分类
数据总线
在CPU与RAM之间来回传送需要处理或需要储存的数据
地址总线
用来指定在RAM之中存储的数据的地址
控制总线
将微处理器控制单元的信号，传送到周边设备，一般常见为USB Bus和1394 Bus
可靠性
串联系统与并联系统
N模混合系统
校验码——3☆
码距：任意两个码字之间变化的二进制位数称为数据校验码的码距
奇偶校验：可检查1位的错误，不可纠错
奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数
偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数
循环冗余校验CRC：可检错，不可纠错【模2除法】
海明码：既可以检错，也可以纠错
操作系统
进程管理
进程概念
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成
进程与程序的区别：进程是程序的一次执行过程，没有程序就没有进程。
程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，程序就永远存在。
程序是一个静态的概念，进程是一个动态的概念。
程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，程序就永远存在。
程序是一个静态的概念，进程是一个动态的概念。
进程的状态
进行、就绪、等待 三态模型
进程的同步和互斥
同步：合作进程间的直接制约关系
互斥：是申请临界资源进程间的间接制约关系
趋势图☆☆☆
信号量与PV操作☆☆☆☆
概念
临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机
临界区：每个进程中访问临界资源的那段代码成为临界区
信号量：一种特殊的变量S
P是荷兰语Passeren，V是荷兰语Verhoog。
P操作表示申请一个资源，V操作表示释放一个资源
P操作表示申请一个资源，V操作表示释放一个资源
互斥模型（争夺打印机资源）和同步模型（生产者、消费者模型）
死锁及银行家算法☆☆☆☆
死锁
产生的条件
互斥条件
请求保持条件
不可剥夺条件
环路条件
在不发生死锁的情况下，最少需要的多少个系统资源：
给每个进程分配他所需要的资源数少1，再给出一个公共资源
给每个进程分配他所需要的资源数少1，再给出一个公共资源
死锁的处理
鸵鸟策略（不理睬策略）
预防策略：破坏4个必要条件
预先静态分配法：破坏不可剥夺资源条件
资源有序分配法：破坏环路条件
避免策略
银行家算法：资源分配规则
当一个进程对资源的最大需求不超过系统中的资源数时可以接纳该进程
进程可以分期请求资源，但请求的总数不能超过最大需求量
当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源
检测死锁
解除死锁
资源剥夺法
撤销进程法
存储管理
段页式存储☆☆☆☆
页式存储
将程序与内存划分为同样大小的块，以页为单位将程序调入内存
优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销，可能产生抖动现象
段式存储
按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样
优点：多道程序共享内存，每道程序修改互不影响
缺点：内存利用率低，内存碎片浪费大
段页式存储
段式与页式存储的综合体，先分段，再分页，1个程序有若干个段，每个段可以有若干页，每个页的大小相同，但每个段的大小不同
优点：空间浪费小，存储共享容易，存储保护容易，能动态连接
缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降
页面置换算法☆
最优算法（OPT）
随机算法（RAND）
先进先出（FIFO）算法
可能产生抖动
最近最少使用（LRU）算法
不会产生抖动。LRU的理论依据是“局部性原理”
时间局部性
刚被访问的内容，立即又被访问
空间局部性
刚被访问的内容，临近的空间很快被访问
磁盘管理
存取时间=寻道时间+等待时间，寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。
磁盘调度算法
先来先服务（FCFS）
最短寻道时间优先（SSTF）
扫描算法（SCAN）
循环扫描（CSCAN）算法
文件管理
索引文件☆☆（从0开始）
直接索引
一级间接索引
二级间接索引
三级间接索引
树型目录结构
绝对路径与相对路径☆☆☆
位示图☆☆
作业管理
作业调度算法
先来先服务
时间片轮转法
短作业优先法
最高优先权优先法
高响应比优先法
响应比=作业等待时间/执行时间
设备管理
虚设备与SPOOLING技术☆
Spooling是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”，spooling技术通过磁盘实现
数据传输控制方式（自上而下，越来越高效）
程序控制（查询）方式：分为无条件传送和程序查询方式2种
特点：方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率
程序中断方式：与程序控制方式相比，中断方式是因为CPU无需等待而提高了传输请求的响应速度
DMA方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效
通道方式
I/O处理机
数据库系统
数据库模式☆☆
三级模式—两层映射
外模式（用户模式或子模式）【视图级】：逻辑存储
是用户与数据库系统的接口
概念模式（模式）【表级】
是数据库中全部数据的逻辑结构和特征的描述
内模式（存储模式）【文件级】：物理存储
两层映射
保证了数据库中的数据具有较高的逻辑独立性和物理独立性
数据的物理独立性：当数据库的内模式发生改变时，数据的逻辑结构不变，只需要改变模式与内模式之间的映像
数据的逻辑独立性：是指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结构改变后，只需修改外模式与模式之间的映像
模式/内模式映像
外模式/模式映像
数据库设计过程
需求分析
数据流图
数据字典
需求说明书
概念结构设计
E-R模型
一个实体转换为一个关系模式
联系转关系模式
1:1联系：可将联系合并至任意一端的实体关系模式中
1：n联系：可将联系合并至n端实体关系模式中
m:n联系：联系必须单独转换成关系模式
逻辑结构设计
关系模式
并
交
差
笛卡尔积
投影π
从关系的垂直方向进行运算，在关系R中选出若干属性列A组成新的关系
选择
从关系的水平方向进行运算，从关系R中国选出满足给定条件的诸元祖
连接（自然连接）
在结果集中去除重复属性，重复记录
物理设计
ER模型☆☆☆☆☆
关系代数☆☆☆
规范化理论☆☆☆☆☆
函数依赖
部分函数依赖
传递函数依赖
键
候选键：可以有多个，唯一标识元祖，且无冗余
主键：从候选键中任选一个
外键：其他关系的主键
求候选键
1、将关系的函数依赖关系，用“有向图”的方式表示
2、找出入度为0的属性，并将该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有得结点，则该属性集即为关系模式的候选键
3、若入度为0的属性集不能遍历图中所有结点，则需要尝试的将一些中间结点（既有入度，也有出度的结点）并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键
主属性和非主属性
组成候选码的属性就是主属性，其他的就是非主属性
范式
第一范式1NF
在关系模式R中，当且仅当所有域只包含原子值，即每个属性都是不可再分的数据项，则称关系模式R是第一范式
第二范式2NF
当且仅当关系模式R是第一范式，且每一个非主属性完全依赖候选键（没有不完全依赖）时，则称关系模式R是第二范式
第三范式3NF
当且仅当关系模式R是第二范式，且R中没有非主属性传递依赖于候选键时，则称关系模式R是第三范式
BC范式BCNF
设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选键
消除主属性对候选码的部分依赖和传递依赖
1NF包含2NF包含3NF包含BCNF
模式分解
保持函数依赖分解
无损分解
指将一个关系模式分解成若干个关系模式后，通过自然连接和投影等运算仍能还原到原来的关系模式
表格法
公式法：
如果R的分解为p={R1,R2}，F为R所满足的函数依赖关系，分解p具有无损连接性的充分必要条件：R1∩R2 —> （R1-R2）或 R1∩R2 —> （R2-R1）
只适用于拆分为2个的模式分解
有损分解
SQL语言☆☆☆☆
并发控制☆☆
事务
原子性
一致性
隔离性
持续性
并发操作带来的问题
丢失更新
不可重复读
读“脏”数据
解决并发操作产生的问题
S封锁（共享锁或读锁）
X封锁（排它锁或写锁）
两段锁协议
数据库完整性约束☆
实体完整性约束
主键
非空
唯一标识
参照完整性约束
外键
若无，则为空
若有，则必须为正确存在
用户自定义完整性约束
触发器
数据结构与算法
数据与矩阵☆☆
数组
一位数组
二维数组
按行存储
按列存储
矩阵
稀疏矩阵
上三角矩阵
下三角矩阵
线性表☆☆☆☆☆
顺序表
链表
单链表
循环链表
双向链表
链表的基本操作
单链表的删除结点
单链表插入结点
双向链表删除结点
双向链表插入结点
队列
先进先出
栈
先进后出
循环队列
队列为空的条件：head=tail
广义表☆☆
广义表是n个元素组成的有限序列，是线性表的推广
通常用递归形式进行定义，记做：LS（a0,a1,..,an），
其中LS是表名，ai是元素，它可以是表（称做子表），也可以是数据元素（称为原子），n是广义表的长度，递归定义的重数就是广义表的深度
其中LS是表名，ai是元素，它可以是表（称做子表），也可以是数据元素（称为原子），n是广义表的长度，递归定义的重数就是广义表的深度
基本运算：取表头head（LS）和表尾tail（LS）
表头只取第一个元素，表尾可以取除了第一个元素之外的所有元素
树与二叉树☆☆☆☆☆
结点的度
树的度
叶子结点
分支结点
内部结点
除了根结点和叶子结点之外的结点
父结点
子结点
兄弟结点
层次（树的深度）
二叉树
满二叉树
深度为k的二叉树有2的k次方-1个结点
完全二叉树
二叉树的遍历
前序遍历
根左右
中序遍历
左根右
后序遍历
左右根
层次遍历
从上到下，从左到右，逐层遍历
树转二叉树
孩子结点——左子树结点
兄弟结点——右孩子结点
兄弟结点——右孩子结点
查找二叉树
二叉树排序，左子树结点小于根结点，右子树节点大于根结点
插入结点
删除结点
最优二叉树（哈夫曼树）
树的路径长度
权
带权路径长度
树的带权路径长度（树的代价）
值越大的月靠近根结点，权重越大越靠近根结点
线索二叉树
平衡二叉树
任何结点的左子树深度与右子树的深度差小于1
图☆☆
完全图
无向图
有向图
图的存储
邻接矩阵
邻接表
图的遍历
深度优先
广度优先
图的拓扑排序
用有向边表示活动之间开始的先后顺序，这种有向图称为用定点表示活动网络，称为AOV网络
图的最小生成树
排序与查找☆☆☆☆☆
时间复杂度和空间复杂度☆☆☆☆☆
算法基础及常见的算法☆☆☆☆☆
0 条评论
下一页
