资源描述
中国传媒大学硕士研究生招生考试初试科目数据结构考试大纲一、考试目的及要求本科目主要考查：1.掌握数据结构的基本概念、基本原理和基本方法。2.掌 握 数 据 的 逻 辑 结 构 、 存 储 结 构 及 基 本 操 作 的 实 现 ， 能 够 对 算 法 进 行 基本的时间复杂度与空间复杂度的分析。3.能 够 运 用 数 据 结 构 基 本 原 理 和 方 法 进 行 问 题 的 分 析 与 求 解 ， 具 备 采 用 C或 C+语言设计与实现算法的能力。二、考试内容第一部分 线性表1.线性表的定义和基本操作2.线性表的实现（1） 顺序存储（2） 链式存储（3） 线 性 表 的 应 用第二部分 栈、队列和数组 1.栈和队列的基本概念2.栈和队列的顺序存储结构3.栈和队列的链式存储结构4.栈和队列的应用5.特 殊 矩 阵 的 压 缩 存 储第三部分 树与二叉树1.树的概念2.二叉树（1） 二叉树的定义及其主要特征（2） 二叉树的顺序存储结构和链式存储结构（3） 二叉树的遍历（4） 线索二叉树的基本概念和构造3.树、森林（1） 树的存储结构（2） 森林与二叉树的转换（3） 树和森林的遍历4.树与二叉树的应用（1） 二叉排序树（2） 平衡二叉树（3） 哈夫曼（Huffman）树 和 哈 夫 曼 编 码第四部分 图1.图的基本概念2.图的存储及基本操作（1） 邻接矩阵法（2） 邻接表法（3） 邻接多重表、十字链表3.图的遍历（1） 深度优先搜索（2） 广度优先搜索4.图的基本应用（1） 最小（代价）生成树（2） 最短路径（3） 拓扑排序（4） 关 键 路 径第五部分 查找1.查找的基本概念2.顺序查找法3.分块查找法4.折半查找法5.B 树 及 其 基 本 操 作 、 B+树的基本概念6.散列（Hash）表7.字符串模式匹配8.查 找 算 法 的 分 析 及 应 用第六部分 排序1.排序的基本概念2.插入排序（1） 直接插入排序（2） 折半插入排序3.起泡排序（bubble sort） 4.简单选择排序5.希尔排序（shell sort） 6.快速排序7.堆排序8.二路归并排序（merge sort） 9.基数排序10.外部排序11.各种内部排序算法的比较12.排序算法的应用三、试题类型选择题、应用题、算法设计题等。四、考试形式及时长笔试，考试时长为 3 小时。五、参考书目数据结构（C 语言版） 严蔚敏、吴伟民著 清华大学出版社。
展开阅读全文