潘鑫博客

软件设计师(中级)笔记

11/12/2022 考试
(adsbygoogle = window.adsbygoogle || []).push({});

# 1. 前言

计划: 参加2023年5月份考试，不允许异地考试，推迟到11月份 11月份顺利通过 上午150min 选择题 下午150min 问答题

# 2. 计算机组成原理与体系结构

# 数据的表示

原码 第一位为符号位，0表示正数，1表示负数 不能直接计算 反码 正数与原码一致 负数：符号位不动，其余按位取反 不能直接计算 补码 正数与原码一致 负数：反码 加一 计算结果正确 移码 正数：补码首位取反 负数：反码首位取反 计算结果正确 利于数轴表示 表示范围 原码、反码：-127~127 补码：-128~127

# 浮点数运算

N = M*R^e^

对阶 => 尾数计算 => 结果格式化 第一个是1-9，不能超过一位，也不能是0

# 计算机结构

CPU:
  运算器:
    1. 算数逻辑单元ALU
    2. 累加寄存器AC
    3. 数据缓冲寄存器DR
    4. 状态条件寄存器PSW
  控制器:
    1. 程序计数器PC
    2. 指令寄存器
    3. 指令译码器IR
    4. 时序部件
  主存储器
  主机
1
2
3
4
5
6
7
8
9
10
11
12
13

指令和数据均存放在内存中，通常由 PC（程序计数器）提供存储单元地址取 出的是指令，由指令地址码部分提供存储单元地址取出的是数据。因此通过不同的寻址方式来区别 指令和数据。

PC（程序计数器）是用于存放下一条指令所在单元的地址。当执行一条指令 时，处理器首先需要从 PC 中取出指令在内存中的地址，通过地址总线寻址获取。

程序计数器（PC）是存放执行指令的地方，计算之前就要用到。

累加寄存器用来暂时存放算术逻辑运算部件 ALU 运算的结果信息。

指令寄存器（IR）保存当前正在执行的一条指令。

地址寄存器（AR）用来保存当前 CPU 所要访问的内存单元的地址。

# Flynn分类法

计算机体系结构分类

体系结构类型 结构 关键特性 代表
单指令流单数据流SISD 控制部分：一个
处理器：一个
主存模块：一个		 单片机
SIMD 控制部分：一个
处理器：多个
主存模块：多个		 :-- 阵列处理机
MISD 控制部分：多个
处理器：一个
主存模块：多个		 :-- 理论模型
多指令流多数据流MIMD 控制部分：多个
处理器：多个
主存模块：多个		 :-- 多处理机系统

# CISC(复杂)与RISC

CISC(复杂)： 计算机还没大规模应用时提出来的，计算机是定制的，很多年前的

  • 指定数量多，使用频率差别大，可变长指令

RISC(精简): 现在的主流

  • 指令数量少，使用频率接近，定长格式
  • 增加了通用寄存器，效率高，硬布线逻辑控制为主
  • 支持流水线

# 流水线

取指 => 分析 => 执行 由三个部件完成，未使用流水线有大量空闲状态 类似于汽车的流水线，充分利用部件

流水线计算 流水线周期：执行时间最长的一段 取指2ns、分析2ns、分析1ns，100条指令多少时间？ 周期：2ns 理论公式(优先) 100*2+2+1=203ns 实践公式： (100+2)*2=204ns 流水线吞吐率(TP，Though Put rate) 单位时间内处理的任务数量 TP= 指令条数/执行时间 上一题的TP：100/203 忽略建立过程： 最大吞吐率=1/流水线周期 流水线的加速比： S=不使用流水线的时间/使用流水线的时间 (2+2+1)*100/203 流水线的效率

# 层次化存储结构

提高速度的性价比方案

# Cache

速度最快的存储器，优先选择寄存器，其次Cache 命中率 局部性原理

  • 时间局部性：刚刚访问完的指令再次访问
  • 空间局部性：数组
  • 工作集理论 例如做循环时 例如做循环时

cache-直接相联映像：

电路简单，冲突概率大，访问速度最快，主存中的一块只能映射到 Cache 的一个特定的块中。

全相联映像：

冲突率低，查询复杂，主存的任意一块可以映射到Cache中的任意一块。

组相联映像：折中方案

# 随机存储器与只读存储器

主存-编址

按字编址

按字节编址

8*4位的存储器 8表示地址空间 4表示，每个地址空间的容量

# 磁盘工作原理

# 计算机总线

内部总线：芯片级别 系统总线：vga

  • 数据总线

  • 地址总线

  • 控制总线

  • 外部总线

单总线结构的优点是控制简单方便，扩充方便。但 由于所有设备部件均挂在单一总线上，使这种结构只能分时工作，即同一时刻只能在两个设备之间 传送数据，这就使系统总体数据传输的效率和速度受到限制，这是单总线结构的主要缺点。

# 系统可靠性分析

串联：可靠度相乘 并联：1-(1-可靠度)相乘 模冗余模型 输入 => 通过表决器 => 输出

# 校验码

码距，两个码字的最小距离，重复发送 例如：码距3，111000，重复3次 检错与纠错

# 奇偶校验

可以做检错，但不能纠错

# 循环校验码CRC

可以做检错，但不能纠错 模2除法 补多项式位数减一个0 余数为0，正确

# 海明校验码

既可以检错，又可以纠错

2r≥m+r+1

# 3. 操作系统原理

管理系统的软硬件资源 人与硬件之间的接口 应用软件与硬件之间的接口

  • 进程管理

  • 存储管理

  • 文件管理

  • 作业管理

  • 设备管理

  • 微内核操作系统

进程是动态的，程序是死的，静态概念，只有程序运行时有进程

# 进程状态

# 三态模型

运行态 就绪态：就差cpu资源了 等待态：除了cpu资源还差其它资源

等待态 =>就绪态 => 运行态

# 五态模型

认为处理 挂起 => 静止就绪

# 前趋图

# 同步与互斥

# PV操作

临界资源：互斥的共享资源，打印机、磁带机 临界区：访问临界资源的代码 信号量(S)：特殊的变量，专属变量 P操作，申请资源：S-1 V操作，释放资源：S+1

箭头起点V操作，终点P操作

# 死锁问题

不发生死锁的最少资源数 (n−1)k+1

产生的条件：

  1. 互斥
  2. 保持和等待
  3. 不剥夺
  4. 环路等待

预防与避免 银行家算法 分配资源后能够执行下去，类似于银行贷款前要评估贷款人能否还款

# 分区存储组织

首次适应法：第一个能容纳的位置 最佳适应法：仅仅比需要的空间大一点的位置，系统可以保留较大的块 最差适应法：使用空闲区最大的块 循环首次适应法：空闲块连成环状，顺次使用

# 页式存储

分区管理只能一次性装入内存，不能运行大内存程序 等分4k，一个页 内存的利用率高 缺点：增加了系统开销，存在页表，可能产生抖动现象

逻辑地址与物理地址的转化 页内地址相同 物理块号(页帧号)

# 段式存储

段的大小可以不一致 优点：便于共享内存 缺点：内存利用率低

# 段页式存储

先分段再分页

# 快表

放在catche里面 慢表在内存里面

# 页面置换算法

最优算法：理论层面的，事后诸葛亮 先进先出：可能产生抖动 抖动：添加了资源反而效率低了 缺页：内存里面没有数据

最近最少使用算法：

不会抖动，理论依据是局部性原理

练习题 没有使用快表：先在内存查表才能读取内存块，每个块需要2次内存访问 对于指令会一次性读取，只产生一次缺页中断

# 索引文件结构

一般是0-12，一共13个索引结点 0-9是直接索引：直接对应物理盘块 10一级间接索引 11二级间接索引 12三级间接索引

逻辑块号从0开始

# 文件和树形目录结构

R 只读文件 A 存档树形 S系统文件 H隐藏文件

# 空闲存储空间管理

位视示图法，飞机票座位展示 1表示已经占用，0空闲

# 数据传输控制方式

程序控制方式：CPU控制，较为低级，严重影响CPU的利用率 程序中断方式：外设完成任务发出中断，CPU无需等待而提高了传输请求的响应速度 DMA方式：直接存取控制方式，有专门的DMA控制器 通道方式：专门开辟一条隧道，成本高 输入输出处理机(IOP)：

# 虚设备与Spooling技术

有缓冲区，假脱机技术

# 微内核操作系统

只把最核心的放在内核里面，出问题的概论较低，区分用户态和核心态 单体内核

# 4. 数据库

# 三级模式-两级映射

外模式/用户模式：视图 映射 概念模式：表

映射 内模式/存储模式：文件 操作系统 物理数据库

# 数据库设计过程

需求分析：需求说明书，数据字典，数据流图、实体联系图

概念结构设计：ER模型

逻辑结构设计：关系模式、关系规范化

物理设计：

# E-R模型

方框--实体 圆形--属性 菱形--联系

# 关系代数

并，数据合在一起，去重 交，公共的数据 差 笛卡尔积 X：行列都组合 投影πSno,Sname(S1)：选择部分列 选择σSno=No00003(S1)：部分行 自然联接S1⋈S2：类似于联表 inner join

# 规范化理论

# 价值与用途

非规范化的关系模型，可能存在问题：数据冗余、更新异常、插入异常、删除异常

# 函数依赖

# 键

超键：唯一标识元组，可能存在冗余属性 候选键：可以有多个，没有冗余，例如：序号、身份证号 主键：候选键中任选一个 外键：其它关系的主键

# 求候选键

找出入度为0的节点 有可能为组合键

主属性

候选键的一部分，主属性是候选码所有属性的并集

# 范式(必考)

层层递进的 1NF 属性值都是不可分的原子值 不能有类似于合并单元格的存在，拆列 2NF 消除非主属性对候选键的部份依赖，分表

例如：学号，课程号，成绩，学分

学号，课程号共同决定了成绩，两个合起来是候选键，只需要课程号可以推出学分(非主属性)

3NF 消除非主属性对候选键的传递函数依赖，分表

例如：学号、姓名、系号、系名、系位置 BCNF 消除主属性对候选键的传递依赖，通过学号可以得到系名，通过系名可以得到系位置(非主属性)

# 模式分解

# SQL语句

建表

CREATE TABLE

查询

SELECT

FROM

GROUP BY HAVING

ORDER BY ASC|DESC

# 并发控制

问题：

丢失更新

不可重复读

都脏数据

封锁协议

S封锁，共享锁

X封锁，排他锁

# 数据库完整性约束

实体完整性约束：主键非空、唯一

参照完整性约束：外键，

用户自定义完整性约束

触发器：需要有脚本支持

# 5. 网络

OSI七层模型

序号 层 主要功能 协议
7 应用层 实现具体的应用功能 DHCP, DNS, FTP, HTTP, IMAP4, NNTP, POP3, SMTP, SNMP, SSH, TELNET, NTP
6 表示层 数据的格式与表达、加密、压缩 SSL, WEP, WPA, Kerberos
5 会话层 建立、管理会话 Logical Ports 21，22， 23， 80
4 传输层 端到端的连接(端口) TCP、UDP
3 网络层 分组传输与路由选择(IP) 三层交换机、路由器、ARP、RARP、IP、ICMP、IGMP
2 数据链路层 传送以帧为单位的信息（MAC） 网桥、交换机、PPTP、L2TP、SLIP、PPP， Wi-Fi
1 物理层 二进制传输(0/1) 中继器、集线器

TCP/IP模型，将OSI的简化为四层模型

基于TCP的

POP3: 110，邮件收取

FTP: 20 数据端口，21控制端口

HTTP/Telnet 23 /SMTP25

基于UDP的

DHCP67/TFTP69/SNMP161/DNS53

管理距离是各种路由协议的优先权，当多个路由协议转发的关于某个目标的 多条路由，使用管理距离选择权限最高的路由，管理距离小的优先级最高。

# IP地址

32位

A类0

B类10

C类110

D类1110和E类11110不用

ip 网络号+主机号

主机号全为1是广播地址，全为0是子网掩码

网关要与IP地址 处于同一网段

# 网络规划与设计

实用性原则

开放性原则

先进性原则

汇聚交换机——过滤作用

# 计算机网络分类

# 6.安全

# 对称加密

使用同一套密钥，效率比较高

DES、3DES、RC-5、IDEA算法

# 非对称加密

公钥和私钥成对出现

公钥加密，私钥解密，也可也私钥加密，公钥解密

RSA、ECC(椭圆曲线加密)算法

# 数字签名

用发送方的私钥加密，用发送方的公钥验证

# 信息摘要

使用的是单向加密技术，不可逆

MD5(128位)、SHA(160位)算法

# PKI公钥体系

管理公钥，密钥的注册，更新、注销

层 措施
应用层 PGP(机密邮件), HTTPs
表示层 ssl
会话层 ssl
传输层 TLS(基于ssl3.0) SET
网络层 防火墙、IPsec
数据链路层 链路加密
物理层 隔离、屏蔽

# 被动攻击

监听：消息内容的获取，业务流分析

# 主动攻击

中断，篡改，伪造

Dos与DDos

拒绝服务

漏洞发现与补丁管理是 针对系统安全需求的措施

# 防火墙

网络级：

包过滤，速度快，安全性低

状态检测，检查包里面，速度慢，安全性高

应用级:

双穴主机

屏蔽主机

屏蔽子网

木马：窃取机器信息，需要联网

病毒：破坏电脑

# 7. 数据结构与算法基础

# 数组与矩阵

代入法求解

# 线性表

循环队列：

队空条件：head=tail

队满条件：(tail+1)%siza=head

# 广义表

表头：最外层第一个元素

表尾：除了第一个元素，其它所有元素

# 二叉树

树的层次==树的深度

满二叉树

完全二叉树：从左到右逐层放置的

非完全二叉树

# 查找二叉树/排序二叉树：

左子节点<根节点<又子节点

类似于mysql 的索引

插入节点：

  1. 如果键值已经存在，则不再插入

删除节点：

  1. 叶子节点，直接删除

  2. 如果删除的节点只有一个子节点，则子节点与父节点连接

  3. 如果有两个子节点，则在左子树上寻找最大的。

# 最优二叉树/哈夫曼树

无损压缩的方式

# 线索二叉树

有虚线的键线

遍历更加快捷

# 平衡二叉树

越平衡查找效率越高

任意节点的左右子树深度相差不超过1

叶子节点深度：0，度就是下面有几个子节点

平衡度为左节点深度-右节点深度

每个结点的平衡度只能为-1，0，1

# 图

# 存储

邻接矩阵

用一个n阶方阵R来存放图中个节点的关联信息，1表示有邻接边，只需要存储一半就可以了

邻接表

第一个数字表示目标，第二个数字表示距离

# 图的遍历

深度优先，先往下走

广度优先，先水平走

# 拓扑排序

活动/任务之间有先后关系

可能产生多个不同的序列

# 图的最小生成树

权值最小

树是没有环路的，边的数量比节点数少一个

普里姆算法

克鲁斯卡尔算法

# 算法的特点

有穷性，执行有穷步之后结束

确定性，算法中每一条指令必须有确切的含义，输入相同，输出相同

输入>=0

输出>=1

有效性，算法中的每个步骤都能有效执行并能得到确定的结果

# 时间复杂度

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

# 二分查找法

注意细节

# 散列表

类似于hash

# 排序(必考)

希尔排序比直接插入排序效率高，先大致理好顺序，再排序

# 堆排序

小顶堆

大顶堆

重建堆的使劲按复杂度log2n

建堆过程，擅长求前几名

image

总体思想，缩小问题规模

# 8. 系统开发基础

# 开发模型

瀑布模型：以线性的顺序，有利于管理，适用于需求比较明确的项目开发。

V模型：重视测试，同样把测试放在编码之后。

喷泉模型：面向对象的开发模型，迭代更新，节约开发成本，管理起来更困难。

原型化模型：用户表述不清楚，产品经理画个原型找客户沟通。

演化模型：

螺旋模型：

统一过程：用例驱动，以架构为中心，迭代和增量

敏捷方法：自适应方法，水晶方法，特性驱动开发，极限编程；

极限编程：

对费用严格控制

XP 提倡结对编程，代码所有权归于整个开发队伍。其中，结对编程就是一 种对代码的审査过程，XP 主要解决代码质量低的问题，编码速度不能改变。

4大价值观：沟通，简单，反馈，勇气；5大原则：快速反馈，

# 软件开发方法

  1. 结构化方法

    面向数据流，不适用于大型项目

    体系结构设计：主要是指要开发的系统中包含哪些部件，这些部件与部件之间的关系就是体系 结构的设计。

    数据设计：也称为数据库设计，主要包含数据库的设计和这个数据所包含的核心表的设计。

    接口设计：用于子系统和模块之间或内部系统和外部系统之间的各种交互，如功能描述、输入 输出的定义、错误处理的设计。

    过程设计：也称为模块详细设计，主要是详细模块的实现算法，以及模块所使用的数据结构。

  2. 原型法

  3. 面向对象方法

    更好的复用性

  4. 面向服务的方法(SOA)

# 需求分析

# 软件设计

模块设计原则：

高内聚低耦合，希望被调用次数多，调用别人次数少

越向下程度越低

内聚类型 描述
功能内聚 每一个完成单一功能
顺序内聚 顺序执行
通信内聚 以一个数据结构
过程内聚 按照特定的次序
瞬时内聚/时间内聚 时间间隔内执行
逻辑内聚 完成逻辑上相关的一组任务
偶然内聚/巧合内聚 完成一组没有关系或松散关系的任务

越向下程度越高

耦合类型 描述
非直接耦合 通过主模块调用来实现
数据耦合 参数表传递简单数据
标记耦合 通过参数传递数据结构/记录信息
控制耦合 控制模块内部信息
外部耦合 通过全局变量
公共耦合 访问一个公共数据环境，例如全局变量和数据结构
内容耦合 直接访问另外一个模块内部的数据

应用的工具：

N/S盒图

# 软件测试

动态测试：

  1. 黑盒测试法

    1. 等价类划分

      1. 边界值分析

  2. 白盒测试法

  3. 灰盒测试法

静态测试：

  1. 桌前检查

  2. 代码审查

  3. 代码走查

# 软件测试

回归测试

负载测试

压力测试

# McCabe复杂度

复杂度计算公式：边数-节点数+2

公式2：封闭区域+1

# 软件维护

可维护性因素决定

  1. 可理解性

  2. 可测试性

  3. 可修改性

软件维护类型：

  1. 改正性维护

  2. 适应性维护，因为外部环境改变而做的

  3. 预防性维护，为了将来的某个事情进行维护

  4. 完善性维护

# 文档

开发文档

  1. 可行性

  2. 需求规格说明

  3. 功能规格说明书

  4. 设计规格说明书

  5. 开发计划

  6. 软件集成和测试计划

  7. 质量保证计划

  8. 安全和测试细腻些

产品文档

  1. 培训手册

管理文档

  1. 开发过程的每个阶段的记录

# 软件质量保证

功能性

可靠性

易用性

效率

维护性

可移植性

# CMMI

公司成熟度

  1. 初始级，不需要评级

  2. 可管理级，纪律化

  3. 已定义级，有标准化

  4. 定量管理级，可预测

  5. 优化管理级，不断改进的过程

# 项目管理

十大知识领域

  1. 范围管理

  2. 时间管理

  3. 成本管理

  4. 质量管理

  5. 人力资源管理

  6. 沟通管理

  7. 风险管理

  8. 采购管理

  9. 整体管理

  10. 项目干系管理

专家估算：根据专家的行业经验和历史数据对软件开发过程的成本进行估算。

Wolverton：也叫作 loc 方法，通过执行的源代码行数来进行成本估算，估算准确性低，现在已 经不用了。

COCOMO：构造性成本模型，是一种参数化的成本估算方法。例如，将软件的难度、规模等 作为参数进行成本估算。

COCOMOⅡ：COCOMOⅡ是 COCOMO 的改进版，把最新的软件开发方法考虑在内。COCOMO Ⅱ由以下三个不同的计算模型组成。 应用组合模型：适用于使用现代 GUI 工具开发的项目。 早起开发模型：适用于在软件架构确定之前对软件进行粗略的成本和事件估算，包含了一系列 新的成本和进度估算方法。基于功能点或代码行。 结构化后期模型：是 COCOMO II 中最详细的模型，用在整体软件架构已确定之后，包含最新 的成本估算、代码行计算方法。

# 9.  面向对象技术

# 面向对象的基本概念

对象：对象ID

类：实体类/控制类/边界类

继承与泛化：复用机制

封装：隐藏对象的属性和实现细节，仅对外公开接口

多态： 不同对象收到同样的消息产生不同的结果

接口：特殊的类，只有方法定义没有实现

重载：同一个类里面

模板类：

消息和消息通信：消息是异步通信的

# 设计的7大原则

  1. 单一职责原则

  2. 开放-封闭原则

  3. 里氏替换原则

  4. 依赖倒置原则：面向接口编程，而不是具体实现

  5. 接口隔离原则：使用多个专门的接口比使用单一的总接口要好

  6. 组合重用原则：要尽量使用组合，而不是继承关系

  7. 迪米特原则/最小知识法则：应当对其它对象尽少的了解

# UML

面向对象：

Booch

OOSE

OMT

Jackson：面向数据结构

结构化方法

# 结构图

  1. 类图
    1. 依赖关系：一个事物的发生影响另外一个事物
    2. 泛化关系：父子关系
    3. 关联关系：
    4. 聚合关系：整体和部分生命周期不同
    5. 组合关系：整体和部分生命周期相同
    6. 实现关系：接口与类之间的关系
  2. 对象图
  3. 包图
  4. 组合结构图
  5. 构件图
  6. 部署图
  7. 制品图

# 行为图

  1. 用例图
  2. 顺序图
  3. 通信图
  4. 定时图
  5. 状态图
  6. 活动图
  7. 交互概览图

在 UML 用例图中，参与者是指存在于系统外部并直接与系统进行交互的人、 系统、子系统或类的外部实体的抽象。

# 设计模式

23个，分为三类。

# 创建型模式

名称 说明 关键字
抽象工厂模式
Abstract Factory		 提供一个接口，可以创建一些列相关或相关依赖的对象，而无需指定他们具体的类 生产成系列的对象
构建器模式
Builder		 将一个复杂类的表示与其构造相分离，使得相同的构造过程能够得出不同的表示 复杂对象构造
工厂方法模式
Factory Method		 定义一个创建对象的接口，但由子类据欸的那个需要实例化哪一个类。 动态生产对象
原型模式 Prototype 用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象。 克隆对象
单实例
Singleton		 保证一个类只有一个实例，并提供一个访问它的全局访问点 单实例

# 结构型模式

名称 说明 关键字
适配器 转换接口
桥接 继承树拆分
组合
Composite		 树形结构目录
装饰模式
Decorator		 附加职责
外观模式
Facade		 定义了一个高层接口，为子系统中的一个组接口提供一个一致的界面，从而简化子 系统的使用。 对外统一接口
享元模式
Flyweight		 复用内存中已存在的对象，减少系统创建对象的实例。 文章共享文字
代理模式
Proxy		 为其他对象提供一种代理以控制这个对象的访问

# 行为型模式

名称 说明 关键字
职责链模式
Chain of Responsibility		 传递职责
命令模式 将一个请求封装为一个对象，从而可以用不同的请求对客户进行参 数化，将请求排队或记录请求日志，支持可撤销的操作。
解释器模式
迭代器模式
中介者模式
Mediator		 不直接引用
备忘录
观察者 定义对象间的一种一对多的依赖关系，当一个对 象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。 联动
状态策略 状态变成类
策略模式 多方案切换
模板方法
访问者模式

# 10. 程序设计语言与语言处理程序基础

# 编译过程

源程序-->词法分析-->语法分析-->语义分析-->(中间代码生成)-->(代码优化)-->目标代码生成-->目标程序

语义分析阶段：主要检查源程序是否存在语义错误，并收集类型信息供后面的代码生成阶段使用，如赋值语句的右端和左端的类型不匹配、表达式的除数是否为零等

解释型，不需要生成目标代码，例如：html，python

常用的中间代码的表达形式有语法树、后缀式、三地址代码。

# 文法

有序四元组

V：非终结符

T：终结符

S：起始符

P：产生式

程序设计语言的语法基本上都是上下文无关的文法

# 语法推导树

# 有限自动机

# 正规式

r|s

r.s

# 表达式

中间的符号作为根节点，后缀就是根节点再最后

前缀表达式

中缀表达式

后缀表达式：技巧是将符号移动到最近的括号末尾

# 各种程序语言的特点

语言 特点
1 Prolog 数据库和专家系统
Lisp 函数式程序，符号处理，人工智能

# 11. 多媒体

人耳：20 -20kHz，说话：300-3400Hz

音频格式：MP3(Moving Picture Experts Group Audio Layer III)，MIDI(一种乐器标准)

# 媒体的种类

感觉媒体：声音、图形、图像、动画

表示媒体：各种编码方式

显示媒体/表现媒体：输入输出的设备

转换媒体：存储媒体和传输媒体

# 12. 知识产权与标准化

根据我国法律法规的规定必须使用注册商标的是烟草类商品。

# 下午题

# 1. 数据流图(DFD，15分)

数据流图用来记录系统中的数据和数据在特定的过 程中的流动，即数据如何被采集、处理、保存和使用的（围绕信息系统的功能）。

外部实体是指系 统之外又与系统有联系的人或事物。它表达了该系统数据的外部来源和去处。

Dx: XXX表

# 数据字典

航班号="Y7100" .. "Y8100" 表示范围

# 平衡原则

父图和子图的平衡

子图内平衡

父图中某个加工的输入输出数据流必须与其子图的输入输出数据流在数量上和内容上 保持一致。父图的一个输入（或输出）数据流对应子图中几个输入（或输出）数据流，而子图中组成的这些数据流的数据项全体正好是父图中的这一个数据流。

# 2. 数据库设计(12分)

# 3. UML图(看运气)

# 4. 算法题(难3分)

# 分治法

经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法

# 贪心法(求满意解)

保证局部最优，不一定是整体最优解

经典问题：找零钱问题

# 动态规划法(求最优解)

经典问题：矩阵乘法、背包问题

# 回溯法

用试探的方法

经典问题：N皇后问题、背包问题

# 5. 面向对象编程(15分)

C++里面：表示继承，允许多继承

.h 定义与声明 .cpp实现文件

::表示类的作用域分辨符

选择java的，比较简单

# 参考资料

https://www.bilibili.com/video/BV1oG4y1q77w

https://www.bilibili.com/video/BV1rD4y1k7qY

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=38dpnhkh4o8wo