软件设计师中级

计算机系统

运算器和控制器

算术逻辑单元
累加寄存器器
状态寄存器
数据缓冲寄存器

指令寄存器
程序计数器
地址寄存器
指令译码器

内存按字节编址

内存存储单元16位 +1

浮点数

浮点数范围：-2的(2的阶码次)-1到-2的(2的阶码次)-1 乘 1-2负尾数次

海明码

海明码： $2^k-1>=n+k$

流水线计算

流水线执行时间=一条指令执行时间+最长时间段x(n-1) n为总指令数，吞吐率=n/流水线执行时间

Cache

cache：全相联。
cache与主存映射由硬件完成。
中断向量提供入口地址。

加密算法

AES：对称分组加密。
RSA：非对称数字签名。
DES：共享密钥加密。
MD5：摘要算法。
RC5：大量明文加密。

系统可靠度

系统可靠性：串联（其中任意一个模块失效都会导致系统失效）： $R=R_1*R_2*.....R_n$ 并行： $R=1-(1-R_1)(1-R_2)....(1-R_n)$

程序设计语言

符号表

高级程序编译时，可执行语句转为中间代码，声明语句则存入符号表。

词法、语法、语义

类型检查：语义分析。其他：语法分析。

有穷自动机

有穷自动机进行词法分析的工具。

有限自动机

最终要到达双圈（有限自动机最后要到达终态）

不确定有限自动机

下图：非确定性有限自动机。0：两种情况。要么循环要么转到B。

文法

文法：上下文无关文法推

知识产权

软件著作权

软著：发发表权（终生、死后五十年）署署名权修修改权保保护作品不受损（署修保永久保护）

数据库

关系代数（重点）

要求该关系表达式的结果集。先进行组合，RXS的属性列名分别为R…A，RB，RC，SA，S.B和SC。从中选取第一个分量(R.A)小于第6个分量(S.C)的元组。从中选取第3,4,5列。

R1<>R2自然连接，去掉重复的。

关系模式、范式

关系模式为R<U,F>，U={A,B,C},F={AB→C,C→B}，则关系有2个候选关键字AC和AB，并且有3个主属性。AC或AB可以推出所有属性。包含在任何一个候选码中的属性叫主属性。
关系模式R(E,N,M,L Q)，其函数依赖集为F={E→N,EM→Q, M→ㄩ}。主键：EM。E–>N，M–>L，N和L部分依赖于主键，所以为1NF。其他一般为2NF。函数依赖集R2(E,M,Q)

E-R图属性

E-R：派生属性：可以计算得到。多值属性：多个value

数据库设计

数据库设计：需求，概念，逻辑，物理

面向对象

多态

过载多态：操作有相同的名称，在不同上下文代表含义不同
包含多态：子类型化

绑定

静态绑定：代码编译时绑定
动态绑定：代码运行时绑定

面向对象设计原则

依赖倒置原则：依赖于抽象不依赖与实现。
里氏替换原则：任何基类可以出现的地方子类一定可以出现。
单一责任：一个类应该仅有一个引起它变化的原因。
开放-封闭：可以扩展不能修改。
共同封闭：一个变化影响到包则对其中所有类产生影响。
接口分离：依赖于抽象，不依赖于具体。
共同重用：重用包中一个类就要重用所有类。

面向对象分析与设计

面向对象分析：认定，组织，描述，确定对象
面向对象设计：识别类，定义属性，定义服务，识别关系，识别包
面向对象测试：算法层，类层，模板层，系统层

UML

UML关系（类间关系依次增强）：

依赖：类A方法中使用类类B的对象
关联：部分和整体。（聚合和组合是其特殊存在）
聚合：类A的部分是由类B对象组成，类A对象消失类B对象仍存在
组合：类A的部分是由类B对象组成，类A对象消失类B对象也消失
继承：
泛化：细化类，子元素共享父元素

类图（考得多）

一个方框里有一两根竖线

对象图（一个方框）

用例图（有小人）

时序图（有虚线分割）

通信图（方框里有冒号）

状态图（有大黑点）（难）

活动图（有黑竖条）（简单）

合并分叉、监护表达式

组件图（有书类标志）

–(供接口 --O需接口

部署图

展示软件和硬件的物理关系，实施阶段

设计模式

抽象类：不实现具体方法，只定义方法。其他类继承抽象类需要重写这些方法，想当与一个模板，占位置。
接口类：类似与抽象类，不需要用abstract。其他类implents接口类也需要重写该方法。

https://refactoringguru.cn/design-patterns

创建型模式（生抽单原，工厂）

工厂方法：创建对象的接口。子类决定实例哪个类。
（抽象工厂，不同工厂生成固定产品）

interface Factor {
	public Product createProduct();
}

class FactoryA implements Factory {
	@Override
	public Porduct createProduct() {
		return new ProductA();
	}
}

Factory factoryA = new FactoryA();
//父类 对象名 = new 子类(); 多态

抽象工厂：创建对象的接口。无需指定具体类。（抽象工厂，抽象产品，不同工厂生成想要的产品）（下午考过一次）

interface Factory {
	public ProductA createProductA();
	public ProductB createProductB();

生成器：复杂对象构建与表示分离。（下午考过两次）

# 产品、生成器构建获取产品、Director组装builder
# 用途：组成、装配
class Director {
	public void Construct(Builder builder) {
		builder.BuilderPart();
	}
}


abstract class Builder {
	public abstract void BuilderPart();
	public abstract Product getResult();
}

class Builder1 extends Builder {
	Product product = new Porcut();
}

原型：原型指定种类，复制原型创建新对象（下午考过一次）

interface Prototype {
	public Object Clone();
}

class Product implement Prototype {
	private int id;
	private double price;

	public Product(int id, double price) {
		this.id = id;
		this.price = price;
	}

	public int getId() {
		return id;
	}
	
	public double getPrice() {
		return price;
	}

	@override
	public Object Clone() {
		Product object = new Product();
		object.id = this.id;
		object.price = this.price;
		return object;
	}
}

单例：一个类仅有一个实例（只考上午）

结构型模式（享代组装外桥，适配器）

适配器：一个接口转换成另一个接口(类适配器、对象适配器)（下午考过一次）

USB usb = new Adapter();
usb.Request();

class USB {
	public void Request() {
		System.out.println("USB shu ju xian");
	}
}

class TypeC{
	public void SpecificRequest() {
		System.out.println("TypeC shu ju xian");
	}
}

class Adapter extends USB {
	private TypeC typeC = new TypeC();
	
	@Override
	public void Request() {
		typeC.SpecificRequest();
	}
}

桥接：抽象与实现分离（下午考过三次）

# n种产品 m种颜色 n*m个类
# 产品类，颜色类  实现和抽象分离
Product productA = new ProductA();
Color red = new Red();
productA.setName("产品A");
productA.setColor(red);
productA.Operation();

abstract class Product {
	private String name;
	protected Color color;
	
	public void setName(String name) {
		this.name = name;
	}

	public void setColor(Color color) {
		this.color = color;
	}

	public abstract void Operation();
}

class ProductA extends Product{ 
	@override
	public void Operation() {
		color.OperationImp(this.getName());
	}

interface Color {
	public void OperationImp(String name);
}

class Red implements Color {
	@ override
	public void Operation(String name) {
		System.out.println(name + "红色");
	}
}

组合：对象组合成树，表示部分-整体（文件夹-文件夹-文件）（下午考过四次）

Abstract floderA = new Floder(name:"floderA");
floderA.printName();
Abstract fileB = new Floder(name:"fileB");
fileB.printName();

abstract class AbstractFile {
	protected String name;
	public void printName() {
		System.out.println(name);
	}
}

class Floder extends AbstractFile {
	public Folder(String name) {
		this.name = name;
	}
}

class File extends AbstractFile {
	public File(String name) {
		this.name = name;
	}
}

装饰：对象添加额外职责（下午考过两次）
外观：子系统接口提供界面（下午考过一次）
享元：共享技术支持细粒度对象（下午考过一次）
代理：给其他对象提供代理控制对象访问

行为型模式

责任链：多个对象处理请求，避免耦合
命令：请求封装为对象
解释器：给定语言，定义文法，定义解释器
迭代器：顺序访问聚合对象各个元素
中介者：中介对象封装对象
备忘录；捕获对象内部状态，在对象外保存这个状态
观察者：一个对象状态改变，通知其他对象更新
状态：一个对象内部状态改变改变其行为
策略：封装起来可以互相替换（下午考过四次）
模板方法：定义算法骨架，一些步骤延迟到子类
访问者：作用于某对象结构的各元素

操作系统

进程管理（前趋图常考）

前趋图：在进程P执行前P信号量(S)，进程P执行后V信号量(S)
先将S1…按顺序标好。

进程三态：就绪、运行、等待

信号量PV

n个共享几个资源代表几个信号量max，-(n-几) 信号量min
信号量S：可以表示存放东西的数量，可以是0,1，n

死锁

系统中m个存储资源，n个进程最多使用w个资源。则m<nw有可能死锁。如果循环分配资源，最好发现不够就会死锁。

文件目录

修改目录文件时发生崩溃，对系统影响最大

多线程

多线程不能共享线程的栈指针

局部性原理（淘汰未被访问未被修改的）

分页存储管理

逻辑地址：2C25H，首数字为2，即页号为2，根据表中得到页帧号+C25H即可

磁盘调度（先排序柱面号，磁头扇区从小到大）

多级索引

一级：块/2
二级：块数平方/2

结构化开发

耦合

内容耦合：A直接访问B内数据
公共耦合：可以访问全局变量
标记耦合：A将数据传给B

内聚

逻辑内聚：
巧合内聚：抽出来组成新模块
通信内聚：读写数据
过程内聚：特定次序执行

设计原则（作用在控制内）

软件工程

CMM（成熟度模型）

1级：杂乱无章 2级：基本项目管理 3级：标准化 4级：详细标准 5级：定量分析

CMMI（成熟度模型集成）

CL0：未完成的 CL1：输入转输出 CL2：已管理的 CL3：已定义的 CL4：定量管理 CL5：优化的

瀑布模型（以前做过的系统需要重新做）（V型模型是瀑布的变种，关于测试活动）

增量模型（核心+一部分一部分）

原型模型（快速构建系统以理解问题）

演化模型（快速开发原型，根据用户意见进行迭代）

螺旋模型（适用于复杂大型软件）

喷泉模型（面向对象，无边界）

统一过程模型（初启、精化、构建、移交、产生）

敏捷方法

极限编程：价值观、原则、实践
水晶法：不同项目不同策略
并列争求法：迭代
自适应软件开发：6基本原则

度量法

环路复杂度：环＋1

白盒测试

覆盖准测由弱到强：语句覆盖-判定覆盖-条件覆盖-路径覆盖

可维护性指标（可理解性、可测试性、可修改性）（不选预防性选完善性）

可靠性：MTTF/ (1+MTTF)
可用性：MTBF/ (1+MTBF)
可维护性：1 / (MTTR+1)
沟通路径：n(n-1)/2

项目活动图

关键路径：时间最长的路径延迟时间：关键路径-最短时间

软件风险（不确定性、损失）

配置数据库：开发、受控、产品
配置管理不包括：质量控制、风险管理
功能性包括质量子特性

信息安全

防火墙

内网、DMZ（web、应用级）、外网

病毒

特洛伊木马：向外连接网络
宏病毒：攻击office软件
X卧底：攻击智能手机
蠕虫病毒：熊猫烧香、红色代码、爱虫病毒、震网

网络安全

HTTPS：SSL 443
MIME：与邮箱安全无关。邮箱加多媒体数据
基于UDP：DHCP、DNS、SNMP、TFTP
基于HTTP：SMTP(20)，POP3（110）、
URL：协议名://主机名.域名/路径/文件名

IP地址

A类地址码（子网掩码）：8位。B类地址码：16位。C类地址码：24位。
222.125.80.128/26。占用了26位。可用主机位: $2^6-2=62$ 。最小地址222.125.80.129，最大222.125.80.190
把上面的划分为222.125.80.128/28,可以的到2的28次-26次，即4个。
其他问题转为2进制

数据结构

时间复杂度

递归时间复杂度：T(n)=2T(n/2)+nlgn （ $nlg^2n$ ）、 T(n)=7T(n/2)+ $n^2$ （7平方-1）
T(n)=T(n-1)+n （ $n^2$ ）、 T(n)=8T(n/2)+ $n^2$ （ $n^3$ ，8平方-1）

线性表

队列

(Q.front+Q.size-1+M)%M、(Q.real-Q.size+1+M)%M

KMP模式匹配

a b a a b a c a
1 2 3 4 5 6 7 8
i从1开始。取1前面的字符串是0。取2前面的字符串a，0+1=1。取3前面的字符串ab，0+1=1。取4前面的字符串aba：前缀a和后缀a相等为1,1+1=2。取5前面的字符串是abaa：前缀a和后缀a相等，1+1=2。取6前面的字符串是abaab：前缀ab和后缀ab相同，2+1=3。取7前面的字符串是abaaba：前缀aba和后缀aba相同：3+1=4。
0 1 1 2 2 3 4

矩阵算位置（直接带入选项）

树

节点总数=度x个数 + 1
二叉树：

算法

回朔法（上午：1次，下午：2次）（N皇后问题）

4x4棋盘，放4个皇后，横竖斜两个皇后不能。
先放一个，一行一行试第二个
判断是否在一列：Qi列 == Qj列
判断是否在斜列：|Qi行-Qj行| == |Qi列-Qj列|

/* 代码填空、算法策略、解数据结果
非递归：循环迭代
j代表行号 */
#include <stdio.h>
#include<math.h>
#define N 4
int q[N+1]; //存储皇后的序号

int check(int j) {
	int i;
	for (i = 1; i < j; i++) {
		if (q[i] == q[j] || abs(i-j) == abs(q[i]-q[j])){
			return 0;
		}
	return 1
}

void queue() { // 求解N皇后方案
	int i;
	for (i=1;i<=N;i++){
		q[i]=0;
	}
	int answer=0; // 方案数
	int j=1; // 表示正在摆放第j个皇后
	while(j>=1){
		q[j] = q[j]+1; // 让第j个皇后向后一列摆放
		while (q[j]<=N&&!check(j)) { // 判断第j个皇后是否合法
			q[j] = q[j]+1;  // 不合法就往后放
		}
		if (q[j]<=N) {  // 表示第j个皇后合法
			if(j==N){ // 找到了N皇后的一组解
				answer = answer+1;
				printf("方案%d: ", answer);
				for (i=1;i<=N;i++){
					printf("%d ", q[i]);
				}
				printf("\n");
			}else{ // 继续摆放
				j = j+1;
			}
		} else { // 表示第j个皇后不合法
			q[j]=0; // 还原
			j = j-1; // 回溯
	}
}

		
int main() {
	queen();
	return 0;
}

// 递归
#include <stdio.h>
#include<math.h>
#define N 4
int answer=0;
int q[N+1]; //存储皇后的序号

int check(int j) {
	int i;
	for (i = 1; i < j; i++) {
		if (q[i] == q[j] || abs(i-j) == abs(q[i]-q[j])){
			return 0;
		}
	return 1
}

void queue(int j) { // 求解N皇后方案
	int i;
	for (i=1;i<=N;i++){
		q[i]=i;
		if (check(j)){ // 当摆放皇后位置合法时
			if (j==N) {  // 找到了N皇后的一组解
				answer = answer+1;
				print("方案%d: ", answer);
				for (i=1;i<=N;i++){
					print("%d ",q[i]);
				}
				printf("\n");
			}else{
				queen(j+1); //递归摆放下一个皇后
			}
		}
	}
}
int main() {
	queen(1);
	return 0;
}

//2015年上半年试题四 回溯法
pos[j]==pos[k]
j=1
!isplace(pos, j)
j<N
j=j-1
回溯法
2,4，1,3
3,1，4,2

//2019年上半年试题四 回溯法
queen[i]==queen[j[
1
Place(j)
Nqueen(j+1)
回溯法
2
(2,4,1,3)
(3,1,4,2)

分治法

一直二分，拆分成多个独立子问题，递归实现。归并排序（拆成一个一个最小，然后合并）

//2014年上半年 分治法
k<r+1
arr[k]=right[j]
begin<end
mergeSort(arr,mid+1,end)
分治
T(n)=2T(n/2)+n
O(nlgn)
O(n)
n1+n2

动态规划法

0-1背包问题、矩阵连乘、最长公共序列
与分治法类似，分成子问题，子问题不独立。表格记录子问题结果，用分治法会耗时。适合求解最优值问题。
两个性质：最优子结构、重叠子问题。

// 0-1背包问题：n个物品、vi价值、wi重量、w背包容量
// 贪心会先装价值最大的
// 动态规划：求背包为w-1的最优解、一直到w为0。然后N个物品也从最大到0。
// 这样就得到一个表格：从前i个物品选放入j容量背包。不选第i个物品：从前i-1个里选。选第i个物品条件：容量j>=第i个物品重量，否则就成为从不选第i个物品问题（即前i-1个里j减第i个物品重量）。
//f[i][j]=v[i]+f[i-1][j-w[i]]
//要考虑选第i个物品和不选第i个物品的总价值进行比较来抉择哪个
#include <stdio.h>
#define N 4 // 物品数量
#define W 5 // 背包容量
int max(int a, int b){
	return a>b?a:b;
}
int main() {
	int v[] = {0, 2, 4, 5, 6}; // 物品价值数组
	int w[] = {1, 2, 3, 4}; // 物品重量数组
	int f[N+1][W+1] = {}; // 子问题解数组
	int i,j;
	for (i=1;i<=N;i++){
		for (j=1;j<=W;j++){ 
			if (j>=w[i]){ // 选第i个物品的前提条件
				// 等于不选第i个物品和选第i个物品两者的较大值
				f[i][j]=max(f[i-1][j], f[i-1][j-w[i]]+v[i]);
			}else{
				f[i][j]=f[i-1][j];
			}
		}
	}
	printf("%d\n", f[N][W]);
	for (i=0;i<=N,i++){
		for (j=0;j<=W;j++){
			printf("%d ", f[i][j]);
		}
		printf("\n");
	}
	return 0;
}
//时间复杂度：O(NW)
//空间复杂度：O(NW)
//矩阵连乘-上午题：1动态规划、2时间复杂度O(n^3)、3空间复杂度O(n^3)、4计算方法
//最长公共序列：

// 2021年下半年动态规划
d[0][j]=j
str1[i-1]==str2[j-1]
d[i-1][j-1]+1
d[len1][len2]
动态规划
O(nm)
4

专业英语

trace 追踪

java题

继承：extends、实现：implements、其他：成员变量

/*2022年下半年 外观模式 */
public String getName()
void dispose(Patient patient)
new ConcreatePatient()
Facade
new Facade(patient)
f.dispose()

/*2022年上半年 备忘录模式 */
new Memento(state)
Memento.getState()
void add(Memento state)
Memento get(int index)
originator.saveStateToMemento()
originator.saveStateToMemento()

/*2015年上半年 访问者模式 */
public void visit(Book p_book)
public void visit(Articl
public void accept(LibraryVisitor visitor)
visitor.visit(this)
visitor.visit(this)

/*2023年上半年 策略模式 */
public void doPrint(Interva val)
ptr.doPrint(this)
st = new PrintIntervalsComma()
st = new PrintIntervalsDots()
st = new PrintIntervalsLine()

/*2019年上半年 策略模式*/
void stop()
BrakeBehavior
wheel.stop()
wheel = behavior
brake()

/*2015年下半年 策略模式*/
double acceptCash(double money)
cs = new CashNormal()
cs = new CashDiscount(0.8)
cs = new CashReturn(300, 100)
return cs.acceptCash(money)

/*2010年上半年 策略模式*/
FlyBehavior flyBehavior
TakeOffBehavior takeOffBehavior
flyBehavior.fly()
takeOffBehavior.takeoff()
extends
SubSonicFly()
VerticalTakeOff()

/*2018年下半年 状态模式*/
double travel(int miles, CfrequentFlyer context)
context.setState(new CSilver())
context.setState(new CGold())
context.setState(new CSilver())
context.setState(new CBasic())

/*2011年下半年 状态模式*/
State
tissueMachine.getNoQuarterState()
tissueMachine.getHasQuarterState()
tissueMachine.getSoldState()
tissueMachine.getSoldOutState()

/*2019年下半年 观察者模式*/
void update()
Observer
obs.update()
Subject
Attach(this)

/*2014年下半年 观察者模式*/
Sbuject
observer.update(temperature, hunidity, cleannerss)
notifyObservers()
measurementsChanged()
Observer
envData.registerObserver(this)

/*2021年下半年 享元模式*/
public abstract void draw()
Piece
Piece
piece.draw()
piece.deaw()

/*2016年下半年 装饰器模式*/
ticket.printInvooice()
super.printInvoice()
super.printInvoice()
new HeadDecorator(new FootDecorator(t))
new HeadDecorator(new FootDecorator(null))

/*2012年下半年 装饰器模式*/
abstract
String getDescription
abstract int cost()
Beverage beverage
beverage
beverage

/*2021年上半年 组合模式*/
protected
abstract boolean addMenuElement(MenuComponent element)
abstract List<MenuComponent> getElement()
LIST<MenuComponent> elementList
mainMenu.addMenuElement(subMenu)

/*2011年上半年 组合模式*/
abstract class
public abstract void add(MenuComponent menuComponent)
add(menuComponent)
menuComponent.print()
allMenus.print()

/*2010年下半年 组合模式*/
abstract class
this.name
Company
Company
children
children
root.Add(comp)
comp.Add(comp1)

/*2009年下半年 组合模式*/
abstract
null
List
childList
printTree(file)

/*2017年下半年 桥接模式*/
abstract void doPaint(Matri m)
imp.doPaint(m)
new GIFImage()
new LinuxImp()
image.setImp(imageImp)

/*2017年下半年 桥接模式*/

/*2017年下半年 桥接模式*/

/*2016年上半年 适配器模式*/
Address address
address.straat()
address.postcode()
address.plaats()
DutchAddress addrAdapter = new DutchAddressAdapter(addr)