数据结构(803)

一、考试范围

1.数据结构基本概念及简单的算法分析

(1)数据结构、抽象数据类型、数据类型、算法的基本概念

(2)算法性能分析与度量：算法的性能标准；算法的空间复杂度与时间复杂度概念与分析方法；时间复杂度的渐进表示法；

2.线性表

(1)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；顺序表的优缺点

(2)单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；静态链表 ；链表的优缺点

(3)循环链表：循环链表的类定义；用循环链表解约瑟夫问题；

(4)双向链表的基本操作

3.栈和队列

(1)栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示

(2)队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；

(3)栈和队列的应用

4.树与森林

(1)树和森林的概念：树的定义；树的术语；树的抽象数据类型

(2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型

(3)二叉树的表示：顺序表表示；链表存储表示

(4)二叉树遍历：中序遍历；前序遍历；后序遍历；不用栈的二叉树中序遍历算法

(5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化

(6)树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历；

(7)哈夫曼树：带权路径长度；哈夫曼树；哈夫曼编码

5. 图

(1)图的基本概念：图的基本概念；图的抽象数据类型。

(2)图的存储表示：邻接矩阵；邻接表。

(3)图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；

(4)图的基本算法：最小生成树：Prim普里姆算法；Kruskal克鲁斯卡尔算法；Dijkstra最短路径；拓扑排序AOV；关键路径AOE。

6.查找

(1)查找、查找表及平均查找长度的基本概念

(2)顺序查找；基于有序顺序表的二分查找算法及分析

(3)二叉排序树：定义，二叉排序树的查找、插入和删除；

(4)平衡二叉树(AVL树)：AVL树的定义,查找，插入和删除，平衡二叉树的调整；

(5)散列：散列表的基本概念，构造方法(除留余数法)，解决冲突的方法(线性探测，二次线性探测)，查找性能的分析。

7.排序

(1)排序的基本术语与概念

(2)插入排序：直接插入排序；折半插入排序；希尔排序

(3)交换排序:冒泡排序；快速排序

(4)选择排序：简单选择排序；堆排序

(5)归并排序：二路归并排序

(6)基数排序：基数排序

(7)各种内排序方法的比较与选择

二、考试形式

（一）试卷成绩及考试时间

本试卷满分为150分，考试时间为180分

（二）答题方式

答题方式为闭卷、笔试

（三）推荐参考书

1. 李春葆，《数据结构教程（第5版）》，清华大学出版社

2. 李春葆，《数据结构教程（第5版）学习指导》，清华大学出版社

3.严蔚敏，吴伟民，数据结构（C语言版）

（四）试卷内容结构

数据结构基本概念：20%，顺序与链式线性表：15%，栈与队列：15%

树与二叉树：20%，图：15%，查找与排序：15%

（五）试卷题型结构

选择题（约30分），填空题（约20分）；判断题（约20分）；应用题（约50分）算法分析设计题（约30分）