软考 -- 软件设计师 -- 二轮复习(3) -- 数据结构(持续更新)

软考 – 软件设计师 – 二轮复习(3) – 数据结构(持续更新)

前言

考试时间：每年5月、11月，软件设计师每年都会开考。
考试条件：三不限
考试形式： 一共两门计算机于软件工程基本知识--120分钟--机考--选择题--75分（45及格）软件设计--120分钟--机考--简答题（4道必做，1道二选一做）--75分（45及格）两门都得一次性及格才算通过，一共4小时考试时间。推荐博客：http://t.csdnimg.cn/5VzY5
推荐bilibli博主：zst_2001
本博客二轮复习资源免费下载：https://download.csdn.net/download/weixin_44399264/89687484

一、时间、空间复杂度

加法规则：多项相加，保留最高阶项，并将系数化为1
乘法规则：多项相乘都保留，并将系数化为1
加法乘法混合规则：先小括号再乘法规则最后加法规则时间复杂度估算看最内层循环，如若没有循环和递归则为O（1）非递归的基本上都是O(1)、O(n)、O(n²)

二、递归式时间复杂度

递归算法的时间复杂度：
递归的次数 × 每次递归的时间复杂度（适用于每次递归时间复杂度不变的情况）如果每次递归的时间复杂度随着n变化而变化则要根据代码来观察

1、f(n)=nlgn，一看就不符合(1)规律；
2、这里面的lgb^a = 1，所以(2)的规律 f(n) = n*lg^k*n，当k=1的时候满足原题中的f(n) = n*lgn，所以满足规律(2);
3、则O(n*1*lg^(1+1)*n) = O(nlg^2*n) 

三、线性表

如果没有给出最好最坏平均时间复杂度的话就默认是平均时间复杂度顺序表：
采用顺序存储，优点是可以随机存取表中的元素；
缺点是插入和删除操作需要移动大量的元素。
时间复杂度：
插入、删除操作最好时间复杂度为O(1)，平均和最坏时间复杂度都为O(n)
查找最好、最坏、平均情况都为O(1)单链表：
采用链式存储，优点是插入和删除操作不需要移动大量的元素，只需要修改指针；
缺点是不能随机访问表中的元素。
时间复杂度：
查找、插入、删除操作最好时间复杂度为O(1)，平均和最坏时间复杂度都为O(n)

单向循环列表插入时间复杂度O(1)，删除时间复杂度O(n)

四、栈

d是先出来的，然后剩余4哥数字，则可能的排序为4*3*2*1 = 24

进是|，出是O

五、栈和队列

单链表是只有头指针的，所以删除、插入需要移动到对对应位置再操作；
循环单链表是有头指针和尾指针的，只需要将队尾指针指向队尾，则在头指针和尾指针位置操作数据，时间复杂度为O(1)；
队列做删除只会在队头做，做插入只会在队尾做，若用循环单链表，只需要将队尾指针指向队尾，则队列的插入删除时间复杂度都为O(1)，不会遍历表

六、串

字符串是线性结构，空格也是字符串
字串是指由主串中任意长度【连续】的字符构成的序列
例如：
主串：abc
字串：a、b、c、ab、bc
ac不是字串，因为它不是主串中连续的字符

七、朴素模式匹配

八、KMP模式匹配

1、记住next[1] = 0, next[2] = 1;
2、当i=1，next[1] = 0，当i=2，next[2] = 1；
3、当i=3，前i-1的串为ab，其最大子缀长度len = 1，则当len=1时，串ab前缀 != 串ab后缀, 即a != b, 则next[3]最长相等前后缀对应的
长度len[max] = 0，则next[3] = len[max] + 1 = 1;
4、当i=4，前i-1的串为aba，其最大子缀长度len = 2，则当len=1时，串aba前缀 == 串aba后缀, 即a == a; 当len=2时，串aba前缀 != 
串aba后缀, 即ab != ba,  则next[4]最长相等前后缀对应的长度len[max] = 1，则next[4] = len[max] + 1 = 2;
5、当i=5，前i-1的串为abaa，其最大子缀长度len = 3，则当len=1时，串abaa前缀 == 串abaa后缀, 即a == a; 当len=2时，串abaa前缀 
!= 串abaa后缀, 即ab != aa; 当len=3时，串abaa前缀 != 串abaa后缀, 即aba != baa,则next[5]最长相等前后缀对应的长度len[max] 
= 1，则next[5] = len[max] + 1 = 2;
6、当i=6，前i-1的串为abaab，其最大子缀长度len = 4，则当len=1时，串abaab前缀 != 串abaab后缀, 即a != b; 当len=2时，串abaab
前缀 == 串abaab后缀, 即ab = ab; 当len=3时，串abaab前缀 != 串abaab后缀, 即aba != aab; 当len=4时，串abaab前缀 != 串abaab
后缀, 即abaa != baab,则next[6]最长相等前后缀对应的长度len[max] = 2，则next[5] = len[max] + 1 = 3;
.........
推出下题选B

1、记住next[1] = 0, next[2] = 1;
2、当i=1，next[1] = 0，当i=2，next[2] = 1；
3、当i=3，前i-1的串为aa，其最大子缀长度len = 1，则当len=1时，串aa前缀 == 串aa后缀, 即a == a, 则next[3]最长相等前后缀对应的
长度len[max] = 1，则next[3] = len[max] + 1 = 2;
4、当i=4，前i-1的串为aaa，其最大子缀长度len = 2，则当len=1时，串aaa前缀 == 串aaa后缀, 即a == a; 当len=2时，串aaa前缀 == 
串aaa后缀, 即aa == aa,  则next[4]最长相等前后缀对应的长度len[max] = 2，则next[4] = len[max] + 1 = 3;
5、当i=5，前i-1的串为aaab，其最大子缀长度len = 3，则当len=1时，串aaab前缀 != 串aaab后缀, 即a != b; 当len=2时，串aaab前缀 
!= 串aaab后缀, 即aa != ab; 当len=3时，串aaab前缀 != 串aaab后缀, 即aaa != aab, 则next[5]最长相等前后缀对应的长度len[max] 
= 0，则next[5] = len[max] + 1 = 1;
6、当i=6，前i-1的串为aaaba，其最大子缀长度len = 4，则当len=1时，串aaaba前缀 == 串aaaba后缀, 即a == a; 当len=2时，串aaaba
前缀 != 串aaaba后缀, 即aa = ba; 当len=3时，串aaaba前缀 != 串aaaba后缀, 即aaa != aba; 当len=4时，串aaaba前缀 != 串aaaba
后缀, 即aaab != aaba,则next[6]最长相等前后缀对应的长度len[max] = 1，则next[5] = len[max] + 1 = 2;
.........
推出下题选A

九、数组

十、矩阵

这一块会带入做题就行了，不需要记住公式；设有一个的矩阵，若矩阵中的任意一个元素都有则该矩阵为对称矩阵
下方的公式都是基于存储的一维数组下标是从1开始的，在软考的题目里面是适用的。
如果一维数组的下标是从0开始的，那需要在带入公式计算出M[x]补上一个减1,为M[x-1]才对。下题：
1、题中一维数组是从1开始，所以计算出来的M[x]，不需要-1；
2、不管是按照行存储，还是按照列存储，A[0,0]，A[1,0]都是第一第二个数，带入A[0,0]到下面公式，BD选项得到的值为M[0]，排除；
3、带入A[1,0]到下面公式，D选项得到的值为M[1]，排除；
选择A

1、题中一维数组是从1开始，所以计算出来的M[x]，不需要-1；
2、不管是按照行存储，还是按照列存储，A[0,0]，A[1,0]都是第一第二个数，则A[0,0] = M[1],A[1,0] = M[2]；
3、A[0,0] = M[1]带入计算排除BC；A[1,0] = M[2]代入计算排除D
选择A

1、题中一维数组是从1开始，所以计算出来的M[x]，不需要-1；
2、按照行存储，A[0,0]，A[1,0]是第一第二个数，则A[1,1] = B[1],A[1,2] = B[2]；
3、代入计算A[1,1] = B[1],A[1,2] = B[2]；
选择A

错误原因，没看到A[]是从0开始的，计算完A[0,0]后直接计算了A[1,2],结果得出了D；
按照下图，实际上如果A[]是从0开始的, 按照行计算A[0,0], A[0,1], 按照列计算A[0,0], A[1,0]
按照下图，实际上如果A[]是从1开始的, 按照行计算A[1,1], A[1,2], 按照列计算A[1,1], A[2,1]

十一、树、二叉树的概念

十二、二叉树的存储结构

十三、二叉树的遍历

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层序遍历：从上到下、从左往右依次遍历通过序列构造二叉树必须有中序序列

十四、平衡二叉树与二叉排序树

1、二叉排序树(二叉查找树)构建，若为空树，则作为树的根节点；
2、若插入的关键字大于根节点，则看根节点的右子树的节点R1，若大于R1，则递归查看R1的右节点....
3、若插入的关键字小于根节点，则看根节点的左子树的节点L1。若小于L1，则递归查看L1的左节点，若大于L1，则递归查看L1的右节点....

十五、最优二叉树（哈夫曼树）

哈夫曼树中权值越大的结点离根结点越近，权值越小的结点离根结点越远。
哈夫曼树只有度为0和度为2的结点，没有度为1的结点。
n个权值构造的哈夫曼树具有2n-1个结点。构造哈夫曼树：首先对【权值列表List从小到大排序】，然后两个权值最小的数合成一个【新的权值X1要加入权值列表List】中，【并对权值列
表List重新排序】，若新的权值x1【等于】原有权值x，则将新的权值x1放到原有相等权值x的【右边】，再次从权值列表中选择最小的两个值，
最小的的放在左子树，次小的放在右子树哈夫曼编码用二进制码表示，不一定是多少位表示一个字符，需要满足：2^n >= 字符总数，则n为每个字符表示需要的位数；例如 2^5 >= 26；
哈夫曼编码：左分支标0，右分支标1； 从根节点到各个叶子节点经历过的0和1组成的编码；文章详解：http://t.csdnimg.cn/GQsP1

哈夫曼编码压缩比：1、等长编码有多少位：2^n >= 权值数量；2、哈夫曼编码(变长编码)直接将第二行的频率看为权值（出现了多少次）即可；3、等长编码总长度 L1 = SUM(每个字符占用的位数(定长) * 权值（出现次数）) = 40*3+10*3+20*3+16*3+14*3 = 3*(40+10+20+16+14)=300;4、下图中a的哈夫曼编码实际长度为1，其余的实际长度为3，则哈夫曼编码长度 L2 = SUM(每个字符占用的位数(变长) * 权值（出现次数）) = 40*1 +  3*(10+20+16+14) = 2205、压缩比：(300-220)/300 = 0.2666666.... = 0.27

***

十六、二叉树类别

线索二又树与二叉树的遍历运算相关，是一种存储结构。
二叉排序树的结构与给定的初始关键码序列相关。
最优二叉树(即哈夫曼树)是一类带权路径长度最短的二叉树，由给定的一个权值序列构造。线索二叉树、二叉排序树和最优二叉树在结构上【都不要求】是平衡二叉树。

十七、图的概念

十八、邻接矩阵、邻接表

十九、图的遍历

二十、拓朴序列

二十一、查找

二分查找：软考的下标都从1开始的，向下取整二分查找关键字(假如为：a、b、c、d、e)的比较序列一般有以下四种规律：1、大小交替：a > b < c > d < e;2、小大交替：a < b > c < d > e;3、小小交替：a < b < c < d < e;4、大大交替：a > b > c > d > e;不符合规律的肯定有问题；

二十二、哈希表

构造hash函数常考：除留取余法；H(key) = key % mod = 地址；取余的结果范围为0 ~ mod-1；mod一般来说的取值：取 【小于n(总数)的最大的质数】
解决冲突的方法常考：
开放地址法(其实就是探测冲突了，就向后面移一位，最后一位也有就移到开头看看有没有)，每探测一次，则其【探测因子+1】
常用质数：2、3、5、7、11、13、17、19、23、29

二十三、堆

堆排序：小顶堆：堆顶位置的数据永远都是最小的数据，且各个子树的根节点 都小于 其叶子节点；大顶堆：堆顶位置的数据永远都是最大的数据，且各个子树的根节点 都大于 其叶子节点。构建大/小顶堆：先将给的数组按照顺序，层次遍历方式变成树，然后从下到上，大顶堆就是从叶子节点开始与根节点对比交换，保证每个子树
的根节点 > 子节点；小顶堆就是从叶子节点开始与根节点对比交换，保证每个子树的根节点 < 子节点；

二十四、直接插入排序

二十五、排序稳定性

稳定：直接插入、冒泡排序、归并排序
其余不稳定

二十六、快速排序

二十七、归并排序

解析：
1、归并排序先将数据递归/2拆分为单个单个的(其实就是原有的数据列表)；
2、从最底层的，每成对的组中选取最小的；
3、一旦成对组中其中某个组已经选择完了，另一个组就不需要比较了，直接填入
如下图：

二十八、杂题精选