821数据结构考试大纲.doc

一、考查目标
;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。
,能够对算法进行设计与分析。
。
二、考试形式和试卷结构

试卷满分150分,考试时间180分钟。

答题方式为笔试、闭卷。

单选题 10题 每小题 2分共20分
填空题 10题 每小题 2分共20分
简答题 5题 每小题 5分共25分
综合题 3题 每小题15分共45 分
算法题 4题 每小题10分共40 分
三、考查内容

(1)基本概念和术语
数据
数据结构
抽象数据类型
(2)算法的描述和分析
算法、算法的时间复杂度和空间复杂度概念
算法描述和算法分析的方法,对于一般算法能分析出时间复杂度

(1)线性表的概念
线性表的逻辑结构
线性表的存储结构:顺序表,单链表,双链表,循环链表
(2)线性表的实现
顺序存储结构:查找、插入、删除等主要操作及其平均时间性能分析
链式存储结构:查找、插入、删除等主要操作及其平均时间性能分析
、队列
(1)栈和队列的概念
栈和队列的逻辑结构
栈和队列的存储结构:顺序栈,循环队列,链式栈,链式队列
(2)栈和队列的实现
顺序存储结构:入栈、出栈、入队、出队等主要操作及其平均时间性能分析
链式存储结构:入栈、出栈、入队、出队等主要操作及其平均时间性能分析

(1)数组和广义表的概念
数组和广义表的逻辑结构
数组的存储结构:特殊矩阵压缩存储、稀疏矩阵压缩存储(三元组表)
广义表的存储结构:链式存储
(2)数组和广义表的实现
数组顺序存储结构:一般数组顺序存储的地址计算方法
广义表链式存储结构:非空广义表的求表头和表尾运算

(1)树和二叉树的概念
树和二叉树的逻辑结构
树和二叉树的存储结构:树的孩子兄弟二叉链表、二叉树的二叉链表
树和二叉树的遍历:树的三种遍历、二叉树的三种遍历
树和二叉树的转换
(2)树和二叉树的实现
二叉树的递归遍历
Huffman树
Huffman编码

(1)图的概念
图的逻辑结构
图的存储结构:邻接矩阵、邻接表
图的遍历:深度优先搜索、广度优先搜索
(2)图的实现
最小(代价)生成树:Prim和Kruskal方法
最短路径:Dijkstra方法
拓扑排序
关键路径

(1)查找的概念
查找表、查找分类、查找结构
查找算法效率的评判标准:平均查找长度
(2)静态表及其查找
顺序查找
折半查找
(3)动态表及其查找
二叉排序树
平衡二叉树
(4)哈希表及其查找
哈希函数
处理冲突方法
哈希查找
(5)各种查找算法的分析

(1)排序的概念
排序方法稳定性、排序分类
排序算法效率的评判标准
(2)插入排序
简单插入排序
希尔排序
(3)交换排序
冒泡排序
快速排序
(4)选择排序
简单选择排序
堆排序
(5)归并排序
二路归并排序
分治归并排序
(6)各种排序算法的比较
四、题型举例
1