北京工业大学计算机学院专业型硕士2011年考研大纲

考试内容及范围说明

896 数据结构

1、数据结构的相关概念、算法概念、算法性质及算法分析（时间复杂度与空间复杂度）；

1. 线性表逻辑定义、存储结构的表示，以及在特定存储结构下线性表基本运算的算法实现；
2. 栈与队列的逻辑定义、存储结构的表示，基本操作特点，栈与队列的基本应用；
3. 串的逻辑定义，基本操作含义与实现；
4. 数组定义、顺序存储，矩阵的压缩存储，广义表定义及存储结构；
5. 树的定义与存储结构、二叉树定义与性质、存储结构，二叉树遍历算法（三序遍历与按层遍历），赫夫曼树与赫夫曼编码以及二叉树基本算法的实现与应用；
6. 图的定义与术语，图的存储结构，图的遍历（深度优先搜索与广度优先搜索），比较小生成树、拓扑排序与从某个源点到其余各顶点的比较短路径；
7. 查找的相关概念，静态查找表（顺序表的查找与有序表的查找），动态查找表（二叉排序树），哈希表的相关概念
8. 排序的相关概念，掌握直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序算法的执行过程、时空复杂度、稳定性以及使用场合。