数据结构考试大纲.docx

《数据结构考试大纲.docx》由会员分享，可在线阅读，更多相关《数据结构考试大纲.docx（13页珍藏版）》请在第一文库网上搜索。

1、一、本课程的地位、作用和任务数据结构是计算机专业(包括软件、应用和科学教育等专业)的主干课、专业基础课，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过教学要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，并为后续课程的学习打下良好的理论基础和实践基础。二、课程内容及学时分配第一章绪论(1)数据、数据对象、数据结构、数据类型(2)算法及算法描述(3)算法的时间复杂度和空间复杂度本章学时数：2,本章习题数：4

2、第二章线性表2.1 线性表的逻辑结构线性表的形式定义及基本操作2.2 线性表的顺序存储结构(1)线性表的顺序存储结构描述2.3 线性表的链式存储结构(1)线性表的单链表表示及其实现方法(2)循环链表(a)表示(b)运算(3)双向链表(a)类型描述(b)运算实现2.4 元多项式的表示及相加(1)一元多项式的线性表表示(2)一元多项式基本操作的实现本章学时数：6,本章习题数：10第三章栈和队列3.1 栈(1)抽象数据类型栈的定义(2)栈的顺序存储和链接存储(3)栈基本操作的实现3.2 表达式求值栈的应用-表达式求值(a)算法描述(b)操作过程3.3 栈与递归过程(1)递归算法执行过程中栈的状态变化

3、过程(2)递归过程转化成非递归过程的变换方法3.4 队列(1)抽象数据类型队列的定义(2)队列的链式存储结构本章学时数：6,本章习题数：10第四章串4.1 串及其操作（1）串的概念（2）串的基本操作4.2 串的存储结构（1）串的静态存储结构（a）非紧缩格式（b）紧缩格式（2）串的动态存储结构（a）串的链表存储方式（b）存储密度4.3 串基本操作的实现（1）静态结构存储串时的操作（a）联接函数（b）求子串函数（C）定位函数（2）模式匹配的改进算法（3）堆结构存储串时的操作（a）赋值操作（b）联接运算（C）求子串操作4.4 串操作应用举例（自学）串的应用及实现本章学时数；4,本章习题数：6第五章数

4、组和广义表5.1 数组的定义和运算（1）二维数组、n维数组的逻辑结构5.2 数组的顺序存储结构（1）以行序为主序的存储结构（2）以列序为主序的存储结构5.3 矩阵的压缩存储（1）特殊矩阵和稀疏矩阵（a）下（上）三角矩阵（b）对角矩阵（C）稀疏矩阵（2）三元组表（a）形式描述（b）转置运算（C）相乘运算（3）十字链表（a）形式描述（b）加法运算5.4 广义表的定义广义表的定义和特点5.5 广义表的存储结构广义表的链式存储结构表示5.6 m元多项式的表示（自学）三元多项式的广义表表示本章学时数：4,本章习题数：8第六章树和二叉树6.1 树的结构的定义和基本操作（1）树的定义及基本术语（2）树的基本

5、操作6.2 二叉树（1）二叉树的定义和操作（3）二叉树的存储结构（a）顺序存储结构（2）链式存储结构6.3 遍历二叉树和线索二叉树（1）遍历二叉树的操作定义与算法描述（a）先序遍历（b）中序遍历（C）后序遍历（2）线索二叉树定义及存储结构（a）线索链表（b）二叉树的线索化（3）线索二叉树的基本操作6.4 树和森林（1）树的存储结构（a）双亲表示法（b）孩子表示法（C）孩子兄弟表示法（2）森林与二叉树的转换（a）森林转换成二叉树（b）二叉树转换成森林（3）树的遍历（a）先序遍历（b）中序遍历（C）后序遍历6.5 树与等价问题（1）等价问题描述及其抽象数据类型（2）基本操作实现6.6 哈夫曼树及应

6、用（1）哈夫曼树定义及哈夫曼算法描述（2）哈夫曼编码（a）前缀编码概念（b）求哈夫曼编码的算法本章学时数：12,本章习题数：15第七章图7.1 图的定义和术语(2)图的基本操作7.2 图的存储结构(1)数组表示法(a)形式描述(b)邻接矩阵(2)邻接表(a)邻接表(b)逆邻接表(3)十字链表(a)存储结构(b)十字链表建立算法(4)邻接多重表7.3 图的遍历(1)深度优先搜索及其算法(2)广度优先搜索及其算法7.4 图的连通性问题(1)无向图的连通分量和生成树(2)有向图的强连通分量(3)最小生成树定义及算法(a)最小生成树概念(b)Prim算法(C)KruskaI算法7.5 有向无环图及应用

7、(1)拓扑排序(2)AOV-网及关键路径7.6 最短路径(1)单源最短路径与DijkStra算法(2)每对顶点之间的最短路径与F1oyd算法本章学时数：10,本章习题数：10第八章动态存储管理8.1 概述动态存储问题概述8.2 可利用空间表及分配方法(1)可利用空间表结构形式(2)三种分配策略(a)首次拟合法(b)最佳拟合法(C)最差拟合法8.3 边界标识法(1)可利用空间表的结构(2)分配算法(3)回收算法8.4 伙伴系统(1)可利用空间表的结构(2)分配算法(3)回收算法8.5 无用单元收集(1)无用单元收集基本步骤(2)三种标志算法8.6 存储紧缩存储紧缩基本步骤本章学时数：4,本章习题

8、数：5第九章查找9.1 静态查找表(1)顺序表的查找(2)有序表的查找(3)静态树表的查找(4)索引顺序表的查找9.2 动态查找表(1)二叉排序树和平衡二叉树(a)二叉排序树查找算法(b)二叉排序树插入和删除算法(C)二叉排序树查找分析(d)平衡二叉树(2)B-树和B+树(a)B-树的查找、插入和删除算法(b)B+树的查找、插入和删除算法(3)键树(a)双链树(b)Trie树9.3 哈希表(1)哈希表定义及哈希函数的构造方法(2)处理冲突方法(a)开放定址法(b)再哈希法(C)链地址法(d)建公共溢出区法(3)哈希表的查找及其分析本章学时数：8,本章习题数：10第十章内部排序10.1概述排序基

9、本概念10.2插入排序(1)直接插入排序(2)折半插入排序、2-路插入排序和表插入排序(3)希尔排序103快速排序(1)快速排序算法(2)快速排序算法性能(1)简单选择排序(2)树形选择排序(3)堆排序(a)堆定义(b)筛选算法(C)堆排序算法(d)时间复杂度分析10.5 归并排序归并排序算法及性能106基数排序(1)多关键字排序(a)MSD法(b)1SD法(2)链式基数排序10.7 各种内部排序方法的比较讨论(课堂讨论)本章学时数：10,本章习题数：12第十一章外部排序11.1 外存信息的存取(简讲)(1)磁带信息的存取(2)磁盘信息的存取11.2 外部排序的方法(1)外部排序的归并过程(2

10、)外部排序所需时间11.3 多路平衡归并的实现(1)败者树概念(2)k-路归并算法描述11.4 4置换-选择排序(1)置换-选择排序排序过程(2)置换-选择排序算法描述11.5缓冲区的并行操作处理(简讲)（1）最佳归并树概念（2）附加虚段数目的判定117磁带归并排序（1）平衡归并（2）多步归并本章学时数：4,本章习题数：4第十二章文件12.1 有关文件的基本概念（1）文件及其类别（2）记录的逻辑结构和物理结构（3）文件的操作（4）文件的物理结构12.2 顺序文件（1）顺序文件概念及特点（2）批处理算法12.3 索引文件概念（1）静态索弓I（2）动态索引12.4 ISAM文件和VSAM文件（I）

11、ISAM文件（2）VSAM文件12.5 直接存取文件（散列文件）直接存取文件组织方法12.6 多关键字文件（1）多重表文件（2）倒排文件本章学时数：2,本章习题数：3三、先修课程离散数学，PASCA1语言（或C语言）四、教材及主要参考书1、严蔚敏等，数据结构（第二版），清华大学出版社2、管纪文等，数据结构，高等教育出版社3、朱望规，数据结构，西安交大出版社4、E.HorowitzandSahni,Foudamenta1sofDataStructures,byPitmenPub1ishing1imited.5、D.E.Knuth,TheArtofComputerProgramming,byAddison-Wes1eyPub1ishingCompany5Inc.五、实验实验1线性表（4学时）要求：熟悉线性表的基本运算以及在两种存储结构上的实现实验2栈、队列与递归算法设计（4学时）要求：进一步了解栈、队列的特点，完成较复杂的递归算法设计实验3串（4学时）要求：熟悉一般文字处理软件的设计方法实验4树、图及其应用（4学时）要求：将树和图结构应用于解决实际问题实验5文件、查找与排序（8学时）要求：设计一个实用系统，涉及文件的组织、查询和排序等操作