软件设计师基础知识点
2020-12-21 10:04:44 1 举报AI智能生成
这是一个软件设计师的知识点,基于https://www.processon.com/view/link/5d6b8a92e4b0b5cfa9d2aaf2#map网址的框架,纯手工打的,如有雷同纯属巧合,若有侵权请联系进行删除
作者其他创作
大纲/内容
下午部分
数据流图DFD
基本概念
基本元素
数据流
--→
加工(某功能)
圆形/圆角矩形
数据储存(文件)
分支主题
外部实体(系统之外)
矩形
层数
顶层图(表示输入和输出)
整个系统只用一个节点显示,和外部实体
0层图
对系统进行细化,例如将各个模块显示出来
底层图
将模块进行拆分,例如显示各个函数
数据字典
被定义为
=
x=a+b说明x由a和b组成
或
[...,...]或[...|...]
说明多个中选一个
重复
{...}
x={a},说明x由0或多个a组成
可选
(...)
x=(a)说明,a可以出现也可以不出现
数据平衡原则
父图与子图之间的平衡
一般会问子图/父图缺失了那些数据流?
在父图里面有的,子图中必须要有..
要看是否缺失数据流和数据流的箭头是否错误?
子图内部的平衡
对于任何形态的加工,应该既有输入也有输出
如果只有输入,就成为黑洞
如果只有输出,就称为奇迹
还有可能叫你补充某缺失的内部数据流
答题技巧
题目的说明部分的每一句话都会都应图中的一个关系,这样容易找出缺失或者错误的数据流能解决图的平衡问题
利用数据平衡原则
UML
9种图
结构图(静态图))
类图
考察类名、多重度、关系
对象图
对象间的关系
构件图
部署图
软件的构件应该部署在硬件的节点位置
行为图(动态图)
用例图(动静图)
描述用例、参与者之间的关系
包含include
必须折行的就是包含
扩展extend
有可能折行而已就是扩展
泛化(父类操作子类对象)
顺序图(序列图)
强调时间顺序，考察消息
对象具有生命线,能显示每一个对象的生命始末时间点
能知道每一个对象传递的消息,对象之间的交互
通信图(协作图)
不强调时间顺序，考察消息、节点
顺序图的另一种表达方式
状态图
状态的变迁，考察状态、触发条件
活动图
类似流程图
粗横线
说明可能有开始或结束并行的线程
类图的关系
依赖关系
-----▶
关联关系
聚合
可分
———◇(实线)
组合
不可分
———◆(实线)
泛化关系(类)
———▷(实线)
对实体类进行操作
实现关系(接口)
-----▷
对接口继承进行操作
用例图关系
扩展关系（非必须）
A---extend--->B
包含关系（必须）
A---include--->B
泛化关系
A—————▷B
题目类型
类图与对象图
问类名
多重度
1 :一个
0..*|* :0或多个
1..*,2..*,1/2到多个
顺序图与活动图
可能会被扣掉某几条线,问这个线是干嘛的
就会问这个对象跟那个对象的交互作用是什么
根据说明每条线进行比对,搞出它的作用
状态图/通信图
扣掉状态/状态/触发的条件(线)
数据库分析与设计
数据库设计过程
↓需求分析
数据流图
数据字典
需求说明
↓概念结构设计
ER模型的建模工作
和具体的数据库无关
↓逻辑设计阶段
↓物理设计阶段
考虑硬件OS特性
ER模型转关系模式
1:1
将联系存到其中一个表即可,也可以多生成一个表进行保存
1:n
只能将联系存到n的那个表中,或者生成第三个表保存
m:n
联系只能生成第三个表进行保存关系
至少有K+1个表,k为实体数
答题技巧
(要求拿到12分左右)
详细分析试题说明
熟练掌握基本知识
常考
ER模型的补充
ER模型转关系模式
关系模式补充
概念问题
数据结构与算法应用
(难点至少6~8分)
分治法
将一个大的问题拆分为多个小规模的子问题
递归
运行过程中调用自己
二分查找
回溯法
深度优选搜索法
试探到底，在回溯，迷宫问题
贪心法
局部最优
整体结果并不是最优解，但性价比高，背包问题
动态规划法
拆分子问题后，存下各个解，通过查表获取最优解
跟分治法非常像,但是很明显的区别是,动态规划法会去查子问题的表得到最优解
往往会构造出一个公用的表,来存子问题所有的解
题目类型
时间复杂度
用了什么算法?
程序填空
先解决非程序填空的题目有利于拿分
面向对象程序设计
语法
类的定义
import导包
类的修饰符
public
private
protected
abstract
final
static
特殊类
接口
interface
实现接口
implements
可以同时实现多个接口
继承
extend
接口还可以继承多个接口
设计模式
上午部分
计算机系统基础
cpu中的寄存器
主机主要分为CPU和硬盘,其他属于外设备
运算器
算数逻辑单元ALU
累加寄存器AC
数据缓冲寄存器DR
状态条件寄存器PSW
控制器
程序计数器PC
指令寄存器
指令译码器
时序部件
进制转换
任何进制转十进制
一般用按权展开法
10进制转K进制
除K取余法(除完后,反向取值就是K进制数)
二进制跟八进制和十六进制的转换
方法是8是2的3次方(8进制一位等于2进制的3位)
16是2的4次方(16进制一位等于2进制的4位)
2进制的10111转成8进制就是27
原、反、补、移码
原码是将一个数化成二进制即可,将最左边一位为最高位,正数为0负数为1
1-1的结果不如意,读出来是-2
反码是最高位除外,其余和原码取反
1-1的结果是-0(因为有最高位)
补码是正数和原码反码一样,但是负数是反码的值+1
1-1的结果是0(相比反码改进了负号)
移码是最高位和补码取反,正数为1,负数为0(数轴上好看)
1-1的结果是0
浮点数运算
跟数学中的科学记数法差不多1001化为1.001*10的3次方
N=M*R的e次方
M为尾数,e是指数R为基数
计算方法,对阶-->尾数计算-->结果格式化
技巧:对阶的时候化成最高阶第三步就省了,否则多做无用功
浮点数的(表示范围)大小由有e的大小来决定,精度就由M的大小决定
flynn分类法
一般问这种数据流属于哪一种结构类型,或者反过来问
(多)单指令(多)单数据流
控制部分,处理器,主存模块都是(多)一个
主要区别:
单指令流多数据流:一个控制部分,多个处理器,多个主存模块
多指令流单数据流:多个控制部分,一个处理器,多个主存模块
CISC/RISC
给出ABCD,那个说法对错属不属于...
区别:
CRSC(复杂/以前的),指令(多)差别大,支持多种寻址方式,周期长
RISC(精简/现在的),指令(少)差别小,支持方式少,复杂的指令用简单的拼凑成
校验码
检错和纠错的概念
检错就是能检查出来
纠错就是不但能检查出来,还要能够纠正错误,一般加冗余信息达到目的,(增大嘛距)
差错控制--海明校验码
由校验位和信息位组成
但是明确规定校验位的位置为2^n 1,2,4,8,16
2^r>=i+r+1(其中i是已知的信息位个数,r是校验位个数,==>r)
则2^r就是需要的总位数 下面是第二步
例如有总位数7
按照上面的步骤后海明码是1010101
别人收到海明码后提取出校验码,
如果两个校验码不一致就进行异或操作
得到的二进制就指明了错误的位置进而改正
比如提取的海明码是111,进行异或操作
001
----- =110,110是二进制的6,说明第6个信息位或校验码出错了
111
循环校验码CRC
第一步生成多项式
X^4+X3+X+1=11011(就是有x的次方位置为1)
第二步在原始报文加(余数的位数)N-1个0,N是多项式个数
第三步进行模二除法
按为异或操作(相同的0,不同得1)
第四步得到的余数替换刚刚加上的0,CRC编码就是原始报文+余数
第五步,对方收到SRC编码和多项式进行模二除法,如果得到的余数为0,说明报文是对的
总线系统
内部总线
微机内部，芯片间的总线
系统总线
各个插件版和系统板中间的总线
数据总线
32位系统为例，一个字为32个bit位，总线宽度32个bit位，一个周期内传输数据量32个bit位
地址总线
32位系统为例，地址空间2^32=4G（最大可管理的主存大小）
控制总线
发送控制信号
外部总线
微机与外部设备的总线
流水线
主要是考计算的问题
什么是流水线?将一条指令(多步骤)的工作分化成多个单步骤的工作,让单步骤不断的重复提高效率(工人不需要全懂,只需要会简单的单步骤就可以胜任工作)
流水线的周期△t 是所有步骤中耗时最长的那个时间(假想所有步骤都并行就好理解了)
执行n条指令所需时间
理论公式:(t1+t2+..+tk)+(n-1)*△t
实践公式:(k+n-1)*△t
流水线的吞吐率
TR=指令条数/流水线的折行时间
最大吞吐率是n/(k+n-1)△t = 1/△t
流水线的加速比
s=不适用流水线的折行时间/适用流水线的折行时间
越高越好
流水线的效率
假设有4条指令一条指针分4个步骤时间片1~3是△t,第4个是3△t
分支主题
效率=(△t+△t+△t+3△t)*4/15△t*4=1/3
简单来说就是图中占用的格子除以总格子数的百分比
每个步骤的时间片越是接近,效率越高(例如每个都是△t的时候效率最高)
存储系统
层次化存储结构
速度快到慢,容量小到大
CPU(内含寄存器)-->cache(缓存)-->内存(主存)-->外存(硬盘)
Cache-缓存
为了提高数据的读取速度
为了缓解CPU神和蜗牛的速度差
分支主题
局部性原理
时间局部性
刚刚访问完的,再次访问,例如在循环中的循环体(一般会放入Cache里面以提高访问的速度)
空间局部性
在数组中这个比较明显,当系统初始化一个数组时,访问了a[0]接下来一定是a[1],就会提前把a[1]放入Cache中
主存的分类
随机存储器RAM
特点是断电后就会清除里面的数据无法保存,代表是内存条
DRAM和SRAM
只读存储器ROM
断电后还可以存储原来的信息,代表是硬盘
MROM、PROM、EPROM和闪速存储器
主存的编址的计算
例题：内存地址从AC000H到C7FFF，问共有几K地址单元？
如果内存地址按字（16bit），由28片存储芯片构成，
已知每片是16K个存储单元
问该芯片每个存储单元为多少位？
①因为题目要求单位是K，所以
第一步先算有多少bit在化成k
C7FFF-AC000+1=1C000
1C000=114688/1024=112k
②意思是问112k放进28片,每片16k的芯片存储,那么求每个芯片的位数
112k*16位
-------------- =1==>x=4 上面的16是内存地址,下面的是存储单元
28*16k*x位 地址单元=芯片个数*每片存储单元(大小)
磁盘结构
存储时间 =寻道时间+等待时间
等待时间=平均定位时间=转动延迟
计算技巧:
物理块N个,磁盘转一圈ims,每个记录处理jms(一般指单缓存,是不能同时处理几个的意思,一开始磁头在第一个数据位置)其中过程是先读取处理在处理
读取为(i/N)
处理记录的最长时间(是指处理一个后转一圈在处理)
计算方法(j+i)*(N-1)+(i/N)+j
计算处理一个并且磁头转到下一个数据位置乘以N-1个+最后一个读取时间+处理时间(因为处理完最后一个就不需要磁头再往下了)
处理记录的最短时间(是指处理完一个立马处理下一个)
(i/N+j)*n
可靠性
串联系统
n和子系统串在一起形成一个大的系统,必须所有子系统正常,大系统才正常
可靠度R=R1*R2*...*Rn
失效率 入=1-R
并联系统
有一条线是通的系统就正常运行
可靠度R=1-(1-R1)*(1-R2)*..(1-Rn)
失效率 入=1-R
串并系统
串联并联混合系统
可靠度
如果整体上是串联
那么局部一般都是并联的就选
R=1-(1-R1)*(1-R2)*..(1-Rn)
在从整体串联计算
R=R1*R2*...*Rn
如果整体上是并联
那么局部一般都是串联的就选
R=R1*R2*...*Rn
在从整体并联计算
R=1-(1-R1)*(1-R2)*..(1-Rn)
当然也有更复杂的
局部中也是串并混合系统
那么可靠度就要细心拆解就散就行了
方法和上面一样
程序设计语言基础
编译与解释
遍历过程↓
解释型
写一行代码,一回车,遍历器就会马上进行代码编译,
马上告诉你是否逻辑错误
编译型
写完后在编译
源程序
词法分析
检查关键字是否写对
语法分析
当前面没有if,直接出现一个 else if时候,
或者少分号.就会报错
语义分析
属于逻辑错误,死循环,除零错误等等,难以杜绝
中间代码生成
为了适应系统硬件
代码优化
目标代码 生成
中间代码转低级代码.为了跨平台
文法
定义
有序四元组G=(V,T,S,P)
非终结符V,一般用小写字母代表
终结符T,一般用大写字母代表
起始符S
产生式P
正规式
定义
a|b，能解析出a或者b
（a|b）*这个比较特殊，只要是a和b字母组成的都能解析
（ab）*能解析出0或多个有ab连起来的串
a（ab）*能解析出a加上0或多个ab串
a*（ab）*，这个有先后关系，先0或多个a在。。
例题
例题:下面文法G[S]它无法识别( 1 D)，此文法对应正规式为(2C)。
G[S]: S→aA|bB A→bS|b B→aS|a
( 1) A. ababab B. bababa C. abbaab D. babba
( 2) A.(alb)* B.(ab)* C. (ab |ba)* D. (ab)*( ba)*
第一空，用G[s]能推出ABC，
第二空，代入法，将ABC能表达出来就可能是答案，但是表达不出来一定是错误的
能选出AC，因为A连D都能表达，所以选C
有限自动机
δ(S, 0)= B, δ(S,1)=A, δ(A, 0)= f, δ(A, 1)= C,
δ(B, 0)= C, δ(B, 1)= f,δ(C, 0)= f, δ(C,1)= f
其中δ属于一个公式,δ(S, 0)= B表示从S状态输入0到达B
分支主题
例题1：题目是上面，图是左边←
一般给你一个图,问是否能够解析出10、01、001、010串？
怎么搞呢？ 只要你能找到一条路把路上的数字连起来，
能连成那个串，就代表能解析，，这里除了010，其他的都能解析
例题2
例题:‘下 图所示为一个有限自动机(其中，A是初态、C是终态)，该自动
机可识别(1)C
(1)A.0000 B.1111 C.0101 D.1010
方法就是根据ABCD给出的串去走哪个状态图，能从A到C并且C是左后一个就对了
表达式
定义
前缀表达式：根左右（+ab）
中缀表达式：左跟右（a+b）
后缀表达式：左右跟（ab+）
例1:表达式(a-b)*(c+ 5 )的后缀式是__
A.abc5+*- B.ab-c+5*
C.abc-*5+ D.ab-c5+*
方法：
步骤1：先构造出树，注意括号，因位括号决定了，
算式的先后顺序，先（a-b），然后（c-5），最后*
步骤2：用后缀表达式的规则遍历这棵树。
得到的是ab-c5+*，答案就是D
分支主题
如果没有 括号。。。。树会完全不一样
例2:表达式a-b*c+ 5 的后缀式是__
A.abc5+*- B.ab-c+5*
C.abc*-5+ D.ab-c5+*
分支主题
传值与传址
传值调用
用新的空间，接收传进来的值，进行修改时不会修改原来的值
普通的形参
传址调用
用传进来值原来的空间地址，修改的时候，原来的值会被修改
C++中的指针就是这个原来
各种语言的特点
Fortran语言，用于科学计算
Pascal为教学开发的
C语言，高效
C++，对于C语言就是C++面向对象
java面向对象，中间代码，跨平台
C#面向对象，中间代码
Prolog，逻辑推理，
操作系统知识
进程管理
进程状态
等待状态:等待IO(用户输入),等待系统资源等等
就绪状态:万事俱备,只欠CUP
运行状态:啥都不缺,连CUP都有了
前驱图
前驱图是一个有向无循环图，用于描述进程之间执行的前后关系。引入前驱图可以比较直观的描述多道程序进程之间的不确定（异步）关系。
进程的同步与互斥
互斥:千军万马过独木桥
同步:可以同时进行的操作,在一定情况下需要等待(数据需要同步)
pv操作
技巧:一般会和前驱图结合然后一起考
每条箭头开始的位置是V操作
末尾位置是P操作
每条线上的S遵从从上到下,从左到右
V操作 S++ if(S<=0){唤醒}
一般先进行V操作,
P操作 S-- if(S<0){唤醒}
死锁
死锁就是进程之间的相互等待(资源不够,运行不了),
都完成不了任务,系统就卡死了
系统有K个进程,总用需要m个,问当有几个资源时,无论怎么分配都不可能产生死锁?
当系统有 m-k+1 个就不会发生死锁
如果每个进程都需要n个进程
当系统有 k(n-1)+1 个就不会发生死锁
死锁的四个必要条件
互斥
资源不可公用
环路等待
大家都在等别人
不剥夺
系统不去剥夺进程的资源
保持和等待
A等待B释放资源
B等待C释放资源
C等在A释放资源
预防和避免
打破上面的四大必要条件
方法1:有序资源分配(资源利用率很低)
方法2就是银行家算法
(比较灵活有效)
预算风险,判断是否分配资源给进程
一般会问:当前会有n个进程P1..Pn,所需不同类型资源m个R1..Rm
每个进程所需各个资源的最大需求量才能运行,还会给出当前
每个进程已经获得几个资源和系统本身一共有几个资源
第一步:先用系统全部的资源求出,系统还剩各个类型的资源数(列个表)
第二步:用每个进程最大需要资源减去已获得的的资源(列个表)
第三步:用系统剩余的资源,对比每个资源还需的资源数,看看那个进程
可以运行,运行后记得将进程释放的资源算进还剩的资源数
再次比对下一个能运行的进程
分支主题
存储管理
分区存储组织
首次适应算法
在内存中顺序找下来(大小无序),有能满足的空间就切割使用
循环首次适算法
跟首次算法相似,但是每次的首次选中后,下一次就+1
(第一次从1算起,第二次就从2算起)
最佳适应算法
将内存空间,按照大小排序,找最小能使用的那块内存切割使用
缺点:到最后会有很多的小内存碎片无法使用
最差使用算法
跟最佳适应算法相反,排序后使用最大的那块内存进行切割使用
段、页、段页式存储系统
页式存储
重要:页式存储中的逻辑地址
与物理地址之间的转化
页号一般不等
页内地址相同(以页为单位)
第一步:将给出的页面大小(例4K)化成2^12次方
说明有12位是页内地址(跟逻辑地址中的页内地址相同)
例如:十六进制5A29H,16进制化成2进制,一位化成4位
所以A29就是物理地址中的页内地址
第二步: 至于页号就要查表页号为5的页帧号,或者页帧号为5的页号
如果访问的某个页面不在内存里面?
只能淘汰已经在内存里面(一般为1)
并且刚刚没有被访问过的(一般为0)
类型二:页的大小为32bit,逻辑地址98,若3号逻辑地址对应的物理地址是4
求物理地址?
第一步:将十进制的98换成二进制11 00010
第二步:把二进制11(3)换成100(4),就是100 00010
第三步:然后再将100 00010在转成十进制130
会分成等分大小的内存,需要页表记录表表之间的映射关系
有点:利用率高,碎片小,分配及管理简单
缺点:增加了系统的开销,可能会产生抖动现象
段式存储组织
按逻辑结构划分,大小不等....由短号+段内地址组成
优点:便于共享,各程序修改互不影响
内存利用率低,内存碎片大
段页式存储
先分段在分页,将两个的优点的结合起来
页面置换算法
最优算法
随机算法
先进先出
可能会出现抖动现象.抖动现象就是得到了
更多的资源反而效率还降低了(缺页率更高了)
当需要访问的页面不在内存里面时候,
就将最先进来的那个页面拿出来换进来
最近最少使用
不会产生抖动现象,资源越多,效率越高
当要访问的页面不在内存里面时候,
就将最久没访问到的那个页面拿出来换进来
代表性问题:
在一台按字节编址的8位计算机系统中，采用虚拟页式存储管理方案，页面的大小为1KB,且系统中没有使用快表(或联想存储器)。图所示的是划分成6个页面的用户程序。
图中swapA, B是16位的指令，A和B表示该指令的两个16位操作数。swap指令存放在内存的1023单元中，操作数A存放在内存的3071单元中，操作数B存放在内存的5119单元中。执行swap指令需要访问_ (1)_ 次内存， 将产生_ (2)_ 次缺页中断。
解释:(记住规律就行)
第一问,就去数指令和数据一共占了多少个内存块然后*2就行了;答案是6*2=12
第二问中的指令默认是一次性调入,不管占了几个块
然后数据就不是,占了几个块就是调入(中断)几次答案是1+2+2=5
文件管理
索引文件
直接、一级、二级,、三级索引
索引就是目录中存目录,将很多盘块连接起来,形成大的空间
假设一个地址4字节,一块物理盘块4K大小
没说明情况下,一共有13个节点;
0~9是直接索引,空间大小是4K*10=40k
10就是一级索引1*(4k/4b)=1024个地址
1024*4K=4M大小
11是二级索引1*4k*1024*1024=4G大小
12是三级索引1*4K*1024*1024*1024=4T
答题时候;一般都会给出每块物理盘大小,和每个地址的大小
例如磁盘索引快和数据块都为1K,每个地址大小4字节
那也就是说,一个物理块能存1k/4b=256个地址
然后就是细心的去数某个逻辑块号对应的物理块号就差不多了
相对、绝对路径
绝对:是从盘号开始的路径例如D:\eclipse\html
不管在哪里都需要从D盘开始
相对:假设当前在eclipse文件夹下,直接html就可以了
从当前路径出发
位示图
例题:某文件管理系统在磁盘上建立了位示图(bi tmap)，记录磁盘的使用情况。若磁盘上的物理块依次编号为: 0、1、2、--系统中字长为32位，每-位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用，如下图所示。假设将4195号物理块分配给某文件.
那么该物理块的使用情况在位示图中的第(1)_ 个字中描述:系统应该将该字第_(2)_位置"1"(必须是1,因为被占用了,如果发现是0,直接×掉该选项)
第一问.一个字有32位(0~31),4195号就有4196(0~4195)个
4196/32=131.125,说明占到了132字中
第二问...那就选选131位置末尾占到了多少
131*32=4191
那么132字的第0位置就是4192,4195就是第3位置
设备管理
数据传输控制方式
程序直接控制方式(查询方式)
最低级,CPU介入最多,每次都是CPU问是否折行完了.效率很低
程序中断方式
跟成粗控制方式不同的是,在完成后发出一个中断出来,进行下一步的操作,效率自然高一些
DMA方式(直接访问储存方式)
有专门的的控制器控制,CUP只需要开始和最后处理一下就可以,效率会很高
通道控制方式
在CPU发出I/O指令后,由通道指令完成这些工作
spooling
虚拟技术,将一台实体设备进行虚拟化,可供多人同时使用(排队),
解决同一时刻资源冲突的问题(实例:一个办公室一台打印机)
主要技术:开拓了缓冲区,解决了外设设备和内设设备的速度瓶颈问题
将多个任何按时间进行排队,按队列进行处理
微内核操作系统
分支主题
单体内核和微内核的区别
(上面是单体内核---->)
实质
将图形、设备驱动及文
件系统等功能全部在内
核中实现,运行在内核
状态和同- -地址空间。
只实现基本功能,将图
形系统、文件系统、设
备驱动及通信功能放在
内核之外。.
优点
减少进程间通信和状态切
换的系统开销,获得较高
的运行效率。
内核精练,便于剪裁和移
植。
系统服务程序运行在用户
地址空间 ,系统的可靠性、
稳定性和安全性较高。
可用于分布式系统
缺点
内核庞大,占用资源较多且
不易剪裁。
系统的稳定性和安全性不好。
用户状态和内核状态需要频
繁切换,从而导致系统效率
不如单体内核。
磁盘调度
作业管理
作业调度算法
数据结构与算法基础
数组、矩阵、广义表
数组
一维数组a[i]的存储地址 =a+i*len
len是每个元素的大小,a是首地址
二维数组a[i][j]的存储地址
按行储存
a+(i*n+j)*len
每行是n个元素
按列存储
a+(j*m+i)*len
每列有m个元素
例题:已知5行5列的数组a中,每个元素占两个字节,求a[2][3]按行优先的存储地址?
A=a+(2*5+3)*2=26+a
稀疏矩阵
上三角矩阵
下三角都是0
不重要:下标i和j计算公式:(2n-i+1)*i/2+j
下三角矩阵
不重要:(i+1)*i/2+j
重要:代入法
设有如下所示的下三角矩阵A[0..8,0..8] ,将该三角矩阵的
非零元素(即行下标不小于列下标的所有元素)按行优先压缩存储在
数组M[ 1..m]中,则元素A[i,j]( 0<=i≤8, j≤i )存储在数组M的()中。
答案ABCD是几个公式,让你找出通用的那个
将几个数带进去,比如A[0][0]肯定是存在M=1中的
意思就是说将0,0带进去不得1的就直接排除
如果还有两个以上就继续代数A[1][0]肯定是存在M=2中
广义表
（表中表）
递归形式例如：LS1=（a,(b,c),(d,e)）.
里面有三个元素,
第二第三都是子表所以长度为3,
只有一层子表(嵌套次数),所以深度=2
基本运算
head 取表头(第一个元素/子表)
tail 取表尾(除第一个元素外全部)
取LS1中的b怎么操作?tail->head->head即可
但是需要这么写head(head(tail(LS1)))
数据机构的定义
线
一条线,不成环
树
不成环
图
成环
线性结构
顺序表
连续的空间
优点是:查询比较快
缺点:增删改就很麻烦
链表
不连续的空间,用指针指定下一个元素的位置
优点:增删改很方便,改指针就行
缺点:查询速度慢
单链表\双向链表\循环链表
顺序表和链表
时间空间对比
空间性能
存储密度
顺序存储更优,不存其他的东西
链式存储需要存指针大部分百分百
容量分配
链表更优,可以动态分配,顺序表要事先确定,容易浪费和不够用
时间性能
查找运算
没有顺序情况了都一样O(n/2)
有顺序就顺序表更优(二分查找)
读运算a[5]
顺序表O(1)更优,直接读取
链表需要移动到a[5]
链式存储最好O(1)最坏O(n)
平均O(n+1)/2
插入运算
顺序表最好0,最坏n
平均O(n/2),需要移动大量的数据
连式存储更优,直接改指针就行
删除运行
和插入运算一个情况
队列
先进先出
循环队列
(将头尾相连,形成一个圈)
队空条件:head=tail(头指针=尾指针)
队满条件:(tail+1)%size=head
size是队列的长度
栈(箱子)
先进后出
习题:元素按照a、b. c的次序进入栈,请尝试写出其所有可能的出栈序列。
abc、acb、bac、bca、cba
习题2：输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出，如上图，若有e1, e2, e3, e4依次进入输出受限的双端队列,则得不到输出序列( )这是栈和队列的组合体
A.e4, e3, e2 , e1（→→→→） B. e4, e2, e1, e3（→→←→）
C.e4，e3,e1,e2 （→←→→） D.e4，e2, e3, e1选D
树
树的概念
节点的度:一个节点拥有的孩子数
树的度:树中所有节点度数最高的那个度
叶子节点:就是没有孩子的节点
分支节点:只要有分支即是(包括跟)
内部节点:区别于分支节点(不包括跟)
父节点/子节点(相对概念)
兄弟节点:同一父亲的节点
层次:一共几层(几代)
二叉树的重要特性
在第i层最多有 2^(i-1)个节点(i>=1)
在前i层最多共有2^i-1个节点(i>=1)
深度为k的二叉树,最多有(2^k)-1
n2:度为2的节点个数(有两个孩子的节点),
n0:度为0的叶子个数(孩子)
满足:n0=n2+1
跟无父节点,节点i的父节点为(向下取整i/2)i>1
满二叉树，完全二叉树
满二叉树:每一层都是满的
完全二叉树:一层满了才到下一层
同一层又是从左到右排序
二叉树遍历
前序遍历
跟左右
值得注意的是:这个东西是个递归,假如你进入了左子树
后要重新按照规则再次遍历,直到最后,每走一步,走一次规则
中序遍历
左跟右
后序遍历
左右跟
反向构造二叉树
知道一定序列的二叉树反推出树的形状
有前序和中序、中序和后续或者三个都有都可以反推出来
但是只要前序和后续就不能反推出来,必须要含有中序才行
技巧：
第一步：
（确认根节点）
如果有前序遍历（根左右），就能直接确定第一个节点就是根节点
如果有后续遍历（左右跟），就能直接确定最后一个是根节点
第二步： 确定完了根节点后，根据中序遍历确定左子树和右子树
第三步：确认出跟节点和左右子树后，将目标看向子树
递归操作重复123步骤，直到每个节点都恢复完
（为了粗心的问题，对自己反推出来的数，再次进行提供的两个
序列进行遍历看看答案跟原来的一不一样）
普通树转二叉树
1将兄弟相连(同一个父亲的)
2保留左边第一条线(多个兄弟节点)
3将树转个方向
排序二叉树
(查找二叉树)
所有左子节点小于跟,所有子节点大于父亲节点,递归规律到下一层
查找起来非常方便,复杂度是O(logˇ2(n))
插入节点
若节点已存在,则不能插入(不知道放左边还是右边就是说排序二叉树中的数不可以重复)
删除节点
如果是叶子节点,直接删除即可
如果是非叶子节点就在左子树中序遍历找最大的那个递归替代
哈夫曼树
(最优二叉树)
常用与编码压缩,将原来的数据压缩到最极致的无损压缩
要求
能构造出哈弗曼树,最小到大排序,最小的两两相加
能计算出带权路径,将所有(叶子的路径长度*叶子的权)相加
线索二叉树
因为一个二叉树中有大量的指针都是空的,为了方便遍历,
就提出了前序/中序/后续线索二叉树
前序线索二叉树
是根据前序遍历做出来的一棵树
规则是 跟左右 例如:ABCDE
那么C的左指针指向B(绿色箭头),
右指针就指向D(红色箭头)
中序线索二叉树
如果该树的中序遍历是ABCDE
那么C的左指针指向B(绿色箭头),
右指针就指向D(红色箭头)
后序线索二叉树
同上
平衡二叉树
任意结点的左右子树深度相差不超过1
每结点的平衡度只能为-1、0或1
左边孩子的代数为正
右边一样,平衡度是 ==
右边的深度数减去右边的深度数
图(考察频度低)
无/有向图
如果有向图中 有①→②说明1能向2,2不能向1
所有点两两之间都连线[能(不拐歪)走通]了就是完全图
邻接矩阵
矩阵大小取决于点数,例如有5个点
那么就是5*5的矩阵
无向图中是没有自己到自己的边,所有(0,0)(1,1)..都为空
例如①--②那么矩阵中(1,2)和(2,1)数值都为1,因为两边都能走通
有向图中有些只能一个方向走得通,就存一边就可以了
邻接表
直接去看图吧,,,,
深度、广度遍历
(图的遍历)
拓扑序列
表示事件折行的先后顺序,跟前驱图差不多
(有些事必须完成 才能到下一个)
上图的拓扑序列有:02143567,01243657,02143657,01243567
(图的)最小生成树
将所有的边和 线都去掉后
连线一下权值最小的能连所有点
普利姆算法
第一步:选中图中的一个中作为红点集合,剩下的就是蓝点集合
第二步:从红点几个出发,选中路径最短的到达蓝点集合,
并将到达的蓝点归并入红点集合
注意:绝对不能形成环路,直到所有点归并到红点集合即可
克鲁斯卡尔算法
步骤是:从最小路径开始选边,选几条边,直到能将所有点都连接起来
注意:选边的过程中,绝对不能成环,否则就丢弃那条边
算法的特性
有穷性
确定性
>=0个输入
>=1个输出
有效性
a=0时,b/a就无效
时间、空间复杂度
时间复杂度
从程序开始到结束所需时间
常见的复杂度及大小关系
当有O(n^3)也有O(n^2)时直接选最高阶就可以了
空间复杂度
一个算法在运行中占用的临时存储空间的大小
查找
顺序查找
序列过多，不宜使用，效率低,最好1次,最差n次;
平均(1+n)/2次;复杂度是O(n)\
二分查找
(择半查找)
必须是有序的序列(递增或递减),
但是效率很高;时间复杂度是O[log∨2(n)]
中间数mid=(high+low)/2
如果key>mid; high不变,low=mid+1
如果key<mid; high=mid-1;low不变
散列表查找
自定义一个规则(关键码/公式)
将这些计算后存储,如果计算出来
的被占用了,那么久向下一个空间存储
例:记录关键码为(3 ,8，1217,9),取
m=10 (存储空间为10) , p=5 ,散列函数
h= key%p.
排序
插入类排序
(先用希尔再用直接
效率会高许多)
直接插入排序
思路简单，操作容易,效率低
第一步:将第一第二个数,对比大的放在后面
第二步:将第三个和前面排好的看看第三个应该放进那里去
第三步:将第四个和前面排好的看看第四个应该放进那里去
......................
第n步:将第n个和前面排好的看看第n个应该放进那里去
希尔排序
Shell排序
效率高（适合多数据量时）
循环
定义一个距离k,完成一遍后k相对减小;k>0
将一个序列,相隔k的元素两两一组,
组内直接对比小的在前面,大的在后面不满足就交换位置
当k=0时候,发现队列相对的排好了,大的基本上在后面...
这时候在用直接插入算法,就会效率很高,因为挪动的位置缩小了
交换类排序
冒泡排序
两两比较,i和i-1比较,比较后i--(从右边往左边排序)
完成一轮后能够将最小的放在最前面
因为完成一轮就能将最小的放在最前面
所以第二轮开始,就不用和前面比较好的再次比较
例如第二轮,只需要对比到第1个(第0个开始)即可
快速排序
(易考程序)
效率高，过程复杂
选择一个基准指针i,一般选择第0个,然后对比指针j,一般是最后一个
如果基准小于对比元素,不交换,然后对比指针j- -
如果基准大于对比元素,交换位置tem=i;i=j;j=tem;并且j++
....
以此折行n-1次;n为数组元素个数
这行玩之后,基准前面作为一个小的数组
后面也作为一个数组,递归折行后相加即可
选择类排序
直接选择排序
从剩余的元素中选择最小的直接与第i个进行交换
将剩余的全部拍好后就排序完成了
堆排序
(易考程序)
效率高，过程复杂，适合选前几个的场景
小顶堆
所有的孩子都比父亲大
大顶堆
所有孩子都比父亲小
堆的操作
堆的初始化
第一步:先将数组中的元素按照完全二叉树进行排序
第二步:按照从左到右,上到下,选择最后一个非叶子节点
然后按照对的规则(例如大顶堆),如果根小于孩子节点,
就选择孩子中最大那个进行交换
第三步:再选倒数第二个同上操作
.....
如果交换的过程中打破了堆的规则,那个再次跳到那个进行调整
调整后想根靠近
......
直到完成所以都满足堆的规则..
......
删除操作:
第一步:堆的初始化
第二步:取走堆顶
第三步:将最后一个元素放在跟位置
第四步:重建堆(再次初始化)
第五步:重复二三四步;
直到元素全部都取走,
取出来的是个有序的序列
归并排序
流程是:
第一步:先相邻的两两一组,进行大小的排序,小的放在前面,
第二步:然后,相邻的组,两两合并成新的一组,第一组下标i=0
第二组下标j=0;声明一个新的数组R,下标k=0;
第三步:先比较i和j 的大小,如果i(值)>j(值);j++,反之亦然..
把j的复制到数组R中,且k++;
[第四步]:如果i或者j超过了长度就直接将另一个组剩余的数直接复制到数组中
第五步:重复2/3/4步,直到归并完所有的元素
基数排序
考的比较少
按个十百千...位排序
步骤:
第一步:声明一个数组arr[k][10],k为所有排序数中的最高位,比如最大1234,则k=4
第二步:收集各位,(只看个位数)将所有个位为0的收集到arr[0][0],arr[1][0]...
所有个位为1收集到arr[0][1],arr[1][1].......个位为9,arr[0][9].....
第三步:将各个收集到的个位,按列顺序进行排序就是arr[0][0],
arr[1][0]..arr[0][1],arr[1][1]......arr[0][9],arr[1][9]..
第四步;收集十位,声明一个新的数组b[k][10];将所有十位为0的收集
到b[0][0],b[1][0]... 规则同个位
第五步:将各十收集到的个位,按列顺序进行排序就是b[0][0],...
规则同个位
第六步:收集百位,....千位...万为 ...规则都一样
直到收集玩最高位,,,,再次按列排序万之后...即可
排序的总结
插入排序
Shell排序
希尔排序
时间复杂度
平均 最坏
O(n^1.3) O(n^2)
空间复杂度
O(1)
稳定性
不稳定
直接插入
O(n^2) O(n^2)
O(1)
稳定
选择排序
直接选择
O(n^2) O(n^2)
O(1)
不稳定
堆排序
O(nLog∨2(n)) O(nLog∨2(n))
O(1)
不稳定
交换排序
冒泡排序
O(n^2) O(n^2)
O(1)
稳定
快速排序
O(nLog∨2(n)) O(n^2)
O(Log∨2(n))
不稳定
归并排序
O(nLog∨2(n)) O(nLog∨2(n))
O(n)
稳定
基数排序
O(d(r+n)) O(d(r+n))
O(r+n)
稳定
算法基础及
常见算法
分治法
动态规划
贪心
回溯
软件工程基础知识
软件生命周期
软件开发模型
瀑布模型
结构化方法模型
适用于二次开发或者需求明确的项目
基本结构
↓软件计划↑
↓需求分析↑(难以把控)
↓软件设计↑
↓程序编码↑
↓软件测试↑
↓运行维护↑
原型模型
和瀑布模型
相当互补
尝试去弥补需求分析这一方面的不足....针对需求不明确的情况
强调,在构造初期.先构造一套简易系统(纯界面,初步系统..),
先跟用户交流清楚是否是满足
不满足的可以立马修改,不用到了后面才发现是无用功
原型法往往只应用于开发中的需求分许阶段.
演化模型
通过最初的原型,一步一步的演化成最终的产品叫做演化模型
增量模型
原型的思想,和瀑布模型的思想,形成了增量模型
从核心模块开始,开发一个模块,给用户用一用,如果不满意就修改...
每一个模块都进行用户测试,到最后,能保证核心功能不出异常..
螺旋模型
包含多个模型(其中包括原型)
风险分析是该模型最为显著的特征之一
如果题目问有一个需求不明确的情况下,首先选原型,再次才能选螺旋模型
V模型
跟瀑布模型差不多,就是测试更加被重视了,
有单元测试,集成测试,系统测试,验收测试....
强调测试的模型...
喷泉模型
迭代,,无间隙.面向对象的模型
RAD
视图.开发,,拖拽按钮图标...
CBSD构建组装模型
将构建进行重复的使用..
需求分析和定义↓
软件设计↓
构件库的建立↓→
原有构件库
(修修改改)
应用软件构建↓
测试和发布
统一过程模型
形式化方法模型
敏捷方法
适用小型项目
基本原则
短平快的会议
小型版本的发布
交少的文档
砍掉无用文档
合作为重
......
4大价值观
沟通
简单
反馈
勇气
5大原则
快速反馈
简单性假设
逐步修改
提倡更改
优质工作
软件开发方法论
结构化法
一旦开发完成,
结构是固化的
与现实不接近
用户至上
严格区分工作阶段，每阶段有任务与成果
强调系统开发过程的整体性和全局性
系统开发过程工程化，文档资料标准化
自顶向下，逐步分解(求精)
原型法
适用于需求不明确的开发
包括抛弃式原型和演化式原型
面向对象法
和现实很接近
更好的复用性
关键在于建立一个全面、合理、统一的模型
分析、设计、实现三个阶段,界限不明确
面向服务法
so方法有三个主要的抽象级别:操作、服务、业务流程
SOAD分为三个层次:基础设计层(底层服务构件)、应用结构层(服务之间的接口和服务级协定)和业务组织层(业务流程建模和服务流程编排)
服务建模:分为服务发现、服务规约和服务实现三个阶段
软件测试与维护
测试原则
尽早、不断的进行测试
程序员避免测试自己设计的程序
既要选择有效、合理的数据,也要选择无效、不合理的数据
修改后应进行回归测试(可能会引入了新的BUG)
尚未发现的错误数量与该程序已发现错误数成正比
相互独立的两组,第一组发现60个错误,第二组发送50个,其中有30个是和第一组相同的,问估计程序中一共有多少个错误?
对于第一组而言:共同发现30个,有20个未发现(第二组中的)
发现率=30/(20+30)=60%
估计有:60/60%=100个
对于第二组而言:共同发现30个,有30个未发现(第一组中的)
发现率=30(30+30)=50%
估计有:50/50%=100个
动态测试
黑盒测试(利用计算机的测试)
白盒测试(纯手工的测试)
灰盒测试(黑白结合)
静态测试
桌前代码
代码走查
代码审查
测试用例
黑盒测试(不知道内部结构)
等价类划分(每等级选一个)
边界值分析
如果年龄范围是0~150;
那么要测试-1,0,150,151
错误推测(比较强调经验)
白盒测试(知道内部结构)
基本路径测试
循环覆盖测试
逻辑覆盖测试
McCabe(环路)复杂度计算
V(G)=m-n+2
m是边数,n是点数
分叉点,可以抽象为一个节点,也可以不抽象为
节点,最终算出来的环路复杂度是一样的
软件维护类型
易分析性
代码容易读/分析
易改变性
代码耦合度要低,容易进行改变.
易测试性
稳定性
软件可维护性
改正性维护
已经出错后的维护
适应性维护
适应软硬件/系统环境...
完善性维护
系统运行过程中,要去扩充功能,改善性能
预防性维护
现在不维护,不会有问题,但是以后可能会有问题.打个比方:
性别只设置了男女...你不能100%确定为了没有人妖这个类别..
需求分类
基本需求
客户说的基本需求
期望需求
客户没说,但是他觉得你会知道的,你能领会的需求
兴奋需求
超出了客户的要求,加了多余的功能..
结构化设计-基本原则
概要设计
自顶向下, 逐步求精
信息隐蔽(提供接口|private成员,set/get方法)
模块独立性高(高内聚,低耦合)
详细设计
保持模块的大小适中
尽可能减少调用的深度
多扇入(上传模块的调用)，少扇出(调用下层模块)
单入口，单出口
模块的作用域应该在模块之内
功能应该是可预测的
测试阶段
单元测试
写个驱动模块,模拟上下级的调用 反参
集成测试
一次性组装(将多个模块进行组装)
增量式组装
确认测试
(验收测试)
内部确认测试
Alpha测试
实在可控的环境中进行的(开发者实验室中)
Beta测试
是在不可控的环境中进行,(内测版本的发布)
验收测试
系统测试
恢复测试
安全性测试
压力测试
性能测试
负载测试
强度测试
容量测试
可靠性测试
可用性测试
可维护性测试
软件质量管理
软件过程改进
CMM1-5级
一级:混乱级别,没有通过CMMI定义
二级:已管理 (个人能力与经验)
需求管理、项目计划、配置管理、项目监督与控制、
供应商合同管理度量和分析、过程和产品质量保证
三级:已定义 (团队经验与模板)
需求开发、技术解决方案，产品集成、验证、确认、组织级过
程焦点、组织级过程定义、组织级培训、集成项目管理、风险
管理、集成化的团队、决策分析和解决方案、组织级集成环境
四级:定量管理 (量化)
组织级过程性能、定量项目管理
5级:优化级别 (优化)
组织级改革与实施、因果分析和解决方案
软件项目管理(1~3分)
时间管理(计算)
Gant图
Pert图
分支主题
松弛时间=某个事件(最晚-最早)发生时间
求某个事件的最晚开始时间
(要求最晚时间就有求出最后一个事件的最早时间然后反推)
步骤1:先将所有事件的最早时间算出来,
(1)找到最开始折行的那个(一般是事件号为1的)
(2)串联路:将路上的数字(事件折行完成所需时间)加起来
(3)并联路:取两条路中最早开始时间 大的 那个(以为还有一天路未完成,它就无法开始)
步骤2:再从左后一个反推最晚时间
(1)将最后一个的最早开始时间算出来后,最晚折行时间也等于它
(2)按最近的一条路反推,将路上的时间数减去.
(3)到达那个事件的时候所剩的时间,就是那个事件的最晚开始时间
风险管理
对你的项目有损失和损害的可能性(对别人的不算)
分类
项目风险
一般是超支了预算...
技术风险
某项未成熟的技术
商业风险
超出了项目组的范畴..
一般是市场是否需要这个产品的问题
项目经理无法控制的,是老板的问题
风险计算
风险一:100万,但是概率是5%,风险曝光度是100*5%=5万
风险二:10万,但是概率是80%,风险曝光度是10*80%=8万
相比起来发现:
虽然风险1的风险是100万,但是概率低,风险曝光度低
所以相比风险2才是我们更加应该重视的那个
数据流图
可能会出现4种基本符合:数据流,加工,数据存储,外部实体(数据源/数据终点)
面向对象技术
面向对象基本概念
对象
类(实体类、边界类、控制类)
边界类是与外界进行交互的类
抽象
继承与泛化
泛化:父类 对象名 =new 子类();
C++中的继承有三种:
公有继承
原有的成员函数的属性不变,派生类可以访问公有和保护属性的成员和函数,不能访问私有的
私有继承
将父类中所以的成员和函数变成私有的,并且不能直接访问,要通过父类对象访问
保护继承
将公有的成员和函数转成保护的,其他的不变,并且只能被派生类或者友元访问
多态
接口名 对象名 =new 实现类();
接口
只有方法的定义,没有方法体,实现类才写方法体
消息
组件(构建)
模式和复用
模式就行一种经验的传承
设计原则
单一原则
设计目的单一的类
目的是降低整个项目的耦合度
开放-封闭原则
对扩展开放,对修改关闭
避免修改的时候,让原来能用的用不了了
李氏替换原则
子类可以替换父类
就是在继承父类的时候不用盲目的重载父类的方法,否则无法替换父类
依赖倒置原则
要依赖于接口,不要依赖实现类.针对接口编程,而不是针对实现编程
为了让程序更加灵活
接口隔离原则
使用多个单一的接口要比使用一个多功能的接口要好
为了降低耦合度和提高复用性,将多个单一接口组装成一个使用接口
组合重用原则
尽量用组合而不是继承达到重用的目的,(继承是一种紧耦合关系,父类变,子类全变)
迪米特原则(最少知识法则)
应该对一个类尽可能少的理解,否则很容易绕开规则直接操作里面的成员,一般用封装进行避免
UML
关系
依赖关系
-----▶
泛化关系
———▷（实线）
关联关系
聚合
可分
———◇（实线）
组合
不可分
———◆（实线）
实现关系
-----▷
结构图(静态图)
类图
类之间的关系
对象图
对象间的关系
包图
包之间，包内部的关系和结构
组合结构图
构件图
制品图
部署图
软件的构件应该部署在硬件的节点位置
行为图(动态图)
用例图(动静图)
系统和外部的交互关系
顺序图(序列图)
强调时间顺序
通信图(协作图)
不强调时间顺序
状态图
状态的变迁
活动图
类似流程图
定时图
交互概览图
设计模式
创建模式
工厂方法
动态生产对象，实例化过程推迟
可以是类模式也可以是对象模式,没说的就只是对象模式
抽象方法
生产成系列对象
原型模式
单实例，保证一个类只有一个实例，并提供唯一一个全局访问点
构建器模式
复杂对象构造，复杂类的表示的构造分离，使相同构建过程得出不同表示
原型模式
克隆对象，用原型实例创建对象类型，并通过拷贝原型来创建新的对象
结构型模式
适配器模式
转换接口(转换成想要的)，协同工作
可以是类模式也可以是对象模式
桥接模式
继承树拆分
组合模式
树形目录结构，整体-部分。
装饰模式
附加职责
外观模式
对外统一接口
享元模式
细粒度对象共享
代理模式
为其他对象提供某一对象的代理
行为型模式
职责链模式
传递职责：财务审批、零件加工
命令模式
日志记录，可撤销
解释器模式
虚拟机机制，解释器根据文法解释语言中的句子
可以是类模式也可以是对象模式
迭代器模式
数据集迭代不用暴露对象内部结构，对外提供顺序访问聚合对象的各个元素
中介者模式
不直接引用，中间件
备忘录模式
保存对象状态，可恢复
观察者模式
联动，对象之间状态发生时通知其他对象
状态模式
状态变成类，内部状态改变后类行为也改变
策略模式
灵活，多方案切换
模板方法模式
可以是类模式也可以是对象模式
访问者模式
数据库技术
数据库模式
三级模式两级映射
外模式（用户模式）
视图级
概念模式
表级别
内模式（存储模式）
文件级
数据库设计过程
需求分许
数据流图,数据字典,需求说明书
概念结构设计
ER模型
跟DBMS无关,可以用任何的数据库实现
逻辑结构设计
转换规则,规范化理论
物理设计
DBMS特性,硬件,OS支持(指定了某数据库/硬件/系统..)
ER模型
图形认识
实体
矩形
属性
椭圆形
联系
菱形
关系模式
1:1
至少两个表,联系信息可以放在其中一个即可,也可以生成第三个表(不推荐)
1:n
至少两个表,联系只能放在n这边,当然也能生成第三个表(不推荐)
n:m
至少三个表,生成两个实体表后,必须在生成一个联系表
问:如果有k个实体,都是m:n模式,至少要生成几个表|?
答:k+1个
关系代数
选择题的形式出现....
理解
并
将两个相同的表合并,取出相同的数据
交
将两个表中公共部分列出来
差
将公共部分去掉,列出其他的数据
掌握
笛卡尔积S1XS2
就是数据两两交叉组合,表格结构可以不一样
投影
πSno,Sname(S1)
只选择S1表中Sno和Sname两个列,其他的丢掉
π1,2(S1)
只选择S1表中1,2两个列,其他的丢掉
选择
分支主题
选择S1表中Sno=No0003的那一条数据
连接
就是笛卡尔积后,提出了相同字段(列)和相同的数据条
连接条件示例:S1.Sno=S2.Sno 符号是▷◁
注意:
π1,3(S1▷◁S2)
将S1,S2表进行连接后,选择1.3两列
一般考试都是这样复合的考题
规范化理论
函数依赖(y=x^2)
给定一个x能够求出唯一的y
给出一个y不能求出唯一的x
部分函数依赖
假设主键由(学号+课程号)组成能够确定唯一一个姓名
但是主键的一部分(学号)也能确定唯一的姓名
传递函数依赖
A→B→C能够推出A→C
但是确定B不能确定A,不然
AB就等价了
价值与用途
非规范化理由可能存在问题:数据冗余,更新异常,插入异常,删除异常
想法就是降低数据冗余,消除各个异常
键
超键:(唯一标识元组),只要能唯一确定某条数据的总和
候选键
:在超键消除多余属性后就是候选键(可以有多个)
求候选键的方法
1. 将关系模式的函数依赖关系用“有向图”的方式表示
2.找入度为0的属性(一或多个)，尝试遍历有向图，若能遍历全图就是;
若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将-一些中间结
点(既有入度，也有出度的结点)并入入度为0的属性集中，直至该集合能遍
历所有结点，集合为候选键
例题1
关系模式R(A, B, C,D，E,F,G，H，I，J)满足
下列函数依赖: FD={ABD →E, AB →G, B→F, ==>
C→J, CJ→I,G→H},求候选码?
分支主题
答案是ABCD(不能写成A,B,C,D)
主键:在候选键中任选一个那就是主键
外键 :其他关系的主键
范式(几乎必考)
第一范式
属性值,原子不可拆分(一个属性不能表达两种信息)
第二NF
只有达到上一级才到下一级
消除非主属性对候选键的部分依赖
非主属性完全依赖于主码就是第二范式
主属性就是候选键
第三NF
消除非主属性对候选键的传递依赖
一般达到这里就行了
BC范式
消除主属性对候选键的传递依赖
级别越高,越能消除插入,删除..异常,数据冗余等等
级别高,表的拆分就越高,性能就越低
模式分解
保持函数依赖的分解
设数据库模式ρ={R1, R2,.., Rk}是关系模式R的一个分解，F是R上的函数
依赖集，ρ中每个模式Ri上的FD集是Fi。如果{F1, F2,Fk}与F是等价
的(即相互逻辑蕴涵)，那么称分解p保持FD
例题1有关系模式R(A,B,C)函数依赖是A→B,B→C
分成R1(A,B),R2(B,C)就保持了函数依赖.对于R3(A,C)冗余信息不要求
如果R1(A,B),R2(A,C)没有保持,因为,函数依赖中A→B,保持了,但是B→C没有保持下来
无损分解
有损
不可还原
无损
可以还原
将一个(学生)表进行分解,每个表之间,必须有一个能和外界进行联系的字段
然后进行表表连接,能够还原,那就是对的.
要求是能将已经拆分的表进行还原.
反规范化技术
物极必反,就是说规范化数据越高,冗余数据就越少,但是性能跟不上了
反规范化就是进行某些表的合并,提高性能,就是规范化的逆过程
SQL语言
并发控制
事务
原子性
将多个操作进行包装,要么全折行,要么全不折行
一致性
前后的数据总和一致
隔离性
持续性
并发控制存在的问题
丢失更新
T1T2读取同一个数据,然后T1把T2的更新覆盖了
不可重复读
T1读取第一次后,T2更新了,T1再次读取的时数据距不一样了,验算错误
读"脏"数据
T1读取到了T2(回滚/roball)的临时数据,不是真的的数据
封锁协议(读写锁)
一级封锁协议
加读锁,可防止丢失修改(更新),对数据进行加锁,访问完之前别人不可访问
二级封锁协议
在一级锁上,再加写锁,还可以防止脏读数据
三级封锁协议
在前两种锁上,还可以防止数据重复读
数据库完
整性约束
实体完整性约束
主键
填数据是时候,主键必须唯一
参照完整性约束
外键
填数据时候,必须填外键已有的数据,比如填自己是每个部门,这个部门必须已经存在
用户自定义完整性约束
x>100
自定义的一个约束,比如填年龄的时候不能填<0|>200的数据
触发器
数据库安全
(本身这个题干上
到这里没有了)
用户标识
用户验证
存取控制
对非root用户进行权限规定
密码存储和传输
对远程中端信息用密码传输
视图的保护
审计
记录对数据库的操作
数据备份
分类一
热备份
动态的(不用关闭数据库)
复杂度很高,并且不能出错,不然后果很严重.
优点就是可以选择性恢复
冷备份
静态的(关闭数据库)
简单,速度快,技术容易,复杂度低(考文件处理即可)
缺点就是需要停止业务的服务
分类二
完全备份
差量备份
仅仅备份,离上一次完全备份的变化部分
增量备份
针对上一次变化的备份部分(不管类型)
分类三
静态海量转储
在无运行事务时进行,每次转储全部数据
静态增量转储
每次转储与上一次变化的数据
动态海量转储
在运行事务时,转储全部数据
动态增量转储
上一次更新过的差异的数据
日志文件
在进行上面的备份后也不能保证数据100%的恢复,每次备份之间的时间中出错呢?
办法是:进行记录日志,将Sql语句中修改语句全部记录下来,配合日志文件,能将数据恢复到某个时间点
数据库故障与恢复
可预期的逻辑故障
可预先设置roball语句
不可预期的算法溢出,违规存储
通过日志文件撤销 对数据库的修改
系统停止运行
通过检查点法
介质故障,外存被破坏
一般通过日志重做业务
数据仓库和数据挖掘
某个系统运行一段时间后,数据越多,系统越卡.
就想找个地方存起来(删掉可惜)
但是一般的数据库是用来经常插入修改的,历史数据只需要偶尔查询即可
所以就搞出了个数据仓库,专门存历史数据的
网络与信息安全基础知识
参考模型
OSI/RM
7应用层
实现具体的应用功能
6表示层
数据的格式与表达、加密、压缩
5会话层
建立、管理好终止绘画
4传输层
TCP、UDP
端到端的连接
3网络层
三层交换机、路由器、arp、rarp、IP、icmp、igmp
分组传输和路由选择
2数据链路层
网桥、交换机、网卡、pptp、l2tp、slip、ppp
传送以帧为单位的信息
1物理层
中继器、集线器
二进制的传输。。。。。。。。。
下面两层是一个局域网，第三层起就是局域网了
TCP/IP
Internet，可扩展，可靠，应用最广，牺牲速度和效率
三次握手
DHCP协议
客户机、服务器模型
租约8天，当租约过半就会申请续约
当超过，87.5%，就会和其他的服务器连续（服务器可能发生变化了）
如果出现169.254.X.X和0.0.0.0那就是说,你没有获得真的IP地址,这个是计算机给你分配的假地址,因为你没有获得地址就会一直想服务器发送请求,浪费资源
DNS协议
主机想本地域名服务器的查询采用递归查询(刨根究底)
递归查询是,本地服务器必须回答IP地址和域名服务器的映射关系,自己会负责人的去问别人
本地域名服务器想根域名服务器的查询采用迭代查询
迭代查询是,我自己不知道,但是我提供线索,让它自己找
拓扑结构
按分布范围分
局域网
城域网
广域网
因特网
安拓扑结构分
总线型
星型
办公室的网络就是
环形
网络规划设计
网络规划原则
实用性
开放性(使用公用标准)
先进性(在实现上面两个后的相对先进,太先进也不好)
网络设计任务
确定网络总体目标
确定总体设计原则
通信子网设计
资源子网设计
设备选型
网络操作系统与服务器资源设备
网络安全设计
网络设计原则
可用性:指网络或网络设备可用于执行预期任务时间所占总量的百分比。
可靠性:网络设备或计算机持续执行预定功能的可能性。
可恢复性:指网络从故障中恢复的难易程度和时间。
适应性:指在用户改变应用要求时网络的应变能力。
可伸缩性:指网络技术或设备随着用户需求的增长而扩充的能力。
网络实施原则
可靠性原则
安全性原则
高效性原则
可扩展性原则
网络实施步骤
工程实施计划
网络设备到货验收
设备安装
系统测试
系统试运行
用户培训
系统转换
分层设计
接入层:向本地网段提供用户接入
汇聚层:网络访问策略控制、数据包处理、过滤、寻址
核心层：数据交换
IP地址与子网划分
IP地址划分
A类
最高位 0
规定前8位是网络号,后24位是主机号
能容纳 2^24-2个主机
减去全0和全1的
B类
最高位 10
规定前16位是网络号,后16位是主机号
能容纳 2^16-2个主机
C类
最高位 110
D类
最高位 1110
E类
最高位 1111
子网划分(无分类编址)
IP地址=网络前缀+主机号
=网络号+子网号+主机号
172.18.129.0/24
什么意思呢?有24位是网络号,主机数2^8-2个,打破了类别
例1,将B类IP地址168.195.0.0划分成27个组网,子网掩码是多少
第一步:将IP地址化成二进制1010 1000 1100 0011 0000 0000 0000 0000
因为是B类,默认前16位是网络号
第二步:2^k>=27 ==>k=5
第三步:16位+5=21位,那就是21个1和11个0写出来就是了
1111 1111 1111 1111 1111 1000 0000 0000
第四步:将二进制的子网掩码换成十进制的子网掩码255.255.248.0
例2 ,将B类IP地址168.195.0.0划分成若干子网，每个子网内有主机700台，子网掩码为多少?
第一步:2^k>=700=>k=10, 说明有10位主机号
第二步写出子网掩码:1111 1111 1111 1111 1111 1100 0000 0000
第三步:将二进制的子网掩码转成十进制255.255.252.0
例3:问两个IP地址是否在同一子网内?
将两个IP地址化成十进制,查看子网掩码是否相同即可
例4:分配给某公司网络的地址快是210.115192.0/20,问该网络可以被划分为几个C类地址?
答:该地址的网络号是20位,C类地址的网络号是24位,所以该地址还能拿出4位当做网络前缀,,,,2^4=16个..
特殊含义的IP地址
127网络
回拨(本机)地址
网络号全0地址
当前子网中的主机
网络号全1地址
本地子网中的广播
主机号全1地址
特定的子网广播///192.168.255.255
对192.168网段进行广播
10.0.0.0/8
172.16.0.0/12 ==>
192.168.0.0/16
10.0.0.1至10.255.255.254
172.16.0.1至172.31.255.254 属于内部地址
192.168.0.1至192.168.255.254
169.254.0.0
0.0.0.0
保留地址,用于DHCP失效(win),当无法获取合法IP地址时,主机分配的一个假址地址,防止无休止的申请 ... (linux)...
无线网
优势
移动性
灵活性
成本低
容易扩展
接入方式
有接入点模式
公用交换电话网络(PSTN)
数字数据网(DDN)
综合业务数字网(ISDN)
非对称数字用户线路(ADSL)
同轴光纤技术(HFC)
无接入点模式
IEEE 802. 11 (WiFi)
IEEE 802. 15 (蓝牙Bluetooth)
红外(IrDA)
WAPI
3G/4G
WCDMA
CDMA2000
TD-SCDMA
名义上的国产
上面的画红----------------------------------------
LTE-Advanced
WirelessMAN -Advanced (802. 16m) (WiMAX)
分类
无线局域网(WLAN , 802.11, Wi-Fi)
无线城域网(WMAN , 802.16 , WiMax)
无线广域网(WWAN , 3G/4G)
无线个人网(WPAN , 802.15 , Bluetooth(蓝牙),ZigBee)
Html/Xml
(偶尔考一分)
选择题
<col>
定义表格中一个或者多个列的属性值
<strong>
定义强调文本
<HTML>
定义Html文档
......
IPV6
是替代IPV4的下一代,地址空间增大了2^96倍
单播地址
用于单个接口的标识符
任播地址
泛播地址.一组接口的标识符,IPv4广播地址
组播地址
IPV6的组播在功能上与IPV4类似
网络安全
安全属性
保密性
最小授权原则、防暴露、信息加密、物理保密
完整性
安全协议、校验码、密码校验、数字签名、公正
可用性
综合保障（IP过滤、业务控制、路由选择控制、审计跟踪）
不可抵赖性
数字签名
各个网络层次的安全保障
HTTPS=http+ssl
加密解密技术
对称加密技术
双方密钥相同
DES、3DES、RC-5、IDEA
优点：速度快，加密可以是大文件，效率高
缺点：加密强度不高，密码发送给对方容易被截获
非对称加密技术
每个人都有公、私密钥
用对方公钥加密
用自己私钥解密
RSA、ECC
优点：加密强度非常强
缺点：加密速度慢，无法很好的加密大文件。效率低
信息摘要
（保障信息完整性）
摘要就是一个正文的概要，这里是用正文生成摘要
将收到的正文产生一个摘要和收到的那个摘要进行对比，
如果相同就是没有被串改（两个都被串改？--->数字签名）
MD5(128)、SHA(160)
数字签名
能够确定这个信息时谁发出来的，解决摘要被截获的问题
发送方私钥签名，接收方用发送方公钥解密校验，
就能确定一定是对方发出来的信息
数字信封
让对称加密和非对称加密进行合作
用对称加密加密原文得到对称密码，再用非对称的对方公钥加密对称密码
数字证书
PGP
X.509
网络身份证
由专门的机构进行颁发
例题整合：
要求邮件以加密方式传输，邮件最大附件可达500MB，大宋这不可抵赖，如果被第三方截获，第三方无法串改
答：
邮件正文用对称加密，产生随机对称密码
邮件正文产生的摘要，用数字签名技术
用非对称（对方公钥）加密对称密码产生密码密文
将邮件密文，摘要密文，和密码密文发送给对方
病毒与木马
网络威胁与攻击
重放攻击(ARP)
所截获的每次合法的通信数据拷贝,处于非法的母的而被重新发送
拒绝服务(DOS)
对信息或其他资源的合法访问被无条件地阻止
窃听
不折手段(可能非法)窃取系统中的资源和敏感信息
业务流分析
长时间的窃听,并且利用统计分析方法对通信频道、信息方向、参数变化等等进行研究。从而发现有价值的信息和规律
信息泄露
信息被泄露或透露给某个非授权的实体
破坏信息的完整性
数据被非法的增删改、破坏儿收到损失
非授权访问
某一资源被某个非授权的人、或以非授权的方式使用
假冒
非法用户通过欺骗手段达到合法
旁路控制
利用系统本身的安全缺陷获取一些权益
授权侵犯(内部攻击)
特洛伊木马
是个间谍程序,目的很明确,破坏系统安全
陷阱门
在某一部件中设置了"机关",当提供特定的输入时允许违反安全策略
抵赖
否定自己发过某条信息
防护墙技术
网络级
效率高,工作层次低
包过滤
将指定的IP包丢掉(但是不能杜绝伪造地址)
状态检测
应用级
双穴主机
屏蔽主机
屏蔽子网
宏病毒一般感染以COM为扩展名的文件
受限站点是IE浏览器中安全级别最高的
Windows中默认权限最高的是administrator用户
多媒体基础知识
多媒体技术基础概念
音频相关概念
声音的带宽
人耳/乐器 :20Hz~20kHz
次声波<20Hz 超声波>20kHz
说话300~3400Hz
采样(放进计算机)
采样频率
频率越高,踩点越多,还原度越高
采样频率应为声音最高频率的2倍.只有达到这个数,才能基本上保证不失真
采样精度
画横线,越多还原度越高
图像的相关概念
亮度(暗,亮)
色调(红,绿)
饱和度
彩色空间
RGB(红绿蓝)普通电脑电脑显示器用得到
YUV(电视,兼容)
CMY(CMYK)印刷的三颜色
k是调出来黑色,因为CMY调成的黑色成本高
而却调出来颜色不怎么正宗
HSV(HSB)
矢量图是用一系列计算机指令描述和记录的内容
媒体种类
感觉媒体:指人们接触信息的感觉形式。如:视觉、听觉、触觉、嗅觉和味觉等。
表示媒体:指信息的表示形式。如:文字、图形、图像、动画、音频和视频等。
显示媒体(表现媒体) :输入输出设备。如:输入显示媒体键盘、鼠标和麦克风等;输出显示媒体显示器、打印机和音箱等。
存储媒体:存储数据的物理设备,如磁盘、光盘和内存等。
传输媒体:传输数据的物理载体，如电缆、光缆和交换设备等。
多媒体相关计算
图像容量计算
知道像素,位数
每个像素16位,图像位640*480像素,求容量?
640*480*16/8=614400B 因为一个一个字节占8位
知道像素,色数
640*480像素,256色的像素,求容量?
640*480*log∨2(256)/8=307200B
总结:一个字节等8位=2^8=256色
音频容量计算
容量=采样频率(Hz)*量化/采样位数(位)*声道数/8
视频容量计算
容量=(每帧图像容量(Byte)*每秒帧数+音频容量)*时间
例题
1.图像容量计算实例
某数码相机内置128MB的存储空间，拍摄分辨率设定为1600x 1200像素,颜色深度
为24位，若不采用压缩存储技术,使用内部存储器最多可以存储(1)张照片。
(1)A. 12 B.22 C.13 D.23
2.音频容量计算实例
CD上声音的采样频率为44.1kHz ,样本精度为16bit，双声道立体声，那么其未经压缩的数据传输率为(2)
(2) A.88.2kb/s B .705.6kb/s C.1411.2kb/s D.1536.0kb/s
3.视频容量计算实例
若视频图像每帧的数据量为6.4MB，帧速率为30帧/秒，则显示10秒的视频信息，其原始数据量为(3) MB.
(3)A.64 B.192 C.640 D.1920
答案:(1)x=(1600*1200*24/3)/1024/1024m,张=128/x=23.3张
(2)44.116*2=1411.2kb/s(因为是双声道)
(3)6.4*30*10=1920m
媒体的种类
JPEG
有损压缩(RBG转成YUV)离散余弦
JPEG-2000
有损&无损,压缩比更高,小波变换,医学图像应用
MPEG-1
离散余弦VCD,MP3
MPEG-2
离散余弦Huffman,DVD,有线/卫星电视,AAC
MPEG-21
融合不同协议,制定新标准,标准集成
MPEG-4
网络应用/可视电话,无线通信,增强交互性,数码权限管理,多媒体传输集成框架
MPEG-7
多媒体内容描述接口,具备描述功能,不是编码标准
标准压缩技术
➢空间冗余(几何冗余)
例如每张照片有大面积是相同的颜色只需要记下，那些位置是同一个颜
色即可,不需要记住每个点什么颜色
➢时间冗余
上一秒和下一秒,有太多画面不动的,(一样的),只需要记住是一样的就行了,不需要再次存一次(上课视频后面的黑板就是个例子)
➢视觉冗余
例如:人眼能分别的颜色远远少于RGB能表示
的颜色,有些一定范围内的都可以认为是一个
颜色,所以只记住少量代表即可
➢信息熵冗余
例如同一个功能函数,代码是不一样的,有些写的罗里吧嗦,
那些代码是可以进行简化的
➢结构冗余
和空间冗余类似,例如一张图片中,有多个相同的图案,只需要存一个,其他的只需要记住是那个一就行,还比如,不同类中的函数功能可能一样,就把函数抽出来做成工具函数
➢知识冗余
A→B,B→C,A→C这里的A→C就是个知识冗余,可以通过推理分析的,不需要再次存
10.法律法规知识
法律法规知识
知识产权
著作权及邻接权;
著作权
保护作者的利益
领接权
保护除了作者以为的权利
专利权;
某人申请了某项目专利
工业品外观设计权;
商标权;
地理标志权
新疆哈密瓜
集成电路布图设计权
保护期限
著作权
公民作品
署名权、修改权、保护作品完整权是没用限制永久保护的
发表权、使用权和获得报酬权，作者终生及死后50年，（第50年12月31日）
单位作品
发表权、使用权和获得报酬权，首次发表后的第50年的12月31日，
若期间未发表不保护
软件作品
公民
署名权、使用权没用限制
发表权、复制权、发行权、出租权、
信息网络传播权、翻译权、使用许
可权、获得报酬权、转让权
作者终生及死后50年，（第50年12月31日，以最后一个死亡作者时间为准）
单位
发表权、复制权、发行权、出租权、
信息网络传播权、翻译权、使用许
可权、获得报酬权、转让权
首次发表后的第50年的12月31日，若期间未发表不保护
注册商标
有效期10年(若注册人死亡或倒闭1年后,未转移
则可注销 ,期满后6个月内必须续注 )
实用新型和
外观设计专利权
保护10年，（从申请当天开始）
发明专利权
保护20年，（从申请当天开始）
商业机密（做了保护措施才算）
不确定的，没公开就保护，公开后公众可用
知识产权人确定
单位享有著作权
软件（职务作品）
属于本职工作中明确规定的开发目标
属于从事本职工作活动的结果
使用了单位资金、专用设备、末公开的信息等物质、
技术条件,并由单位或组织承担责任的软件
专利权（职务作品）
本职工作中作出的发明创造
履行本单位交付的本职工作之外的任务所作出的发明创造
离职、退休或调动工作后1年内，与原单位工作相关
单位享有部分著作权
（除署名权外）作品
利用公司的物质技术条件
合同约定著作权属于单位
委托创作
合同里面有的就属于委托方
合同中没有约定的就属于创作方
合作开发
只进行组织，提供物质咨询等辅助工作的没有著作权
共同创作的，按人头分割成果，可以分开申请
商标
谁先申请谁的
同时申请，先试用者得，需要证据
没有证据的就协商，或者抽签（不能留着）
专利
谁先申请谁的
同时申请就协商，但是不能同时驳回双方的专利申请
侵权判定
我在家完成的一篇论文（作品），不管是否发表（公之于众），都享有著作权
开发思想、过程、操作方法或者数学概念不受著作权保护
（如果说，我的处理过程比较独特，可以申请专利）
处理著作权的其他权利还可以保护（够独特）
不受保护的：
法律、法规，国家机关的决议、决定、命令和其他具有立法、行政、司法性质文件、官方正式译文
时事新闻
历法，通用数表、通用变革和公式
判定
不侵权
个人学习、研究或者欣赏;
适当引用;
公开演讲内容
用于教学或科学研究
复制馆藏作品;
免费表演他人作品:（他人要表演过）
室外公共场所艺术品临摹、绘画、摄影、录像:
将汉语作品译成少数民族语言作品或盲文出版。
侵权
未经许可,发表他人作品;
未经合作作者许可,将与他人合作创作的作品当作自己单独创作的作品发表的;
未参加创作,在他人作品署名;
歪曲、篡改他人作品的:
剽窃他人作品的;
使用他人作品,未付报酬;
未经出版者许可,使用其出版的图书、期刊的版式设计的。
标准的分类和编号
国家标准:GB-（国标的拼音）中国、 ANSI-美国、 BS-英国、JIS一日本
行业标准: GJB-中国军用标准、MIT-S-美国军用标准、 IEEE- 美国电气电子工程师协会
地方标准:国家的地方-级行政机构制订的标准
企业标准（规范）
企业内部规定的标准和规范
标准的编号
我国国家标准代号:强制性标准代号为GB推荐性标准代号为GB/T
指导性标准代号为GB/Z.实物标准代号GSB
行业标准代号由汉语拼音大写字母组成(如电子行业为SJ)
地方标准代号:由DB加上省级行政区划代码的前两位
企业标准代号:由Q加上企业代号组成
国际、国外标准代号:标准代号+专业类号+顺序号+年代号
基础框架地址(别人的):https://www.processon.com/view/link/5d6b8a92e4b0b5cfa9d2aaf2#map
收藏
0 条评论
下一页
