《数据结构》考试大纲

考试大纲

一、课程的性质和地位

         数据结构是计算机科学技术专业考试计划中一门专业基础课,在计算机软件的各个领域中均会使用到数据结构的有关知识:本课程的目的和任务是使学生较全面地掌握各种常用的数据结构,为学习后续软件课程提供必要的基础,提高运用数据结构解决实际问题的能力。

二、理论教学部分的考核目标

  • 1.从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构。
  • 2.掌握在各种常用的数据结构上实现的排序和查找运算。
  • 3.对算法的时间和空间复杂性有—定的分析能力。
  • 4.针对简单的应用问题,应能选择合适的数据结构及设计有效的算法解决之。

第一章 概论

一、一般学习目的与要求

  • 1. 一般了解:本章介绍的各种基本概念和术语以及学习数据结构的意义
  • 2. 一般掌握:算法描述和分析的方法
  • 3. 熟练掌握:数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系;算法复杂度的分析方法

二、考核知识点

  • 1.1 基本概念和术语
  • 1.2 学习数据结构的意义
  • 1.3 算法的描述和分析

三、考核要求

  • 1、识记:数据、数据元素、数据项、数据结构等基本概念;数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系;数据结构的两大类逻辑结构和四种常用的存储表示方法;数据结构在各种软件系统中所起的作用;选择合适的数据结构是解决应用问题的关键步骤。
  • 2、领会:算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念;算法的时间复杂度不仅仅依赖于问题的规模,也取决于输入实例的初始状态;算法描述和算法分析的方法,对于一般算法能分析出时间复杂度。

第二章 线性表

一、一般学习目的与要求

  • 1. 一般掌握:线性表的逻辑结构和各种存储表示方法,以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。
  • 2. 熟练掌握:顺序表和单链表上实现的各种基本算法及相关的时间性能分析。

二、考核知识点

  • 2.1 线性表逻辑结构
  • 2.2 线性表的顺序存储及运算实现
  • 2.3 线性表的链式存储和实现
  • 2.4 顺序表和链表的比较

三、考核要求

  • 1、识记:线性表的逻辑结构特征;线性表上定义的基本运算,并能利用基本运算构造出较复杂的运算。
  • 2、领会:顺序表和链表的主要优缺点;针对线性表上所需要执行的主要操作,知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。
  • 3、综合应用:顺序表的含义及特点,即顺序表如何反映线性表中元素之间的逻辑关系;顺序表上的插入删除操作及其平均时间性能分析;利用顺序表设计算法解决简单的应用问题;链表如何表示线性表中元素之间的逻辑关系;链表中头指针和头结点的使用;单链表、双链表、循环链表链接方式上的区别;单链表上实现的建表、查找、插入和删除等基本算法,并分析其时间复杂度;循环链表上尾指针取代头指针的作用,以及单循环链表上的算法与单链表上相应算法的异同点;双链表的定义及其相关的算法;利用链表设计算法解决简单的应用问题。

第三章 栈和队列

一、一般学习目的与要求

  • 1. 一般掌握:栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。
  • 2. 熟练掌握:在掌握栈和队列的特点的基础上,知道在什么样的情况下能够使用栈或队列。

二、考核知识点

  • 3.1 栈
  • 3.2 队列
  • 3.3 栈和队列的应用

三、考核要求

1、领会:栈和队列的特点,什么样的情况下能够使用栈或队列 2、综合应用:栈的逻辑结构特点,栈与线性表的异同;顺序栈和链栈上实现的进栈、退栈等基本算法;栈的“上溢”和“下溢”的概念及其判别条件;利用栈设计算法解决简单的应用问题;队列的逻辑结构特点,队列与线性表的异同;顺序队列(主要是循环队列)和链队列上实现的入队、出队等基本算法;队列的“上溢”和“下溢”的概念及其判别条件;使用数组实现的循环队列取代普通的顺序队列的原因;循环队列中对边界条件的处理方法;利用队列设计算法解决简单的应用问题。

第四章 串

一、一般学习目的与要求

  • 1. 一般掌握:串的逻辑结构、存储结构及其串上的基本运算
  • 2. 熟练掌握:串上实现的模式匹配算法

二、考核知识点

  • 4.1 串及其运算
  • 4.2 串的存储结构

三、考核要求

  • 1、领会:串的有关概念及基本运算;串与线性表的关系。
  • 2、简单应用:串的两种存储表示;串上实现的模式匹配算法及其时间性能分析;使用C语言提供的串操作函数构造与串相关的算法解决简单应用问题。

第五章 数组和广义表

一、一般学习目的与要求

  • 1. 一般掌握:多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其表头和表尾的运算
  • 2. 熟练掌握:稀疏矩阵的压缩存储表示下实现的算法。

二、考核知识点

  • 5.1 多维数组
  • 5.2 矩阵的压缩存储
  • 5.3 广义表的概念

三、考核要求

1、领会:多维数组的逻辑结构特征;多维数组的顺序存储结构及地址计算方式;数组是一种随机存取结构的原因;特殊矩阵和疏稀矩阵的概念;特殊矩阵和压缩存储时的下标变换方法;稀疏矩阵的三元组表表示方法及有关算法;广义表的有关概念及其与线性表的关系;广义表的括号表示和图形表示之间的转换;求给定的非空广义表的表头和表尾运算。

第六章 树

一、一般学习目的与要求

1. 一般掌握:二叉树的定义、性质、存储结构、遍历、线索化,树的定义、存储结构、遍历、树和森林与二叉树的转换,哈夫曼树及哈夫曼编码等内容。 2. 熟练掌握:二叉树的遍历算法及其有关应用

二、考核知识点

  • 6.1 树的概念
  • 6.2 二叉树
  • 6.3 二叉树的遍历
  • 6.4 线索二叉树
  • 6.5 树和森林
  • 6.6 哈夫曼树及其应用

三、考核要求

1、领会:树的逻辑结构特征;树的不同表示方法;树的常用术语及含义;二叉树线索化的目的及实质;在中序线索树中查找给定结点的中序前趋和中序后继的方法; 查找给定结点的前序前趋和后序后继并非有效的原因;树和森林与二叉树之间的转换方法;树的各种存储结构及其特点;树的两种遍历方法。 2、简单应用:二叉树的递归定义及树与二叉树的差别;二叉树的性质,了解相应的证明方法;二叉树的两种存储方法、特点及适用范围;最优二叉树和最优前缀码的概念及特点;哈夫曼算法的思想;根据给定的叶结点及其权值构造出相应的最优二叉树;根据最优二叉树构造对应的哈夫曼编码。 3、综合应用:二叉树的三种遍历算法,理解其执行过程;确定三种遍历所得到的相应的结点访问序列;以遍历算法为基础,设计有关算法解决简单的应用问题。

第七章 图

一、一般学习目的与要求

1. 一般掌握:图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法 2. 熟练掌握:在图的两种存储结构上实现的遍历算法;求最小生成树;求最短路径以及拓扑排序

二、考核知识点

  • 7.1图的概念
  • 7.2图的存储结构
  • 7.3图的遍历
  • 7.4生成树和最小生成树
  • 7.5最短路径
  • 7.6拓扑排序

三、考核要求

1、领会:图的逻辑结构特征;图的常用术语及含义;生成树和最小生成树的概念;对遍历给定的图,画出深度优先和广度优先生成树或生成森林;Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点;要求对给定的连通图,根据Prim和Kruskal算法构造出最小生成树;最短路径的含义;求单源最短路径的Dijkstra算法的基本思想和时间性能;对于给定的有向图,根据Dijkstra算法画出求单源最短路径的过程示意图;拓扑排序的基本思想和步骤;拓扑排序不成功的原因;对给定的有向图,若拓扑序列存在,则要求写出一个或多个拓扑序列。 2、简单应用:邻接矩阵和邻接表这两种存储结构的特点及适用范围;根据应用问题的特点和要求选择合适的存储结构;连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析;确定两种遍历所得到的顶点访问序列;图的两种遍历与树的遍历之间的关系;两种遍历所使用的辅助数据结构(栈或队列)在遍历过程中所起的作用;利用图的两种遍历设计算法解决简单的应用问题。

第八章 排序

一、一般学习目的与要求

1. 一般掌握:五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。 2. 熟练掌握:快速排序、堆排序、归并排序和基数排序的基本思想及排序过程

二、考核知识点

  • 8.1 基本概念
  • 8.2 插入排序
  • 8.3 交换排序
  • 8.4 选择排序
  • 8.5 归并排序
  • 8.6 分配排序
  • 8.7 各种排序方法的比较和选择

三、考核要求

  • 1、识记:排序在数据处理中的重要性;排序方法的“稳定”性含义;排序方法的分类及算法好坏的评判标准。
  • 2、领会:归并排序的基本思想和算法实现,以及时间性能分析;针对给定的输入实例,能写出归并排序的排序过程;
  • 3、简单应用:堆、小根堆、大根堆、堆顶等有关概念和定义;堆性质及堆与完全二叉树的关系;直接选择排序和堆排序的基本思想和算法实现,以及时间性能分析;针对给定的输入实例,写出堆排序的排序过程;通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点;根据实际问题的特点和要求选择合适的排序方法。
  • 4、综合应用:直接插入排序的基本思想和算法实现,以及在最好、最坏和平均情况下的时间性能分析;直接插入排序中哨兵的作用;针对给定的输入实例,要能写出直接插人排序的排序过程;冒泡排序的基本思想;快速排序的基本思想和算法实现,以及在最坏和平均情况下的时间性能分析,了解算法的稳定性;基准元素(划分元)对划分是否平衡的影响;针对给定的输入实例,能写出快速排序的排序过程。

第九章 查找

一、一般学习目的与要求

1. 一般掌握:线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析 2. 熟练掌握:顺序查找、二分查找,二叉查找树上查找以及散列表上查找的基本思想和算法实现

二、考核知识点

  • 9.1 基本概念
  • 9.2 线性表的查找
  • 9.3 树的查找
  • 9.4 散列技术

三、考核要求

1、识记:查找在数据处理中的重要性;查找算法效率的评判标准; 2、简单应用:顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析;顺序查找中哨兵的作用;二分查找对存储结构及关键字的要求;通过比较线性表上三种查找方法的优缺点,能根据实际问题的要求和特点,选择出合适的查找方法; 二叉查找树和B—树的定义和特点以及用途;二叉查找树的插入、删除、建树和查找算法及时间性能;建立一棵二叉查找树的过程实质上是对输入实例的排序过程,输入实例对所建立的二叉查找树形态的影响;B—树的插入、删除及查找方法的基本思想; B—树的查找效率;散列表、散列函数、散列地址和装填因子等有关概念;散列函数的选取原则及产生冲突的原因;几种常用的散列函数构造方法;两类解决冲突的方法及其优缺点;产生“堆积”现象的原因;采用线性探测法和拉链法解决冲突时,散列表的建表方法、查找过程以及算法实现和时间分析;散列表和其它表的本质区别。

第十章 文件

一、一般学习目的与要求

1. 一般了解:存储在外存上的数据结构(即文件)的有关概念、各种文件的特点、组织方法及查询和更新操作

二、考核知识点

  • 10.1 文件的基本概念
  • 10.2 顺序文件
  • 10.3 索引文件
  • 10.4 索引顺序文件
  • 10.5 散列文件
  • 10.6 多关键字文件

三、考核要求

1、识记:文件的有关概念;文件的逻辑结构及其操作;文件的存储结构(组织方式)分类;评价文件组织效率的标准;顺序文件的特点及外存种类的适应性;顺序文件上各种查找方法的基本思想及对外存种类的要求;索引文件的组织方式和特点;索引文件的查询和更新操作的基本思想;索引顺序文件是最常用的一种文件组织方式的原因;两种最常用的索引顺序文件(1SAM文件和VSAM文件)的组织方式和特点;在ISAM文件和VSAM文件上查询和更新操作的基本思想;散列文件的组织方式和特点;散列文件的查询和更新操作的基本思想;多关键字文件与其它文件的区别;多重表文件和倒排文件的组织方式和特点;多重表文件和倒排文件上查询及更新操作的基本思想。

三、考试题型

试题的主要题型有:填空、单项选择、简答、应用和算法设计等五种。

四、考试方式

考试方式为闭卷、笔试。考试时间为120分钟。

五、成绩评定

总成绩的计算办法:平时成绩占30%,期末考试成绩占70%