《数据结构导论》考试大纲.docx

《《数据结构导论》考试大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构导论》考试大纲.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构导论考试大纲第一章概论一、学习目的与要求本章集中介绍贯穿和应用于数据结构课程始终的基本概念，概括反映了后续各章的基本 问题，为进入具体内容的学习提供了必要的引导。本章总的要求是：理解数据、数据元素和数据项的概念及其相互关系；理解数据结构的 含义；理解逻辑结构、基本运算和存储结构的概念、意义和分类；理解存储结构与逻辑结构 的关系；理解算法的概念；理解衡量一个算法效率的两个标准：时间复杂度和空间复杂度。二、课程内容（1）基本概念和术语。（2）算法及描述。（3）算法分析。三、考核的知识点与考核要求1 .数据结构、数据、数据元素和数据项的概念识记：数据结构；数据；数据元素；数据项。领会：数据结

2、构的作用；数据、数据元素、数据项三者关系。2 .数据逻辑结构和数据存储结构识记：数据逻辑结构、数据存储结构领会：四类基本逻辑结构的特点；顺序存储结构；链式存储结构；逻辑结构与存储结构 的关系。3 .运算、算法和算法分析识记：运算；基本运算；算法分析：时间复杂度；空间复杂度。领会：运算与数据结构的关系;算法的描述方法；算法的评价因素；时间复:杂度分析方 法；空间复杂度分析方法。简单应用：运用类C语言描述算法：简单算法时间复杂度分析；简单算法的空间复杂度 分析。四、本章重点、难点本章重点：数据结构、数据逻辑结构、数据存储结构以及运算等概念。难点：算法时间复杂度分析。第二章线性表一、学习目的与要求顺

3、序表和单链表分别是简单、基本的顺序存储结构和链式存储结构。顺序表和单链表上 实现基本运算的算法是数据结构中简单和基本的算法。这些内容构成以下各章的重要基础， 因此本章是本课程的重点之一。本章要求：理解线性表的概念；熟练掌握顺序表和链表的组织方法及实现基本运算的算 法；掌握在顺序表和链表上进行算法设计的基本技能；了解顺序表与链表的优缺点。二、课程内容（1）线性表的基本概念。（2）线性表的顺序存储。（3）线性表的链接存储。（4）其他运算在单链表上的实现。（5）其他链表。三、考核的知识点与考核要求1 .线性表概念识记：线性表概念；线性表的基本特征。领会：线性表表长；线性表初始化、求表长、读表元素、定

4、位、插入、删除等基本运算 的功能。2 .线性表的顺序存储结构一顺序表识记：顺序表表示法、特点和类C语言描述。领会：顺序表的容量；顺序表表长；插入、删除和定位运算实现的关键步骤。简单应用：顺序表插入、删除和定位运算的实现算法。综合应用：顺序表上的简单算法；顺序表实现算法的分析。3 .线性表的链式存储结构一单链表识记：结点的结构；单链表的类C语言描述。领会：头指针；头结点；首结点；尾结点；空链表；单链表福入、删除和定位运算的关 键步骤。简单应用：单链表插入、删除和定位等基本运算的实现算法。综合应用：用单链表设计解决应用问题的算法。4 .循环链表和双向循环链表识记：循环链表的结点结构；双向循环链表结

5、点结构；循环链表和双向循环链表类C 语言描述。领会：循环链表插入和删除运算的关键步骤；双向循环链表插入和删除运算的关键步骤。四、本章重点、难点本章重点线性表概念和基本特征：线性表的基本运算；顺序表和单链表的组织方法和算 法设计。难点：单链表上的算法设计。第三章栈、队列和数组一、学习目的与要求栈和队列的逻辑结构与线性表的逻辑结构相同，可以把栈和队列看做是特殊的线性表， 其操作只肇在表的一端或两端进行。二维数组逻辑结构可以看成是线性结构的推广。本章总的要求是：理解栈和队列的定义、特征及与线性表的异同；掌握顺序栈和链栈的 组织方法和运算实现算法，栈满和栈空的判断条件；掌握顺序队列和链队列的组织方法和

6、运 算实现算法，队列满和队列空的判断条件；掌握数组的存储方法和特殊矩阵的压缩存储方法, 并能设计特殊矩阵的一些简单的算法。二、课程内容（1）枝。（2）队列。（3）数组。三、考核的知识点与考核要求1 .栈及其顺序实现和链接实现识记：栈的概念；栈的后进先出特征；栈的基本运算。领会栈顶和栈底；顺序栈的组织方法及其类c语言描述；顺序栈栈满和栈空的条件；链 栈的组织方法及其类C语言描述；链栈为空的条件。简单应用：采用顺序存储和链接存储实现栈的基本运算的算法。综合应用：用栈解决简单问题。2 .队列及其顺序实现和链接实现识记：队列的概念；队列的先进先出基本特征;队列的基本运算；循环队列。领会：队列头和队列尾

7、；顺序队列的组织方法及其类C语言描述；顺序队列满和队列空 的条件；循环队列的组织方法；循环队列的队列满和队列空的条件；链队列的组织方法及其 类C语言描述；链队列为空的条件。简单应用：用数组实现循环队列的基本运算；用链表实现队列的基本运算。综合应用：设计用队列解决简单问题的算法。3 .数组及其实现识记：一维、二维数组的逻辑结构及其顺序存储方法。领会：顺序存储的一维数组、二维数组的地址计算；特殊矩阵（三角矩阵、对称矩阵） 的概念。简单应用：用一维数组存储特殊矩阵的压缩存储方法；给定特殊矩阵中某个元素的位置 （ij）:计算该元素在一维数组中的位置k。四、本章重点、难点本章重点：栈和队列的特征；顺序栈

8、和链栈上基本运算的实现和简单算法；顺序队列和 链队列上基本运算的实现和简单算法。难点：循环队列的组织，队列满和队列空的条件及循环队列基本运算的算法。 第四章树和二叉树一、学习目的与要求树形结构用于表示具有分支和层次结构，有着广泛的应用背景。树和二叉树是重要的树 形结构。本章总的要求是：理解树形结构的基本概念和术语；深刻领会二叉树的定义及其存储结 构，理解二叉树的遍历的概念并掌握二叉树的遍历算法；掌握树和森林的定义、树的存储结 构以及树、森林与二叉树之间的相互转换方法；熟练掌握构造哈夫曼树和设计哈夫曼编码的 方法。二、课程内容（1）树的基本概念。（2）二叉树。（3）二叉树的存储结构。（4）二又树

9、的遍历。（5）树和森林。（6）判定树和哈夫曼树。三、考核的知识点与考核要求1 .树结构、森林识记：树的菜本概念；术语：森林基本概念。领会：树的基本运算。简单应用：结点的度计算：树的度计算；树的高度计算；结点的层次数计算。2 .二叉树识记：二叉树的概念；左子树；右子树。领会：二叉树的基本运算；二叉树的性质；二叉树顺序存储及类C语言描述；二叉树链 式存储及类C语言描述，二叉树的遍历算法。简单应用：二叉树结点数计算；二叉树深度计算；给出二叉树先序序列、中序序列和后 序序列；由二叉树先序序列、中序序列和后序序列构造二叉树。综合应用：设计二叉树上基于先序遍历、中序遍历和后序遍历的应用算法。3 .树和森林

10、识记：树的先序遍历方法；树的后序遍历方法；树的层次遍历方法；森林的先序遍历方 法；森林的中序遍历方法。领会：树、森林与二叉树的关系；树转换成二叉树方法；森林转换成二叉树方法；二叉 树转换成对应森林方法。4 .判定树和哈夫曼树识记：判定树概念；哈夫曼树概念；哈夫曼编码。领会：分类与判定树的关系；哈夫曼树构造过程；哈夫曼算法。简单应用：由一组叶结点的权值构造一棵对应的哈夫曼树，设计哈夫曼编码。四、本章重点、难点本章重点：树形结构的概念；二叉树的定义、存储结构和遍历算法。难点：二叉树的遍历算法和哈夫曼树构造算法。第五章图一、学习目的与要求图是一种有广泛应用背景的数据结构。本章在运算实现方面着重研究图

11、遍历这一常用运 算的实现，以及最小生成树、单源最短路径和拓扑排序等典型的应用问题的求解。本章总的要求是：理解图的概念并熟悉有关术语；熟练掌握图的邻接矩阵表示法和邻接 表表示法；深刻理解连通图遍历的基本思想和算法；理解最小生成树的有关概念和算法；理 解图的最短路径的有关概念和算法；理解拓扑排序的有关概念和算法。二、课程内容（1）图的基本概念。（2）图的存储结构。（3）图的遍历。（4）最小生成树。（5）单源最短路径。（6）拓扑排序。三、考核的知识点与考核要求1 .图的逻辑结构、图的存储结构识记：图的应用背景；图的概念；图的逻辑结构：有向图；无向图；子图；图的连通性; 边（弧）的权值；带权图；生成树

12、；图的存储结构。.领会：图的基本运算：图的邻接矩阵存储方式及类c语言描述：图的邻接表和逆邻接表 存储方式及类C语言描述。简单应用：建立图邻接矩阵算法：建立图邻接表算法。2 .图的遍历识记：图的遍历；图的深度优先搜索；图的广度优先搜索。领会：图的深度优先搜索算法；图的广度优先搜索算法。简单应用：求图的深度优先遍历的顶点序列；求图的广度优先遍历的顶点序列。3 .图的应用识记：最小生成树；单源最短路径；AOV网；拓扑排序。领会：求最小生成树的Prim算法；求最小生成树的Kruskal算法思想；求单源最短路径 Dijkstra算法思想；拓扑排序算法。简单应用：求最小生成树；求从一源点到其他各顶点的最短

13、路径；求给定有向图的顶点 的拓扑序列。四、本章重点、难点本章重点：图的邻接矩阵和邻接表两种存储结构，图的深度优先和广度优先搜索算法。 难点：求最小生成树的Prim算法：求单源最短路径算法：求拓扑排序算法。第六章查找一、学习目的与要求数据结构课程中的集合是四类基本逻辑结构之一。查找表是一种以集合为逻辑结构的常 用的数据结构，其基本特点是以查找运算为核心。因此，如何高效率地实现杳找运算是本章 的核心问题。本章总的要求是：了解集合的基本概念；理解查找表的定义、分类和各类的特点；掌握 顺序查找和二分查找的思想和算法；理解二又排序树的概念和有关运算的实现方法；掌握散 列表、散列函数的构造方法以及处理冲突

14、的方法；掌握散列存储和散列查找的基本思想及有 关方法、算法。二、课程内容（1）基本概念。（2）静态查找表的实现。（3）二叉排序树。（4）散列表。三、考核的知识点与考核要求1 .查找表、静态查找表识记：查找；查找表；关键字；主关键字；顺序表；索引顺序表；静态查找表的运算； 顺序查找；二分查找；平均查找长度等有关概念和术语。领会：顺序查找算法；设置岗哨的作用；二分查找算法；索引顺序表查找算法思想。简单应用：顺序查找的过程：二分查找的过程；索引顺序查找的过程。2 .二叉排序树识记：动态查找；二叉排序树查找的概念。领会：二叉排序树的建树过程；二叉排序树的查找算法；二叉排序树的结点的插入方法; 二叉排序

15、树的平均查找长度。简单应用：二叉排序树的建树过程；二叉排序树的查找过程。3 .散列表识记：散列表；散列函数；同义词；冲突。领会：几种常用散列法；解决冲突的方法：线性探测法、二次探测法和链地址法。简单应用：散列表构造/散列表的查找过程及其冲突处理。四、本章重点、难点本章重点：二分查找方法；二叉排序树的杳找方法；散列表的查找方法。难点：二叉排序树的插入算法。第七章排序一、学习目的与要求在很多实际问题中，排序是一种常用运算，而且对这种运算的时、空性能有较高的要求, 由此而发展出各种排序方法和技术。本章总的要求是：深刻理解各种内部排序方法的指导思想和特点；熟悉几种内部排序算 法，并理解其基本思想；了解

16、几种内部排序算法的优缺点、时空性能和适用场合。二、课程内容（1）概述。（2）直接插入排序。（3）交换排序。（4）选择排序。（5）归并排序。三、考核的知识点与考核要求1 .排序的基本概念识记：排序；内部排序；外部排序；稳定排序；不稳定排序。2 .插入排序识记插入排序；直接插入排序。领会：真接插入排序的算法；直接插入排序的稳定性；直接插入排序的时间复杂度。简单应用：直接插入排序的过程。3 .交换排序识记：交换排序；冒泡排序；快速排序。领会：交换排序的基本思想；冒泡排序的基本步骤和算法；快速排序的基本步骤和算法。简单应用：冒泡排序的过程；快速排序的过程。4 .选择排序识记：选择排序；直接选择排序；堆；堆排序。领会：选择排序的基本思想；直接选择排序的基本步骤和算法：堆排序基本步骤和算法。简单应用：直接选择排序的过程；堆排序的过程。5 .归并排序识记：归并；归并排序。领会：归并排序的基本思想：二路归并排序的基本步骤和算法。简单应用：二路归并排序的过程。四、本章重点、难点本章重点：直接插入排序算法、冒泡排序算法、快速排序算法，直接选择排序算法、堆 排序算法、二路归并排序算法。难点：快速排序算法和堆排序算法。