Skip to main content
学院查询 专业查询 考试大纲

834数据结构与程序设计


(一)可参考书目

1、《数据结构-C语言描述》(第2版)殷人昆编著  机械工业出版社

2、《数据结构》 严蔚敏,吴伟民编著 清华大学出版社

(二)复习内容

1、数据结构的概念

(1) 数据结构的概念与分类

(2) 算法定义

(3) 算法分析与度量

2、线性表

(1) 线性表的概念与逻辑特点

(2) 顺序表的实现与应用

(3) 链表(单链表、单向循环链表、双向循环链表)的实现与应用

(4) 静态链表的实现

3、栈与队列

(1) 栈的定义、逻辑特点及实现

(2) 队列的定义、逻辑特点及实现

(3) 栈的应用:括号配对、表达式求值

(4) 递归:递归定义、递归程序的编写、递归程序转化为非递归

(5) 双端队列和优先级队列的实现

4、字符串、数组与广义表

(1) 字符串的概念、实现与模式匹配

(2) 多维数组寻址、特殊矩阵的压缩存储、稀疏矩阵

(3) 广义表的概念、存储及算法实现

5、树与二叉树

(1) 树的定义与基本概念

(2) 二叉树的定义、性质与实现

(3) 二叉树的遍历与应用

(4) 二叉树的计数

(5) 线索二叉树的概念与实现

(6) 树的多种存储表示,树的遍历,树、森林与二叉树的相互转换

(7) 哈夫曼树的概念与实现

(8) 堆的概念与实现

(9) 二叉搜索(查找)树的概念与实现

(10) AVL树的概念与实现

(11) 树的应用:并查集的概念与实现

6、图

(1) 图的基本概念与存储表示

(2) 图的遍历与连通性

(3) 最小生成树算法

(4) 最短路径算法

(5) 拓扑排序与关键路径

7、查找

(1) 查找的概念

(2) 顺序查找与折半查找的算法实现与性能分析

(3) 次优查找树的构造方法

(4) 跳表

(5) 索引结构:B树和B+

(6) 散列:概念、散列函数构造方法以及解决冲突的方法

8、排序

(1) 排序的概念

(2) 插入排序:直接插入排序、折半插入排序、希尔排序

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

(4) 选择排序:简单选择排序、锦标赛排序、堆排序

(5) 归并排序、基数排序、表排序

(6) 各种排序算法的实现、性能分析及比较