软考-软件设计师
2021-08-06 15:29:05 4 举报AI智能生成
软考复习提纲
作者其他创作
大纲/内容
下午
数据流图(第六章)
实体名字
存储名字
缺失的数据流
结构化语言描述某加工
某数据流组成
数据流如何保持平衡
父图中某个加工的输入输出数据流必须与其子图的输入输出数据流在数量和名字上相同.
父图的一个输入输出数据流对应子图中几个输入输出数据流,而子图中的组成这些数据流的数据项正好是父图中的一个数据流.
父加工,分解为了哪几个子加工
技巧
1、父图子图平衡
2、看圆角矩形（加工）是否缺少输入，或者输出
3、数据守恒（换句话说，输入是否足够产生输出）
UML(第七章)
图的类型
用例图
包含<include> 抽取公共用例,必然会执行的用例
扩展 <extend> 可选用例
泛化关系<generalization> 父子关系
参与者是组织或者人 某某系统,某某人
extend 如果,则 分支条件
查询用例 <--<extends>--修改
扩展用例指向基准用例
查询用例 <--<extends>--修改
扩展用例指向基准用例
include 包含必须完成 用例1 才会执行 用例2
登陆用例<--<include>--查询用例
先登陆才能查询
登陆用例<--<include>--查询用例
先登陆才能查询
类图
属性
方法
多重度
1
0.. *
n..* 至少几个
乐队 0..* 歌手 一名歌手可以属于 0个或多个乐队
歌手 2..* 乐队 乐队由两名以上的歌手组成
关系
依赖
--▶ 依赖关系 虚线 实心箭头 (使用)
泛化
-▷ 实线空心箭头 父子关系 对于类
聚合
-◇ 实现空心菱形 不同声明周期
组合
-◆ 实线实心菱形 同一生命周期
实现
-----▷ 虚线空心箭头 对于接口实现
对象图
类图的实例,有生命周期
时序图
活动图
类似于流程图
粗横线 并行分支
菱形 分支
状态图
通信图
又叫通讯图
实例消息 1 1.1 1.2 等等
构件图
数据库分析与设计,ER图(第九章)
ER模型补充
联系类型
1:1
1:*
*:*
部门 1 <--> * 员工
员工 * <--> 1 部门
学生 * <--> * 科目
ER模型转关系模式
关系模式补充
数据结构与算法应用(第三章&第八章)
贪心
0-1背包问题
每一步取最优,但得不到最优解
回溯
迷宫
到底再回来
分治
快排 归并排序
分而治之
动态规划
局部最优解
每一步都是最优解,存在下最优解查表来解决后面的问题.
面向对象程序设计(第十二章)
设计模式概念
java语法
作用域
+ public
- private
# protected
抽象类
abstract
抽象类中都是抽象方法 要写 abstract
接口
interface
implements
上午
计算机组成原理与体系结构(第一章)
数据的表示
进制转换
按权展开法(任意进制转换为十进制)
R^k 底数是R(R进制) 指数是k k是小数点的距离
七进制:605.02 = 6*7^2+5*7^0+2*7^-2
二进制:10101.01=1*2^4+1*2^2+1+1*2^-2
十进制转换为R进制
短除法
除R,取余然后逆序排列
整数
37/2=18 1
18/2=9 0
9/2=4 1
4/2=2 0
2/2=1 0
2/1=0 1
二进制:100101
18/2=9 0
9/2=4 1
4/2=2 0
2/2=1 0
2/1=0 1
二进制:100101
2/8/16进制转换
2转8
每三位转换
10101
补0 010 101 = 25
010 = 2
101 = 5
补0 010 101 = 25
010 = 2
101 = 5
2转16
每四位转换
1C00
0001
1100
0000
0001
1100
0000
浮点进制
乘法
乘以R,取整
0.375=
最高位,首位符号位0正数,1负数,不足字节数补0
原码
1 = 0000 0001
-1 = 1000 0001
1 -1 = 1000 0010
= -2 原码不能在计算机中直接进行计算的
范围 8位
-(2^x-1 - 1) ~ 2x^1-1 = 2^7 -127 ~ 127
反码
1 = 正数与原码相同 0000 0001
-1 = 1111 1110 除了符号位与原码取反
1 -1 = 1111 1111
= -2 原码不能在计算机中直接进行计算的
范围 8位
-(2^x-1 - 1) ~ 2x^1-1 = 2^7 -127 ~ 127
补码
1 = 正数与原码相同 0000 0001
-1 = 原来反码的基础上+1 1111 1111
1 -1 = 0000 0000
范围 8位
-(2^x-1 ) ~ 2x^1-1 = 2^7 -128 ~ 127
由于±0 都是 0000 0000 所以少占用了一位
移码
浮点运算的阶码 在补码的基础上 首位取反
1 = 1000 0001
-1 = 0111 1111
1 -1 = 1000 0000
浮点数运算
N=M*R^e M是尾数 e是指数 R是基数
1000= 1.0*10^3 1.0->尾数 10->基数 3->指数
119= 1.19*10^2
低对高
0.119*10^3
1.119*10^3 = 1119
格式化->小数点左边的数据不能超过一位,也不能是0.
119= 1.19*10^2
低对高
0.119*10^3
1.119*10^3 = 1119
格式化->小数点左边的数据不能超过一位,也不能是0.
对阶->尾数计算->结果格式化
考点例题
多少块芯片组成多大的存储空间
计算IP地址,子网掩码
计算机结构
CPU如何划分
运算器(运算/加减法)
算术逻辑单元(ALU)
运算职能,加减法
累加寄存器(AC)
运算过程中存储中间值
数据缓冲寄存器(DR)
内存读写操作,暂存数据
状态条件寄存器(PSW)
运算过程中 相关标志位 例如 进位/中断等状态信息
控制器
程序计数器PC
记录执行下一条指令
指令寄存器IR
暂存当前正在执行的指令
指令译码器ID
指令通常由操作码和地址码两部分组成,译码器去解释指令
时序部件
主机(CPU/主存)+外设(鼠标/显卡/声卡/硬盘)
Flynn分类法
单指令流单数据流 SISD
控制器:1
处理器:1
主存模块:1
处理器:1
主存模块:1
单处理器系统
单指令流多数据流 SIMD
控制器:1
处理器:多个
主存模块:多个
处理器:多个
主存模块:多个
一条指令会有多个运算部件去同时处理
各处理器以以部的形式执行一条指令
并行处理机
阵列处理机(处理数组类型的运算)
超级向量处理机
阵列处理机(处理数组类型的运算)
超级向量处理机
多指令流单数据流 MISD
控制器:多个
处理器:1个
主存模块:多个
处理器:1个
主存模块:多个
理论模型
被证明不实际
被证明不实际
多指令流多数据流 MIMD
控制器:多个
处理器:多个
主存模块:多个
处理器:多个
主存模块:多个
能够实现作业/任务指令等各级全面并行
多处理机系统
多计算机
多计算机
CISC&RISC
CISC(Complex Instruction Set Computers,复杂指令集计算集)
指令:数量多,使用频率差别大,可变长格式.
寻址方式:支持多种
实现方式:微程序控制术(微码)
其他:研制周期长
寻址方式:支持多种
实现方式:微程序控制术(微码)
其他:研制周期长
定制划,指令数量多.
RISC(Reduced Instruction Set Computers)
指令:数量少,使用频率接近,定长格式,大部分为单周期指令,操作寄存器.只有load/store操作内存.
寻址方式:支持方式少
实现方式:增加了通用寄存器,硬不限逻辑控制为主,适合采用流水线
其他:优化编译,有
寻址方式:支持方式少
实现方式:增加了通用寄存器,硬不限逻辑控制为主,适合采用流水线
其他:优化编译,有
流水线技术(pipeline)
程序执行时多条指令重叠进行操作的一种准并行处理实现技术
取指->分析->执行,无需等待第一条指令执行,则开始第二条指令取指
流水线周期=执行时间最长的一段
指令执行时间+(指令条数-1)*流水线周期
取值2ns,分析2ns,执行1ns
理论时间=(t1+t2+tk)+(n-1)Dt Dt:流水线周期
(2+2+1)+99*2=203 首先用理论公式
(2+2+1)+99*2=203 首先用理论公式
实践公式=(k+n-1)*Dt k分成几段就是几
(3+99)*2=204
(3+99)*2=204
流水线吞吐率
单位时间能够处理任务的数量
TP=指令条数/流水线执行时间
依照上个例子 指令条数100 流水线执行时间 203 100/203
最大吞吐率:TP(max)=Lim(n->∞)*n/(k+n-1)&Dt = 1/Dt
流水线加速比
完成同一批任务不使用流水线执行时间与使用流水线时间的比值
不适用流水线时间/使用流水线时间
存储系统
存储的结构
CPU->寄存器
cache-->按内容存取
提高CPU输入输出的速率,突破冯诺伊曼瓶颈
依据局部性原理改善系统性能
cache访问命中率(H),t1周期时间,t2为主存储的周期时间. t3=h*t1+(1-H)*t2
例如:t1=1ns,t2=1ms=1000ns,H=95% 95%*1ns+5%*1000ns=50.95ns 提升约 20倍
局部性原理
时间局部性
循环体
空间局部性
数组
工作集理论
工作集是进程运行时被频繁访问页面的集合
内存(主存)
分类
随机存储器(内存)
DRAM(Dynamic RAM) - SDRAM
SRAM(Static RAM)
只读存储器
MROM(Mask ROM)
PROM(Programmable ROM)
EPROM(Erasable PROM 可擦除的PROM)
flash member(闪存)
编址
内存地址AC000H到C7FFFH,共有()k个地质单元. 大的减小的+1
AC000H到C7FFFH = (C7FFF+1)-AC000=C8000-AC000=C8-AC=11 - 10 | 8+16-12 = 1|12 = 1C000H
k个=1024b=2^10
1C000 转十进制=1*16^4+12*16^3=114668 / 1024 = 112
如果上诉内存地址(112)按字编址(16bit),由28片存储构成,已知构成此内存的芯片每片有16k存储单元,则该芯片每个存储单元存储(N)位.
112k*16bit/28*16k*N 则 N=4
外存(辅存)-->硬盘/光盘/U盘
磁盘
磁道
类似于年轮 一圈一圈
扇面
类似于蛋糕 一角
扇区
扇面被磁道分割的一小块,数据存储于此
存取时间=寻道时间+等待时间(定位磁道+旋转时间)
旋转时间=平均时间(磁盘转一圈时间),最好情况不需要转动,最坏情况是转一圈的时间.
假设某磁盘划分成11个物理块(扇区),每块存放1个逻辑记录R0-R10,如果磁盘的旋转周期是33ms,磁头当前处于R0位置,
若系统使用单缓冲区顺序处理这些记录,每个记录处理时间为3ms,则处理这11个记录最长时间为(X);若对信息存储进行优化分布后,处理11个记录的最少时间为(Y)
若系统使用单缓冲区顺序处理这些记录,每个记录处理时间为3ms,则处理这11个记录最长时间为(X);若对信息存储进行优化分布后,处理11个记录的最少时间为(Y)
转一圈=33ms,转动一格是3ms,写入缓存处理是3ms
(33+3)*10+6
r0写入缓存区,转动到了r2,当r0处理完需要转动一圈到r1,反复处理以上内容到r9. 0-9=10相当于 转动+处理 *10,加最后一个处理 写入转动一格3+3;
R0R6R1 R0处理完正好读到 R1,读取和处理分别是3ms,那么最快是11*(3+3)=66ms
(33+3)*10+6
r0写入缓存区,转动到了r2,当r0处理完需要转动一圈到r1,反复处理以上内容到r9. 0-9=10相当于 转动+处理 *10,加最后一个处理 写入转动一格3+3;
R0R6R1 R0处理完正好读到 R1,读取和处理分别是3ms,那么最快是11*(3+3)=66ms
总线系统
分类
内部总线
计算机内部外围的芯片与处理器的级别,芯片级别的
系统总线
插线板
PCI
VGA
数据总线
32位 则 一个字就是32个bit位 数据的宽度
地址总线
32 2^32 = 4g
控制总线
外部总线
模型
串联(其中一个子系统失效则失效)
可靠度
R1-RN 串联 = R1*R2*R3...*Rn
失效率
累加 H1+H2+H3
近似公式,可能有误差
并联(全部子系统失效才失效)
可靠度
R=1-(1-R1)*(1-R2)*....(1-Rn)
失效率
1-可靠度
模冗余系统与混合系统(多个同样系统冗余计算,汇总到表决器(少数服从多数),输出)
R=
混合系统 先识别最终是串联还是并联
效验码
CRC校验码
可以检错但不能纠错的一种编码
原始报文为11001010101,生成多项式为x^4+x^3+x+1 转为二进制 11011(根据多项式成成进制位数为是1或0)
11001010101 ,在原始编码加多项式长度-1个0
11001010101 0000 摸二 11011 = CRC编码 0011
海明校验码
可以检错也可以纠错
校验位:信息为 2^r>=4+r+1
检错(检查错误)&纠错(纠正错误)
码距
二进制举例,当一位长度A=1 B=0则 码距是1
若用2位长度 A=11 B=00 码距是2
若用3位长度 可选用111,000作为合法编码,最小码距是3
在一个码组内为了检测e个误码,最小码距d应该满足 d>=e+1
在一个码组内为了纠正t个误码,要求最小码距d应该满足 d>=2t+1
数据结构与算法基础(第三章)
数组与矩阵
数组(存储地址的计算)
一维数组
a[i]的存储地址为:a+i*len len是元素的字节数
二维数组a[m][n]
a[i][j]按行存储 a+(i*n+j)*len
1|2|3|4|
5|6|7|8|
5|6|7|8|
a[i][j]按列存储 a+(j*m+i)*len
1|3|5|7|
2|4|6|8|
2|4|6|8|
5*5的二维数组,元素占2个字节,求a[2][3]按行优先的存储地址
a[2][3]=a+(2*5+3)*2=a+13*2
矩阵
稀疏矩阵(大量元素都是0)
上三角矩阵(上面是满的,下面大部分是0)
(2n-i+1)*i/2+j
下三角矩阵(下面是满的,上面大部分是0)
在矩阵中下标分别为i和j的元素,对应的一维数组的下标公式为:(i+1)*i/2+j
计算某一个元素一维数组的下标
线性表
栈(弹夹)
先进后出
队列(排队)
先进先出(FIFO)
循环队列
头尾相接,一个环.
(tail+1)%size=head
链表(指针&数据)
单链表
有头节点(不存储数据),所有的操作是一致的,否则需要特殊处理头节点.
循环链表
尾元素指向头节点,无需重新定位到头节点
双向链表
广义表
冠以表是n个元素组成的有限序列,是线性表的推广,通常用递归形式定义.
长度:最外层的表长度
深度:包含括号的重数,
head=最外层的第一个表元素
tail=表尾,除了第一个元素外的所有元素
有广义表 LS1=(a,(b,c),(d,e)) 长度? 深度? 3,2
有广义表 LS1=(a,(b,c),(d,e)) 要把广义表的b元素取出? tail(b,c),(d,e) head(b,c) head(b)
树与二叉树
概念
结点的度
拥有的孩子的个数
树的度
所有节点数最高的,就是树的度(二叉树整个树的度为2),子节点的个数
叶子节点
没有孩子节点,末端节点,结点的度是0
分支节点
子主题
内部节点
非叶子节点,非根节点
父节点
子节点
兄弟节点
平级节点
层次
根节点1层,叶子节点=树的高度,
二叉树
满二叉树
所有子节点没有缺失的部分
完全二叉树
除右边叶子节点缺失,其余都是满的 1,2,3,4,5,6
非完全二叉树
1,2,3,4,5,7 | 1,2,4,5
二叉树第i层上最多有 2^i-1
二叉树遍历
1
(2,3)
(4,5) (0,6)
(7,0)
(0,8)
1
(2,3)
(4,5) (0,6)
(7,0)
(0,8)
前序
根,左,右.
1,2,4,5,7,8,3,6
中序
左,根,右
4,2,7,8,5,1,3,6
后序
左,右,根
4,8,7,5,2,6,3,1
层次遍历
1,2,3,4,5,6,7,8
树转二叉树
孩子节点-转为 左子树节点
兄弟节点 - 转为 右子树节点
排序二叉树
左小于根,根小于右
插入:1.若节点已存在,则不再插入.2.若树为空树,则插入3.将要插入的值与父节点比较确定左子节点还是右子节点
删除 1.若是叶子节点直接删除,2.删除的节点只有一个孩子节点,则将父节点与子节点相连.3.若p节点有两个子节点,则在其左子树上用中序遍历查找关键之最大的节点s,用节点s的值代替节点p的值(左子树的最大值).删掉s节点,再执行上诉1,2.
最优二叉树(哈夫曼树)
概念
树的路径长度=一段一段(边)累加
权:某个叶子节点的数值出现的频度
带权的路径长度:累加所有叶子节点(路径长度*权值(边*权值))
树的带权路径长度:累加所有的带权路径长度(树的代价),排除构造出的节点累加叶子节点的路径长度
构建一条哈夫曼树目标是树的带权路径长度要最短(缩短权重大的路径,把权重大的放在上面)
如何构造哈夫曼树
5,29,7,8,14,23,3,11
选权值最小的,构造一棵小树
哈夫曼编码
0,1编码 左节点为0,右节点是1.到此节点的编码就是哈夫曼编码
线索二叉树
二叉树的叶子节点有大量空的指针,利用空闲资源.方便遍历
有虚线的渐线把节点串起来
前序线索二叉树
左子树的指针指向当前遍历节点的前驱节点,右子树指向后序节点
中序线索二叉树
后序线索二叉树
平衡二叉树
定义
提高排序二叉树的平衡,让其层更少.
任意节点的深度相差不超过一
每节点的平衡度只能为-1,0,或1
平衡度,叶子节点的平衡度是0. 左是正数的边累加,右是负数边累加. 根的是左子树的层数 - 右子树的层数
动态平衡问题
旋转
图
图的概念
存在环路-连成一个圈
无向图
节点间(边)没有方向
有向图
边有方向,
完全图
所有的边都连满了
邻接矩阵存储图
5个节点=矩阵5*5矩阵,矩阵的值,有边就记1,没有边就记0
对角是有一致性,可以存上三角或下三角矩阵
邻接表
节点的表
用链表存储
节点-距离
图的遍历
深度优先
先访问下一层次,类似于树的前需遍历
广度优先
先访问相邻节点,再访问下一层次
拓扑排序
用一个序列表达一个图当中哪些事件可以先执行,哪些事件可以后执行.
执行完的边可以划掉,如果没有节点指向自己就可以执行了.
图的最小生成树
普利姆算法
红点选出边最短的,且不能形成环,一旦选出则蓝点变红点
克鲁斯卡尔算法
1.先确定边数,2.选最短的边,且不成环
树的节点是N , N-1条边就是树 >=N条边就是图
排序与查找
排序
算法
归并排序
计数排序
桶排序
基数排序
插入类
直接插入排次序
顺序比较,插入到合适的地方. n,稳定
1.从第二个开始,向前比较,如果小于前一个则交换,
希尔排序
分为len/2个组,逐个组用直接插入排序
交换类
冒泡排序
快速排序
选择类
选择排序
堆排序
概念
稳定:排序后顺序是否一致,稳定:一致,不稳定:不一致
内排序/外排序:内:只在内存,外:外部存储
查找
顺序查找
n+1/2(等差队列)
O(n)
二分查找
序列首先要有序(ASC/DESC)
1+12/2=6,下标中间值->取整;
确定左右.
1+5/2=3
确定左右.
确定左右.
1+5/2=3
确定左右.
O(logn)
散列表
hashtable
算法基础及常见的算法
分治算法(分解Divide|解决Conquer|合并Combine)
贪心
DP
回溯
算法的特性
有穷性,确定性,有效性
输入>=0,输出>=1
操作系统知识(6-8分)(第四章)
进程管理
进程状态
三态模型
运行/就绪/等待
等待(等待某个事件发生)-->就绪(调度)-->运行
运行(等待某资源/事件)-->等待
运行(时间片轮转,让出cpu)-->就绪
五态模型
运行/活跃就绪/活跃阻塞 新增静止就绪/静止阻塞
前趋图
表达并行以及执行的先后约束关系
同步与互斥
互斥
在某一时刻,只允许某一个进程访问资源. e.g. 独木桥 ,反义词是共享
同步
执行速度存在差异,在一定情况下等待.反义词是异步.
生产者消费者
单缓冲区
缓冲区只有一个资源(互斥资源),同一时刻只能由一个生产者或者消费者访问资源
多缓冲区
缓冲区有多个资源,待缓冲区满了后才会进行同步等待.
PV操作
临界资源
进程间需要互斥方式对其进行共享的资源,如打印机/磁带机等
临界区
每个进程中访问临界资源的那段代码称为临界区(访问临界资源的代码段)
信号量
一种特殊的变量
P操作
s=s-1;s<0?push queue&wait:goon
V操作
s=s+1;s<=0?pull queue&wait:goon
PV操作与前趋图
无依赖则V(S自己),有依赖则先P(S前置节点)之后V(S自己)
每个箭头对应一个信号量,从左到右,从上到下,减头的起点操作是V操作,减头的结尾是P操作.
死锁问题
最少多少个资源不会产生死锁
大于每个资源的n-1个,比如ABC各需要5各,则3*4+1=13个就不会
k*(n-1)+1
死锁条件
互斥
共享则不会死锁
环路等待
A->B B->C C->A
保持和等待
这个进程会保持自己的资源,等待别人释放资源
不剥夺
系统不会把某个进程的资源剥夺掉分配个其他系统
避免死锁
共享资源
打破四大条件
有序资源分配法
银行家算法
如果无法偿还资源,则不会分配资源
计算所剩资源数
总数-已分配
还需资源数
最大需求-已分配
当前置进程执行完,会释放刚刚分配的资源和已占用的资源
存储管理
段页式存储
逻辑地址和物理地址的转化
将页号和页内地址分开
根据页面大小 4k=2^12 说明一个页的页内地址是12位 ,高于12位的就是页号
逻辑地址 5A29H 每4位是一个16进制位 所以 5是页号 页内地址是A29H
页号5 对应的物理块号(页帧号)
页面淘汰(按照顺序 在内存 没有访问
状态位=在内存中 淘汰在内存中的
访问位=没有 淘汰没有访问的
修改位= 没有 修改过
页式存储
用户程序等分为4k的页
按页大小存储
段式存储
按程序段存储
段页式存储
混合段和页
快表
按内容存储
页面置换算法-分区存储组织
首次适应算法
第一个匹配够的
最佳适应算法
第一个匹配够的,则分配剩余的空间链到之前的空间
最差适应算法
最小的块分配
循环首次适应算法
空闲区域连城环状,按顺序链接
典型算法
最优
随机
先进先出
最少使用
试题
访问了多少次内存
如果用了快表直接访问内存则是页面数*1,
否则每次都需要操作两次内存 页面数*2
否则每次都需要操作两次内存 页面数*2
meifou
缺页中断次数
指令1次 操作数2次
文件管理
索引文件
索引分类
直接索引,一级/二级/三级简介索引
数据块1KB,每个地址4字节,每个数据块快也存储256个地址, 逻辑块号5(0开始) 和261的信息分别对应物理块是(一级索引 256 一块) 261则在一级索引的第二块里
101物理块存放的是 二级索引地址
空闲存储空间的管理
空闲区表法
空闲链表法
位示图
字长32位,4195号物理块
多少字是从1开始算
多少位是从0开始算
成组链接法
文件和属性目录结构
绝对路径/相对路径
作业管理
设备管理
数据传输控制
程序控制
程序中断
DMA
不需要CPU接入
通道
输入输出处理机
微内核操作系统
虚设备与SPOOLING技术
要打印的内容,放入缓冲区输出井,排队打印
概述:管理软硬件/数据资源,控制程序运行,人机之间接口,应用软件与硬件之间的接口
软件工程基础知识(第五章)
系统开发与设计(第六章)
耦合
内容:一个模块直接访问另一个模块的内容
公共:一组模块访问同一个全局数据结构
外部:一组模块访问同一个全局简单变量
控制:模块间传递的不是数据信息,二十标志/开关量等.一个模块控制另一个模块的功能.
标记:传递数据结构而不是简单数据
数据:传递简单的数据项
非直接:没有之间关系,通过主模块的控制和调用来实现.
内聚
功能
顺序
通讯
过程
时间
逻辑
偶然
顺序
通讯
过程
时间
逻辑
偶然
功能:一个模块内所有处理元素仅完成一个功能.
顺序:处理元素必须按顺序执行
通讯:使用同一个数据缠身同一个输出数据
过程:必须以特定次序执行
时间:必须在同一时间内执行
逻辑:逻辑上属于相同或相似的一类
偶然:毫无关系处理元素偶然组合.
面向对象技术(第七章)
UML
静态结构图Static Structure Diagram
类图
关系
依赖
泛化
关联
组合
整体-部分(同生命周期)
聚合
整体-部分(不同生命周期)
实现
用例图
<include>
用例会无条件发生
<extends>
用例有条件发生
泛化
组件图
包图
交互图Interaction Diagram
时序图
协作图
状态图
活动图
描述活动的流程
实现图Implementation Diagrams
组件图
部署图
算法设计与分析(第八章)
数据库技术基础(第九章)
数据库模式
三级模式-两级映射
内模式
与物理文件打交道
概念模式
表
概念模式的映射
外模式
视图
内模式->概念模式-内模式映射->概念模式->外模式-概念模式映射->外模式
数据库设计
需求分析
数据流图
数据字典
需求说明书
概念结构设计
ER模型
逻辑结构设计
关系模式
物理设计
OS/硬件/DBMS特性
ER模型
ER图说明
方框
实体
子实体 方框加竖线
椭圆
属性
菱形
联系 M:N
- 一个实体转换为一个关系模式
多对多用一个单独的实体记录
关系代数
并
A(a,b,c)∪B(b,c,d)
A∪B(a,b,c,d)
交
A(a,b,c)∩B(b,c,d)
A∩B(b,c)
差
A(a,b,c)差B(b,c,d)
A有B没有的 a
笛卡尔积
AXB
前面的字段来自t1,后面的字段来自t2
属性数为t1与t2的属性数之和,记录为t1,t2的积
t1(1-1-1,2-2-2,3-3-3)
t2(4-4-4,5-5-5,6-6-6)
t2(4-4-4,5-5-5,6-6-6)
t1Xt2(1-1-1-4-4-4,1-1-1-5-5-5,1-1-1-6-6-6
2-2-2-4-4-4,2-2-2-5-5-5,2-2-2-6-6-6
3-3-3-4-4-4-3-3-3-5-5-5,3-3-3-6-6-6)
2-2-2-4-4-4,2-2-2-5-5-5,2-2-2-6-6-6
3-3-3-4-4-4-3-3-3-5-5-5,3-3-3-6-6-6)
投影
t1(c1,c2)
选列的操作
选择
t1(row3)
选行的操作
连接操作
子主题
规范化理论
函数依赖
部分函数依赖
学号,课程号,姓名
主键的一部分可以确定某一个属性
传递函数依赖
A确定B,B确定C,则能推到A能确定C
但B不能确定A,否则A与B就是等价
价值与用途
非规范化,可能存在,数据冗余,更新异常,插入异常,删除异常
数据冗余
员工:部门=1:N 员工表记录部门名称,则部门名称就是冗余的
更新异常
冗余数据更新不一致
插入异常
存在部分依赖时,没有联合主键中其他的属性无法插入
删除异常
部份依赖的信息也被删除了,比如学分,城市.
键
超键
唯一标识元组(单个或者属性的组合)
可能存在冗余属性(多余的标识,,学号,姓名,性别 学号或学号,姓名可以确定性别 学号与姓名就是超键,去掉一个就是主键)
候选键
超键消除冗余的属性,就是候选键
主键
候选键可以有多个,主键只有一个(学号,身份证号)选其中一个作为主键
外键
别的关系的主键
求候选键
将关系模式的函数依赖关系用有向图标识
找到入度为0的属性,尝试遍历有向图,若能正常遍历途中所有节点,则为候选键
若入度为0的属性不能遍历所有节点,则需要尝试将一些中间节点并入入度为0的属性集种,直至可以遍历所有节点,集合为候选键.
若没有入度为0的,则选择既有入度又有出度的节点
范式
三范式
1NF
属性都是不可分的原子值
列不可拆分
2NF
消除非主属性对候选键的部份依赖
非主属性完全依赖主键(不存在部分依赖)
学号,课程号,成绩,学分
学号与课程号可以确定唯一的成绩
学分快也根据课程号确定,课程号和学分是1:1
所以课程号就是部分依赖
3NF
消除非主属性的传递依赖
主键单属性,单主键不可能有部分依赖
BCNF
消除主属性对候选键的传递依赖
设R是一个关系模式,F是它的依赖集,R属于BCNF当且仅当其F种每个依赖的决定因素必定包含R的候选码
子主题
级别越高,规范程度越高,更有可能解决,插入异常,删除异常,数据冗余.
并发控制
事务
原子
一致
隔离
持久性
一旦提交永久有效
并发产生的问题
丢失更新
不可重复读
脏读
封锁协议
读写锁
S锁
shared lock 共享锁 读锁
又称读锁，若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。
X锁
exclusive lock 排他锁 写锁
又称写锁。若事务T对数据对象A加上X锁，事务T可以读A也可以修改A，其他事务不能再对A加任何锁，直到T释放A上的锁。
一级封锁协议
事务T在修改数据前必须对其加X锁,可防止丢失修改.
二级封锁协议
读数据前先对其加S锁,读完即释放S锁.可防止丢失修改,防止读藏数据
三级封锁协议
一级加上读加S锁,直到事务释放才释放.
二段锁协议
可串行化
死锁问题
预防法
死锁的解除法
数据库完整性约束
实体完整性约束
主键
参照完整性
外键完整性约束,允许空或存在的外键值
用户自定义预完整性
>=0 || <=200
触发器
写脚本约束数据的完整性
分布式数据库
用户标识和鉴定
身份认证(用户名密码),最外层的保护机制.
存储控制
对用户进行授权,GANT,不同用户有不同的操作权限
密码存储和传输
远程终端用密码传输
视图保护
视图保护数据
审计
日志审计
数据备份
冷备份
数据库关闭,对日志进行备份,直接拷贝文件
热备份
数据仓库与数据挖掘
反规范化
网络与多媒体基础知识(第十章)
IP地址与子网划分
A
2^24-2
1的8位是网络号,后三位为主机数
B
2^16-2
C
2^8-2=254
D
子主题
七层模型
物理层
二进制传输
中继器,集线器
数据链路层
传送以帧为单位的信息
网桥,交换机,网卡,PPTP,L2TP,SLIP,PPP
网络层
分组传输和网络选择
三层交换机,路由器 ARP,RARP,IP,ICMP,IGMP
传输层
端到端的链接
TCP,UDP
会话层
建立,管理和终止会话
表示层
数据的格式与表达,加密,压缩
应用层
实现具体的应用功能
POP3 FTP HTTP Telent SMTP
标准化和知识产权(第十一章)
结构化分析与设计(第十二章)
数据流图
基本概念
数据流
-->
实体
矩形
人,组织/系统/硬件
加工
圆角矩形(函数,处理过程,功能模块)
存储
双横线,半框型
文件,表,库
分层
顶层,0层,1层
数据字典
= 被定义为
+ 与
例如 x=a+b x由a,b组成
[..., |]
选择
{...}
重复
(...)
可选
数据平衡原则
父子平衡
只有输入没有输出,黑洞
只有输出没有输入,奇迹
只有外部和内部才能体现,加工和加工是体现不出来的.
子图内部平衡
答题技巧
计算机英语
资料
软件设计师教程（第5版）
视频讲义
0 条评论
下一页
