# 软考中级 7 数据结构与算法

# 基本名词

缩写 名称 备注

# 主要概念

哈希冲突时,冲突的 key 称为同义词

队列空或满不是由数据结构决定的

矩阵压缩方法:三元组顺序表、行逻辑连接的顺序表、十字链表

# 简单选择排序

去 Bilibili 看简单选择排序 (opens new window)

# 冒泡排序

去 Bilibili 看冒泡排序 (opens new window)

# 希尔排序

要点:按间隔进行分组,组内使用直接插入排序,间隔每次减半,间隔为 1 时做最后一次组内直接插入排序

希尔排序的目的是:减少比较次数与交换次数,所以最差的时间复杂的是 O(n^1.3)

与快速排序相比,希尔排序的空间复杂度比较高,每次都要分配新的数组

去 Bilibili 看希尔排序 (opens new window)

# 快速排序

要点:基准值(挖坑),头尾指针与跟基准值比较并填坑,头尾指针相遇时完成一轮排序

golang 使用快速排序作为基础算法

快速排序的时间复杂度(平均)、空间复杂度都很好

去 Bilibili 看快速排序 (opens new window)

# 复杂度对比

排序算法 最好时间复杂度 最坏时间复杂度 稳定性
直接插入 O(n) O(n^2) 稳定
简单选择 O(n^2) O(n^2) 不稳定
冒泡排序 O(n) O(n^2) 稳定
希尔排序 O(n) O(n^1.3) 不稳定
快速排序 O(nlogn) O(n^2) 不稳定
堆排序 O(nlogn) O(nlogn) 不稳定
归并排序 O(nlogn) O(nlogn) 稳定

# 重要习题

# 某文档包含 5 个字符,字符出现频率如下,采用霍夫曼编码进行压缩,则单词 “cade” 的编码为 ( ? ),压缩率为 ( ? )

字符 a b c d e
频率 % 40 10 20 16 14

a: 0
b: 100
c: 111
d: 110
e: 101

cade: 1110110101

压缩后长度=1*0.4+3*0.1+3*0.2+3*0.16+3*0.14=2.2
压缩率=(3-2.2)/3=27%
最后更新于: 10/29/2022, 3:11:35 PM