2014年北京航空航天大学交通科学与工程学院考研大纲

　　991数据结构与C语言程序设计考试大纲（2014版）
　　2014年"数据结构与C语言程序设计"考试内容包括"数据结构"与"C语言程序设计"两门课程的内容，各占比例50%，试卷满分为150分。
　　"数据结构"部分
　　一、概述
　　1．数据的逻辑结构与存储结构的基本概念；
　　2．算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。
　　二、线性表
　　1．线性关系、线性表的定义，线性表的基本操作；
　　2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；
　　3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。
　　三、堆栈与队列
　　1．堆栈与队列的基本概念与基本操作；
　　2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；
　　3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；
　　4．堆栈和队列在解决实际问题中应用。
　　四、树与二叉树
　　1．树与二叉树的基本概念，基本特征、名词术语；
　　2．完全二叉树与满二叉树的基本概念，二叉树的基本性质；
　　3．二叉树与树、树林之间的转换；
　　4．二叉树的顺序存储结构与二叉链表存储结构；
　　5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法)的设计与应用；
　　6．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算；
　　7．哈夫曼(Huffman)树的基本概念，哈夫曼树的构造与带权路径长度(WPL)的计算。
　　五、图
　　1．图的基本概念、名词术语；
　　2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；
　　3．图的深度优先搜索与广度优先搜索；
　　4．最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求
　　解过程。
　　六、文件及查找
　　1．顺序查找法以及平均查找长度(ASL)的计算；
　　2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的"判定树"的构造；
　　3．B-树和B+树的基本概念，B-树的插入与查找；
　　4．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。
　　七、内排序
　　1．排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算；
　　2．插入排序法(含折半插入排序法)；
　　3．选择排序法；
　　4．(起)泡排序法；
　　5．谢尔(Shell)排序法；
　　6．快速排序法；
　　7．堆积(Heap)排序法，包括堆积的定义与构造；
　　8．二路归并排序法。