2019年中国传媒大学2006《数据结构》考博大纲

中国传媒大学博士研究生普通招考
《数据结构》科目考试大纲
一、考试目的及要求
本科目主要考查考生综合运用数据结构知识和技术分析和解决计算机程序与算法设计
问题的能力。要求考生系统地掌握数据结构课程的基本概念、基本原理和基本方法；掌握
程序设计中常用的数据结构的基本概念、对应的逻辑结构和存储结构及其基本运算；具备
较强的抽象思维和逻辑推理能力；能够综合运用所学的知识分析、判断和解决有关理论问
题和实际问题；熟练使用基础数据结构进行算法程序设计与分析，并用类 C/C++语言进行
算法描述。
二、考试内容
第一部分：数据结构基本概念
主要内容：
1. 数据结构的概念，数据的逻辑结构及物理结构；
2. 算法的定义和应具有的特性，算法设计的要求；
3. 算法的时间复杂度分析和算法的空间复杂度分析。
第二部分：线性表
主要内容：
1. 线性结构的特点、线性表的定义，线性表的基本操作；
2. 线性表的顺序存储结构及操作；
3. 单链表、双向链表和循环链表等链表形式的存储结构和特点以及操作；
4. 顺序表及链表的应用算法设计与分析。
第三部分：栈、队列和递归
主要内容：
1. 栈和队列的基本概念和基本操作；
2. 栈和队列的顺序和链式储结构；
3. 栈和队列的典型应用；
4. 递归的基本概念，用递归的思想描述问题和书写算法的方法，用栈实现递归问
题的非递归解法。
第四部分：数组与串
主要内容：
1. 数组的存储结构，在顺序存储的情况下，数组元素与存储单元的对应关系；
2. 稀疏矩阵的压缩存储；
3. 串的基本概念、串的存储结构和相关的操作算法、字符串匹配算法。
第五部分：树与森林
主要内容：
1. 树的结构和主要概念，各种二叉树的结构及其特点；
2. 二叉树的三种常见遍历方法及递归算法的运用，基于遍历的问题求解；
3. 线索化二叉树的的结构与基本操作，线索应用；
4. 树与二叉树的应用，包括二叉排序树、平衡二叉树、哈夫曼树和哈夫曼编码等；
5. 森林的定义和存储结构，树与森林的转化，森林的遍历。
第六部分：图
主要内容：
1. 图基本概念、图的邻接矩阵和临接链表存储方法;
2. 图的深度优先和广度优先遍历方法；图的连通性判定方法；
3. 图的最短路径寻找，图的生成树寻找方法，拓扑排序
第七部分：查找
主要内容：
1. 顺序查找法，折半查找法；
2. B 树及其基本操作、B+树的基本概念；
3. 散列(Hash)表及其查找；
4. 查找算法的复杂度分析及应用。
第八部分：排序
主要内容：
1. 插入排序、选择排序、起泡排序、快速排序、堆排序、归并排序、基数排序、
外部排序等排序方法的原理和特点；
2. 各种排序算法的应用和时空复杂度的分析。
三、试题类型
主要题型：问答题、算法设计题、综合应用题等。
四、考试形式及时间
笔试，不需要任何辅助工具。考试时间为三小时。