2012年硕士研究生入学考试专业课考试大纲

考试科目代码：817    考试科目名称：数据结构

　　一、考试要求

数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。主要有三个方面：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

 

通过本课程的学习，使学生获得计算机科学各领域的数据结构知识，及有关的应用软件所要用到的各种数据结构知识。掌握常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算法知识。提高软件设计和编程技能。学会初步对不同的存储结构和相应算法的对比，有一定的算法改进能力。

 

　　二、考试内容

　　（一）绪论

　　1. 数据结构的一些基本术语和概念。

　　2. 抽象数据类型定义和使用。

　　3. 算法的基本概念和术语和算法的描述方法。

4. 掌握算法的时间复杂性分析。

 

　　（二）线性表

　　1. 线性表的基本概念和类型定义；

　　2. 顺序表和单链表的常用操作方法及其程序实现；

3. 循环链表和双向链表的定义和它的插入、删除等操作方法。

 

　　（三）栈和队列

　　1. 栈和队列的定义；

　　2. 顺序和链式存储的栈和队列的各种运算的方法及程序实现；

3. 表达式求值等经典问题求解方法及其算法。

 

　　（四）数组和字符串

　　1. 特殊矩阵和稀疏矩阵的存储表示；

　　2. 掌握字符串的简单模式匹配算法；

3. KMP算法。

 

　　（五）树和二叉树

　　1. 二叉树的性质及遍历算法及其有关应用。

2. 二叉树的非递归算法，设计出应用问题的有效算法。

 

　　（六）图

　　1. 图的定义和术语；

　　2. 邻接矩阵和邻接表表示法；

　　3. 图两种遍历的基本思想和算法；

　　4. 求图的最小生成树的prim和kruskal算法；

5. 了解最短路径问题和拓扑排序。

 

　　（七）检索技术

　　1. 查找的基本概念，

　　2. 线性表的顺序查找的思想和算法；

　　3. 二叉查找树的概念以及二叉查找树上查找的基本思想和算法；

4. 平衡二叉树的调整方法；理解哈希表、哈希表构造的基本方法以及处理冲突的方法；以及各种查找方法的时间性能分析。

 

　　（八）内排序

　　1. 内部排序算法并理解其基本思想；

2. 各种内排序算法的优缺点、时间和空间的性能比较以及使用场合。

 

　　三、题型结构

　　1. 名词解释（共5题，每题4分，共20分）

　　2. 填空题（共10题，每题2分，共20分）

　　3. 简答题（共4题，每题10分，共40分）

　　4. 操作题（共4题，每题10分，共40分）

5. 设计分析题（共3题，每题10分，共30分）

 

　　四、参考书目

　　《 数据结构与算法分析C++描述（第3版）》，Mark Allen Weiss 著 张怀勇等译，清华大学出版社，2008年。