2018年中传算法与数据结构考研大纲--新祥旭考研.docx

中国传媒大学硕士研究生入学考试 算法与数据结构考试大纲一、考试的总体要求算法与数据结构不仅是大学本科计算机科学与技术专业的专业基础课，也是其他从事计算机信息处理专业的一门重要的基础课程。它主要考查考生对数据的组织、存储、处理等能力，算法设计以及对算法的分析和评价的掌握程度。要求考生理解数据结构的逻辑结构和物理结构的基本概念，熟练掌握各种数据结构以及有关算法，并具有综合运用所学知识分析和解决实际问题的能力。二、考试的内容（一）数据结构的基本概念1什么是数据结构2逻辑结构3存储结构4数据运算5抽象数据类型的表示与实现6算法和算法分析（二）线性表1线性表的基本概念2线性表的顺序表示和实现3线性链表4循环链表5双向链表6链表的应用（三）栈和队列1栈和队列的基本概念2栈的顺序实现3栈的链式实现4栈的应用5栈与递归的实现6队列的顺序实现7队列的链式实现（四）串1串的顺序存储表示2串的堆分配存储表示3串的块链存储表示4Brute-Force 模式匹配算法5KMP 模式匹配算法6串操作的应用（五）数组和广义表1数组的顺序表示和实现2特殊矩阵3稀疏矩阵4广义表的定义5广义表的存储结构6广义表的运算（六）树和二叉树1树的定义和基本术语2二叉树的定义和性质3二叉树的顺序存储4二叉树的链式存储5遍历二叉树6线索二叉树7树的存储结构8森林与二叉树的转换9树和森林的遍历10树与等价问题11赫夫曼树及其应用（七）图1图的定义和基本术语2图的数组表示法3邻接表4十字链表5邻接多重表6图的深度优先搜索7图的广度优先搜索8无向图的连通分量和生成树9有向图的强连通分量10最小生成树11拓扑排序12关键路径（八）动态存储管理1可利用空间表及分配方法2边界标识法3伙伴系统4无用单元收集（九）查找1查找的基本概念2顺序查找3二分查找4分块查找5二叉排序树6平衡二叉树7B -和 B 树8哈希表的构造方法9处理冲突的方法10哈希表的查找及分析（十）内部排序1直接插入排序2希尔排序3冒泡排序4快速排序5简单选择排序6树形选择排序7堆排序8归并排序9基数排序10各种内部排序方法的比较（十一）外部排序1外部排序的方法2多路平衡归并的实现3置换选择排序4最佳归并树（十二）文件1、 文件的基本概念2、 顺序文件3、 索引文件4、 ISAM 文件5、 VSAM 文件6、 散列文件7、 多重表文件8、 倒排文件三、考试的基本题型主要题型可能有：是非题、选择题、填空题、简答题、算法设计题、综合题等。四、考试的形式及时间笔试，不需要任何辅助工具。考试时间为三小时。