中国农业科学院

2013年硕士研究生统一入学考试自命题科目考试大纲

科目代码： 808 考试科目：数据结构

一、考查目标

要求考生比较系统地理解数据结构的基本概念和基本理论，掌握数据结构的基本方法，具备一定的运算能力、逻辑思维能力、编程能力和综合运用所学知识分析问题和解决实际问题的能力。

二、考试形式和试卷结构

1.试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟。

2.答题方式

闭卷、笔试。

3.试卷内容结构

考试内容包括数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。题型包括单项选择、填空、简答和写算法题等。

三、考试大纲

1、数据结构概论

1)数据、数据元素、抽象数据类型、数据结构、数据的逻辑结构与存储结构等概念；

2)算法的定义、特性、算法的时间复杂度、算法的空间复杂度、递归算法等概念。

2、 线性表

1） 掌握线性表的基本概念及其存储结构；

2）掌握顺序表的各种操作（插入、删除等）实现及算法复杂度；

3)掌握单链表的各种操作（插入、删除等）实现及算法复杂度；

4)了解顺序表和链表的特点，对比他们的优缺点。

3、桟和队列

1)了解栈、队列的基本概念；

2)掌握栈的入桟、出栈操作，并能利用栈解决实际问题；

3)掌握队列的入队、出队操作，并能利用队列解决实际问题。

4、数组和广义表

1)理解多维数组的行主序、列主序存储；

2)了解特殊矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储；

3)了解广义表的定义、表示和存储方法。

5、树和二叉树

1)了解树和二叉树的基本概念、术语和性质；

2)掌握二叉树的两种存储结构（顺序存储、二叉链表存储）；

3)掌握二叉树的先根、中根、后根遍历算法；

4)掌握常见的构造二叉树的方法；

5)掌握二叉树的层次遍历算法，能够用顺序循环队列演示遍历过程；

6)掌握建立哈夫曼树和哈夫曼编码的方法及带权外路径长度（WPL）的计算；

7)了解树和二叉树的相互转换，了解树的存储、遍历。

6、图

1)了解图的基本概念；

2)掌握图的存储结构（邻接矩阵表示法、邻接表表示法）；

3)掌握图的两种遍历算法（深度优先搜索遍历、广度优先搜索遍历）；

4)掌握图的最小生成树算法思想（Prim、Kruskal）；

5)掌握图的最短路径算法思想（Dijkstra）。

7、查找

1)了解查找的基本概念（查找表、查找、平均查找长度ASL）；

2)掌握线性表的查找算法（顺序查找、折半查找、分块查找）。会计算查找过程中的比较次数，会分析它们的算法时间复杂度，了解它们的优点和缺点，能够根据实际情况选择适当的查找算法；

3)掌握二叉排序树的定义以及查找、插入等操作。了解平衡二叉树；

4)掌握散列技术：会利用除余法构造散列函数，掌握处理冲突的两种方法（开放定址法、链地址法），会计算平均查找长度。

8、排序

1)掌握排序的基本概念（排序算法的稳定性、排序算法性能评价）；

2)掌握各种内排序算法（直接插入排序、折半插入排序、、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序）；

3)掌握上述排序算法的时间复杂度和空间复杂度，能够根据实际情况选择适当地排序算法。