您的位置:首页 > 本科插班 > 本科插班生专业课考试复习大纲 > 2015《数据结构》考试大纲

2015《数据结构》考试大纲

2014-12-25 11:19 | 来源:招生办 | 查看:939 [ 字号: ]

一、总体要求

1、基本理论知识
(l)什么是数据结构、基本概念和基本术语,算法的描述和算法分析。
(2)什么是线性表、在线性表上常进行的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。
(3)栈和队列的定义、表示方法和实现。
(4)串的定义及其基本操作。
(5)数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和操作。
(6)树的定义、基本术语和存储结构,二叉树的定义和性质、二叉树的存储结构及其各种操作,哈夫曼树。
(7)图的定义和术语、图的存储结构及其各种操作。
(8)各种查找方法的算法、适用范围及时间复杂度的分析。
(9)多种内排算法的基本思想和算法的时间复杂度分析,不同排序方法的比较。
2、基本技能
(1)能阅读用类C语言编写的算法。
(2)能分析算法所完成的功能、运行结果和时间复杂度。
(3)能根据要求用类C语言编写算法。
二、考核知识点
第一章 绪论
1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。
2.算法、算法的特性、如何用类C语言来描述算法。
3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。
第二章 线性表
1.线性表的定义和操作。
2.顺序存储线性表的实现和运算。
3.链式存储线性表,带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的实现和查找对插入、删除等基本操作。
第三章 栈和队列

1.栈和队列的定义及其存储结构、循环队列。
2.栈和队列的主要运算。
3.栈的应用举例,如:数制转换、表达式求值等。
第四章
1.串的定义、空串、空格串。
2.串的基本操作。
3.串的顺序存储结构及在顺序存储结构下基本操作的实现。
4. 串的模式匹配算法。
第五章 数组和广义表
1.数组的顺序存储结构。
2.二维数组的按行存储及按列存储和计算数组元素的地址计算公式。
3.矩阵的压缩存储、特殊矩阵的表示。
4.广义表的定义和基本操作。
第六章 树和二叉树
1.树的定义和术语。
2.二叉树(完全二叉树、满二叉树)的定义和性质、二叉树的存储结构(顺序表示法和二叉链表表示法)。
3.二叉树遍历的递归算法。
4.二叉树线索化的实质及线索化的过程。
5.树和森林转换为二叉树的方法。
6.树的路径长度、树的带权路径长度、Huffman树的构造方法。
第七章
1.图的定义。
2.图的基本术语。
(1)图及无向图、有向图、网、子图、连通图、强连通图。
(2)顶点的度、入度、出度。
(3)顶点间路径、路径长度、环。
3.图的存储结构
(l)邻接矩阵
(2)邻接表(含逆邻接表)
4.遍历图 
(l)深度优先搜索遍历图的算法及其时间复杂度。
(2)广度优先搜索遍历图的思想及其时间复杂度。
5.生成树
(1)生成树、最小生成树的概念。
(2)最小生成树的构造过程(Prim算法和Kruskal算法)及其时间复杂度。
6.拓扑排序
7.两类求最短路径问题的解法。
第九章 查找
1.查找、关键字、平均查找长度等概念。
2.静态查找表的查找算法及其效率(最坏和平均查找长度)。
(l)顺序查找
(2)折半查找
(3)分块查找
3.动态查找表
(1)二叉排序树定义、构造过程及其查找算法和效率。
(2)平衡二叉树的定义。
4.哈希表
(l)哈希表的特点。
(2)构造哈希函数的方法(除留余数法等)。
(3)处理冲突的方法。
第十章 内部排序
1.排序的目的、分类和排序方法的稳定性的定义。
2.插入排序
(1)直接插入排序的算法。
(2)折半插入排序的算法。
(3)希尔排序的思想。
3. 快速排序
(1)起泡排序的算法。
(2)快速排序的思想。
4.选择排序
(1)简单的选择排序的算法。
(2)堆的定义、堆排序的思想。
5.归并排序的思想。
6.基数排序的思想及特点。
7.各种内部排序方法的比较。

三、教材:

《数据结构(C语言版)》    严蔚敏等编著   清华大学出版社