资源描述
1 中央民族大学硕士研究生入学考试初试 科目 考试 大纲 科目代码： 856 科目名称： 数据结构 I.考查目标 要求考生系统地掌握 数据结构 课程的基本概念、基本原理和基本方法；掌握数据的逻辑结构、存储结构及基本操作的实现；能够综合运用所学的知识与方法解决有关理论和实际问题，具备一定的算法设计与实现能力。 II.考试形式和试卷结构 一、试卷满分及考试时间 本试卷满分为 150 分，考试时间为 180 分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 150 分 四、试卷题型结构 单项选择题 60分 （ 20小题 ，每小题 3分） 按要求解答问题 40分 （ 4道 题 ） 算法设计 题 50分 （ 5道 题 ） III.考查内容 一、数据结构与算法 (一 ) 数据结构的基本概念 (二 ) 算法和算法分析 1. 算法基本概念 2. 算法的时间和空间性能分析 二、线性表 (一 ) 线性表的基本概念 (二 ) 线性表的顺序存储结构和链式 存储 结构 (三 ) 线性表的应用 三、栈和队列 (一 ) 栈 1. 栈的基本概念 2. 栈的顺序存储结构和链式 存储 结构 2 (二 ) 递归 (三 ) 队列 1. 队列的基本概念 2. 队列的顺序存储结构和 链式存储结构 (四 ) 栈和队列的应用 四、数组、广义表 (一 ) 数组的基本概念及存储结构 (二 ) 矩阵的压缩存储 (三 ) 广义表的基本概念及存储结构 五、二叉树、树和森林 (一 ) 树的基本概念 (二 ) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 5. 哈夫曼树和哈夫曼编码 (三 ) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历 六、图 (一 ) 图的基本概念 (二 ) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 3. 邻接多重表、十字链表 (三 ) 图的遍历 1. 深度优先搜索 2. 广度优先搜索 (四 ) 图的应用 1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 七、查找 (一 ) 查找的基本概念 (二 ) 线性表的查找 3 1. 顺序查找法 2. 折半查找法（二分查找） 3. 分块查找法 (三 ) 树表的查找 1. 二叉排序树的查找 2. 平衡二叉树的查找 3. B 树基本概念及其基本操作、 B+树的基本概念 (四 ) 散列（ 哈希 ）表 (五 ) 字符串模式匹配 (六 ) 查找算法的分析及应用 八、排序 (一 ) 排序的基本概念 (二 ) 插入排序 1. 直接插入排序 2. 折半插入排序 3. 希尔排序 (三 ) 交换排序 1. 气泡排序 2. 快速排序 (四 ) 选择排序 1. 简单选择排序 2. 堆排序 (五 ) 二路归并排序 (六 ) 基数排序 (七 ) 各种 内部排序 的 算法分析 (八 ) 外部排序 (九 ) 排序算法的应用
展开阅读全文