“计算机软件基础”考试大纲1、数据结构基本概念数据、数据元素、数据项、数据对象、数据结构的定义；数据的逻辑结构、数据的物理结构、数据的运算、数据类型以及抽象数据类型的理解。2、算法和算法分析算法的定义、算法的特性、算法的时间复杂度和算法的空间复杂度的定义及计算。3、线性表线性表的定义和基本操作、线性表的实现（包括顺序存储结构方式、链式存储结构方式）、线性表的应用。4、栈和队列栈和队列的基本概念、栈和队列的实现（包括顺序存储结构方式、链式存储结构方式）、栈和队列的应用。5、二叉树、树和森林二叉树、树和森林的概念、二叉树的定义及其主要特征、二叉树的实现（包括顺序存储结构和链式存储结构）、二叉树的遍历、二叉检索树、树和森林的存储结构、森林与二叉树的转换、树和森林的遍历、等价类问题、哈夫曼（Huffman）树和哈夫曼编码、最小堆或最大堆。6、图图的概念、图的存储（邻接矩阵和邻接表）和基本操作、图的遍历、图的基本应用极其复杂度分析（最小支撑树、最短路径、拓扑排序、关键路径）。7、查找查找的基本概念、顺序查找法、折半查找法、散列（Hash）技术、查找算法的分析及应用。8、内部排序排序的基本概念、排序的稳定性、直接插入排序、冒泡排序、简单选择排序、Shell排序、快速排序、堆排序、归并排序、基数排序、各种内排序算法的特点和性能的比较、内部排序算法的应用。9、矩阵和串特殊矩阵的压缩存储、稀疏矩阵的三元组表示法、串的基本概念、串的基本操作、串的模式匹配（Brute-Force和KMP）。10、程序设计掌握使用任意编程语言（建议C或者Java）的基本理论、基本算法和方法，能够运用数据结构的基本知识，进行程序设计。
