中级
教材：软件设计师教程第5版
第一章 计算机系统知识
知识点1：计算机系统的组成
计算机的基本硬件系统由运算器、控制器、存储器、输入设备和输出设备5大部件组成。运算器、控制器等部件统称为中央处理单元（CPU）。CPU是硬件系统的核心。
知识点2：CPU
CPU负责获取程序指令、对指令进行译码并加以执行。CPU主要由运算器、控制器、寄存器组和内部总线等部件组成。
【1、CPU的功能】
1）程序控制：CPU通过执行指令来控制程序的执行顺序。
2）操作控制：一条指令功能的实现需要若干操作信号配合来完成，CPU产生每条指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。（考过）
3）时间控制
4）数据处理：对数据的加工处理是CPU最根本的任务
程序控制、操作控制、时间控制也是控制器的功能，数据处理是运算器的功能。
【2、运算器】
运算器的功能：算术运算（加减乘除等）、逻辑运算（与或非等）
运算器的组成：算数逻辑单元、累加寄存器、数据缓冲寄存器、状态条件寄存器等。
运算器是执行部件，控制器发出控制信号，运算器执行。
（1）算数逻辑单元（ALU）：算数运算、逻辑运算，包括加法器、减法器等（考过）
（2）累加寄存器（AC）：简称累加器，当运算器的算术逻辑单元执行算数或逻辑运算时，为ALU提供一个工作区。运算结果放在累加器中，运算器中至少要有一个累加寄存器。（考过，重要）
（3）数据缓冲寄存器（DR）
（4）状态条件寄存器（PSW）
【3、控制器】
运算器只能完成运算，而控制器用于控制整个CPU的工作，它决定了计算机运行过程的自动化。控制器不仅要保证程序的正确执行，而且要能够处理异常事件。（考过）
（1）指令寄存器（IR）：CPU执行一条指令时，先把它从内存储器取到缓冲寄存器中，在送入IR暂存。——暂存指令
（2）程序计数器（PC）：存下一条指令的地址（考过，重要）
（3）地址寄存器（AR）：存当前CPU所访问的内存单元的地址。
（4）指令译码器（ID）：指令=操作码+地址码，比如2+3，“+”为操作码，“2”、“3”为地址码，指令译码器要分析识别操作码是什么操作
运算器和控制器都分别包括哪些，区分概念，尤其注意累加寄存器、程序计数器、地址寄存器的功能，容易出混淆题
知识点3：计算机基本单位
位（比特）：bit，b （最小的数据单位）
字节：byte，B （最小的存储单位） 1B=8b
千字节：KB，1KB=1024B
兆字节：MB，1MB=1024KB
吉字节：GB，1GB=1024MB
太字节：TB，1TB=1024GB
知识点4：进制、各进制间的转换、进制的运算
【1、进制】
常用进制：十进制、二进制、八进制、十六进制
十进制：0~9，（D）
二进制：0~1，（B）
八进制：0~7，（O）
十六进制：0~15，（H），其中10-15分别用A-F表示
【2、进制间的转换】
（1）n进制转十进制：按权展开求和
例：0101（B）转十进制
02的三次方+12的二次方+02的一次方+12的零次方=5
（2）十进制转n进制：除n取余法
当商为0时停止，余数从下往上写（文字不方便描述）
例：5（D）转二进制
5÷2=2…1
2÷2=1…0
1÷2=0…1
余数从下往上，所以二进制数为：101
补充：1位十六进制的数=4位二进制的数
1位八进制的数=3位二进制的数
【3、进制的运算】
只需掌握进制的加减法，除法和乘法不考
（1）进制的加法：逢n进1
例：二进制的加法即逢2进1
0111+1010=10001
（2）进制的减法：借1当n
例：八进制的减法即借前面1当8
205-7
5-7减不到，借前面的1，借不到；
0借前面的1，2成了1，0成了8，成了185-7；
5借前面的1，8成了7，5成了5+8=13，13减7=6；
所以205-7=176（O）
知识点5：原码、反码、补码、移码
各种数据在计算机中表示的形式称为机器数，其特点是采用二进制计数制。对于机器数带符号数，机器数的最高位表示正负的符号位，其余位表示数值。在计算机系统中常采用补码来表示和运算数据，其原因是采用补码可以简化计算机运算部件的设计
【1、原码、反码、补码、移码的定义】
（1）原码
在原码表示法中，最高位是符号位，0 表示正号，1 表示负号，其余的 n-1 位表示数值的绝对值。数值 0的原码表示有两种形式:[+0]原=0 000000，[-0]原=1 0000000。
例：-3的原码
首先确定符号位，为符号，则符号位为1；
还剩下7位，3转为二进制是11，占2位，剩下的补0；
所以-3的原码是1 0000011
[+1]原=0 0000001 [-1]原=1 0000001
[+127]原=0 1111111 [-127]原=1 1111111
（2）反码
在反码表示中，最高位是符号位，0 表示正号，1 表示负号，正数的反码与原码相同，负数的反码则是其绝对值按位求反。数值 0 的反码表示有两种形式:[+0]反=0 0000000,[-0]反=1 1111111。
例：-3的反码
-3的原码=1 0000011
因为是负数，所以绝对值按位求反，符号位不变，[-3]反=1 1111100
[+1]反=[+1]原=0 0000001
[-1]反=[-1]原按位求反= 1 1111110
[+127]反=[+127]原=0 1111111
[-127]反=[-127]原按位求反=1 0000000
（3）补码
在补码表示中，最高位为符号位，0 表示正号，1 表示负号，正数的补码与其原码和反码相同,负数的补码则等于其反码的末位加 1。在补码表示中,0 有唯一的编码:[+0]补=0 0000000。
例：求-3的补码
[-3]原=1 0000011
[-3]反=1 1111100
[-3]补=1 1111101
[+1]补=[+1]反=[+1]原=0 0000001
[-1]补=[-1]反末位加1=1 1111111
[+127]补=[+127]反=[+127]原=0 1111111
[-127]补=[-127]反末位加1=1 0000001
（4）移码
在补码的基础上，符号位求反。在移码表示中,0 有唯一的编码:[+0]移=1 0000000。
[+1]补=[+1]反=[+1]原=0 0000001
[+1]移=[+1]补符号位求反=1 0000001
[-1]补=1 1111111
[-1]补=[-1]补符号位求反=0 1111111
例题：（2010年上）若某整数的16位补码为FFFFH（H表示十六进制），则该数的十进制为（）
解析：思路：根据补码求原码，再转换为十进制
先把十六进制转成二进制，为1111 1111 1111 1111B
确定正负数，因为最高位是1，所以是负数
负数补码求原码，反码=1 000000000000000，原码=1 000000000000001
转成十进制为-1
知识点6:定点数和浮点数
定点数：小数点的位置固定不变的数。小数点的位置通常有两种约定方式：定点整数和定点小数
定点表示法中，小数点不需占一个存储位
当n=8时
定点整数各码制取值范围：
原码：-127~+127
反码：-127~+127
补码：-128~+127
移码：-128~+127
当机器字长为n时，定点数的补码和移码可表示2的N次方个数，而其原码和反码只能表示2的N次方-1个数。
码制表示范围
知识点7：寻址
指令=操作数+操作码
寻址也就是寻找操作数的地址
（主要看前五个）
1、立即寻址：操作数就包含在指令中。指令直接是：1+2；（最快）
2、直接寻址：操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址。指令为：0x1 + 0x2，内存0x1中存1，0x2中存2。
3、寄存器寻址：操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名。从寄存器中拿地址要比在内存中拿快，指令为：R1 + R2，寄存器名为R1的存1，名为R2的存2。
4、寄存器间接寻址。操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中。指令为R1+R2，寄存器名R1存0x1，R2存0x2，内存0x1中存1，0x2中存2。
5、间接寻址：指令中给操作数地址的地址。
6、相对寻址：指令地址码给出的是一个偏移量（可正可负），操作数地址等于本条指令的地址加上该偏移量。
7、变址寻址：操作数地址等于变址寄存器的内容加偏移量。
寻址速度有快到慢：立即寻址>寄存器寻址>直接寻址>寄存器间接寻址>间接寻址
指令系统中采用不同寻址方式的目的是：扩大寻址空间并提高编程灵活性
例1：（2011年下）若某条无条件转移汇编指令采用直接寻址，则该指令的功能是将指令中的地址码送入（A）
A.PC（程序计数器） B.AR(地址寄存器) C.AC（累加器） D.ALU(算数逻辑运算单元)
例2：(2012 年上半年)若 CPU 要执行的指令为: MOV R1，#45（即将数值 45 传送到寄存器 R1 中)，则该指令中采用的寻址方式为（B）
A.直接寻址和立即寻址 B.寄存器寻址和立即寻址 C.相对寻址和直接寻址 D.寄存器间接寻址和直接寻址
例3：（2013下）若某计算机字长为 32 位，内存容量为 2GB，按字编址，则可寻址范围为
解析：2GB/32bit=21024MB/4B=2102410241024B/4B==51210241024B=512MB
例4：在机器指令的地址字段中，直接指出操作数本身的寻址方式称为：立即寻址
知识点8：校验码
码距：所谓码距，是指一个编码系统中任意两个合法编码之间至少有多少个二进制位不同。
1、奇偶校验码-只能检测出奇数位出错（出错的个数有奇数个）-只能检错不能纠错-码距2
2、海明码-码距=2，具有检错能力；码距>=3，才可能有纠错能力-可以检错纠错-码距为3
海明码利用多组数位的奇偶性来检错和纠错
设数据位是 n位，校验位是k位，则n 和必须满足以下关系:（2的k次方）-1>=n+k
例1：已知数据信息为 16 位，最少应附加 ( ) 位校验位，以实现海明码纠错。 (2016年下半年)
解析：n=16 满足公式：（2的k次方）-1>=16+k ，求k，k=5
3、循环冗余校验码-只能检错不能纠错-码距为2
代码格式：k个数据位+r个校验位
采用模运算
例2：以下关于校验码的叙述中.正确的是(A)。(2009 年下半年)
A.海明码利用多组数位的奇偶性来检错和纠错
B.海明码的码距必须大于等于 1
C.循环冗余校验码具有很强的检错和纠错能力
D.循环冗余校验码的码距必定为 1
例3：以下关于采用一位奇校验方法的叙述中，正确的是_C_。2018 年下半年)
A。若所有奇数位出错，则可以检测出该错误但无法纠正错误
B。若所有偶数位出错，则可以检测出该错误并加以纠正
C，若有奇数个数据位出错，则可以检测出该错误但无法纠正错误
D。若有偶数个数据位出错，则可以检测出该错误并加以纠正
例4：(2014 年上半年)海明码利用奇偶性检错和纠错，通过在n个数据位之间插入k个校验位，扩大数据编码的码距。若n=48，则k应为6.
知识点9：RISC与CISC
牢记表格
知识点10：指令流水线
I：输入
C：计算
O：输出
【1、顺序执行】
I→C→O顺序执行
若输入计算输出的用时分别是0.1s、0.2s、0.3s，执行100个总用时（0.1+0.2+0.3）x100=60s
设备利用率为33.3%，比较低
【2、流水线执行】
I：输入 I1 I2 I3 I4 I5
C：计算 C1 C2 C3 C4 C5
O：输出 O1 O2 O3 O4 O5
流水线公式=第1条指令的执行时间+（n-1）x 最长时间段，n为几条指令，（0.1+0.2+0.3）+（100-1）x0.3=30.3s
加速比=不采用流水线用时/采用流水线用时=60s/30.3s=198%
操作周期=最长时间段
吞吐率=1/最长时间段（即最长时间段的倒数）
执行n条指令的吞吐率=n/采用流水线用时
注意：流水线采用异步控制不会明显提高其性能。单条指令的执行速度与顺序执行速度一致。流水线方式提高了各部件的利用率和系统的吞吐率。
【3、例题】
例1：某四级指令流水线分别完成取指、取数、运算、保存结果四步操作。若完成上述操作的时间依次为 8ns、9ns、4ns、8ns，则该流水线的操作周期应至少为 ( ) ns。(2017年下半年)
解析：操作周期=最长时间段=9ns
例2：
解析：执行n条指令的吞吐率=n/采用流水线用时
采用流水线用时=第1条指令的执行时间+（n-1）x 最长时间段=(t+3t+t+2t+t)+(n-1)x3t
选B
例3：
解析：串行方式执行=顺序执行=（3+2+4）x10=90
流水线方式执行=第1条指令的执行时间+（n-1）x 最长时间段=（3+2+4）+（10-1）x4=45
知识点11：存储器
主存储器（主存）：由DRAM（动态随机存储器）构成，特点：需要周期性地刷新
Cache:由SRAM（静态随机存储器）构成
闪速存储器（Flash Memory）：以块为单位删除，断电信息不会丢失，可代替ROM，不能代替主存。
相联存储器是一种按内容访问的存储器
按寻址方式分类：随机存储器（RAM）、 顺序存储器（SAM）、 直接存储器（DAM）
虚拟存储器由主存和辅存构成
空间局部性：访问一个下次可能访问相邻
时间局部性：访问一个下次可能再访问这个
知识点12：Cache
高速缓存用来存放当前最活跃的程序和数据，存放主存的部分拷贝（副本）信息；
Cache作用：解决CPU与内存速度不匹配的问题；提高CPU访问主存数据或指令的效率；
Cache位于CPU与主存之间，速度比主存快，对程序员来说是透明的；
Cache 容量越大，则命中率越高，随着 Cache 容量的增加，其大效率接近 0% (命中率逐渐接近 100%)，但不是线性关系；
增加 Cache 容量意味着增加 Cache 的成本和增加 Cache 的命中时间；
替换算法：CPU从cache中取数据，如果cache中没有，就要去内存中拿，拿过来如果cache满了，就要替换出去。替换算法的目标是使Cache获得尽可能高的命中率，替换算法是一个因素但不是关键因素；
常用的替换算法：随机替换算法、先进先出算法、近期最少使用算法、优化替换算法；
【高速缓存中的地址映像方法】
在CPU 工作时，送出的是主存单元的地址，而应从 Cache 存储器中读/写信息。这就需要将主存地址转换成 Cache 存储器的地址，这种地址的转换称为地址映像。Cache 的地址映像有如下 3 种方法。
（1）直接映像
直接映像是指主存的块与 Cache 块的对应关系是固定的
（2）全相联映像
主存与 cache 存健器均分成大小相同约块。这种映像方式允许主存的任一块可以调入 Cache 存储器的任何一个块的空间中.
（3）组相联映像
直接映像和全相联影响的结合
冲突由小到大：全相联映像<组相联映像<直接映像
Cache 与主存地址的映射是由硬件自动完成的
知识点13：中断
计算机在执行程序过程中，当遇到急需处理的事件时，暂停当前正在运行的程序转去执行有关服务程序，处理完后自动返回源程序，这个过程称为中断。
中断向量：提供中断服务程序的入口地址
中断响应时间：发出中断请求开始到进入中断服务程序
保存现场：目的是返回来执行源程序
为了便于实现多级中断嵌套，使用堆栈来保护断点和现场最有效
知识点14：输入输出（I/O）控制方式
程序查询方式、中断驱动方式、直接存储器方式（DMA）
由I/O 设备提出的中断请求是可屏蔽中断，电源掉电是不可屏蔽中断；
直接存储器方式（DMA）在主存与外设之间建立了直接的数据通路；
例1：(2017 年下半年)计算机运行过程中，CPU 需要与外设进行数据交换。采用_B_控制技术时，CPU与外设可并行工作。
A。程序查询方式和中断方式
B。中断方式和 DMA 方式
C。程序查询方式和 DMA 方式
D。程序查询方式、中断方式和 DMA 方式
例2：（2021 年上半年)异常是指令执行过程中在处理器内部发生的特殊事件中断是来自处理器外部的请求事件。以下关于中断和异常的叙述中，正确的是B
A.“DMA 传送结束”、“除运算时除数为 0”都为中断
B。“DMA 传送结束”为中断、“除运算时除数为 0”为异常
C。“DMA 传送结束”为异常、“除运算时除数为 0”为中断
D。“DMA 传送结束”“除运算时除数为0”都为异常
例3：(2021 年下半年)以下关于中断方式与 DMA 方式的叙述中，正确的是_A_。A。中断方式与 DMA 方式都可实现外设与 CPU 之间的并行工作
B，程序中断方式和 DMA 方式在数据传输过程中都不需要 CPU 的干预
C，采用 DMA 方式传输数据的速度比程序中断方式的速度慢
D，程序中断方式和 DMA 方式都不需要 CPU 保护现场
知识点15：总线
数据总线：数地控，数据总线、地址总线和控制总线;
总线结构可以减少信息传输线的数量；
常见总线：
PCI：并行内总线
SCSI：并行外总线
知识点16：加密技术与认证技术
【加密技术】
- 对称加密（私有密钥加密）
加密和解密是同一把密钥，只有一把密钥
密钥分发有缺陷 1. 加密解密速度很快 2. 适合加密大量明文数据 - 非对称密钥（公开密钥加密）
加密和解密不是同一把密钥，一共有两把密钥 分别是公钥和私钥
用公钥加密只能用私钥解密 用私钥加密只能用公钥解密
不能通过一把推出另一把 用接收方的公钥加密明文，可以实现防止窃听的效果
密钥分发没有缺陷 1.加密解密速度很慢 - 混合加密
【认证技术】
- 摘要：将发送的明文进行Hash算法后得到的摘要放在密文后一起发送过去，与接收方解密后的明文进行相同的Hash算法得到的摘要进行对比，如果一致，则没有篡改，否则有篡改。
- 数字签名：发送方用自己的私钥对摘要进行签名（加密）得到数字签名放在密文后一起发送过去
接收方用发送方的公钥对数字签名进行验证（解密）如果验证成功则该消息没有被假冒且不能否认，否则该消息的真实性为假冒发送。 - 数字证书：用户向CA（权威机构）机构申请数字证书，将个人信息和公钥发给CA机构，CA机构颁给用户数字证书，数字证书用CA的私钥进行签名（加密）用CA的公钥验证（解密）数字证书得到用户的公钥。
数字证书：验证身份，防止假冒
加密：防止被窃听
数字签名：防止发送方否认发送过
摘要：防止被篡改
私钥无论如何都不能互换
例1：(2010 年下半年)公钥体系中，私钥用于___,公钥用于__
(66) A。解密和签名B，加密和签名 C.解密和认证 D.加密和认证
(67) A。解密和签名B。加密和签名 C.解密和认证 D.加密和认证
公钥加密认证，私钥解密签名
例2：用户 B 收到用户 A 带数字签名的消息 M，为了验证 M 的真实性，首先需要从 CA 获取用户A的数字证书，并利用 (8) 验证该证书的真伪，然后利用 (9) 验证 M 的真实性。(2012 年下半年)
A.CA 的公钥 B.B 的私钥 C.A的公钥 D。B 的公钥
A.CA 的公钥 B。B的私钥 C.A 的公钥 D。B 的公钥
【加密算法】
| 对称密钥（私钥、私有密钥加密）算法（共享密钥加密算法） | 非对称密钥（公钥、公开密钥加密）算法 |
|---|---|
| DES | RSA |
| 3DES | ECC |
| RC-5 | DSA |
| IDEA | |
| AES | |
| RC4 |
知识点17：可靠性公式
记住公式
例题：
第二章 程序设计语言基础知识
知识点1：程序设计语言
程序设计语言的基本成分包括数据、运算、控制和传输。
高级程序设计语言不依赖于具体的机器硬件。
知识点2：编译程序和解释程序
因为计算机只能理解由0、1序列构成的机器语言，所以高级程序设计语言需要翻译。比如高级语言x=2需要翻译成由0、1序列构成的机器语言。
语言之间翻译的基本方式：汇编、解释、编译
例题：
程序设计语言的控制成分（程序的三种基本控制结构）：顺序结构、选择结构、循环（重复）结构；
许多程序设计语言规定，程序中的数据都必须具有类型，其作用：1、便于为数据合理分配存储单元；2、便于对参与表达式计算的数据对象进行检查；3、便于规定数据对象的取值范围及能够进行的计算；（注意，便于定义动态数据结构是错误的）
【变量与常量】
变量的取值在程序运行的过程中可以改变，但常量不行；
变量和常量都具有类型属性；
变量具有对应的存储单位，常量则没有；
可以对变量赋值，不能对常量赋值。
【短路计算-逻辑表达式】
例题：
知识点3：传值调用与传地址调用
函数的定义包括两部分：函数首部和函数体。函数的定义描述了函数做什么和怎么做。
函数定义的一般形式为：
返回值的类型 函数名(形式参数表) //函数首部 函数名(实参表)；
{
函数体；
}
(1)值调用（Call by Value）。若实现函数调用时将实参的值传递给相应的形参， 则称为是传值调用。在这种方式下形参不能向实参传递信息。
(2)引用调用（Call by Reference）。引用是 C++ 中引入的概念，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实参所做的访问和改变。
例题1：
例2：
解析：注意a是整型全局变量
（1）传值调用，形参r不会影响a
int x=f(a) 此时a=5，把a的值传递f(int r)，r的值为5；
a=r+1，此时r=5，a=6
r=r2，此时r=10
return r，此时返回r值赋值给x，x=r=10
a+x=6+10=16
（2）传地址调用，形参r会影响a
int x=f(a) 此时a=5，a的地址比如为ox123，把a的地址传递f(int &r)，r的地址等于a的地址等于0x123，r的值也就是5；
a=r+1，此时r=5，a=6，由于a与r指向的地址相同，那么r=6;
r=r2，此时r=12，那么a与r的地址相同存的值都为12，即a=r=12;
return r，此时返回r值赋值给x，x=r=12
a+x=12+12=24
例3：
解析：
x=5
a=35+1=16
x传值，a传地址
r的值=x的值=5，但地址不同
s的地址=a的地址，s的值=a的值=16
x=2s+1=2*16+1=33
s=x+r=33+5=38，此时a也为38
r=x-1=33-1=32
return a-x=38-5=33
知识点4：编译、解释程序翻译阶段及符号表
高级语言经过编译/解释给翻译成机器语言
编译器的工作阶段示意图：
编译方式:词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成解释方式:词法分析、语法分析、语义分析
编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换即词法分析、语法分析、语义分析是必须的。
编译器方式中中间代码生成和代码优化不是必要，可省略。即编译器方式可以在词法分析、语法分析、语义分析阶段后直接生成目标代码
符号表:
不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。
记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。
例1：
【词法分析】–很少考，更多作为干扰选项
输入：源程序 输出：记号流
词法分析阶段的主要作用是：分析构成程序的字符以及由字符按照构造规则构成的符号是否符合程序语言的规定。
【语法分析】–常考
输入：记号流 输出：语法树（分析树）
语法分析阶段的主要作用：对各条语句的结构进行合法性分析，分析程序中的句子结构是否正确
【语义分析】
输入：语法树（分析树）
分析各语法结构的含义，检查源程序是否包含静态语义错误；
语义分析的主要工作：进行类型分析和检查；
语法分析阶段可以发现程序中的所有语法错误；
语义分析阶段不能发现程序中所有的语义错误；
语义分析阶段可以发现静态语义错误；
不能发现动态语义错误，动态语义错误运行时才能发现；
【目标代码生成阶段】–很少考
该阶段的工作与具体的机器密切相关；寄存器的分配处于目标代码生成阶段；
【中间代码生成】
常见的中间代码有: 后缀式、三地址码、三元式、四元式和树(图) 等形式
中间代码与具体的机器无关.(不依赖具体的机器)可以将不同的高级程序语言翻译成同一种中间代码。中间代码可以跨平台。
因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性
例：
知识点5：词法分析的工具
【正规式】
例：
【有限自动机】
有限自动机是词法分析的一个工具，它能正确地识别正规集
确定的有限自动机 (DFA) : 对每一个状态来说识别字符后转移的状态是唯一的
不确定的有限自动机 (NFA) : 对每一个状态来说识别字符后转移的状态是不确定的
例题：
知识点6：上下文无关文法
大多数程序设计语言的语法规则用上下文无关文法描述即可。
知识点7：中缀、后缀表达式转换
逆波兰式也就是后缀式，可以利用栈进行求值
优先级相同，从右向左
中缀表达式：1-2*(3+4)/5
后缀表达式：1234+5/*-
例题1：
有括号的先算括号里的，逻辑与的优先级大于逻辑或，优先级相同的从右往左算
先算括号内，>优先级最大，x>0变成x0>
b|x>0变成b|x0> 变成bx0>|
a&b|c&bx0>|，从右向左，变成a&b|cbx0>|&
&的优先级大于|，变成ab&|cbx0>|&
最后看|，变成ab&cbx0>|&|
例题2：
把树转为中缀表达式：左根右
A：(a+b)*(c-d)
B：(a+(b-c))*d
C：(a-(b+c))*d
D：ax((b+c)-d)
第三章 数据结构
知识点1：时间复杂度与空间复杂度
算法时间复杂度以算法中基本操作重复执行的次数_简称为频度) 作为算法的时间度量-般不必要精确计算出算法的时间复杂度，只要大致计算出相应的数量级即可
【大O表示法】
T(n)：n表示问题的规模，比如循环多少次，n会增大，规模会增大
T(n)=3：常量，与n无关，不随规模增大而改变
T(n)=3=O(1)
加法规则:多项相加，保留最高阶项，并将系数化为1
乘法规则:多项相乘都保留，并将系数化为1
加法乘法混合规则:先小括号再乘法规则最后加法规则
为O(n的4次方)
第一个括号保留n
第二个括号保留n的平方
T(n)=nxn的平方=n的三次方，所以为O(n的三次方)
【时间复杂度】
1、常数阶
没有循环、递归等，跟n无关
2、对数阶
2的x次方<=n 转成 
3、线性阶
T(n)=1+1+n+1+n+n=O(n)
4、线性对数阶
5、平方阶
6、立方阶
【空间复杂度】
例题：
第四章 知识产权
考2~3题
知识点1：著作权
著作权（也称为版权）是指作者对其创作的作品享有人身权和财产权。
人身权：发表权、署名权、修改权、保护作品完整权；其中发表权受时间限制，其他不受时间限制，永远归作者
发表权的保护期：终生及其死后50年
地域性：知识产权具有严格的地域性特点，只在本国受保护
知识点2：计算机软件著作权
1、计算机软件著作权的主体：
享有著作权的人（公民、法人、其他组织）
《中华人民共和国著作权法》、《计算机软件保护条例》
2、计算机软件著作权的客体：
是指著作权法保护的计算机软件著作权的范围(受保护的对象)。根据《著作权法》第三条和《计算机软件保护条例》第二条的规定，著作权法保护的计算机软件是指计算机程序及其有关文档（软件文档）。
计算机程序包括源程序和目标程序。
计算机软件的文档一般以程序设计说明书、流程图、用户手册等表现。
计算机软件著作权的保护期
根据《著作权法》和《计算机软件保护条例》的规定，计算机软件著作权的权利自软件开发完成之日起产生，保护期为 50 年。保护期满，除开发者身份权以外，其他权利终止。
软件著作权属于软件开发者
职务开发软件著作权的归属
职务软件作品是指公民在单位任职期间为执行本单位工作任务所开发的计算机软件作品。《计算机软件保护条例》第十三条做出了明确的规定，即公民在单位任职期间所开发的软件，如果是执行本职工作的结果，即针对本职工作中明确指定的开发目标所开发的，或者是从事本职工作活动所预见的结果或自然的结果;则该软件的著作权属于该单位。
职务作品著作权属于单位，开发者只有署名权
委托开发的软件著作权归属：
《计算机软件保护条例》第十一条规定:“接受他人委托开发的软件，其著作权的归属由委托者与受委托者签订书面合同约定;无书面合同或者合同未作明确约定的，其著作权由受托人享有。
知识点3：侵权行为
知识点4：计算机软件的商业秘密权
《反不正当竞争》中商业秘密定义为“指不为公众所知悉的、能为权利人带来经济利益、具有实用性并经权利人采取保密措施的技术信息和经营信息”。
经营秘密和技术秘密是商业秘密的基本内容。
经营秘密，即未公开的经营信息，是指与生产经营销售活动有关的经营方法、警理方法、产销策略、货源情报、客户名单、标底和标书内容等专有知识。
技术秘密，即未公开的技术信息，是指与产品生产和制造有关的技术诀窍、生产方案、工艺流程、设计图纸、化学配方和技术情报等专有知识。
商业秘密的构成条件：未公开性、实用性、秘密性
例题：
知识点5：专利的申请与商标的注册
专利申请的原则
专利申请人及其代理人在办理各种手续时都应当采用书面形式。一份专利申请文件只能就一项发明创造提出专利申请，即“一份申请一项发明”样的原则。两个或者两个以上的人分别就同样发明创造申请专利的，专利权授给最先申请人。先申请先得，同一天申请协商。
(6)时间性。知识产权具有法定的保护期限，一旦保护期限届满，权利将白行终止，成为社会公众可以自由使用的知识。至于期限的长短，依各国的法律确定。例如，我国发明专利的保护期为 20 年，实用新型专利权和外观设计专利权的期限为 10 年，均自专利申请日起计算。*我国公民的作品发表权的保护期为作者终生及其死亡后 50 年。我国商标权的保护期限白核准注册之日起 10 年内有效，但可以根据其所有人的需要无限地延长权利期限，在期限届满前 6 个月内申请续展注册，每次续展注册的有效期为 10 年，续展注册的次数不限。*如果商标权人逾期不力理续展注册，其商标权也将终止。商业秘密受法律保护的期限是不确定的，该秘密一旦被公众所知悉，即成为公众可以自由使用的知识。
软件商标权的权利人是：软件注册商标所有人（看谁去注册）
商标注册原则：先注册先得，同一天注册先使用先得，同一天注册都没使用协商
算法、规则、方法、计算机程序代码不能取得专利权
第五章 数据库
考6题
关系代数、SQL语言、关系模式、范式、关系分解（无损连接、函数依赖）
第六章 面向对象
知识点1：面向对象的基本概念
【1、面向过程与面向对象的区别】
万物皆为对象
面向对象=对象+分类+继承+通过消息的通信
【2、类】
一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行和属性。
类是在对象之上的抽象，对象是类的具体化，是类的实例。
类可以分为三类：
（1）实体类：人、物等；（是应用领域中的核心类）
（2）接口类（边界类）：为用户提供一种与系统合作交互的方式；（是系统内对象和系统外参与者的联系媒介）
（3）控制类：控制活动流，充当协调者；（协调上述两种类对象之间的交互）
特殊类是一种一般类。特殊类是一般类的子类，一般类是特殊类的父类。如汽车类是交通工具类的子类
【3、对象】
在面向对象的系统中，对象是基本的运行时的实体。
它既包括数据（属性/状态/成员变量)，也包括作用于数据的操作（行为/方法/函数/成员函数）。
一个对象通常可由对象名、属性/状态/成员变量、操作/方法/行为/函数三个部分组成。
【4、消息】
对象之间进行通信的一种构造叫作消息。当一个消息发送给某个对象，包含要求接收对象去执行某些活动的信息。接收到信息的对象经过解释，然后予以响应。这种通信机制称为消息传递。
【5、方法重载】
方法名相同，参数个数不同；
方法名相同，参数类型不相同；
方法名相同，参数类型顺序不同；
【6、封装】
封装是一种信息隐蔽技术，目的是使对象的使用者和生产者分离，使对象的定义和实现分开
【7、继承】
继承是父类和子类之间共享数据和方法的机制。这是类之间的一种关系，在定义和实现一个类的时候，可以在一个已经存在的类的基础上进行，把这个已经存在的类所定义的内容作为自己的内容，并加入若干新的内容。
一个父类可以有多个子类，这些子类都是父类的特例，父类描述了这些子类的公共属性和方法。一个子类可以继承它的父类(或祖先类) 中的属性和方法，这些属性和操作在子类中不必定义，子类中还可以定义自己的属性和方法 。 只从一个父类 A 得到继承，叫作“单重继承”。如果一个子类有两个或更多个父类，则称为“多重继承”
知识点2：UML
知识点3：设计模式
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！