2015数据结构与算法设计考试大纲

《2015数据结构与算法设计考试大纲》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2015数据结构与算法设计考试大纲1．绪论（1）了解数据结构的意义，数据结构在计算机领域的地位和作用；（2）掌握数据结构各名词、术语的含义和有关的基本概念；数据的逻辑结构和存储结构之间的关系；（3）了解使用C语言对数据结构进行抽象数据类型的表示和实现的方法；（4）了解算法的五要素；（5）掌握计算语句频度估算算法时间复杂度的方法；学习重点：（1）数据的逻辑结构和存储结构及其之间的关系（2）算法时间复杂度及空间复杂度及其计算2．线性表（1）理解线性表的逻辑结构特性。（2）深入掌握线性表的两种存储方法,即顺序表和链表。体会这两种存储结构之间的差异

2、。（3）重点掌握顺序表和链表上各种基本运算的实现。（4）综合运用线性表这种数据结构解决一些复杂的实际问题。学习重点：（1）线性表的逻辑结构及两种不同的存储结构（2）顺序表的表示和实现（3）链表的表示和实现3．栈和队列（1）理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构。（2）重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。（3）重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件。（4）灵活运用栈和队列这两种数据结构解决一些综合应用问题。学习重点：（1）栈的逻辑结构、存储结构

3、及其相关算法（2）队列的逻辑结构、存储结构及其相关算法4．串、数组、广义表（1）掌握串的特点、表示和实现（2）熟悉串的类型和作用（3）了解数组的表示和实现（4）掌握稀疏矩阵（5）了解广义表的概念和相关操作学习重点：（1）串的逻辑结构、存储结构及其相关算法（2）串的操作应用（3）数组的表示5．树型结构（1）掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。（2）掌握树的表示,包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。（3）掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的

4、定义。（4）掌握二叉树的性质。（5）重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。（6）重点掌握二叉树的基本运算和各种遍历算法的实现。（7）掌握线索二叉树的概念和相关算法的实现。（8）掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。（9）灵活运用二叉树这种数据结构解决一些综合应用问题。学习重点：（1）二叉树的存储结构（2）二叉树的遍历（3）Huffman树6．图型结构（1）掌握图的相关概念,包括图、有向图、无向图、完全图、子图、连通图、度、入度、出度、简单回路和环等定义。（2）重点掌握图的各种存储结构,包括邻接

5、矩阵和邻接表等。（3）重点掌握图的基本运算,包括创建图、输出图、深度优先遍历、广度优先遍历算法等。（4）掌握图的其他运算,包括最小生成树、最短路径、拓扑排序等算法。（5）灵活运用图这种数据结构解决一些综合应用问题。学习重点：（1）图的存储结构（2）图的遍历算法7．查找（1）理解查找的基本概念，包括静态查找表和动态查找表、内查找和外查找之间的差异。（2）重点掌握线性表上各种查找算法，包括顺序查找、二分查找和分块查找的基本思路、算法实现和查找效率等。（3）掌握二叉排序树的查找算法，了解各种树表包括AVL树和B-树的基本思路、算法实现和查找效率等

6、。（4）掌握哈希表查找技术以及哈希表与其他表的本质区别（5）灵活运用各种查找算法解决一些综合应用问题学习重点：掌握顺序查找、折半查找、二叉排序树上查找以及哈希表上查找的基本思想和算法实现8．排序（1）理解排序的基本概念，包括排序的稳定性、内排序和外排序之间的差异（2）重点掌握插入排序算法，包括直接插入排序和希尔排序的过程和算法实现。（3）重点掌握交换排序算法，包括冒泡排序和快速排序的过程和算法实现。（4）重点掌握选择排序算法，包括直接选择排序和堆排序的过程和算法实现。（5）掌握归并排序的过程和算法实现（6）了解基数排序的过程和算法实现（7）

7、灵活运用各种排序算法解决一些综合应用问题学习重点：（1）各种简单排序、快速排序、堆排序、归并排序的排序方法、算法描述和性能分析（2）各种排序方法的比较