中国农业科学院
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)掌握上述排序算法的时间复杂度和空间复杂度,能够根据实际情况选择适当地排序算法。