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