2024年北京交通大学非全日制研究生招生考试《数据结构》考试大纲

　　1. 绪论

　　(1) 数据结构基本概念和术语

　　(2) 算法的特性和设计要求

　　(3) 算法时间复杂度和空间复杂度分析

　　2. 线性表

　　(1) 线性表的特点

　　(2) 在顺序存储结构上实现线性表的各种基本操作

　　(3) 在链式存储结构上实现线性表的基本操作(单链表，单向循环链表)

　　(4) 线性表的简单应用

　　3. 栈和队列

　　(1) 栈和队列的操作特点

　　(2) 在顺序存储结构和链式存储结构上实现栈(顺序栈、链栈)和队列(循

　　环队列、链队列)的各种基本操作

　　(3) 栈和队列的简单应用

　　(4) 递归程序设计的基本方法(分治法、减治法)

　　4. 串

　　(1) 串的基本运算的定义，

　　(2) 采用定长数组和变长数组(动态分配)实现串的各种基本操作

　　5. 树和二叉树

　　(1) 二叉树的结构特点和性质

　　(2) 二叉树的存储结构(数组表示法、二叉链表、三叉链表)

　　(3) 二叉树的深度优先遍历(先序、中序和后序)(递归算法)

　　(4) 二叉树的层次次序遍历

　　(5) 利用二叉树的遍历求解问题

　　(6) 树的存储结构(双亲表示法、孩子表示法、孩子兄弟表示法)

　　(7) 树与二叉树的相互转换

　　(8) 树和森林的遍历方法

　　(9) 最优二叉树和哈夫曼编码

　　6. 图

　　(1) 图的基本概念

　　(2) 图的存储结构(数组表示法、邻接表表示法)

　　(3) 图的深度优先搜索和广度优先搜索算法及简单应用

　　(4) 图遍历的应用：最小生成树﹑最短路径﹑拓扑排序﹑关键路径等

　　7. 查找

　　(1) 基本概念(静态查找，动态查找，关键字，平均查找长度等)

　　(2) 静态查找算法(顺序查找、折半查找、索引顺序表查找)

　　(3) 二叉排序树的建立、插入和删除过程

　　(4) 哈希表(概念、构造方法和处理冲突的方法)

　　8. 排序

　　(1) 排序的基本概念

　　(2) 插入排序(简单插入，折半插入，希尔排序)

　　(3) 交换排序(冒泡排序，快速排序)

　　(4) 选择排序(简单选择排序，堆排序)

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

　　(6) 基数排序

　　(7) 各种排序方法的比较分析(稳定性、时间和空间性能等)

　　参考书目：《数据结构(C 语言版)(第2 版)》，严蔚敏，李冬梅，人民邮电出版社