流水线技术

流水线执行时长

流水线吞吐率

流水线加速比计算

比如 三个指令 分别是 2ns 2ns 1ns 一共100 条指令 不使用流水线需要 500 ns ，使用 流水线 需要203ns 所以 加速比是 500/203

流水线的效率

(6△t)/(4△t*15) = 24 /60

缓存计算系统平均周期

比如 t1 为 1ns t2为1000ns , h 命中率 95% ， 计算得到系统平均周期 50.95 ns

磁盘计算

CB

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

串联模型

所有的子系统必须都正常，系统才能正常运行， 所以 可靠度为每个结点的 可靠度相乘

并联模型

并联模型 只要有一个结点是好的 就能正常工作 ，所以他的可靠度 为 1减去 每个结点的不可靠度相乘 ，得到可靠度

海明校验码 重点

我们要了解海明码编码的基本的规则，要知道如何去编码，要会计算多少位的信息位 需要多少个校验位，要了解这些知识 我们要知道海明码中 编码完成的串中 哪些位置是校验位 ，哪些位置是信息位，在这种编码体系中 明确规定了校验位的 位置是位于 整个信息编码中的 2的n次方位，比如 2^0 位 放的是校验位 2^1 位 放的是校验位 ， 2^2次方位 等等 ，校验位的位置定死了，其他位置是信息位

上面的公式 2的r次方 大于等于 4 + r +1 里面的4 是 信息1011 位的个数 r 是 校验位的个数 计算得到 校验位有3 位

海明校验码 是一个难点 但是也是一个热点 我们要了解海明码编码的规则 要知道如何去编码 要回计算多少位的信息位 需要多少个校验位

要了解这些 首先我们要了解 海明码中 编码完成的串中 哪些位是校验位 哪些位是信息位 ，校验位的位置是位于整个信息编码完成的串中的 2的n次方的位置 比如 2的0次方 也就是第一位 应该放校验位 2的一次方位 也就是第二位 2 的2次方位 也就是第4位 应该放校验位

我们可以直接把这些位置的信息 挑出来 知道这些是校验位，其他位置 是填充信息位 。如果 我有一个信息位 最终的 编码 会有3 位

2个信息位 最终的编码 就会有5位的长度 ，3个信息位 6位的长度 ， 4 个信息位 7位的长度 ，5个信息位 会是9位的长度。这个规律用数学公式表达 2的r次方 大于等于 4 + r +1 ,其中的4 就是信息位的个数 r 就是 校验位的个数 ， 如果 信息位 有x 位 那么 x + r + 1 <= 2的r次方。 比如 x 信息位 有5 位 ，那么 校验位r 就得取4 。

以上 就是 就校验位的位数 和 信息位的位数的关系

信息位 直接把 信息 填到对应的位置即可 ，问题是 如何计算校验位 我们需要计算出校验位的值

我们把信息位的 位数 写成 2进制相加的形式

7这个位数 = 2的2次方 + 2的1次方 + 2的0次方 （7这个位置 会影响到 r2 r1 和 r0）

6这个位数 = 2的2次方 + 2的1 次方 (影响 r2 r1)

5这个位数 = 2得2次方+2 的0次方 (影响 r2 和 r0)

3这个位数 = 2 的1次方+2的0次方 (影响 r1 和 r0)

那么 r2 = 第四个信息位 （第七位） 异或 第三个信息位（第六位） 异或 第二个信息位（第五位) （r2 就看那个信息位 有 2的2次方 对这些信息位数字 进行异或运算）

r2 = 1 异或 0 异或 1 = 0 i4 异或 i3 异或 i2 就是信息位的数字

r1 = 1 异或 0 异或 1 = 0

r0 = 1 异或 1 异或 1 = 1

所以 最终 三位校验码 为 0 0 1

异或运算：相同为0 相异 为1

海明码 不但能校验 还能纠错

如果 收到的信息 为 1010100 校验位 为 0 0 0 ， 根据 信息码 推出 校验码 位 001

对二者 进行异或运算 得到 001 说明 1010100 这个信息的第 1 位 出错了 ， 对第一位 取反 就是正确的 1010101

如果 收到信息为 1011101 校验码为 101 根据信息码 推出来的校验码位 001 对二者 进行异或运算 得到 100 （转10进制为4） 则 1011101 的 第四位 出错了 ， 正确的应该是 1010101

如果收到信息为 1111111 校验码位 111 根据信息码 退出来的校验码位 001 异或得到 110 说明第六位出错

环路复杂度-重点

解题方法：1. 弧（边）- 节点数 + 2

2. 闭合区域个数 + 1

题型一 直接数数

题型二 开始节点漏掉了

题型三 箭头重复 漏掉了

还有 结合路径覆盖的题型

对下图所示流程图扫用白盒测试方法进行测试，若要满足路径覆盖，至少需要（ ）个测试用例。采用McCabe度量法计算该程序的环路复杂度为（ ）

A： 3 B: 4 C: 6 D: 8

前驱图 重点

题型1

题型2

有限自动机 重点

题型1,2

传值传址 重点

B D

C 传值时 实参可以是变量 也可以是 常量和表达式 ，引用调用时 可以实现 形参和实参的双向传递数据效果

知识产权

计算机软件保护条例 是由国务院颁布的

中华人民共和国著作权法 和 计算机软件保护条例 是构成我国保护计算机软件著作权的两个基本法律文件

著作权中 修改权 署名权 保护作品完整权 的 保护期 不受限制 （小书包）

KMP算法

D

进制转换

2 B

8 O

10 D

16 H

逻辑地址转物理地址 重点

内存按字节编址

计算得出256kb ，第二空要注意 16k * 4bit ， 需要用（256kb * 8bit ）/(16k*4bit) = 32

先用400FFFFF+1 = 40100000 , 再减去 40000000 等于 100000 除以 1024 等于 1024kb

1024kb 除以 256k*8bit 等于 4

D

B

Gannt (甘特图) 和(PERT) 网络图 重点

GANNT图 能表示每个任务的开始与结束 可以表示每个任务的并行（进展）情况 ，不能表示每个任务的依赖关系

PERT图能表示每个任务的开始与结束 可以表示每个任务的以来关系 不能表示每个任务的并行关系

D B

原码反码补码移码

最高位是 符号位 正数用0 表示 负数用1表示

正数的原码 反码 补码 都相同 ， 移码 是在补码的基础上 符号位取反

正数的移码 是在补码的基础上 符号位取反

负数的反码 是 在 原码的基础上 符号位不变，其他位取反

负数的补码 是在反码的基础上 加1

负数的移码 是在补码的基础上 符号位取反

负数 的 补码 的 补码 为原码

注意 看清楚 是可以表示几个数 还是 表示 数的范围，这个是 数的范围

媒体

感觉媒体：作用于人的器官，能够感受到的媒体，视听嗅味触的媒体，语言 音乐 图形 文字 动画都是感觉媒体

表示媒体：表述感觉媒体的数据编码， 如 JPG PNG GIF MP3 MP4 ASCLL

表现媒体： 媒体输入输出设备 如鼠标 键盘 麦克风 为 输入表现媒体 音响 显示器 打印机 为输出表现媒体

存储媒体：存储表示媒体的物理介质 如 硬盘 光盘

传输媒体： 纯属表示媒体的物理介质 如 电缆 光缆

• 使用150DPI的扫描分辨率扫描3*4英寸的彩色照片 ，得到原始24位真彩色图像的数据量是（ ）byte.

​ A :1800 B:90000 C:270000 D810000

理解：DPI:（Dots Per Inch ） 每英寸点数 通常用来描述数字图像输入设备（如图像扫描仪）或点阵图像输出设备（点阵打印机）输入或输出点阵图像的分辨率。一幅3×4英寸的彩色照片在150DPI的分辨率下扫描得到原始的24位真彩色图像的数据量是（150×3）×（150×4）×24/8=810000字节

• 使用（ ）DPI的分辨率扫描一副2*4 英寸的照片，可以得到一副300 * 600 像素的图像

  • A 100 B 150 C 300 D 600 x*2 *x *4 = 180000

• 以下媒体中，（ ）是表示媒体，（/） 是表现媒体

  • A 图像 B 图像编码 C 电磁波 D 鼠标

树

有且仅有一个根节点

具有相同父节点的节点 互为兄弟节点

节点的度： 一个节点的子树的个数 就是该节点的度

树的度：树中节点的度的最大值

叶子结点：度为0的结点 没有子树的结点

结点的层次：根节点为第一层 根节点的孩子为第二层

二叉树

每个节点 最多只有两个子树 也就是不存在 度>2 的结点

对于二叉树的第i层 最多有 2^(i-1)次方个节点

深度为k的二叉树 一共有 2^i次方 - 1 个节点

度为0的结点 一定比度为2的结点多一个

满二叉树

所有分支都存在左子树个右子树，并且最后一层叶子结点为满

非叶子节点的度一定为2

叶子结点只能在最后一层

完全二叉树

和满二叉树类似，但是除了最后一层 其他节点都为满

叶子结点只能出现在最后一层，并且 不满的叶子结点 只能在左侧

哈夫曼树 重点

每次会选择权值最小 的两个节点 构造出一个新的节点 左小 右大

这个题不太懂 6 个 字符 2^n 这个大于6 是啥意思？

（3-2.2）/3 =0.266666≈C

前缀中缀后缀表达式

中缀表达式 就是 运算法在 数据之间 例如 3 + （4*7） -2

前缀表达式 运算符在数字的前面

后缀表达式 运算符放在 数据后面

A

公钥私钥

公钥：加密和验证

私钥：解密和签名

CA机构：权威机构

公家宴 私借钱

甲的 数字签名 相当于 甲用私钥进行签名

上下文无关文法

B

循环队列

计算机网络计算

D

这里的网络地址说的应该就是 主机地址 ，不是网络号， 可以有 不是 可用 那么 就不用减2 了 所以是 2^24

CD

关系模式无损连接

面向对象技术

面相对象的方法有 Booch Coad 和 OMT 方法 ， Jackson 方法是一种面向数据结构的开发方法

面向对象分析 主要强调 理解问题是什么 不考虑问题的解决方案 描述软件要做什么

面向对象设计 侧重问题的解决方案 并且需要考虑实现细节问题饿

抽取和整理用户需求 并建立问题域精确模型的过程 叫 面向对象分析

多态 有 参数多态 包含多态 过载多态(同一个名字在上下文中所代表的含义不同) 强制多态 ,其中 参数多态是应用比较广的多态，包含多态在许多语言中都存在，最常见的例子就是子类型化，过载多态是同一个名字在不同的上下文中代表的含义

在领域模型中 不包含 领域对象

xml是标记型语言

python 是面向对象 解释型语言

Prolog 是逻辑型程序设计语言

C++ 是面向对象 编译型语言

软件开发模型

瀑布模型 适合需求明确 或者 二次开发的场景

原型模型 适合需求不明确的场景 因为可以画原型图

增量模型

螺旋模型 包含了 原型模型的迭代特征 还包含了风险分析 这个特征 使软件无法排除重大风险时 有机会停止 螺旋模型适合大型昂贵的系统级软件应用

喷泉模型 属于 面向对象的开发模型

风险的优先级通常是根据 风险暴露 设定

逆向工程工具属于 软件维护 工具

UP（统一过程）模型 是一种以用例和风险为驱动、以架构为中心、迭代并且增量的开发过程，由UML方法和工具支持。UP过程定义了五个阶段，起始阶段、精化阶段、构建阶段、移交阶段和产生阶段。

瀑布模型将软件生存周期各个活动规定为线性顺序连接的若干阶段的模型，规定了由前至后，相互衔接的固定次序，如同瀑布流水，逐级下落。这种方法是一种理想的开发模式，缺乏灵活性，特别是无法解决软件需求不明确或不准确的问题。原型模型从初始的原型逐步演化成最终软件产品，特别适用于对软件需求缺乏准确认识的情况。螺旋将瀑布模型与快速原型模型结合起来，并且加入两种模型均忽略了的风险分析，适用于复杂的大型软件。增量是开发把软件产品作为一系列的增量构件来设计、编码、集成和测试，可以在增最开发过程中逐步理解需求。

软件工程

需求分析 确定软件要完成的功能及非功能性要求

概要设计 将需求转化为软件的模块划分 确定模块之前的调用关系

详细设计 将模块进行细化 得到详细的结构和算法

编码 根据详细设计 进行代码编写 得到可运行的软件 并进行单元测试

在概要设计阶段 选择适当的解决方案 将系统分解为若干个子系统 建立整个系统的体系结构

极限编程

• 敏捷开发方法是一种强调灵活性和快速开发的一种方法，有多种具体的方法，其中极限编程时敏捷开发中一种普遍的方法，极限编程包含12个实践操作，其中，集体所有权表示任何开发人员可以对系统任何部分进行改变，结对编程实际上存在一个非正式的代码审查过程，可以获得更高的代码质量。据统计，结对编程的编码速度与传统的单人编程相当

系统设计知识

• 在软件设计中，人们总结了一些启发式原则，根据这些原则进行设计，可以设计出较高质量的软件系统。其中，模块的扇入扇出适中，模块大小适中以及完善模块功能都可以改进设计质量。而将相似功能的模块合并可能会降低模块内聚和提高模块之间的耦合，因此并不能改进设计质量 , 模块的功能越单纯越好 也不能改进设计质量

  模块的内聚是一个模块内部各个元素彼此结合的紧密程度的度量。

  ①(偶然内聚)巧合内聚：指一个模块内的各处理元素之间没有任何联系。

  ②逻辑内聚：指模块内执行考干个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。

  ③时间内聚：把需要同时执行的动作组合在一起形成的模块。

  ④过程内聚：指一个模块完成多个任务，这些任务必须按指定的过程执行。

  ⑤通信内聚：指模块内的所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或产生相同的输出数据。

  ⑥顺序内聚：指一个模块中的各个处理元素都密切相关于同—个功能且必须顺序执行，前一个功能元素的输出就是下一功能元素的输入。

  ⑦：功能内聚：指模块内的所有元素共同作用完成一个功能，缺一不可。

  其中 巧合内聚 该内聚类型具有最低的内聚性，是最不好的一种内聚类型。具有该类内聚类型的模块具有不易修改、不易理解和不易维护等特点，同时会影响到模块间的耦合关系。

​

模块独立性是创建良好设计的一个重要原则，一般采用模块间的耦合和模块的内聚两个准则来进行度量。耦合程度越低，内聚程度越高，则模块的独立性越好。存在多种模块之间的耦合类型，从低到高依次为非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。其中， 公共耦合是指一组模块都访问同一公共数据环境； 控制耦合是指一个模块通过传送开关、标志、名字等控制信息，明显地控制选择另一个模块的功能； 标记耦合是一组模块通过参数表传递记录信息； 数据耦合是一个模块访问另一个模块时，彼此之间通过数据参数（不是控制参数，公共数据结构或外部变量），来交换输入输出信息。

可以按照在软件系统中的功能将模块分为四种类型。

①传入模块:取得数据或输入数据，经过某些处理，再将其传送给其他模块.

②传出模块：输出数据，在输出 之前可能进行某些处理，数据可能被输出到系统的外部，或者会输出到其他模块进行进一步处理。③变换模块：从上级调用模块得到数据，进行特定的处理，转换成其他形式，在将加工结果返回给调用模块。

④协调模块 一般不对数据进行加工，主要是通过调用、协调和管理其他模块来完成特定的功能。

界面设计的三条黄金准则 1.置于用户的控制之下 2. 减少用户的记忆负担 3，保持界面的一致性

标准化和知识产权

1.软件著作权中的翻译权 是指 以不同于原软件作品的一种程序语言转换该作品原使用的程序语言，而重现软件作品内容的创作的产品权利 简单说 就是将原软件从一种程序语言 转换成另一种程序语言的权利

利用商业秘密权 可以对软件的技术信息 经营信息提供保护

王某买了一副美术作品 他享有该作品的 所有权预与其览权

网络安全

数据库容灾属于 系统安全 和 应用安全

机房安全属于物理安全

入侵检测属于网络安全

漏洞补丁管理属于系统安全

数据库安全属于应用安全

ARP攻击（ARP欺骗）是欺骗攻击的一种，通过伪造IP地址和MAC地址，能够在网络中产生大量的ARP通信量使网络阻塞，如果伪造网关的IP地址和MAC地址对，则所有发往网关的IP包将因为MAC地址错误而无法到达网关（ARP攻击一般会将MAC地址改为发起ARP攻击的主机地址），造成无法跨网段通信。 处理ARP攻击的方法为首先断开ARP攻击主机的网络连接，然后用“arp-d”命令清除受攻击影响的ARP缓存。

X.509是国际密码学里公钥证书的格式标准，推荐使用的密码算法是RSA。而国密SM2数字证书采用的公钥密码算法是ECC基于椭圆曲线的公钥密码算法。ECC算法与RSA算法相比具有加密强度高、计算速度快的优点。

IE浏览器中 安全级别最高的区域设置是 受限站点

FTP服务器 数据端口20 控制端口 21

ICMP (Internet control Message Protocol ) 与 IP协议同属网络层，用于传送有关通信问题的消息，例如 数据报不能达到目标站，路由器没有足够的缓存空间，或者 路由器向主机发送最短路由信息等，ICMP报文 封装在IP数据报中传送，因而 不保证可靠的提交

中继器是物理层设备，其作用是对接收的信号进行再生放大，以延长传输的距离。

网桥是数据链路层设备，可以识别MAC地址，进行帧转发。

交换机是由硬件构成的多端口网桥，也是一种数据链路层设备。

路由器是网络层设备，可以识别IP地址，进行数据包的转发。

TCP与UDP均提供了端口寻址的 能力

ipconfig 查看信息

ipconfig/all 查看详细信息 可查看DHCP服务是否启用

ipconfig/renew 更新所有适配器

ipconfig/release 释放所有匹配的链接

媒体

矢量图中的图形元素称为图元。而另一类图具有代表性的图像表示形式是位图图像，该图采用像素来表示图像

VCD使用了MPEG-1标准作为其音、视频信息压缩编码方案，而MPEG-2标准中的音、视频压缩编码技术被应用到DVD中。

声音信号时模拟信号，要使声音信号数字化并传递 首先要进行A/D转换

操作系统原理

存储管理

若计算机系统的IO接口与主存采用统一编址 ，则输入输出操作是通过 访存 指令 来完成的

DMA控制方式是在 主存 与 外设之间 建立数据通路 进行数据的交换处理

CPU是在 一个总线周期 结束时响应DMA请求的

虚拟存储体系由 主存-辅存 两级存储器构成

在机器指令的地址字段只中，直接指出操作数本身的寻址方式是 立即寻址

DRAM的原理是使用电容存储信息，由于存在一定的自放电，因而需要周期性地进行刷新，即读出再写入。

中间代码生成和代码优化 并不是每个编译器都必须的，与编译器相比 解释器 参与运行控制，程序执行的速度慢

解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间代码后再加以执行；而编译程序（编译器）则是将源程序翻译成目标语言程序，然后在计算机上运行目标程序。这两种语言处理程序的根本区别是：在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程;而在解释方式下，解释程序和源程序（或其某种等价表示）要参与到程序的运行过程中，运行程序的控制权在解释程序。简单来说，在解释方式下，翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立保存的目标程序。

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

直接相联映射 ： 主存中 一块 只能映射到Cache 的一个特定块中

组相联映射 ： 各区中的某一块 只能存入缓存的同组号的空间内 ，但组内各块地址之间 则可以任意存放

直接映射： 从主存的组 到 Cache 的组之间 采用直接映射方式 两个对应的组内部 采用全相联映像方式

将高级语言程序转换为一种中间代码是现代编译器的常见处理方式 常用的中间代码 有 后缀式 三地址码 语法树 等

指令周期是执行一条指令所需要的时间，一般由若干个机器周期组成，是从取指令、分析指令到执行完所需的全部时间。CPU执行指令的过程中，根据时序部件发出的时钟信号按部就班进行操作。在取指令阶段读取到的是指令，在分析指令和执行指令时，需要操作数时再去读操作数。 CPU首先从程序计数器（PC）获得需要执行的指令地址，从内存（或高速缓存）读取到的指令则暂存在指令寄存器（IR），然后进行分析和执行。

网络系统中 通常把 Web 服务器 置于DMZ区

冰河 是 木马软件 不是蠕虫病毒，常见的蠕虫病毒有 熊猫烧香 红色代码 爱虫病毒 爱丽滋病毒 等

在CPU中，常来为ALU执行算术逻辑运算提供数据并暂存运算结果的寄存器是 累加寄存器，在运算器中，累加寄存器是专门存放算术或逻辑运算的一个操作数和运算结果的寄存器，能进行加、减、读出、移位、循环移位和求补等操作，是运算器的主要部分。

算法

若数据基本有序 插入排序是 最佳选择

输入 数据是否有序 对 归并 和 计数排序 算法没有影响

对传统的快速排序 输入数据有序 反而使其效率降低

若关键字取值范围较小 则计数排序是最佳选择

0 1 背包 是动态规划算法 自底向上 递推 从小范围 推到大范围

算法思维 递贪分动回

递归算法

贪心算法 普利姆算法 克鲁斯卡尔算法 最小生成树， 迪杰斯特拉算法 最短路径

分治算法 二分查找 快速排序 归并排序

动态规划算法 佛洛依德算法 最短路径 ， 0 1 背包

回溯算法 又叫试探法 马踏棋盘 八皇后 走迷宫

冒泡排序

冒泡排序是一种简单的排序算法，它的特征如下：

1. 基本思想: 冒泡排序的基本思想是依次比较相邻两个数的大小，将大的数往后移，小的数往前移，从而实现数据序列的排序。
2. 稳定性: 冒泡排序是一种稳定的排序算法，相等大小的元素不会互换位置。
3. 时间复杂度: 冒泡排序的时间复杂度为O(N^2)。比较和交换的次数都是N(N-1)/2次，其中N为数组的长度。
4. 空间复杂度: 冒泡排序的空间复杂度为O(1)，即原地排序。
5. 适用范围：冒泡排序适用于数据规模不大的情况，其优点是代码简单、易于理解和实现。但随着数据规模的增大，冒泡排序的效率会大大降低，不适合大规模数据的排序。

总的来说，冒泡排序虽然不是一个高效的排序算法，但是由于其简单易懂的实现方式，以及有利于教学和理解算法原理的特点，仍然具有一定的实际应用价值。

public static void bubbleSort(int[] arr) {
    // 外层循环控制排序轮数
    for (int i = 0; i < arr.length - 1; i++) {
        // 内层循环控制每轮排序次数
        for (int j = 0; j < arr.length - 1 - i; j++) {
            // 比较相邻元素的值，将大的元素往后移
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
//其中，外层循环控制排序轮数，每一轮之后都会把最大的元素排到当前轮的最后；内层循环控制每轮排序次数，每一次比较相邻两个元素的大小并交换位置，将当前未排序序列中的最大元素交换到当前轮的末尾。该算法的时间复杂度为O(N^2)。

选择排序

选择排序是一种简单的排序算法，它通过重复选择数组中的最小元素，并把它与当前位置的元素交换位置，
* 来将最小的元素逐渐移动到数组的前面，直到整个数组排序完成。
*
* 选择排序的具体实现如下：
*
* 1. 从数组的第一个元素开始，遍历整个数组，查找最小的元素，并记录它的位置。
*
* 2. 如果当前元素比最小元素还要小，则将当前元素位置和最小元素位置进行交换。
*
* 3. 重复上述过程，直到整个数组排序完成。
*
* 选择排序的时间复杂度是 O(n^2)，因为算法需要进行 n 次遍历，每次遍历需要查找最小元素，
* 并执行一次交换操作。尽管选择排序的时间复杂度比较高，但是它对于大部分数据集合是相当有效的，
* 因为它的内存占用很小。

// 定义一个选择排序的方法
    public static void selectionSort(int[] arr) {
        int len = arr.length;
        //还是 只排 len-1 次就够了   前面的都排好了   最后一个不用排
        for (int i = 0; i < len - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                //在内层循环内  只是把最小数 所在的索引存了下来
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //先把 当前准备交换的数存在临时变量
            int temp = arr[i];
            //把最小的数 放在对应的位置
            arr[i] = arr[minIndex];
            //把原来位置的数 往后面放
            arr[minIndex] = temp;

            System.out.println(Arrays.toString(arr));
        }
    }

插入排序

思想
* 插入排序是一种简单的排序算法，它通过构建一个有序的数组序列来排序，
* 逐个将未排序的元素插入到有序序列中的正确位置。
*
* 插入排序的具体实现如下：
*
* 1. 从数组的第二个元素开始，将它与之前的元素进行比较，并将它插入到正确的位置上。
*
* 2. 对于当前要插入的元素，从后向前逐个比较，如果它比前面的元素要小，
* 则将前面的元素向后移动一个位置。
*
* 3. 最后，将当前元素插入到合适的位置上。
*
* 4. 重复上述过程，直到整个数组排序完成。
*
* 插入排序的时间复杂度为 O(n^2)，但实际上它却很高效，因为对于部分有序的数组，
* 它的实际运行效率比 O(n^2) 要快，而且它的空间复杂度为 O(1)，在排序小规模数据时表现良好。

public static void insertionSort(int[] arr) {
        int n = arr.length;
        // 外层循环 从 索引为1 的地方 开始取元素
        for (int i = 1; i < n; i++) {
            //拿到要比较的数据 的数据
            int key = arr[i];

            int j = i - 1;
            //内层循环
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

快速排序

基本思想
* 1．先从数列中取出一个数作为基准数。
* 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
* 3．再对左右区间重复第二步，直到各区间只有一个数
*
*
* 快速排序是一种基于分治思想的排序算法，其主要思路是将一个待排序的序列分成两部分，然后对每一部分递归地进行快速排序，最终将所有部分合并起来得到排序结果。
*
* 具体来说，快速排序的算法流程为：
*
* 1. 选择一个基准元素（pivot），通常可以选择序列的第一个元素、最后一个元素或者中间位置的元素；
* 2. 将序列分成两部分，一部分是小于等于基准元素的，另一部分是大于基准元素的；
* 3. 对这两部分递归地进行快速排序，直到分成的部分长度为 1 或 0，递归结束；
* 4. 将递归得到的部分合并起来得到排序结果。
*
* 在每次划分之后，基准元素会被放到最终的位置，使得左边的子序列都小于等于基准元素，右边的子序列都大于基准元素。这个过程称为一次划分。
*
* 快速排序的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)，是不稳定的排序算法，常用于需要使用原地排序算法或者需要对大数据量进行排序的场景。
*

public class KuaiSu {

    public static void main(String[] args) {
        int[] arr = {5, 7, 3, 8, 4, 2, 9, 1, 6}; // 待排序的数组
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high); // 划分数组
            quickSort(arr, low, pivot - 1); // 对左半部分排序
            quickSort(arr, pivot + 1, high); // 对右半部分排序
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为枢轴
        int i = low - 1; // i记录小于等于pivot的元素个数
        for (int j = low; j < high; j++) { // j滑动到右边
            if (arr[j] <= pivot) { // 找到一个比pivot小的元素
                i++; // i右移
                swap(arr, i, j); // 交换arr[i]和arr[j]
            }
        }
        swap(arr, i + 1, high); // 把pivot换到中间，arr[i+1]就是pivot
        return i + 1; // 返回枢轴位置
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

堆排序

sort()方法在最初先创建一个最大堆，接着它会执行堆排序算法进行排序。最大堆由数组中的元素实现。
*
* heapify()方法作为一个递归函数去调整当前节点，并把其子树转换成最大堆。
*
* 在主方法中创建一个数组并对其排序，最后输出排序后的结果。
*
* ----
* 堆排序是一种基于堆数据结构的排序算法，其主要思路是将待排序的元素构建成一个二叉堆，
* 然后不断地将堆顶元素与未排序部分的最后一个元素交换，并重新调整堆，直到堆的大小为 1，
* 即所有元素都已经排好序。
*
* 堆是一种满足如下条件的完全二叉树：任意节点的值都大于等于（或小于等于）其子节点的值。
* 通常我们使用大根堆排序，即堆顶节点为整个堆的最大值。
*
* 具体来说，堆排序的算法流程为：
*
* 将待排序的数组构建成一个最大堆，即堆顶元素是数组中的最大值；
* 不断地将堆顶元素交换到未排序部分的最后，然后重新调整堆，使得堆顶元素依然是最大值；
* 重复步骤 2，直到堆的大小为 1，即所有元素都已经排好序。
* 堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)，是不稳定的排序算法，常用于内存有限、
* 数据量较大的排序场景。

public class Dui {

    public static void main(String args[]) {
        //int arr[] = { 10, 9, 8, 7, 6, 5,4,3,2,1 };
        int arr[] = { 1, 2, 3, 4, 5, 6,7,8,9,10 };

        sort(arr);

        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }

        public static void sort(int[] arr) {
            int n = arr.length;

            // 创建最大堆    把数组内的元素顺序 调整为 大顶堆的顺序
            for (int i = n / 2 - 1; i >= 0; i--){
                heapify(arr, n, i);
            }


            // 把堆顶元素(最大值)与未排序部分的最后一个元素交换，并重新调整最大堆
            for (int i = n - 1; i >= 0; i--) {
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;

                heapify(arr, i, 0);
            }
        }

        // 调整最大堆
        static void heapify(int[] arr, int n, int i) {
            int largest = i; // 初始化最大值为当前的根节点 i
            int l = 2 * i + 1; // 左子树节点
            int r = 2 * i + 2; // 右子树节点

            // 如果左子树比最大值大，则更新最大值
            if (l < n && arr[l] > arr[largest]){
                largest = l;
            }


            // 如果右子树比最大值大，则更新最大值
            if (r < n && arr[r] > arr[largest]){
                largest = r;
            }


            // 如果最大值被更新，则递归调整最大堆
            if (largest != i) {
                int swap = arr[i];
                arr[i] = arr[largest];
                arr[largest] = swap;

                heapify(arr, n, largest);
            }
        }
}

希尔排序

希尔排序  是插入排序的一种  他是针对插入排序算法的改进   希尔排序又称缩小增量排序
* 他通过比较相聚一段间隔的元素来进行  各趟比较所用的距随着算法的进行而减小  直到只比较
* 相邻元素的最后一趟排序为止
*
* 希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。
* 希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，
* 因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 )
* 复杂度的算法快得多。
*
* 希尔排序是一种基于插入排序的排序算法，也被称为缩小增量排序。它的基本思想是将待排序的数组分割成若干个子序列，每个子序列进行插入排序，待整个数组中的元素基本有序时，在对全体元素进行一次插入排序。
*
* 希尔排序通过将待排序的数组元素分组，对每个分组进行插入排序，然后逐步减少每组包含的元素，直到剩下的元素全部有序。
*
* 这个算法的主要思想是通过插入排序算法对大量元素无序的数组进行初步排序，然后缩小步长（gap）并重复进行插入排序，直到整个序列被排序完成。
*
* 希尔排序的时间复杂度是 O(n^2)，但实际的运行时间要比其他的 O(n^2) 排序算法（如冒泡排序、选择排序）要少得多。另外，希尔排序还可以适用于大型数组的排序，因为它的空间复杂度是 O(1)。
*

// 定义一个希尔排序的方法
    public static void shellSort(int[] arr) {
        int len = arr.length;
        // 定义增量gap，初始值为数组长度的一半
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 从gap开始，对每个组进行插入排序
            for (int i = gap; i < len; i++) {
                int temp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
        }
    }

归并排序

归并排序是一种分治思想的排序算法，其主要思路是将一个复杂的排序问题拆分成两个相对简单的子问题来解决，
* 然后再通过将子问题的解合并起来得到原问题的结果。
*
* 具体来说，归并排序的算法流程为：
*
* 1.将待排序数组分成左右两个子数组；
* 2.对左右两个子数组分别进行归并排序，直到子数组长度为 1；
* 3.将已经排好序的左右两个子数组进行合并，得到最终结果。
* 合并时，我们需要创建一个新的数组，按照大小关系将左右两个子数组中的元素逐个放入新数组中。
* 当其中一个子数组已经全部放入新数组后，我们就可以将另一个子数组中剩余的元素全部放入新数组中，
* 最终得到排好序的新数组。
*
* 归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)，是稳定的排序算法，
* 常用于数据量较大的排序场景。

结构化分析与设计

数据流图是结构化分析的一个重要模型，描述数据在系统中如何被传送或变换，以及描述如何对数据流进行变换的功能，用于功能建模。 数据流图中有四个要素：外部实体，也称为数据源或数据汇点，表示要处理的数据的输入来源或处理结果要送往何处，不属于目标系统的一部分，通常为组织、部门、人、相关的软件系统或者硬件设备；数据流表示数据沿箭头方向的流动；加工是对数据对象的处理或变换；数据存储在数据流中起到保存数据的作用，可以是数据库文件或者任何形式的数据组织。

结构化分析模型包括数据流图、实体联系图、状态迁移图和数据字典，因此这些模型是需求分析阶段的输出。而确定软件体系结构是在软件设计阶段进行的。

UML

活动图(activity diagram)是一种特殊的状态图，它展现了在系统内从一个治动到另一个活动的流程，专注于系统的动态视图，它对于系统的功能建模特别重要，并强调对象间的控制流程。

如下图所示：

活动图一般包括活动状态和动作状态、转换和对象。活动图有开始、结束和一系列动作，可以表示分支、合并、分岔和汇合。分支描述基于布尔表达式的可选择路径，可有一个入流和2个或多个出流，在每个出流上放置一个布尔表达式条件(监护表达式)，每个出流的条件不应该重叠，但需要覆盖所有可能性。合并描述当两条控制路径重新合并，不需要监护条件，只有一个出流。分岔描述把一个控制流分成两个或多个并发控制流，可以有一个进入转移和两个或多个离去转移，每个离去的转移表示一个独立的控制流，这些流可以并行的进行。汇合表示两个或多个并发控制流的同步，可以有两个或多个进入转移和一个离去转移，意味着每个进入流都等待，直到所有进入流都达到这个汇合处。

注意 中括号 那玩意叫 监护表达式

序列图 通信图 交互该蓝图 时序图 均被称为 交互图 ， 对象图 不是 交互图

序列图 展示了 一个用例 和 多个对象的行为

设计模式 23 种设计模式

单原建工象 ----- 创建型设计模式

单例模式

原型模式

（Prototype）模式用原型实例指定创建对象的种类，并且通过拷贝这个原型来创建新的对象。原型模式适用于以下几种情况： ①当一个系统应该独立于它的产品创建、构成和表示时； ②当要实例化的类是在运行时刻指定时，例如，通过动态装载； ③为了避免创建一个与产品类层次平行的工厂类层次时； ④当一个类的实例只能有几个不同状态组合中的一种时，建立相应数目的原型并克隆它们可能比每次用合适的状态手工实例化该类更方便一些。

构建者（建造者）模式

(Builder）模式将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。生成器模式适用于以下几种情况： ①当创建复杂对象的算法应该独立于该对象的组成部分以及它们的装配方式时； ②当构造过程必须允许被构造的对象有不同的表示时。

工厂(方法)模式

（Factory Method）定义一个用于创建对象的接口，让子类决定将哪一个类实例化，使一个类的实例化延迟到其子类。工厂方法适用于以下几种情况： ①当一个类不知道它所必须创建的对象的类的时候； ②当一个类希望由它的子类来指定它所创建的对象的时候； ③当类将创建对象的职责委托给多个帮助子类中的某一个，并且你希望将哪一个帮助子类是代理者这一信息局部化的时候。

抽象工厂模式

（Abstract Factory）模式提供一个创建一系列相关或相互依赖对象的接口，而无须指定它们具体的类。适用于：一个系统要独立于它的产品的创建、组合和表示时;一个系统要由多个产品系列中的一个来配置时；要强调一系列相关的产品对象的设计以便进行联合使用时；当提供一个产品类库，而只想显小'它们的接口而不是实现时。如为图形用户界面（GUI）组件定义不同平台的并行类层次结构，适合采用此模式，其中抽象工厂声明一个创建抽象界面组件的操作接口，具体工厂实现创建产品对象的操作。

代式乔装外组享 ------结构型

代理模式

适配器模式

桥接模式

装饰模式

（Decorator）模式描述了以透明围栏来支持修饰的类和对象的关系，动态地给一个对象添加~些额外的职责，从增加功能的角度来看，装饰器模式相比生成子类更加灵活。适用于：在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责；处理那些可以撤销的职责；当不能采用生成子类的方式进行扩充时。

外观模式

（Facack）模式为子系统中的一组接口提供一个-致的界面，Facade模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。适用于：要为一个复杂子系统提供一个简单接口时，子系统往往因为不断演化而变得越来越复杂；客户程序与抽象类的实现部分之间存在着很大的依赖性；当需要构建一个层次结构的子系统时，使用facade模式定义子系统中每层的入口点。

组合模式

享元模式

（Flyweight）模式运用共享技术有效地支持大量细粒度的对象。适用于：一个应用程序使用了大量的对象；完全由于使用大量的对象而造成很大的存储开销；对象的大多数状态都可变为外部状态；如果删除对象的外部状态，那么可以用相对较少的共享对象取代很多组对象；应用程序不依赖于对象标识。

状观中叠备解仿 ----- 行为型

状态模式

观察者模式

（Observer）模式定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。

中介模式

迭代器模式

备忘录模式

解释器模式

访问者模式

命责莫测

命令模式

Command）将一个请求封装为一个对象，从而使得可以用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤销的操作。

责任链模式

（Chain of Responsibility）使多个对象都有机会处理请求，从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它为止。

模版方法模式

策略模式

（Strategy）定义一系列的算法，把它们一个个封装起来，并且使它们可以相互替换。此模式使得算法可以独立于使用它们的客户而变化。

6大设计原则

开里依 单迪离

开闭原则 对拓展开放 对修改关闭

里氏替换原则 父类引用 指向子类对象

依赖倒置 面相接口编程

单一职责 不要让类太累

迪米特法则 最少知道原则 对象与对象之间 尽量减少引用 不要互相引用

接口隔离 接口的粒度 要合适

下午大题技巧

数据流图

题型1 找实体 一般 人 物 设备 系统

题型2 数据存储 一般 也是一些 固定的 用词 ： 比如 xxx表 xxx 文件 xxx 库 xxx信息

题型3 补全数据流图

• 根据 父图与子图的 平衡 ，
• 子图内 加工的平衡 ，子图的加工 既要有 输入 也要有输出
• 根据说明中的文字 来看对应的加工 是否按照文字说明 来完成对应的操作