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

《数据结构导论》考试大纲第一章概论

一、学习目的与要求本章集中介绍贯穿和应用于数据结构课程始终的基本概念，概括反映了后续各章的基本问题，为进入具体内容的学习提供了必要的引导本章总的要求是理解数据、数据元素和数据项的概念及其相互关系；理解数据结构的含义；理解逻辑结构、基本运算和存储结构的概念、意义和分类；理解存储结构与逻辑结构的关系；理解算法的概念；理解衡量一个算法效率的两个标准时间复杂度和空间复杂度

二、课程内容

（1）基本概念和术语

（2）算法及描述

（3）算法分析

三、考核的知识点与考核要求

1.数据结构、数据、数据元素和数据项的概念识记数据结构；数据；数据元素；数据项领会数据结构的作用；数据、数据元素、数据项三者关系

2.数据逻辑结构和数据存储结构识记数据逻辑结构、数据存储结构领会四类基本逻辑结构的特点；顺序存储结构；链式存储结构；逻辑结构与存储结构的关系

3.运算、算法和算法分析识记运算；基本运算；算法分析时间复杂度；空间复杂度领会运算与数据结构的关系;•算法的描述方法；算法的评价因素；时间复:杂度分析方法；空间复杂度分析方法简单应用运用类C语言描述算法简单算法时间复杂度分析；简单算法的空间复杂度分析

四、本章重点、难点本章重点数据结构、数据逻辑结构、数据存储结构以及运算等概念难点算法时间复杂度分析第二章线性表

一、学习目的与要求顺序表和单链表分别是简单、基本的顺序存储结构和链式存储结构顺序表和单链表上实现基本运算的算法是数据结构中简单和基本的算法这些内容构成以下各章的重要基础，因此本章是本课程的重点之一本章要求理解线性表的概念；熟练掌握顺序表和链表的组织方法及实现基本运算的算法；掌握在顺序表和链表上进行算法设计的基本技能；了解顺序表与链表的优缺点

二、课程内容

（1）线性表的基本概念

（2）线性表的顺序存储

（3）线性表的链接存储

（4）其他运算在单链表上的实现

（5）其他链表

三、考核的知识点与考核要求

1.线性表概念识记线性表概念；线性表的基本特征领会线性表表长；线性表初始化、求表长、读表元素、定位、插入、删除等基本运算的功能

2.线性表的顺序存储结构一顺序表识记顺序表表示法、特点和类C语言描述领会顺序表的容量；顺序表表长；插入、删除和定位运算实现的关键步骤简单应用顺序表插入、删除和定位运算的实现算法综合应用顺序表上的简单算法；顺序表实现算法的分析

3.线性表的链式存储结构一单链表识记结点的结构；单链表的类C语言描述领会头指针；头结点；首结点；尾结点；空链表；单链表福入、删除和定位运算的关键步骤简单应用单链表插入、删除和定位等基本运算的实现算法综合应用用单链表设计解决应用问题的算法

4.循环链表和双向循环链表识记循环链表的结点结构；双向循环链表结点结构；循环链表和双向循环链表类C语言描述领会循环链表插入和删除运算的关键步骤；双向循环链表插入和删除运算的关键步骤

四、本章重点、难点本章重点线性表概念和基本特征线性表的基本运算；顺序表和单链表的组织方法和算法设计难点单链表上的算法设计第三章栈、队列和数组

一、学习目的与要求栈和队列的逻辑结构与线性表的逻辑结构相同，可以把栈和队列看做是特殊的线性表，其操作只肇在表的一端或两端进行二维数组逻辑结构可以看成是线性结构的推广本章总的要求是理解栈和队列的定义、特征及与线性表的异同；掌握顺序栈和链栈的组织方法和运算实现算法，栈满和栈空的判断条件；掌握顺序队列和链队列的组织方法和运算实现算法，队列满和队列空的判断条件；掌握数组的存储方法和特殊矩阵的压缩存储方法,并能设计特殊矩阵的一些简单的算法

二、课程内容

（1）枝

（2）队列

（3）数组

三、考核的知识点与考核要求

1.栈及其顺序实现和链接实现识记栈的概念；栈的后进先出特征；栈的基本运算领会栈顶和栈底；顺序栈的组织方法及其类c语言描述；顺序栈栈满和栈空的条件；链栈的组织方法及其类C语言描述；链栈为空的条件简单应用采用顺序存储和链接存储实现栈的基本运算的算法综合应用用栈解决简单问题

2.队列及其顺序实现和链接实现识记队列的概念；队列的先进先出基本特征;队列的基本运算；循环队列领会队列头和队列尾；顺序队列的组织方法及其类C语言描述；顺序队列满和队列空的条件；循环队列的组织方法；循环队列的队列满和队列空的条件；链队列的组织方法及其类C语言描述；链队列为空的条件简单应用用数组实现循环队列的基本运算；用链表实现队列的基本运算综合应用设计用队列解决简单问题的算法

3.数组及其实现识记一维、二维数组的逻辑结构及其顺序存储方法领会顺序存储的一维数组、二维数组的地址计算；特殊矩阵（三角矩阵、对称矩阵）的概念简单应用用一维数组存储特殊矩阵的压缩存储方法；给定特殊矩阵中某个元素的位置（ij）:计算该元素在一维数组中的位置k

四、本章重点、难点本章重点栈和队列的特征；顺序栈和链栈上基本运算的实现和简单算法；顺序队列和链队列上基本运算的实现和简单算法难点循环队列的组织，队列满和队列空的条件及循环队列基本运算的算法第四章树和二叉树

一、学习目的与要求树形结构用于表示具有分支和层次结构，有着广泛的应用背景树和二叉树是重要的树形结构本章总的要求是理解树形结构的基本概念和术语；深刻领会二叉树的定义及其存储结构，理解二叉树的遍历的概念并掌握二叉树的遍历算法；掌握树和森林的定义、树的存储结构以及树、森林与二叉树之间的相互转换方法；熟练掌握构造哈夫曼树和设计哈夫曼编码的方法

二、课程内容

（1）树的基本概念

（2）二叉树

（3）二叉树的存储结构

（4）二又树的遍历

（5）树和森林

（6）判定树和哈夫曼树

三、考核的知识点与考核要求

1.树结构、森林识记树的菜本概念；术语森林基本概念领会树的基本运算简单应用结点的度计算树的度计算；树的高度计算；结点的层次数计算

2.二叉树识记二叉树的概念；左子树；右子树领会二叉树的基本运算；二叉树的性质；二叉树顺序存储及类C语言描述；二叉树链式存储及类C语言描述，二叉树的遍历算法简单应用二叉树结点数计算；二叉树深度计算；给出二叉树先序序列、中序序列和后序序列；由二叉树先序序列、中序序列和后序序列构造二叉树综合应用设计二叉树上基于先序遍历、中序遍历和后序遍历的应用算法

3.树和森林识记树的先序遍历方法；树的后序遍历方法；树的层次遍历方法；森林的先序遍历方法；森林的中序遍历方法领会树、森林与二叉树的关系；树转换成二叉树方法；森林转换成二叉树方法；二叉树转换成对应森林方法

4.判定树和哈夫曼树识记判定树概念；哈夫曼树概念；哈夫曼编码领会分类与判定树的关系；哈夫曼树构造过程；哈夫曼算法简单应用由一组叶结点的权值构造一棵对应的哈夫曼树，设计哈夫曼编码

四、本章重点、难点本章重点树形结构的概念；二叉树的定义、存储结构和遍历算法难点二叉树的遍历算法和哈夫曼树构造算法第五章图

一、学习目的与要求图是一种有广泛应用背景的数据结构本章在运算实现方面着重研究图遍历这一常用运算的实现，以及最小生成树、单源最短路径和拓扑排序等典型的应用问题的求解本章总的要求是理解图的概念并熟悉有关术语；熟练掌握图的邻接矩阵表示法和邻接表表示法；深刻理解连通图遍历的基本思想和算法；理解最小生成树的有关概念和算法；理解图的最短路径的有关概念和算法；理解拓扑排序的有关概念和算法

二、课程内容

（1）图的基本概念

（2）图的存储结构

（3）图的遍历

（4）最小生成树

（5）单源最短路径

（6）拓扑排序

三、考核的知识点与考核要求

1.图的逻辑结构、图的存储结构识记图的应用背景；图的概念；图的逻辑结构有向图；无向图；子图；图的连通性;边（弧）的权值；带权图；生成树；图的存储结构.领会图的基本运算图的邻接矩阵存储方式及类c语言描述图的邻接表和逆邻接表存储方式及类C语言描述简单应用建立图邻接矩阵算法建立图邻接表算法

2.图的遍历识记图的遍历；图的深度优先搜索；图的广度优先搜索领会图的深度优先搜索算法；图的广度优先搜索算法简单应用求图的深度优先遍历的顶点序列；求图的广度优先遍历的顶点序列

3.图的应用识记最小生成树；单源最短路径；AOV网；拓扑排序领会求最小生成树的Prim算法；求最小生成树的Kruskal算法思想；求单源最短路径Dijkstra算法思想；拓扑排序算法简单应用求最小生成树；求从一源点到其他各顶点的最短路径；求给定有向图的顶点的拓扑序列

四、本章重点、难点本章重点图的邻接矩阵和邻接表两种存储结构，图的深度优先和广度优先搜索算法难点求最小生成树的Prim算法求单源最短路径算法求拓扑排序算法第六章查找

一、学习目的与要求数据结构课程中的集合是四类基本逻辑结构之一查找表是一种以集合为逻辑结构的常用的数据结构，其基本特点是以查找运算为核心因此，如何高效率地实现杳找运算是本章的核心问题本章总的要求是了解集合的基本概念；理解查找表的定义、分类和各类的特点；掌握顺序查找和二分查找的思想和算法；理解二又排序树的概念和有关运算的实现方法；掌握散列表、散列函数的构造方法以及处理冲突的方法；掌握散列存储和散列查找的基本思想及有关方法、算法

二、课程内容

（1）基本概念

（2）静态查找表的实现

（3）二叉排序树

（4）散列表

三、考核的知识点与考核要求

1.查找表、静态查找表识记查找；查找表；关键字；主关键字；顺序表；索引顺序表；静态查找表的运算；顺序查找；二分查找；平均查找长度等有关概念和术语领会顺序查找算法；设置岗哨的作用；二分查找算法；索引顺序表查找算法思想简单应用顺序查找的过程二分查找的过程；索引顺序查找的过程

2.二叉排序树识记动态查找；二叉排序树查找的概念领会二叉排序树的建树过程；二叉排序树的查找算法；二叉排序树的结点的插入方法;二叉排序树的平均查找长度简单应用二叉排序树的建树过程；二叉排序树的查找过程

3.散列表识记散列表；散列函数；同义词；冲突领会几种常用散列法；解决冲突的方法线性探测法、二次探测法和链地址法简单应用散列表构造/散列表的查找过程及其冲突处理

四、本章重点、难点本章重点二分查找方法；二叉排序树的杳找方法；散列表的查找方法难点二叉排序树的插入算法第七章排序

一、学习目的与要求在很多实际问题中，排序是一种常用运算，而且对这种运算的时、空性能有较高的要求,由此而发展出各种排序方法和技术本章总的要求是深刻理解各种内部排序方法的指导思想和特点；熟悉几种内部排序算法，并理解其基本思想；了解几种内部排序算法的优缺点、时空性能和适用场合

二、课程内容

（1）概述

（2）直接插入排序

（3）交换排序

（4）选择排序

（5）归并排序

三、考核的知识点与考核要求

1.排序的基本概念识记排序；内部排序；外部排序；稳定排序；不稳定排序

2.插入排序识记插入排序；直接插入排序领会真接插入排序的算法；直接插入排序的稳定性；直接插入排序的时间复杂度简单应用直接插入排序的过程

3.交换排序识记交换排序；冒泡排序；快速排序领会交换排序的基本思想；冒泡排序的基本步骤和算法；快速排序的基本步骤和算法简单应用冒泡排序的过程；快速排序的过程

4.选择排序识记选择排序；直接选择排序；堆；堆排序领会选择排序的基本思想；直接选择排序的基本步骤和算法堆排序基本步骤和算法简单应用直接选择排序的过程；堆排序的过程

5.归并排序识记归并；归并排序领会归并排序的基本思想二路归并排序的基本步骤和算法简单应用二路归并排序的过程

四、本章重点、难点本章重点直接插入排序算法、冒泡排序算法、快速排序算法，直接选择排序算法、堆排序算法、二路归并排序算法难点快速排序算法和堆排序算法。