软考中数据结构考什么

软件工程数据结构的考试内容主要包括以下几个方面：

栈、队列和向量

栈的基本概念和性质，栈的ADT及其顺序和链接实现，栈的应用，栈与递归。

队列的基本概念和性质，队列的ADT及其顺序和链接实现，队列的应用，环形队列，双向队列。

向量的基本概念和性质，向量的ADT及其数组和链接实现。

树

树的基本概念和术语，树的前序、中序、后序、层次序遍历。

二叉树及其性质，普通树与二叉树的转换，树的存储结构，标准形式，完全树的数组形式存储，空树的表示。

树的应用，如Huffman树的定义与应用。

查找

查找的基本概念。

对线性关系结构的查找，如顺序查找、二分查找。

Hash查找法，常见的Hash函数及其实现，Hash冲突的概念及解决方法（如开放散列方法、拉链法、闭散列方法、开址定址法）。

二次聚集现象。

BST树的定义、性质、ADT及其实现，BST树的查找、插入。

图

图的定义和术语。

图的存储结构，包括邻接矩阵和邻接表。

图的遍历（如深度优先搜索、广度优先搜索）。

图的连通性问题。

有向无环图及其应用。

最短路径（如Dijkstra算法、Floyd算法）。

排序

排序的基本概念。

常见的排序算法（如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序）。

算法分析及时间、空间复杂度

算法的时间复杂度及空间复杂度计算方法，从而分析算法优劣。

实际应用

通过编程题考察候选人对数据结构的理解和应用能力，包括数据结构的选择、基本操作的实现、问题分析与抽象能力、时间和空间复杂度分析。

建议考生重点掌握上述内容，并通过编程练习来巩固和提高自己的数据结构应用能力。