公共课 - 计算机 | 兰州工业学院2018年数据结构考试大纲

一、考试内容及要求

数据结构是计算机专业的专业基础课程之一。本课程主要讲述如何组织各种数据在计算机中的存储与运用。通过学习，要求学生比较系统地理解数据结构的基本概念和基本理论，掌握各种数据结构特点、存储表示和常用算法，初步具备综合运用所学知识分析问题和解决问题的能力。

（一）数据结构和算法

1.了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。

2．掌握算法以及算法分析。

（二）线性表

1.理解线性表的概念、定义、逻辑结构和存储结构；

2.掌握线性表的顺序存储结构及各种基本运算；

3.掌握单链表的存储结构及各种基本运算；

4.理解循环链表的存储结构及运算。

（三）栈和队列

1.掌握栈与队列的定义、基本操作和实现算法；

2.理解链式存储结构实现的链队列；

3.理解顺序存储结构实现的循环队列。

（四）串

1.理解串的定义、逻辑结构及基本操作；

2.理解串的存储结构；

3.了解模式匹配的定义及基本算法。

（五）数组和广义表

1.掌握数组的顺序存储结构；

2.理解稀疏数组的概念和压缩存储的方法；

3.理解稀疏矩阵的三元组表示法及十字链表表示法；

4.了解广义表的基本概念。

（六）树和二叉树

1.理解树的基本概念及其存储结构；

2.掌握二叉树的定义以及各种存储结构；

3.掌握二叉树的性质及遍历算法；

4.理解树与二叉树的相互转换、森林与二叉树的相互转换，树的遍历算法；

5.掌握哈夫曼树的概念、存储结构及其应用。

（七）图

1.理解图的定义和术语；

2.掌握图的邻接矩阵和邻接表的存储结构；

3.掌握图的深度优先搜索和广度优先搜索算法；

4.理解图的连通性，掌握生成树及最小生成树的概念；

5.掌握构造无向图的最小生成树的算法。

（八）查找

1.理解顺序查找算法、折半查找算法；

2.了解平衡二叉树的概念；

3.理解二叉排序树的概念；

4.理解哈希表的含义。

（九）内部排序

1.掌握直接插入排序算法、希尔排序算法；

2.掌握冒泡排序算法、快速排序算法；

3.掌握简单选择排序算法；

4.了解归并排序、堆排序的思想。

二、考试形式及时间

1.答题方式为闭卷笔试。

2.答卷时间为60分钟，满分100分。

三、试题类型

1. 填空题   2. 选择题   3. 判断题   4. 简答题   5. 计算或综合题

四、参考书目

《数据结构》，严蔚敏、吴伟民编著，清华大学出版社。