软件设计师:05-数据结构与算法

这篇具有很好参考价值的文章主要介绍了软件设计师:05-数据结构与算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  • 本章难度在软件设计师中最高,推荐最后一章进行学习
章节 章节
01 - 计算机组成原理与体系结构 07 - 法律法规与标准化与多媒体基础
02 - 操作系统基本原理 08 - 设计模式
03 - 数据库系统 09 - 软件工程
04 - 计算机网络 10 - 面向对象
05 - 数据结构与算法 11 - 结构化开发与UML
06 - 程序设计语言与语言处理程序基础 12 - 下午题历年真题
End - 二周目上午真题 End – 二周目下午真题
End - 临考快速记忆 Java工程师的进阶之路


数据结构

一、复杂度

1.1、大O表示法

软件设计师:05-数据结构与算法


1.2、时间复杂度

软件设计师:05-数据结构与算法


1.3、空间复杂度

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

O(n)
软件设计师:05-数据结构与算法

O(n^2)
软件设计师:05-数据结构与算法


1.4、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


二、渐进符号

软件设计师:05-数据结构与算法

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

软件设计师:05-数据结构与算法


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

软件设计师:05-数据结构与算法


三、递归

3.1、时空间复杂度

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法


3.2、递归式

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


3.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法


四、线性结构

4.1、定义

软件设计师:05-数据结构与算法


4.2、存储结构

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

软件设计师:05-数据结构与算法


4.3、顺序存储

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

软件设计师:05-数据结构与算法

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

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

软件设计师:05-数据结构与算法

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

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

软件设计师:05-数据结构与算法

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


4.4、链式存储

软件设计师:05-数据结构与算法

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

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


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

软件设计师:05-数据结构与算法


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

软件设计师:05-数据结构与算法


4.5、真题

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

软件设计师:05-数据结构与算法

真题2

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

软件设计师:05-数据结构与算法

真题3

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

真题4

软件设计师:05-数据结构与算法

真题5

软件设计师:05-数据结构与算法

真题6

软件设计师:05-数据结构与算法

真题7

软件设计师:05-数据结构与算法

真题8
软件设计师:05-数据结构与算法


五、栈

5.1、定义

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


5.2、真题

真题1
软件设计师:05-数据结构与算法

真题2

软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4(必须先进入abcd,e看情况进入:decba - dceba - dcbea - dcbae)

软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法


六、队列

6.1、定义

软件设计师:05-数据结构与算法


6.2、真题

真题1

软件设计师:05-数据结构与算法

真题2

软件设计师:05-数据结构与算法

真题3(这题和题1一样,这里用代入求出答案)

软件设计师:05-数据结构与算法

真题4

软件设计师:05-数据结构与算法

真题5

软件设计师:05-数据结构与算法

真题6

软件设计师:05-数据结构与算法

真题7

软件设计师:05-数据结构与算法

真题8

软件设计师:05-数据结构与算法


6.3、栈与队列真题

真题1

软件设计师:05-数据结构与算法

真题2(出栈序列有多种,出队和入队序列一定一样)
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法


七、串

7.1、定义

软件设计师:05-数据结构与算法


7.2、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法


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

软件设计师:05-数据结构与算法


软件设计师:05-数据结构与算法


7.4、真题

真题1
软件设计师:05-数据结构与算法

真题2(最长相等前后缀+1)

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

软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

a:求 “空” 也就是
aa:求a也就是 0 + 1 = 1
aaa:求aa也就是1+1=
aaab:求aaa也就是2+1=
aaaba:求aaab也就是0+1=
aaabaa:求aaaba也就是1+1=
aaabaaa:求aaabaa也就是2+1=


八、数组

软件设计师:05-数据结构与算法

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法


九、矩阵

9.1、对称矩阵

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


9.2、三对角矩阵

软件设计师:05-数据结构与算法


9.3、稀疏矩阵

软件设计师:05-数据结构与算法


9.4、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法


十、树

10.1、定义

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


10.2、树的性质

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


10.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


十一、二叉树

11.1、定义

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


11.1、真题

真题1
软件设计师:05-数据结构与算法

真题2(二叉树性质3:度0的节点等于度2的节点+1)
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法


11.2、存储结构

1、顺序存储

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

2、链式存储

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


11.2、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


11.3、遍历

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


11.3、反向构造

1、先+中


11.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法


11.4、平衡二叉树

软件设计师:05-数据结构与算法


11.4、二叉排序树

软件设计师:05-数据结构与算法


11.4、真题

真题1
软件设计师:05-数据结构与算法
真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法


11.5、最优二叉树(哈夫曼树)

1、定义

软件设计师:05-数据结构与算法

2、构造哈夫曼树

软件设计师:05-数据结构与算法

3、概念

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

4、规范化构造

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

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法


11.5、哈夫曼编码

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

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


11.5、哈夫曼编码压缩比

软件设计师:05-数据结构与算法


11.5、真题

真题1

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

软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法

真题8
软件设计师:05-数据结构与算法

真题9
软件设计师:05-数据结构与算法

真题10
软件设计师:05-数据结构与算法


11.6、线索二叉树

软件设计师:05-数据结构与算法


11.7、混合题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法


十二、图

12.1、定义

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

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

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


12.1、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法


12.2、邻接矩阵

软件设计师:05-数据结构与算法

12.2、邻接表

软件设计师:05-数据结构与算法


12.2、稠密图和稀疏图

软件设计师:05-数据结构与算法


12.2、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


12.3、图的遍历

软件设计师:05-数据结构与算法

1、深度优先搜索(DFS)

软件设计师:05-数据结构与算法
1111软件设计师:05-数据结构与算法

2、广度优先(BFS)

软件设计师:05-数据结构与算法


12.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法


12.4、拓扑排序

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


12.4、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


十三、查找

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


13.1、顺序查找

软件设计师:05-数据结构与算法


13.2、二分查找

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


13.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3

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

软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法

真题8
软件设计师:05-数据结构与算法

真题9
软件设计师:05-数据结构与算法

真题10
软件设计师:05-数据结构与算法

真题11
软件设计师:05-数据结构与算法

真题12
软件设计师:05-数据结构与算法


十四、哈希表

14.1、哈希表定义

软件设计师:05-数据结构与算法


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

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

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


14.3、处理冲突扩展

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法


14.4、哈希表的查找

软件设计师:05-数据结构与算法


14.5、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法


十五、堆

15.1、定义

软件设计师:05-数据结构与算法


15.2、构造

软件设计师:05-数据结构与算法


15.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法


十六、排序

Java实现八大排序算法

16.1、定义

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法


16.2、插入排序(稳定 不归位)

适用于序列基本上有序

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

无法归位(元素位置在下一轮可能改变)

软件设计师:05-数据结构与算法

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;
            }
        }
    }
}
  • 最坏(n2):每个未排序序列元素都需与每个已排序序列进行比较(混乱序列{2,1,5,3,7,3,1,3}
  • 最好(n):每个未排序序列元素只需与一个已排序序列进行比较(基本有序序列{1,1,2,4,5,8,6}

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


16.2、希尔排序(不稳定)

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

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;
                }
            }
        }
    }
}

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


16.2、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


16.3、选择排序(不稳定 归位)

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

软件设计师:05-数据结构与算法

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;
        }
    }
}

16.2、堆排序(不稳定 归位)

软件设计师:05-数据结构与算法

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

软件设计师:05-数据结构与算法


16.2、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法


16.3、冒泡排序(稳定 归位)

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

软件设计师:05-数据结构与算法

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;
            }
        }
    }
}

软件设计师:05-数据结构与算法


16.3、快速排序(不稳定 归位)

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

// 首元素为基准值
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);
}

空间复杂度是log2n

软件设计师:05-数据结构与算法


16.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


16.4、归并排序(稳定 不归位)

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法

// 分+合 默认值
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++;
    }
}

16.4、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法

真题8
软件设计师:05-数据结构与算法


十七、杂题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法

真题8
软件设计师:05-数据结构与算法

真题9
软件设计师:05-数据结构与算法


算法

一、回溯法-N皇后问题

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法

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 4 1 3 
方案2: 3 1 4 2 

1.2、递归法求解

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

(1 2 3 4) (1 2 3) (1 2 3 4) ?
软件设计师:05-数据结构与算法

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

软件设计师:05-数据结构与算法

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

软件设计师:05-数据结构与算法

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.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

真题3

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法


二、分治法

2.1、递归的概念

软件设计师:05-数据结构与算法


2.2、基本思想

软件设计师:05-数据结构与算法


2.3、上午真题

真题1

软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


2.4、下午真题

真题1

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法

真题2

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


三、动态规划法

3.1、基本思想

软件设计师:05-数据结构与算法


3.2、0-1背包问题

视频教程

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

软件设计师:05-数据结构与算法

软件设计师:05-数据结构与算法

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();
        }
    }
}

3.3、上午真题

真题1

软件设计师:05-数据结构与算法

真题2

软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法

真题7
软件设计师:05-数据结构与算法


3.4、下午真题

真题1
软件设计师:05-数据结构与算法

解析

软件设计师:05-数据结构与算法

官方解析
软件设计师:05-数据结构与算法


四、贪心法

4.1、基本思想

软件设计师:05-数据结构与算法


4.2、部分背包问题

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


4.3、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法


五、算法总和

5.1、动态规划

软件设计师:05-数据结构与算法
软件设计师:05-数据结构与算法


5.2、贪心法

软件设计师:05-数据结构与算法


5.3、回溯法

软件设计师:05-数据结构与算法


5.4、分支限界法

软件设计师:05-数据结构与算法


5.5、真题

真题1
软件设计师:05-数据结构与算法

真题2
软件设计师:05-数据结构与算法

真题3
软件设计师:05-数据结构与算法

真题4
软件设计师:05-数据结构与算法

真题5
软件设计师:05-数据结构与算法

真题6
软件设计师:05-数据结构与算法文章来源地址https://www.toymoban.com/news/detail-436503.html

到了这里,关于软件设计师:05-数据结构与算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 中级软件设计师备考---计算机组成与体系结构3

    计算题 概念题 计算可靠度 码距:是指两个码字之间的不同位数。例如,1010和1111之间的码距是2,因为它们在第二位和第三位上不同。在信息传输中,码距越大,就越容易检测和纠正错误。 在一个码组内为了检测e个误码,要求最小码距d应满足:d=e+1 在一个码组内为了纠正

    2023年04月15日
    浏览(42)
  • 软考高级系统架构设计师系列论文九十七:论软件三层结构的设计

    软考高级系统架构设计师:软件架构设计系列二 随着中间件与Web技术的发展,三层或多层分布式应用体系越来越流行。在这种体系结构中,将应用功能分成表示层、功能层和数据层三部分。 本人在去年参加了一个备件流程管理项目的开发,在此项目中担任需求分析和结构设

    2024年02月11日
    浏览(73)
  • 软考:中级软件设计师:大数据

    提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性 关于互联网大厂的笔试面试,都是需要细心准备的 (1)自己的科研经历, 科研内容 ,学习的相关领域知识,要熟悉熟透了 (2)自己的实习经历,做了 什

    2024年02月11日
    浏览(56)
  • 软考软件设计师 数据库知识点笔记

    了解即可 外模式对应视图 概念模式对应的是数据库管理系统里面的基本表 内模式对应的是数据库里的一些存储文件 上图可直接背下面概念 有内模式跟物理独立性相关,有外模式跟逻辑独立性相关 两级映像其中有一方肯定是模式,如下提d选项 候选码的意思它只能表示那个

    2023年04月13日
    浏览(61)
  • 软考:中级软件设计师:数据库模式、ER模型

    提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性 关于互联网大厂的笔试面试,都是需要细心准备的 (1)自己的科研经历, 科研内容 ,学习的相关领域知识,要熟悉熟透了 (2)自己的实习经历,做了 什

    2024年02月12日
    浏览(52)
  • 【软件设计师暴击考点】计算机组成原理与体系结构高频考点暴击系列【一】

    👨‍💻个人主页 :@元宇宙-秩沅 👨‍💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍💻 本文由 秩沅 原创 👨‍💻 收录于专栏 : 软件设计师考点暴击 下午题 ⭐【软件设计师暴击考点】下午题高频考点暴击系列 上午题目录 进入专栏浏览:

    2024年02月10日
    浏览(42)
  • 软件设计师学习笔记12-数据库的基本概念+数据库的设计过程+概念设计+逻辑设计

    目录 1.数据库的基本概念 1.1数据库的体系结构 1.1.1常见数据库 1.1.2分布式数据库的特点 1.1.3分布式数据库的透明性 1.1.4例题 1.2三级模式结构 1.2.1三级模式概念图 1.2.2例题 1.3数据仓库 1.3.1数据仓库的特点 1.3.2数据仓库的过程 1.3.3例题 2.数据库的设计过程 2.1设计过程概念图 2

    2024年02月07日
    浏览(64)
  • 【软件设计师】程序猿需掌握的技能——数据流图

    作为一个程序员,不仅要具备高水平的程序编码能力,还要是熟练掌握软件设计的方法和技术,具有一定的软件设计能力,一般包括软件分析设计图(常见的有数据流图,程序流程图,系统流程图,E-R图)和其他对业务表达的说明资料。 数据流图(Data Flow Diagram,简称DFD)

    2024年02月20日
    浏览(48)
  • 系统架构设计师考试论文:论NoSQL 数据库技术在现代软件项目中的应用与效果

            随着互联网 web2.0 网站的兴起,传统关系数据库在应对 web2.0 网站,特别是超大规模和高并发的 web2.0 纯动态 SNS 网站上已经显得力不从心,暴露了很多难以克服的问题,而非关系型的数据库则由于其本身的特点得到了非常迅速的发展。NoSQL(Not only SQL )的产生就是为

    2024年02月11日
    浏览(43)
  • 软件设计师——软件工程(四)

    本文主要是【软件工程】——软件设计师——软件工程的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句:狠狠沉淀,顶峰相见 21.某开发小组欲为一公司开发一个产品控制软件,监控

    2024年01月24日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包