《数据结构》考试大纲

一、考试内容及要求

（一）了解

1．数据、数据元素、数据项、抽象数据类型等概念。

2．数据结构的基本概念；数据的逻辑结构及物理结构；算法的定义及特点。

3．线性表的定义及特点；在线性表上常进行的基本操作。

4．头指针、头结点及首元结点的概念及它们的区别；设置头结点的好处。

5．栈和队列的定义、特点、表示方法和实现；入栈和出栈序列的对应关系；入队和出队序列的对应关系。

6．串的定义及其相关概念。

7．数组的定义、运算和存储；特殊矩阵和稀疏矩阵的压缩存储；广义表的定义和相关概念。

8．树的定义、基本术语和存储结构；二叉树的定义和性质；二叉树的存储结构及其各种操作的基本原理；树和森林的相关概念；Huffman树和Huffman编码。

9．图的定义和常用术语。

10．查找表、关键字、查找操作、静态查找、动态查找等查找相关概念。

11．排序的定义及相关概念；各种常用内部排序操作的一趟排序的概念。

（二）掌握

1．数据逻辑结构的分类；逻辑结构和物理结构的区别与联系；物理存储结构的分类及不同存储结构的特点。

2．数据结构的二元组表示；算法设计的要求；算法的时间复杂度和空间复杂度分析。

3．线性表的顺序和链式存储结构；两种不同存储结构下常用操作算法的实现及复杂度分析；顺序存储结构和链式存储结构的优缺点。

4．循环链表、双向链表及双向循环链表的基本操作算法实现及这些特殊链表的应用；

5．栈和队列的与线性表的关系；栈和队列的共同点与不同点；栈和队列在顺序存储和链式存储时基本操作的算法实现；栈和队列的应用。

6．串与线性表的联系与区别；串的存储表现形式；串的常用操作及串操作的特点；空串和空格串的区别。串的模式匹配及求子串的基本原理。

7．数组存储的特点和数组操作的特点；一维数组和二维数组中数据元素存储地址的计算；特殊矩阵和稀疏矩阵的压缩存储时，一维存储空间地址下标和其行号列标的对应关系；广义表的嵌套定义；求解非空广义表的表头和表尾；求解广义表的长度和深度。

8．二叉树的特点及性质；二叉树的存储结构及其特点；二叉树遍历的基本原理；树和森林与二叉树的相互转换；树和森林的遍历及与其对应二叉树遍历的关系；构建哈夫曼树的基本原理及哈夫曼编码。

9．图的存储结构及其遍历操作；求最小生成树、关键路径、最短路径的基本方法，拓扑排序的基本原理；最小生成树的构造过程(Prim算法和Kmskal算法)。

10．各种查找方法的基本查找原理；每种查找的适用范围及平均查找长度的分析；各种查找的特点；不同查找方法查找某一特定数据元素时的具体比较次数；静态查找与动态查找的特点；二叉排序树与平衡二叉树的特点；哈希函数的构造方法及冲突解决办法。

11．各种常用内部排序方法基本实现原理；各种内排序算法的基本思想和算法的时间复杂度、空间复杂度分析，不同排序方法的比较。

（三）应用

1．能阅读用类C语言编写的算法。

2．能分析算法所实现的功能、运行结果和时间、空间复杂度。

3．能应用线性表的基本操作算法解决现实生活中的相关问题。

4．能应用栈和队列解决现实生活中的相关问题。

5．能设计算法解决现实生活中字符串处理的问题。

6．能根据实际的特殊矩阵推算其压缩存储一维存储空间地址下标与其元素的行号列标之间的对应关系，能计算对应元素的实际物理地址；能求解实际非空广义表的表头、表尾、长度和深度。

7．能利用树和二叉树设计算法解决现实生活中的相关问题；能针对实际数据进行哈夫曼编码。

8．能应用图的基本操作解决现实生活中的相关问题。

9．能针对实际查找记录，选择合适的查找算法进行数据查找。

10．能针对实际待排序记录，选择合适的排序方法进行数据排序操作，并能分析实际采用的排序算法的时间复杂度和空间复杂度。

11．能综合应用数据结构的相关知识解决实际生活中的问题。

二、考试形式

考试采用闭卷、笔答的考试方式。

满分：150分(单科成绩)。

考试时间：120分钟。

三、试题难易程度分布

较易试题    约占50％

中等试题    约占30％

较难试题    约占20％

四、题型及题型分值分布

判断题                  约占15％

单选题                  约占35％

多选题                  约占10％

算法阅读与算法设计题    约占20％

综合题                  约占20％

五、章节内容占比

第一章  绪论          约占7％

第二章  线性表        约占15％

第三章  栈和队列      约占15％

第四章  串            约占5％

第五章  数组和广义表  约占8％

第六章  树和二叉树    约占20％

第七章  图            约占10％

第八章  查找          约占10％

第九章  内部排序      约占10％