软件设计师中级

软件设计师中级考试

一、计算机组成原理

1、数据表示

1、原码、反码、补码、移码（整数）

原码：符号位 0 （正）；1（负），其余位是数据位。1比特表示范围（-127到+127。[+0]原 = 0000 0000；[-0]原 = 1000 0000）
反码：正数与原码一样；负数，非符号位取反。（-127 ~ +127）
补码：正数与原码一样；负数，非符号位取反加一（-128 ~ +127；），[10000000]补= -256

使用补码可以进行方便的加减运算：
补码运算时，算出来的还是补码，再转原码，再表达出真正的意思

计算机中存储整数时皆是以补码的形式进行存储。我们知道补码是由原码符号位不变，其余位按位取反，再加1得来，其实补码符号位不变其余位按位取反，再加1得到的就是原码。我们在计算机屏幕上显示时，可定需要将补码再返回到原码，然后展示其对应的数值。用补码存储的另一个好处就是计算机用计算补码的那套硬件电路就能够用其再将补码翻译回原码而不需要增加多余的硬件电路，极大地简化了计算机硬件设计。

2、浮点数

2、效验码

1、奇偶校验码：增加一位，判断编码中1的个数是奇数还是偶数

2、海明码，既能检错也能纠错

数据位是n位，校验位是k位，n和k的关系要满足：
2的K次方 -1 >= n+k
海明码生成（从高位到低位）：冗余位占据2的K次方位（k从0到k-1）即1、2、4位，数据位依次填充
冗余位的检验位，是从第x位开始（即从Rx开始），检验x位，跳过x位，再检验x位，再跳过x位，以此类推。
偶校验(R1, 1, 0, 1, 0) → R1 = 0
偶校验(R2, 1, 1, 1) → R2 = 1
偶校验(R4, 0, 1, 1) → R4 = 0
偶校验(R8, 0) → R8 = 0
参考链接

3、计算机体系结构

4、指令系统

一个处理器支持的指令和指令的字节级编码称为其指令集体系结构

CISC：复杂指令集complex。
RISC：精简指令集reduced。

5、存储系统

高速缓存的地址映射方法（cache到主存，对程序员透明）
1）直接映射：主存区号、区内地址、块内地址（主存的块与Cache块的对应关系是固定的）
2）全相联映射：主存块号、块内地址
3）组相连映射：上面方法的折中

虚拟存储器：主存到外存的抽象

6、总线系统

数据总线、地址总线、控制总线

7、输入输出技术

8、可靠性

加密技术：对称加密、非对称加密（RSA）
认证技术：

二、数据结构与算法

1、基本概念与三要素

2、算法

3、线性表

顺序存储、链式存储

4、栈和队列

栈：先进后出，插入、删除的一端称为栈顶

队列：先进先出，队尾插入、队头删除

5、串、数组、矩阵和广义表

6、树和二叉树

树的基本概念：双亲、孩子、兄弟；节点的度；叶子节点；内部节点：度不为0的节点；节点的层次；树的高度；有序树

二叉树：满二叉树：满了；完全二叉树：

二叉树遍历：先序、中序、后序

线索二叉树：

最优二叉树：又称为哈夫曼树，他是一种带权路径长度最短的树。

哈夫曼编码：选出最小的2个数，和替代这个两个数，放数组中，继续

树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法

7、图

G=(V,E)，V是顶点的集合、E是边的有限集合。邻接矩阵表示法：用一个矩阵来表示图中顶点之间的关系，N个顶点的图，其邻接矩阵是一个n阶方阵。

邻接链表表示法：为图的每个顶点建立一个单链表，单链表记录的是该顶点连接的点

8、查找

9、排序

三、算法

1、分治法

分治法：
1、二分搜索算法：给定已经排好序的n个元素a[0 : n-1]，现在要从中找出一个特定的元素x。
2、合并排序：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并为所要求排好序的集合。
3、快速排序：
对于输入的子数组a[p : r]，按以下步骤进行排序
分解：以a[p]为基准元素将a[p : r]划分为3段a[p : q-1]，a[q]和a[q+1 : r]，并且让a[p : q-1]中的任何元素都小于等于a[q]，a[q+1 : r]中的任何元素都大于等于a[q]。通俗的来说就是，小于基准的放左边，大于基准的放右边。
递归求解：通过递归的调用快排算法，分别对a[p : q-1]，a[q+1 : r]两段递归调用算法。
合并：对于a[p : q-1]，a[q+1 : r]的排序是就地进行的，所以在a[p : q-1]，a[q+1 : r]排好序后不需要执行任何计算，原数组就排好序。

参考链接

2、回溯法

回溯和递归唯一的联系就是，回溯法可以用递归思想实现。

使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。例如，在解决列举集合{1,2,3}所有子集的问题中，对于每个元素，都有两种状态，取还是舍

回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点，都有可能是问题的答案。
C语言中文网_回溯法

3、贪心法

贪心算法，顾名思义就是计算机模拟一个贪心的人进行决策，在贪婪的作用下，计算机变得十分短视，它只会对每一步操作之前按某种指标选取最优处理的操作，即做到一个局部最优解。但是局部最优并不是全局最优，因此使用贪心算法需要确保正确性。

参考资料

4、动态规划

是一种将复杂问题分解成很多子问题，并将子问题的求解结果存储起来避免重复求解的一种算法。动态规划一般用来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。最后通过一组决策序列（动态转移方程），产生最终期望的最优解。能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

参考链接