科目代码：828
科目名称：数据结构
一、考试内容
1．数据结构及相关基本概念
(1)了解数据结构与算法的概念。
(2)理解数据结构有关的概念和术语：数据、数据元素、数据对象、数据结构、线性结构、树形结构、图结构、集合结构。
(3)了解抽象数据类型的概念与一般实现方法。
(4)掌握算法及其评价方法：算法的定义，表示形式、特性，时间复杂度及其计算方法，空间复杂度。
2．线性表
(1)了解线性表的概念：定义，特点，线性表抽象数据类型定义。
(2)掌握线性表在顺序存储结构和链式存储结构上基本操作（如查找、插入、删除）的算法实现和效率评价。
(3)掌握线性表的应用，能灵活应用适当的存储形式来解决具体问题。
3．栈和队列
(1)掌握栈的概念，特点，抽象数据类型的定义。
(2)掌握栈在顺序存储结构和链式存储结构上基本操作（如查找、插入、删除）的算法实现及效率评价。
(3)掌握队列的概念，特点，抽象数据类型队列的定义。
(4)掌握队列顺序存储和链式存储上基本操作（如查找、插入、删除）的算法实现及效率评价。
(5)掌握栈和队列的应用，能灵活应用适当的存储形式来解决具体问题。
4．串
(1)理解串类型的定义：串的定义，特点，串的抽象数据类型定义。
(2)掌握串的表示和实现。
(3)掌握串的模式匹配。
(4)了解串的应用。
5．数组和广义表
(1)掌握数组：定义，特点，数组元素存储位置的计算。
(2)掌握特殊矩阵的压缩存储及其运算。
(3)了解广义表：定义，特点，存储及运算。
6．树和二叉树
(1)理解树的定义及相关概念。
(2)掌握二叉树定义及性质。
(3)掌握二叉树的顺序存储结构和链式存储结构。
(4)掌握二叉树的遍历算法及其应用。
(5)掌握线索二叉树的概念和构造。
(6)掌握哈夫曼树和哈夫曼编码。
(7)掌握树和森林的特点，树的存储结构，树和森林的遍历，树和森林与二叉树的转换。
7．图
(1)理解图的定义及相关概念。
(2)掌握图的存储结构：邻接矩阵，邻接表，十字链表。邻接多重表。
(3)掌握图的图的遍历：深度优先搜索，广度优先搜索
(4)掌握图的应用：无向图的连通分量和生成树、最小生成树、有向无环图及其应用、最短路径，并能利用图的基本操作解决实际问题。
8．查找
(1)理解查找的定义及相关概念。
(2)掌握顺序表的查找，有序表的查找，索引顺序表的查找。
(3)掌握二叉排序树，平衡二叉树，B-树。
(4)掌握哈希表及其查找。
9．内部排序
(1)理解排序的定义及相关概念。
(2)掌握直接插入排序，二分法插入排序，直接选择排序，冒泡排序，希尔排序，快速排序，堆排序，归并排序，基数排序等。
(3)理解各类内部排序方法的特点：时间复杂度，空间复杂度，稳定性。
二、考试要求
1.掌握数据结构的基本知识、问题的求解方法。
2.掌握主要算法，能够估算主要算法的时间复杂度和空间复杂度。
3.能够使用C语言或其它高级语言及数据结构的基本操作实现主要算法。
4.能够灵活运用数据结构解决实际问题。
甘公网安备62010502000995号 陇ICP备14001560号-2 设计制作 宏点网络
