软件设计师笔记

计算机组成与体系结构

数据的表示、计算机结构、Flynn分类法、CISC与RISC、流水线技术、存储系统、总线系统、可靠性、校验码

1. 数据的表示

（一）进制转换
R进制转十进制使用按权展开法：

十进制转R进制使用短除法

二进制转八进制、16进制

原码、反码、补码、移码

正数的反码不变。负数的反码符号位不变，其他位取反

溢出丢弃进位法则：在用有符号整型表示二进制数时，当后面的非符号位发生溢出时，符号位不变，直接丢弃溢出的进位。

二、开始转换：

1. [-128]原码 = 1000 0000
   说明：最高位1表示符号位，后7位发生了溢出，进位丢弃，符号位不变。
2. [-128]反码 = 1111 1111
   说明：除符号位外，其余各位对原码取反。
3. [-128]补码 = 1000 0000
   说明：在反码的末位加1，从而使后7位再次发生溢出，进位丢弃，符号位不变。

（二）浮点数运算

浮点数表示 KaTeX parse error: Undefined control sequence: \ce at position 1: \̲c̲e̲{N=M*R^e}
其中M称为尾数，e是指数，R为基数。
浮点数运算先要对阶、尾数计算、结果格式化

对阶部分：结果往大的对
尾数计算：尾数相加
结果格式化：保证小数点前面1位是1

计算机结构

PC，程序计数器。CPU首先从PC获取需要执行的指令地址，从内存（或者Cache）读取到的指令则暂存在IR（指令寄存器），然后进行分析和执行。

Flynn分类

SISD：386、486，目前多见于单片机
SIMD：阵列处理机常用，适合处理数组运算
MISD：理论模型
MIMD

CICS与RISC

CISC（复杂指令集计算机）：进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬件话，导致机器的指令系统逐渐庞大复杂。包含至少300条以上的指令

RISC（精简指令集计算机）：减少指令总数和简化指令功能，降低硬件设计的复杂度，指令能单周期执行，并通过优化编译提高指令的执行速度，采用硬布线控制逻辑优化编译程序

流水线

程序执行时多条指令重叠进行操作的一种准并行处理时限技术。取指-分析-执行

流水线吞吐量计算——单位时间内流水线完成任务数量或输出的结果数量

流水线的加速比计算公式

流水线的效率

层次化存储结构

Cache的存储形式：按内容存储、相联存储

Cache：提高CPU数据输入输出的效率，突破冯诺伊曼瓶颈，即CPU与存储系统间数据传送带宽限制。Cache改善系统性能的依据是程序的局部性原理。

局部原理

时间、空间局部性
工作集理论：工作集是进城运行时被频繁访问的页面集合。把频繁使用的页面打包放到cache中

主存

RAM，随机存取储存器。DRAM、SRM

ROM：MROM（Mask ROM，掩模式ROM）、PROM（Programmable ROM，EPROM（Erasable PROM，可擦出的PROM）、闪速存储器flash memory 闪存） BIOS就是ROM这类，BIOS（Basic Input Output System）基本输入输出biotin是一组固化到计算机内主板上一个ROM芯片上的程序，保存着计算机最重要的基本输入输出程序，开机后自检程序和系统自启动程序，可从CMOS中读写系统设置的具体信息。

（1）存储系统

主寸与Cache的地址映射中，全相联方式可以实现主存任意一块装入Cache中任意位置，只有装满才需要替换。

直接相联映射：主存中一块只能映象到Cache的一个特定块中。
组相联的映射：各区中某一块只能存入缓存的同组号的空间内，但组内各地址之间则可以任意存放。

计算机系统的存储器按照位置划分可分为内存和

磁盘结构与参数

当顺序排的时候，由于读取R0放到缓冲区，然后处理，磁头还在继续，所以要经过一个旋转周期到达下一个位置，总共耗时（33+3）*10+6（6表示读取+处理）

最短时间，应该是隔空排开，R0-x-R1，这样在处理缓冲区的同事，磁头已经转到R1位置就可以

DMA控制方式在主寸和外设之间直接建立数据通路进行数据的交换处理。

总线

内部总线：芯片级别
系统总线：
数据总线:一次性传输的bit位数
地址总线：操作系统管理的内存空间大小，比如32位系统地址空间索引范围在4g
控制总线

外部总线

系统可靠性分析——串联系统与并联系统

可靠性
失效率：

常考串、并联混合的一种，而模冗余系统不常考

差错控制——crc与海明校验码

常用的三种校验码：奇偶校验码、海明码、循环冗余校验码；

循环冗余校验码应用于数据通信领域和磁介质存储系统中。。利用生成多项式为k个数据为产生r个数据为产生r个校验位来进行编码，其编码长度为k+r。

海明码的校验位如何插入？是随机的吗？

操作系统

进程管理

进程的状态

前驱图

划分可以并行的任务，找到关键节点

进程管理——进程的同步与互斥

生产者——消费者问题

PV操作

临界资源：进程需要互斥地对其共享的资源
临界区：进入临界资源的那段代码
信号量

PV操作其实就是并发问题的解决方案

PV操作与前驱图

死锁问题

银行家算法——分配资源的原则

存储管理

分区存储组织（连续存储方法）：
首次适应算法、最佳适应算法、最差适应算法、

循环首次适应方法

页式存储组织

段式存储

快表
页面置换算法

补充LFU算法

LRU算法：最近最少使用算法
随机算法不稳定

这道题目要注意没有使用快表、要经过2次查表，第一次去读页表，第2次去找内存。其次，指令即使跨页了也是1次性读入，而数据跨页了需要2次

索引文件结构

文件和树型目录结构

空闲存储空间的管理

空闲区表发、空闲链表法、位示图法（重点）、成组链接法

注意把这个题中4195是序号

数据传输控制方式

内存和外设之间数据传输控制问题

虚设备与SPOOLING技术

把临界资源弄成共享资源

解决磁盘与外设速度差异

微内核系统

数据库（2023年3月9日）

数据库模式、ER模型、关系代数与元组盐酸、规范化理论、并发控制、数据库完整性约束、分布式数据库、数据仓库与数据挖掘

三级模式——两级映射

内模式管理如何存储数据、如何优化
概念模式：

表和视图的映射关系反映在外模式-概念模式映射

数据库设计过程

1. 概念结构设计主要就是做ER模型
2. ER模型转成关系模式（规范化理论【必考】）
3. 融入DBMS特点、考虑硬件方面进行物理设计

ER模型

先画局部、在合成全局ER图

一个实体转换为一个关系模式

联系：1-1、1-n、m-n

1-1联系：可以讲中间的关系与实体合并
1-n联系：可以将联系放在n这边实体
m-n联系：必须弄一个新的模式

关系代数

综合题目以选择题形式出现

并、交、差、【笛卡尔积、投影、选择、联接】

【要区分连接操作和笛卡尔积】
连接操作：把S1、S2都有的操作只保留1个

自然连接：需要对字段做选择

等值连接

左连接

右连接

外连接

内连接

规范化理论——函数依赖

设R(U)是属性U上的一个关系模式，X和Y是U的自己，r为R的任一关系，如果对于r中的任意两个原则u，v，只要有U[X]=v[X]，就有u[Y]=v[Y],则称X函数决定Y，或者Y函数依赖于X，记为X–>Y.

部分函数依赖

传递函数依赖

规范化理论价值与用途
数据冗余、更新异常、插入异常、删除异常

键

超码：唯一标识元组
候选码：超码去掉多余的属性
主码：候选码中任选一个
外码：其他关系的主键

求候选键（图示法）

范式

1NF：属性原子性，不可在分，存在数据冗余情况
2NF：1NF消除非主属性对候选码的部分依赖，要求非主属性对码的完全依赖
3NF：2NF消除非主属性对候选码的传递依赖。
BCNF：3NF消除主属性对候选键的传递依赖

模式分解（3月12号）

保持函数依赖分解

无损分解

判断是否是无损分解的方法：

1. 表格法

如果某一行全部为a，则R分解是无损分解

2. 集合法

并发控制

事务（把多个操作封装成一个整体来执行）：原子性、一致性、隔离型、持续性

并发产生的问题：丢失修改、不可重复度、脏读、幻读

解决方案：封锁协议，分为S封锁和X封锁，由此产生

两段锁会带来带来死锁问题：预防法、死锁的解除法。

数据库完整性约束

实体完整性约束：约束主键，要求主键不为空且唯一

参照完整性约束：对外码进行约束

用户自定义完整性约束

触发器：复杂的约束要求 实现方式。

数据库安全

数据备份

数据库故障与恢复

数据仓库与数据挖掘

BI的核心是数据仓库和数据挖掘。

数据仓库面向主题的，不是面向应用的。数据仓库会记录集成的数据。相对稳定性。

反规范化

由于规范化使得表不断拆分、从而导致数据表过多。这样虽然减少了数据冗余，提高了增删改的速度，但会增加查询的工作量。

技术：增加派生荣誉咧、增加荣誉列、重新组表、分割表（垂直分割和水平分割）。

大数据

数据量Volume、速度Velocity、多样性Variety、值Value

数据量大、关系复杂。

大数据处理系统应该具备的重要特征：高度可扩展性、高性能、高度容错、支持异构环境。

计算机网络（3月13）

七层模型

局域网内部有广播机制、不能通过的就是跨越网络的。局域网只能通过2层一下、集线器是1层设备。

网络技术标准与协议

IPX/SPX协议？
NETBEUI协议？

TCP协议的三次握手：

DHCP协议：IP地址的动态分配

DNS协议
重要的是递归查询和迭代查询c

计算机网络的分类

按分布范围分：LAN、MAN、WAN、因特网

按拓扑结构分：总线型、星型、环形

网络规划与设计

逻辑网络设计

物理网络设计

核心层：要求可靠性高、

IP地址与子网划分

主机号全0表示网络地址，全1表示广播地址

A类地址：第一个字是网络号
B类：前3个字是网络号
C类：前3个字
子网划分、合并子网称超网

子网掩码用来区分一个ip地址哪些是网络号、哪些是主机号

解题1:划分27个子网，则有5位二进制来表示。因此在B类地址上的主机号划分5位出来，子网掩码为256.256.1111 1000.0.0

无分类编址（无类域间路由）

无线网

网络接入结束

ADSL：非对称数字用户线路。上下行速率不对称

ipv6

系统安全分析与设计

信息系统安全属性

保密性：最小授权原则、防暴露、信息加密、物理保密
完整性：安全协议、校验嘛、密码校验、数字签名、公证
可用性：综合保障（IP过滤、业务流控制、路由选择控制、审计跟踪）
不可抵赖性：数字签名

对称加密和非对称加密

对称加密：加密和解密的密钥是同一个。DES（替换+移位）、3DES（使用两个56位密钥K1、K2）、AES、RC-5、IDEA。加密速度快、效率高、但强度不高、密钥分发困难
非对称：公钥加密，私钥解密；私钥加密，公钥解密；RSA（512位或者1024位密钥，计算量大，难破解）、Elgamal、ECC（椭圆曲线算法）

信息摘要

摘要算法采用单向散列函数、固定长度的散列值
常用的消息摘要算法有MD5、SHA等，MD5数据产生128位、sha产生160位

数字签名

防止抵赖的技术

对数字摘要进行签名，避免数据过大。

数字信封与PGP

数字证书：证明身份的东西，由CA授权，验证数字证书的有效性真实性采用数字签名

练习题

要求邮件以加密方式传输，邮件最大附件内容可达500MB，发送者不可抵赖、若邮件被第三方截获，第三方无法篡改。

对数据量大的文件采用对称加密方法，所以第一步产生随机密钥K，对数据进行加密，然后需要把随机密钥发送给接收方。第二步，就把随机密钥用接收方的公钥加密发送出去，接收方用自己的私钥解密拿到随机密钥K。

各个网络层次的安全保障

http+ssl
http+tsl

二层以上靠协议来保证安全。IPSec 通过

传输层：TLS、SET（电子商务而生的协议）

网络威胁与攻击

注意区分：窃听与业务流分析

防火墙技术

应用级要把信息拆开进行分析

防火墙最基本的功能就是控制在计算机网络中，不同信任程度区域传送的数据流。防火墙对刘静它的网络通信进行扫描，这样就能够过滤掉一些攻击，以免其在目标计算机上被执行。防火墙还可以关闭不使用的端口、隐藏内部细节。所有访问都经过防火墙因此就能产生记录日志，统计网络使用情况。

数据结构与算法

数组与矩阵、线性表、广义表、树与二叉树、图、排序与查找、算法基础与常见算法

数组

考察存储地址的计算

稀疏矩阵

数据结构的定义

1. 数据结构的概念

2. 数据逻辑结构

线性表的定义

顺序表和链表

单链表、双链表、循环链表

线性表-顺序存储与链式存储对比

线性表-队列与栈

先进先出

广义表

广义表是以递归形式定义的

广义表的长度与深度

基本运算是head、tail

树与二叉树

（1）性质

（2）二叉树的遍历：前序、中序、后序、层次遍历

（3）反向构造二叉树：
根据前序和中序构造一颗二叉树。

（4）树转二叉树

（5）查找二叉树

图论

图的存储分为（临接矩阵和邻接表）

算法基础

特性：有穷性、确定性、输入、输出、有效性

时间复杂度和空间复杂度

查找

• 顺序查找，从头到尾与表中元素比较一遍，如果中间存在关键字key的元素，则返回成功；否则，查找失败。ASL = （n+1） / 2；

• 二分查找

• 散列查找： 冲突解决方法：开放定址法、线性探测法、伪随机数法

排序（重点）

考点：稳定性、时空复杂度

• 插入类排序：直接插入排序、希尔排序（分组）

好处是减少直接插入排序的挪动次数，从大的范围线做好排序，然后使用简单插入排序

• 交换类排序：冒泡、快速排序

• 选择类排序：简单选择排序、堆排序

堆排序：先建立堆，调整

归并排序

基数排序：借助多关键字排序思想对单逻辑关键字进行排序的方法。

【记忆】

程序设计语言与语言处理程序基础（编译原理部分）

编译与解释、文法、正规式、有限自动机、表达式、传值与传址、多种程序语言特点。

文法定义

语法推导树

有限自动机

正规文法与DFA的转化

DFA可以表达出状态之间的转换

根据文法对应正规式G[S]

有限自动机

表达式

前缀表达式、中缀表达式、后缀表达式

逆波兰表达式，括号不要写到树上去。

函数调用——传值与传址

传值调用：形参取的是实参的值，形参改变不会导致调用点所传的实参的值发生改变。

引用（传值）调用：形参取的是实参的地址

程序语言特点

1. fortran语言：科学计算、执行效率高
2. Pascal语言，为教学而开发，表达能力强，Delphi
3. C语言，指针操作能力强，高效
4. Lisp语言，函数式程序语言，符号处理，人工智能
5. C++ 面向对象
6. Java语言，面向对象，中间代码 跨平台 JVM
7. C#语言 面向对象，中间代码 .net
8. Prolog语言，逻辑推理，简介性

法律法规（2-3分）

著作权法、计算机软件保护条例、商标法、专利法

知识产权：著作权及邻接权、专利权、工业品外观设计全、商标全、地理标志全、集成电路布图设计权。

考点：保护期限、知识产权人确定、侵权判断

保护期限：

知识产权人确定

侵权判定（常考）

标准化基础知识

标准分类

多媒体基础

多媒体技术基本概念
多媒体相关计算问题、常见多媒体标准、数据压缩技术

音频相关技术

声音带宽：人耳：20HZ-20KHz，说话300-3400
乐器：20-20khz
采样：采样频率、采样精度、采样频率应为声音最高频率2倍

图像相关概念

彩色空间：RGB、YUV（YIQ、YCbCr）、CMY、HSV（HSB）

媒体的种类

注意：显示媒体（表现媒体）：输入设备也是这一类的

多媒体相关计算问题

计算数据容量

常见的多媒体标准

数据压缩基础

空间、时间、视觉、信息熵、结构、知识冗余

有损压缩与无损压缩

软件工程

（1）瀑布模型、结构化模型代表

当前阶段严重依赖于上一个阶段的成果
问题在于：在需求分析阶段，需求并不明确，

【使用场景】适用于需求明确的模型，和二次开发的模型

原型模型：适用于需求分析阶段，针对需求不明确的情况下，构建一个简易的系统

增量模型：原型 + 瀑布，一步步叠加，先完成核心模块，风险比较小。

螺旋模型

螺旋模型引入了风险分析，这个是它最显著特征。

V模型：与瀑布模型很接近。

测试分为各个阶段，在需求分析阶段就会开始写验收测试和系统测试阶段。
概要设计会进行集成测试，详细设计会写单元测试，V模型强调测试要贯穿于整个过程

喷泉模型：【面向对象的建模】

构件组装模型：

把软件做成一个个构件，提高复用性，构建一个构建库。

统一过程（UP）：用例驱动、架构为中心、迭代和增量

敏捷开发方法：

需求分类

系统涉及的角色、流程，收集用户需求转成计算机系统需求

系统需求：功能、性能、设计约束

结构化设计

内容耦合的耦合程度最高。

软件测试

测试原则与类型

测试类型：动态测试和静态测试

动态测试：黑盒、白盒测试、灰盒测试

测试用例设计
黑盒测试：等价类划分、边界值分析、错误推测、因果图

等价类划分：对所有类的数据进行分类
边界值分析：及其容易发生问题的地方，在边界上下浮动一丢丢
错误推测：
因果图：从结果反推原因

白盒测试：基本路径测试、循环覆盖测试、逻辑覆盖测试
主要了解一系列逻辑覆盖测试
语句覆盖、判定覆盖、条件覆盖、条件判定覆盖、修正的判断覆盖、条件组合覆盖、点覆盖、边覆盖、路径覆盖。

测试阶段

单元测试、集成测试、确认测试、系统测试；

软件测试-McCabe复杂度

路径覆盖要设计若干个测试用例、覆盖程序中所有的路径

系统运行与维护

软件过程改进CMMI

能力成熟度模型、衡量软件开发承包商改善软件质量的问题

分为5个等级：一级：混乱级、二级已管理级

定量管理级别要强调量化

项目管理

风险管理

风险曝光度：计算方法是风险出现的概率乘以风险可能造成的损失

面向对象

对象、类（实体类、边界类、控制类）、抽象、封装、继承与泛化、多态、接口、消息、组建、模式和复用；

多态：对于Java、C++˙中多态实现、Python有特殊的鸭子类型；

单一职责原则：设计目的单一的类
开放-封闭原则：对扩展开放，对修改封闭
Liskov替换原则：子类可以替换父类
依赖倒置原则：要依赖于抽象，针对接口编程，不要对实现编程
接口隔离原则（单一职责）：多个专门的接口与使用单一的总接口要好
组合重用原则：尽量使用组合，而不是继承关系，继承是一种紧耦合
迪米特原则：一个对象应当对其他对象有尽可能少的了解，

UML

UML就是建模，用图和关系对现实世界抽象

结构图（静态图）；类图、对象图、包图、组合结构图、构件图、部署图、制品图

行为图（动态图）：用例、顺序/序列图、通信/协作图、定时图、状态图、活动图、交互概览图；

注意用例图这个得根据题目来归类。

设计模式的概念

架构模式：软件设计中的高层角色，C/S结构属于架构模式，反映了开发软件系统过程中所做的基本设计决策；

设计模式：关注软件系统的设计，与具体实现语言无关

惯用法：是最低层的模式，关注软件系统的设计与实现

设计模式的分类

创建型模式：抽象工厂模式、构建器模式、工厂方法模式、原型模式、单例模式

解释器模式相当于构造一个虚拟机

数据流图（15分）

数据流图基本概念

数据字典

数据流图平衡原则

1. 父图与子图之间的平衡
2. 子图内的平衡原则

两种典型数据流图问题，黑洞（加工只有流入没有流出）和奇迹（加工只有流出没有流入）

习题

第（4）问中，讲可能出现的问题包括：加工出现黑洞或者奇迹情况、数据流命名错误，以及数据流的流入和流出名称相同。

数据库设计

ER模型和关系模式
需求分析（需求说明书、数据字典）
概念结构设计——ER模型；
逻辑结构设计：
物理设计

ER联系，1:1联系、1:n的联系、m：n的联系；
转换的基本原则要注意，中间的联系如何处理这个需要注意到/

UML

用例图、类图与对象图、顺序图、活动图、状态图、通信图、构件图

用例图

包含关系、扩展关系、泛化关系

注意：参与者和用例的识别

类图与对象图

要注意类图之间的关系

棱型的位置表示整体

顺序图（动态图）

要表现对象之间的消息
对象 、 生命线、消息传递

活动图

从结构上来将，能够表现处理流程。

状态图

通信图

顺序图和通信图都是表现交互特征。

UML建模例题

数据结构及算法应用

分治法、回溯法、贪心法、动态规划法
【未完待补～～～】