2024软考-数据结构与算法-数据库工程师/网络工程师/软件设计师/信息系统管理视频教程

介绍《软考中级》中“数据结构与算法”部分的考试内容、要点、题目出现方式，以及本课程的具体授课内容。

算法定义；算法四个基本特性；算法常用描述工具；算法的复杂度：时间复杂度、空间复杂度；数据结构三要素：数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算；数据的四种基本逻辑结构：线性结构、树型结构、网状结构、集合结构。

算法与数据结构基本概念－习题讲解，请打印课程配套习题手册先行做题，习题手册密码为：zzhstudio

线性表、线性表的顺序存储特点、线性表的链式存储结构特点；栈：后进先出(LIFO,last in first out)。队列：先进先出（FIFO）、循环队列；s = ‘a1a2…an’串的存储结构：定长顺序存储、堆分配存储、块链存储（链表）

线性表、栈、队列、串－习题讲解

数组的定义、数组结构的特点、二维数组的顺序存储结构（按行存储、按列存储）、特殊矩阵、稀疏矩阵。

树的基本概念：结点、结点的度、结点的层次、叶子、孩子、兄弟、双亲、深度、子树、森林；二叉树、满二叉树、完全二叉树；二叉树结点的顺序存储和链式存储；二叉树的遍历：先序遍历(D L R)、中序遍历(L D R)、后序遍历(L R D)。

将树转换为二叉树、森林转换成二叉树、二叉树转换成森林。

赫夫曼树 Huffman (最优二叉树)、赫夫曼树构造算法、赫夫曼前缀编码、译码方法、二叉查找树(二叉排序树)的定义、构造方法。

树形结构－习题精讲。

图的分类：有向图、无向图；网、顶点的度、完全图、子图、路径、回路(环)、链、简单路径、连通、连通图、连通分量（对无向图）、强连通图、强连通分量（对有向图）。

邻接矩阵、带权图(网) 的邻接矩阵、邻接表；图的遍历: 深度优先搜索（先序遍历、栈实现）、广度优先搜索（层序遍历、队列实现）。

生成树性质、最小生成树、最小生成树算法：普里姆(Prim)最算法、克鲁斯卡尔 (Kruskal) 算法；拓扑排序算法、AOE网络；单源点最短路径算法：迪杰斯特拉算法(Dijkstra)。

图的相关习题讲解

静态查找：查找时只进行元素的查询和检索点，查找表长度不变。如：顺序查找、二分查找、分块查找等；动态查找：查找时还进行元素的添加、删除操作。如：二叉搜索（排序）树、平衡二叉树、哈希表等。

稳定排序、不稳定排序、内部排序、外部排序；直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序和希尔排序算法和时间复杂度

选择排序、交换排序、归并排序相关思想、算法步骤。

查找与排序相关习题讲解