2014年中国石油大学（华东）085212软件工程考研大纲

　　考研网快讯，据中国石油大学（华东）研究生院消息，2014年中国石油大学（华东）软件工程考研大纲已发布，详情如下：

　　2014年硕士研究生入学考试大纲
　　考试科目名称：数据结构考试时间：180分钟，满分：150分
　　一、考试要求：
　　1．理解数据结构、算法、抽象数据类型(ADT)的基本概念。
　　2．掌握线性表、树、图等基本数据结构的ADT定义以及在顺序存储和链式存储下相关算法的实现，并能对算法的时间复杂度进行分析。
　　3．掌握"查找"和"排序"中主要算法的基本思想和特点。
　　4．能够运用学习的数据结构知识和技能进行问题的分析与求解，具备采用C或C++或JAVA语言设计与实现算法（编程）的能力。
　　二、考试内容：
　　1．一般线性表
　　（1）基于顺序存储的定义和实现（方式、特点）
　　（2）基于链式存储的定义和实现（方式、特点）
　　（3）线性表的应用
　　2．特殊线性表（栈、队列、字符串、数组）
　　（1）栈、队列、字符串、数组的基本概念、特点
　　（2）栈和队列基于顺序存储的定义与实现（方式、特点）
　　（3）栈和队列基于链式存储的定义与实现（方式、特点）
　　（4）字符串基于顺序存储的定义与实现（能够求模式的失败函数）
　　（5）数组的逻辑定义和顺序存储
　　（6）特殊数组的存储（存储方式、占用空间情况、数组操作的实现、在一维存储空间中下标的计算）
　　（7）稀疏矩阵的压缩存储及转置算法实现
　　4．树与二叉树
　　（1）二叉树
　　①二叉树的定义、主要特征及相关特征的证明
　　②二叉树基于顺序存储和链式存储的实现（方式、特点）
　　③二叉树重要操作的实现（建立、遍历、计算叶子结点、结点、深度等算法实现）
　　④线索二叉树的基本概念和构造（为什么加线索？如何记录线索？如何使用线索？）
　　（2）树、森林
　　①树的存储结构（重点掌握子女-兄弟表示）
　　②森林与二叉树的相互转换
　　③树和森林的遍历
　　（3）特殊二叉树及应用
　　①哈夫曼（Huffman）树和哈夫曼编码的构造过程
　　②二叉排序树（重点掌握结点的插入和删除的思想和过程）
　　③平衡二叉树（平衡的目的？如何达到平衡？）
　　④堆（堆的构造和调整过程）
　　5．图
　　（1）图的基本概念
　　（2）图的存储及基本操作
　　①邻接矩阵存储（无向图、有向图、无向带权图、有向带权图）
　　②邻接表存储（无向图、有向图、无向带权图、有向带权图）
　　③各种存储方式下操作的算法实现（图的建立、遍历、插入边、删除边等）
　　（3）图的遍历
　　①深度优先遍历（思想、过程及算法实现）
　　②广度优先遍历（思想、过程及算法实现）
　　（4）图的基本应用（掌握算法的思想、过程）
　　①最小生成树问题
　　②最短路径问题
　　③有向图与工程（AOV网与拓扑排序，AOE网与关键路径）
　　6．查找
　　（1）查找的基本概念
　　（2）顺序查找法（监视哨法的思想和算法）
　　（3）折半查找法（思想和算法）
　　（4）B树及其基本操作、B+树的基本概念（思想和过程）
　　（5）散列（Hash）表（Hash函数和解决冲突的方法的思想和过程）
　　（6）查找算法的时间复杂度、平均查找长度的分析
　　7．排序
　　（1）排序的基本概念
　　（2）基于"插入"思想的排序方法
　　①直接插入排序
　　②折半插入排序（思想和过程）
　　③希尔排序（思想和过程）
　　（3）基于"交换"思想的排序方法
　　①冒泡排序（思想、过程和算法）
　　②快速排序（思想、过程和算法）
　　（4）基于"选择"思想的排序方法
　　①简单选择排序（思想、过程和算法）
　　②堆排序（思想和过程）
　　（5）基于"归并"思想的排序方法
　　二路归并排序（思想、过程）
　　（6）各种常用内部排序算法的特点及应用
　　三、考试形式和试卷结构
　　1.考试时间：180分钟，满分：150分
　　2.题型结构
　　a:选择题(50分)
　　b:应用题(50分)
　　c:算法分析与设计(50分)
　　3.答题方式：闭卷、笔试
　　四、参考书目
　　1.数据结构（用面向对象方法与C++语言描述）（第2版）.殷人昆主编.北京：清华大学出版社.2007.6
　　2.数据结构（C语言版）.严蔚敏、吴伟民编著.北京：清华大学出版社.2007

　   点击【2014年中国石油大学（华东）研究生自命题科目考试大纲】查看更多考研大纲。
【相关阅读】
研究生招生专业索引
2014年研究生考试大纲汇总