新闻动态
您现在的位置: 首页>>新闻动态>>通知公告>>正文

数据结构课程考试大纲

2018年09月14日 08:59  点击:[]

 

数据结构课程考试大纲

课程名称:数据结构(data structures

适用学科:计算机应用

一、课程的性质、类型、目的和任务

数据结构课程是计算机科学与技术专业必修的一门重要的专业基础课。在计算机软件的各个领域中均会使用到数据结构的有关知识。当用计算机来解决实际问题时,就要涉及到数据的表示及数据的处理,因此,数据结构课程在计算机相关专业中具有举足轻重的作用。

通过本课程的学习,使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,培养基本的、良好的程序设计技能,编制高效可靠的程序,为学习操作系统、编译原理和数据库等课程奠定基础。

在数据结构的教学中,要求学生掌握常用数据结构的基本概念及其不同的实现方法;同时,通过系统学习,能够在不同存储结构上实现不同的运算,并对算法设计的方式和技巧有所体会。使学生较全面的掌握各种常用的数据结构,能够合理地组织数据、有效地存储和处理数据,正确地设计算法以及对算法的分析和评价。教学过程中注重学生分析问题和解决问题能力的培养,注重学生探索精神和创新意识的培养,切实提高学生运用数据结构解决实际问题的能力。

二、本课程与其它课程的联系与分工

学习本课程必须具备高级语言程序设计(如C语言)的基础知识与基本技能,还应具备面向对象程序设计的基本方法,以及离散数学的基础知识。它的后续课程为操作系统、编译原理、数据库原理等。

三、考核内容及基本要求(△表示自学内容,不在考试范围内)

[1]表示“了解”;[2]表示“理解”或“熟悉”;[3]表示“掌握”;△表示自学内容;○表示略讲内容;

第一章 概论

第一节 什么是数据结构

数学模型○,线性表○,树○,图○

第二节 基本概念和术语

数据:Data[2],数据元素:Data Element[2],数据项:Data Item[2],数据对象:Data Object[2],数据结构:Data Structure[3],抽象数据类型 Abstract Data Type------ADT[2]

第三节 抽象数据类型的表示与实现

各种预定义和约定[2],抽象数据类型示例[1]

第四节 算法和算法分析

算法的概念[2],算法的特征[1],算法设计的要求[1],算法的时间效率与空间效率分析[3]

第五节 数据结构的发展简史及它在计算机科学中的地位

数据结构的发展过程△,数据结构在计算机知识体系内的作用[1]

重点:对数据结构知识体系的理解

难点:算法时空效率分析

第二章 线性表

第一节 线性表的类型定义

线性表的逻辑结构[3],线性表的ADT[2]

第二节 线性表的顺序表示和实现

顺序表示[3],线性表的动态分配实现[3]

第三节 线性表的链式表示和实现

单链表[3],静态链表,循环链表[2],双向链表

第四节 一元多项式的表示及相加

一元多项式的表示,一元多项式的抽象数据类型定义,一元多项式抽象数据类型的实现

重点:是对线性表的理解

难点:线性链表的各种操作的实现

教学手段:多媒体教学

教学方法:讲授法+讨论法

第三章 栈和队列

第一节

栈的定义[3],栈的顺序表示和实现[3],多个栈共享空间,栈的链式表示与实现

第二节 栈的应用

数制转换[1],括号匹配,行编辑,迷宫求解,表达式求值,表达式的后缀表示

第三节 栈与递归的实现

递归基本思想[2],递归与栈的关系[2],汉诺塔问题[1]

第四节 队列

队列定义[3],循环队列实现[3],链式队列实现[3]

重点:对栈和队列的理解,基本操作的实现

难点:栈与递归的关系

第四章

第一节 串类型的定义

串的概念[1],串的抽象数据类型的定义[1]

第二节 串的表示和实现

定长顺序存储[2],堆分配存储[2],块链存储

第三节 模式匹配算法

定长串上实现的模式匹配算法及其时间性能分析[1],先进模式匹配算法△

重点:对串的理解的串操作的应用

难点:模式匹配算法

第五章 数组和广义表

第一节 数组的定义

数组的ADT[1]

第二节 数组的顺序表示和实现

顺序表示[2],地址计算[3]

第三节 矩阵的压缩存储

三角矩阵[2],对称矩阵,对角矩阵,稀疏矩阵的三元组表示与实现,稀疏矩阵的十字链表表示法

第四节 广义表

广义表的表示,广义表特性,抽象数据类型广义表定义,广义表的存储结构

重点:矩阵的压缩存储

难点:矩阵的压缩存储

第六章 树和二叉树

第一节 树的定义和基本术语

树的定义[2],相关术语[3],树的ADT

第二节 二叉树Binary Tree

二叉树的定义[2],二叉树的性质[3],二叉树的存储结构[3]

第三节 遍历二叉树和线索二叉树

遍历二叉树Traversing Binary Tree[3],线索二叉树[1]

第四节 树和森林

树的存储结构[2],森林和树的转换[3],树和森林的遍历[3]

第五节 哈夫曼树及其应用

最优树[3]WPL[3],哈夫曼树构造[3],哈夫曼算法[3],哈夫曼编码[2]

重点:二叉树的遍历,夫曼树

难点:夫曼树,线索二叉树

第七章

第一节 图的定义

有向图和无向图[3],完全图[3],子图[3],度[3],路径[3],连通图[3],图的ADT[1]

第二节 图的存储结构

数组表示法[3],邻接表[3],十字链表△,邻接多重表△

第三节 图的遍历Traversing Graph

深度优先搜索 Depth-First-Search DFS[3],广度优先搜索 Breadth-First-Search BFS[3]

第四节 图的连通性问题

无向图的连通分量和生成树[3],最小生成树Mininum Cost Spanning Tree[3]

第五节 有向无环图及其应用

DAG[3],拓扑排序[3],关键路径[3]

第六节 最短路径

从某个源点到其余各个顶点的最短路径[3],每一对顶点之间的最短路径[2]

重点:图的遍历,图存储方法,最小生成树,拓扑排序,关键路径

难点:图的生成树算法,关键路径,最短路径

第九章 查找

第一节 静态查找表

查找算法概述[2],静态查找表的ADT○,顺序表的查找[3],有序表的查找[3],分块查找(索引顺序查找)△

第二节 动态查找表

动态查找表ADT○,二叉排序树Binary Sort Tree[3],平衡二叉树Balanced Binary Tree[1]B-树和B+树○

第三节 哈希表

哈希思想[2],哈希函数的构造方法[3],处理冲突的方法[3],哈希表的查找[3]

重点:顺序查找,二叉排序树,哈希表

难点:平衡二叉树,B-树查找

第十章 内部排序

第一节 概述

排序的定义[2],排序方法的稳定性[2],排序方法分类[2],待排序记录的存储方式[1]

第二节 插入排序

直接插入排序[3],折半插入排序○,表插入排序△,希尔排序(缩小增量排序)[1]

第三节 快速排序

起泡排序Bubble Sort[3],快速排序Quick Sort[3]

第四节 选择排序

简单选择排序[3],树形选择排序○,堆排序Heap Sort[2]

第五节 归并排序

归并排序基本思想[3]2路归并排序算法[2]

第六节 基数排序

多关键字排序[1],链式基数排序[3]

第七节 各种内部排序方法的比较讨论

排序算法的时间、空间效率分析[3],稳定性、适用性分析[3]

重点:直接插入法排序,起泡法排序,快速排序,排序算法比较

难点:希尔排序,快速排序,堆排序,归并排序,基数排序

第十一章 外部排序

第一节 外存信息的存取

磁带△,磁盘△

第二节 外部排序的方法

初始归并段的生成△,外排时间效率分析○,基本外排算法简介○

重点:外排时间效率分析

难点:外排时间效率分析

第十二章 文件

第一节 有关文件的基本概念

文件○,记录△,ISAM文件△,VSAM文件△,评价文件组织效率的标准○

第二节 顺序文件

顺序文件相关术语○,顺序文件组织形式○

第三节 索引文件

索引文件相关术语○,索引文件组织形式○

重点:顺序、索引文件的结构特点

难点:顺序、索引文件的结构特点

四、选用教材及参考书(资料)

教材:

《数据结构》(C语言版). 严蔚敏、吴伟民编著. 清华大学出版社,1997年版

参考书目:

1.《数据结构题集》(C语言版). 严蔚敏、吴伟民编著. 清华大学出版社,1997年版

2.《数据结构习题与解析》. 李春堡等编. 清华大学出版社,2000年版

3.《数据结构教程》. 蔡子经、施伯乐等编. 复旦大学出版社,1994年版

4.《数据结构与算法设计》. 王晓东等编. 电子工业出版社,2002年版

 

关闭