软件设计师：05-数据结构与算法_软件设计师数据结构与算法题

• 本章难度在软件设计师中最高，推荐最后一章进行学习

---

---

数据结构

一、复杂度

1.1、大O表示法

---

1.2、时间复杂度

---

1.3、空间复杂度

定义的数据占用多少空间就是空间复杂度

O（n）

O(n^2)

---

1.4、真题

真题1

真题2

真题3

真题4

---

二、渐进符号

• 渐进上界：大于等于平均时间复杂度
• 渐进下界：小于等于平均时间复杂度
• 渐进紧致界：等于平均时间复杂度

---

真题（如下的O小于平均时间复杂度所以错误）

---

三、递归

3.1、时空间复杂度

---

3.2、递归式

---

3.3、真题

真题1

真题2

真题3

真题4

真题5

真题6

---

四、线性结构

4.1、定义

---

4.2、存储结构

也就相当于一个数组，所以可以直接通过下边快速查询到表中的元素，所以效率高，但是插入和删除会批量移动，所以效率低，简称查询高效率，插删低效率

---

4.3、顺序存储

1、插入元素的代码和时间复杂度

• 最好的情况就是直接在顺序表后面插入一个元素，时间复杂度为O(1)
• 最坏的情况是在插入一个元素到原来第一个元素的位置，时间复杂度为O(n)
• 平均复杂度为O(n)

---

2、删除元素的代码和时间复杂度

• 最好的情况就是直接在删除最后一个元素，时间复杂度为O(1)
• 最坏的情况是删除第一个元素，时间复杂度为O(n)
• 平均复杂度为O(n)

---

3、查找元素的代码和时间复杂度

时间复杂度为O(1)，因为这是直接根据数组下边就可以快速查询到对应的元素

---

4.4、链式存储

1、插入元素的代码和时间复杂度

---

2、删除元素的代码和时间复杂度

---

3、查找元素的代码和时间复杂度

---

4.5、真题

真题1（一般没有问最好或者最坏的时间复杂度那就是默认为平均复杂度）

真题2

删除是要找到删除结点的前面一个结点的位置，循环单链表删除是要找到前面一个结点的位置，也就是要遍历链表，但是插入到尾结点后面就不用遍历直接插入就行

真题3

真题4

真题5

真题6

真题7

真题8

---

五、栈

5.1、定义

---

5.2、真题

真题1

真题2

真题3

真题4（必须先进入abcd，e看情况进入：decba - dceba - dcbea - dcbae）

真题5

真题6

真题7

---

六、队列

6.1、定义

---

6.2、真题

真题1

真题2

真题3（这题和题1一样，这里用代入求出答案）

真题4

真题5

真题6

真题7

真题8

---

6.3、栈与队列真题

真题1

真题2（出栈序列有多种，出队和入队序列一定一样）

真题3

真题4

真题5

真题6

---

七、串

7.1、定义

---

7.2、真题

真题1

真题2

---

7.3、串的模式匹配和朴素匹配

---

---

7.4、真题

真题1

真题2（最长相等前后缀+1）

例如abaab，最长相等前后缀是ab，那么就是2+1=3
例如abaaaba，最长相等前后缀是aba，那么就是3+1=4

真题３

ａ：求 “空” 也就是０
ａａ：求ａ也就是 0 + 1 ＝ 1
ａａａ：求ａａ也就是１＋１＝２
ａａａｂ：求ａａａ也就是２＋１＝３
ａａａｂａ：求ａａａｂ也就是０＋１＝１
ａａａｂａａ：求ａａａｂａ也就是１＋１＝２
ａａａｂａａａ：求ａａａｂａａ也就是２＋１＝３

---

八、数组

真题1

真题2

真题3

---

九、矩阵

9.1、对称矩阵

---

9.2、三对角矩阵

---

9.3、稀疏矩阵

---

9.4、真题

真题1

真题2

真题3

真题4

真题5

---

十、树

10.1、定义

---

10.2、树的性质

---

10.3、真题

真题1

真题2

---

十一、二叉树

11.1、定义

---

11.1、真题

真题1

真题2（二叉树性质3：度0的节点等于度2的节点+1）

真题3

真题4

真题5

真题6

真题7

---

11.2、存储结构

1、顺序存储

2、链式存储

---

11.2、真题

真题1

真题2

真题3

真题4

---

11.3、遍历

---

11.3、反向构造

1、先+中

---

11.3、真题

真题1

真题2

真题3

真题4

真题5

真题6

---

11.4、平衡二叉树

---

11.4、二叉排序树

---

11.4、真题

真题1

真题2

真题3

真题4

真题5

---

11.5、最优二叉树（哈夫曼树）

1、定义

2、构造哈夫曼树

3、概念

• 权值越大离根节点越近
• 给定的权值节点为叶子节点
• 每个非叶子节点度都为2
• 总的节点为给定的节点的(2倍-1)

4、规范化构造

• 从前往后找两个权值最小
• 小左大右加入末尾（若构造完的权值和原本的权值一样，那么构造完的放右边 ）
• 权值相同从前往后
• 用时再调用

---

11.5、哈夫曼编码

26个字符可用 2ⁿ>=26 n=5位二进制串表示

---

11.5、哈夫曼编码压缩比

---

11.5、真题

真题1

叶子节点有n个，度为0的节点数=度为2的节点数+1
节点总数=0度节点数+2度节点数=n+n-1=2n-1

真题2

真题3

真题4

真题5

真题6

真题7

真题8

真题9

真题10

---

11.6、线索二叉树

---

11.7、混合题

真题1

真题2

真题3

---

十二、图

12.1、定义

可以是非直接路径比如下图1-4可以通过1-3-4，这样求出来的就是最少

---

12.1、真题

真题1

真题2

---

12.2、邻接矩阵

12.2、邻接表

---

12.2、稠密图和稀疏图

---

12.2、真题

真题1

真题2

真题3

真题4

---

12.3、图的遍历

1、深度优先搜索（DFS）

1111

2、广度优先（BFS）

---

12.3、真题

真题1

真题2

真题3

真题4

真题5

真题6

---

12.4、拓扑排序

---

12.4、真题

真题1

真题2

真题3

真题4

---

十三、查找

---

13.1、顺序查找

---

13.2、二分查找

---

13.3、真题

真题1

真题2

真题3

• 第一轮mid为55，mid小于目标值，将l定位为mid+1
• 第二轮mid为95，结束

真题4

真题5

真题6

真题7

真题8

真题9

真题10

真题11

真题12

---

十四、哈希表

14.1、哈希表定义

---

14.2、哈希函数构造与处理冲突

哈希表表长一般为不大于散列函数且最接近散列函数的质数

---

14.3、处理冲突扩展

---

14.4、哈希表的查找

---

14.5、真题

真题1

真题2

真题3

真题4

真题5

真题6

真题7

---

十五、堆

15.1、定义

---

15.2、构造

---

15.3、真题

真题1

真题2

真题3

---

十六、排序

Java实现八大排序算法

16.1、定义

---

16.2、插入排序（稳定 不归位）

适用于序列基本上有序

• 将一个待排序的数组分成两部分，前一部分代表是有序序列，后一部分代表未排序序列
• 将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置
• 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面，直到未排序序列全部扫描完毕为止。

无法归位（元素位置在下一轮可能改变）

public static void insertionSort(int[] arr) {
	// 待插入的数为从下标为1开始，因为先把下标为0的固定住了
    for (int i = 1; i < arr.length; i++) {
    	// 循环与前面的有序序列的每个值进行比较，若有序序列的下标小于0则中断循环
        for (int j = i - 1; j >= 0; j -= 1) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 最坏(n²)：每个未排序序列元素都需与每个已排序序列进行比较（混乱序列{2,1,5,3,7,3,1,3}）
• 最好(n)：每个未排序序列元素只需与一个已排序序列进行比较（基本有序序列{1,1,2,4,5,8,6}）

---

16.2、希尔排序（不稳定）

public static void shellSort(int[] arr) {
    for (int step = arr.length / 2; step > 0; step /= 2) {
        //核心代码就是插入排序，把所有的一替换成step
        for (int i = step; i < arr.length; i++) {
            for (int j = i - step; j >= 0; j -= step) {
                if (arr[j] > arr[j + step]) {
                    int temp = arr[j];
                    arr[j] = arr[j + step];
                    arr[j + step] = temp;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

16.2、真题

真题1

真题2

真题3

真题4

---

16.3、选择排序（不稳定 归位）

• 从待排序的元素中选出最小的元素，存放在起始位置，固定住该最小元素
• 同理取出未固定的元素中的最小元素，存放在起始位置，固定
• 以此类推，直到全部待排序的数据元素的个数为零。
• 5个元素只需要选择4次，因为最后一个默认为最大的

public static void selectionSort(int[] arr) {
	// 5个元素只需要选择4次，因为最后一个默认为最大的
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        // 从第二个元素开始比较，找出最小值下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

16.2、堆排序（不稳定 归位）

大顶堆：将堆顶元素取出作为序列最大值，将堆底元素提到堆顶，在进行一次调整堆，将75作为第二大值。。。（产生递增序列，小顶堆则产生递减序列）

---

16.2、真题

真题1

真题2

---

16.3、冒泡排序（稳定 归位）

• 比较相邻的元素，如果第一个比第二个大，就交换他们两个
• 对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对，这步做完后，最后的元素应该会是最大的数
• 每次过后，需要排序的元素就越来越少，对剩下需要排序的元素重复上面的步骤，直到没有任何一对数字需要比较

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;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

---

16.3、快速排序（不稳定 归位）

// 首元素为基准值
public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right, pivot = arr[i];

    while (i < j) {
    	// 从右开始找比基准值小的元素
        while (i < j && arr[j] >= pivot) j--;
        // 将该元素放在最左侧
        arr[i] = arr[j];
        // 从左开始找比基准值大的元素
        while (i < j && arr[i] <= pivot) i++;
        arr[j] = arr[i];
    }
    arr[i] = pivot;

    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

空间复杂度是log2n

---

16.3、真题

真题1

真题2

真题3

真题4

---

16.4、归并排序（稳定 不归位）

// 分+合 默认值
public static void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}

// 分+合
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 向左分解
        mergeSort(arr, left, mid, temp);
        // 向右分解
        mergeSort(arr, mid + 1, right, temp);

        // 合并
        merge(arr, left, mid, right, temp);
    }
}

// 治
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;    // 左边序列初始索引
    int j = mid + 1; // 右边序列初始索引
    int t = 0;       // temp数组的当前索引

    // 1）先把左右序列按顺序填充到temp数组，直到左右序列有一方处理完毕
    while (i <= mid && j <= right) {
        // 如果左序列的值小于右序列则进行存放并将左序列指针右移
        if (arr[i] < arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else { // 如果右序列的值小于等于左序列则进行存放并将右序列指针右移
            temp[t] = arr[j];
            t++;
            j++;
        }
    }

    // 2）把有剩余数据的一边序列全部填充到temp
    // 如果左边还有剩余
    while (i <= mid) {
        temp[t] = arr[i];
        t++;
        i++;
    }
    // 如果右边还有剩余
    while (j <= right) {
        temp[t] = arr[j];
        t++;
        j++;
    }

    // 3）将temp数组的元素拷贝回arr
    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

---

16.4、真题

真题1

真题2

真题3

真题4

真题5

真题6

真题7

真题8

---

十七、杂题

真题1

真题2

真题3

真题4

真题5

真题6

真题7

真题8

真题9

---

算法

一、回溯法-N皇后问题

1.1、非递归求解

public class NTest {
    public static void main(String[] args) {
        queen();
    }

    static int N = 4;
    static int[] q = new int[N + 1];
    static int answer = 0; // 方案数

    // 检查放入的皇后是否合法
    public static boolean check(int j) {
        for (int i = 1; i < j; i++) {
            if (q[i] == q[j] || Math.abs(i - j) == Math.abs(q[i] - q[j])) {
                return false;
            }
        }
        return true;
    }

    public static void queen() {
        // 初始化棋盘
        for (int i = 1; i <= N; i++) {
            q[i] = 0;
        }
        
        int j = 1;  // 表示摆放第 j 个皇后
        while (j >= 1) { // 防止回溯时溢出
            // 让该皇后按列摆放
            q[j] = q[j] + 1;

            // 判断皇后位置是否合法且不越界
            while (q[j] <= N && !check(j)) {
                q[j] = q[j] + 1;    // 不合法就往下一个位置摆放
            }

            if (q[j] <= N) {
                // 第j个找到合法位置
                if (j == N) { // 找到一组解
                    answer++;
                    System.out.print("方案" + answer + ": ");
                    for (int i = 1; i < q.length; i++) {
                        System.out.print(q[i] + " ");
                    }
                    System.out.println();
                } else { // 继续摆放
                    j = j + 1;
                }

            } else {
                // 还原第j个皇后的位置
                q[j] = 0;
                // 第j个找不到合法位置,回溯到上一个皇后的位置
                j = j - 1;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

方案1: 2 4 1 3 
方案2: 3 1 4 2 
1
2

---

1.2、递归法求解

大概的意思就是如下三图，对递归不了解的再去查查资料

(1 2 3 4) (1 2 3) (1 2 3 4) ？

(1 2 3 4) (1 2 3 4)

(1 2 3 4) (1 2 3 4)(1 2) ？

public class NTest02 {
    public static void main(String[] args) {
        queen(1);
    }

    static int N = 4;
    static int[] q = new int[N + 1];
    static int answer = 0;

    // 检查放入的皇后是否合法 (true 合法 | false 不合法)
    public static boolean check(int j) {
        for (int i = 1; i < j; i++) {
            if (q[i] == q[j] || Math.abs(i - j) == Math.abs(q[i] - q[j])) {
                return false;
            }
        }
        return true;
    }
    // 打印解决方案
    public static void answer() {
        answer++;
        System.out.print("方案" + answer + ": ");
        for (int k = 1; k < q.length; k++) {
            System.out.print(q[k] + " ");
        }
        System.out.println();
    }
    
    // 放入皇后
    public static void queen(int j) {
        for (int i = 1; i <= N; i++) {
            q[j] = i;         // 每行都循环按列摆放
            if (check(j)) {   // 不冲突则检查是否摆放完成，否则摆放下一个
                if (j == N) { // 摆放完成
                    answer();
                } else {      // 摆放下一个
                    queen(j + 1);
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

1.3、真题

真题1

真题2

真题3

---

二、分治法

2.1、递归的概念

---

2.2、基本思想

---

2.3、上午真题

真题1

真题2

真题3

真题4

---

2.4、下午真题

真题1

真题2

---

三、动态规划法

3.1、基本思想

---

3.2、0-1背包问题

视频教程

时空间复杂度O(N x W)

public class Plan {
    public static void main(String[] args) {
        int N = 4;  // 物品数量
        int W = 5;  // 背包容量
        int[] v = {0, 2, 4, 5, 6};   // 物品价值数组
        int[] w = {0, 1, 2, 3, 4};   // 物品重量数组
        int[][] f = new int[N + 1][W + 1]; // 子问题解数组

        for (int i = 1; i <= N; i++) {     // 物品编号
            for (int j = 1; j <= W; j++) { // 背包容量
                if (j >= w[i]) { // 选择当前物品
                    // (上一个物品的最优解) 比较 (当前物品价值+剩余容量在上一个物品的最优解)
                    f[i][j] = Math.max(f[i - 1][j], v[i] + f[i - 1][j - w[i]]);
                } else {		 // 不选择当前物品
                    // 直接使用上一个物品的最优解
                    f[i][j] = f[i - 1][j];
                }
            }
        }

        System.out.println("最优解:" + f[N][W]);

        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= W; j++) {
                System.out.printf("%d", f[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

3.3、上午真题

真题1

真题2

真题3

真题4

真题5

真题6

真题7

---

3.4、下午真题

真题1

解析

官方解析

---

四、贪心法

4.1、基本思想

---

4.2、部分背包问题

---

4.3、真题

真题1

真题2

真题3

真题4

---

五、算法总和

5.1、动态规划

---

5.2、贪心法

---

5.3、回溯法

---

5.4、分支限界法

---

5.5、真题

真题1

真题2

真题3

真题4

真题5

真题6