浙江海洋大学

数据结构

一、考查目标

数据结构是计算机专业的一门综合性基础课程，是学科的核心课之一。它是在离散数学、程序设计后，以C语言为工具研究数据的逻辑结构、存储结构及其数据抽象的方法。是编译原理、操作系统、数据库和面向对象程序设计等课程的重要基础。课程目标是使学生在学习过程中逐步了解和掌握数据抽象的方法和意义，并根据数据对象的特征，选择合适的存储结构以及相应的算法。

二、试卷结构

1、题型结构

选择题20分(单选，每题2分);简答题36分(每题6分);算法设计题44分(可出3-4题，题目分数根据题目难度分配)。

2、内容结构

线性表(15%)、栈和队列(5%)、串(5%)、数组与广义表(5%)、树和二叉树(20%)、图(20%)、查找(15%)、内部排序(15%)。

三、考试内容

1、线性表

1)理解并掌握线性表的逻辑结构和顺序存储结构;

2)掌握线性链表，循环链表，双向链表的链式存储结构及实现算法;

2、栈和队列

1)熟练掌握栈的定义、基本操作和实现算法;

2)掌握应用栈来实现表达式求值;

3)熟练掌握队列的定义、基本操作和实现算法;

4)熟练掌握链式存储结构实现的链队列;

3、串

1)熟练掌握串的定义、逻辑结构及基本操作;

2)掌握串的存储结构;

3)掌握模式匹配的定义及基本算法。

4、数组和广义表

1)掌握数组的定义和运算;

2)熟练掌握数组的顺序存储结构及特殊矩阵的压缩存储;

3)熟练掌握十字链表表示的稀疏矩阵;

4)理解并掌握广义表的定义、存储结构。

5、树和二叉树

1)熟练掌握树的结构定义及基本操作;

2)熟练掌握二叉树的结构定义及基本操作;

3)熟练掌握二叉树的性质及存储结构;

4)能熟练应用前序，中序，后序遍历二叉树;

5)掌握哈夫曼树及其应用。

6、图

1)熟练掌握图的定义和术语;

2)熟练掌握图的邻接矩阵表示法，邻接表表示法;

3)熟练掌握图的深度优先搜索和广度优先搜索算法;

4)理解生成树，最小生成树的概念;

5)熟练掌握构造无向图的最小生成树的算法;

6)熟练掌握拓扑排序和构造关键路径的算法;

7)能快速求出从某个源点到其余各顶点的最短路径。

7、查找

1)熟练掌握顺序查找，折半查找，分块查找的算法;

2)掌握二叉排序树，平衡二叉树;

3)了解哈希表的定义，哈希函数的构造方法及处理冲突的方法;

8、内部排序

1)熟练掌握直接插入排序,希尔排序及算法;

2)熟练掌握冒泡排序、快速排序及算法;

3)熟练掌握简单选择排序及算法;

4)了解二路归并排序的算法。

四、推荐书目：

1、严蔚敏，吴伟民 著，《数据结构(C语言版)》， 清华大学出版社，2018.