808数据结构.doc-中国农业科学院.doc

中国农业科学院 2013年硕士研究生统一入学考试自命题科目考试大纲 科目代码： 808 考试科目：数据结构 基本概念基本，运算能力、逻辑思维能力、和综合所学知识解决实际问题能力二、考试形式和试卷结构 1.试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 2.答题方式 闭卷、笔试。 3.试卷内容结构 考试内容包括数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。题型包括单项选择、填空、简答和写算法题等。 三、考试大纲 1、数据结构概论 数据、数据元素、抽象数据类型、数据结构、数据的逻辑结构与存储结构等概念； 算法的定义、特性、算法的时间复杂度、算法的空间复杂度、递归算法等概念。 线性表 掌握线性表的基本概念及其存储结构 2）掌握顺序表的各种操作（插入、删除等）实现及算法复杂度 掌握单链表的各种操作（插入、删除等）实现及算法复杂度 了解顺序表和链表的特点，对比他们的优缺点。 3、桟和队列 了解栈、队列的基本概念 掌握栈的入桟、出栈操作，并能利用栈解决实际问题 掌握队列的入队、出队操作，并能利用队列解决实际问题。 、数组和广义表 理解多维数组的行主序、列主序存储； 了解特殊矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储 了解广义表的定义、表示和存储方法。 、树和二叉树 了解树和二叉树的基本概念、术语和性质； 掌握二叉树的两种存储结构（顺序存储、二叉链表存储）； 掌握二叉树的先根、中根、后根遍历算法； 掌握常见的构造二叉树的方法 掌握二叉树的层次遍历算法，能够用顺序循环队列演示遍历过程； 掌握建立哈夫曼树和哈夫曼编码的方法及带权外路径长度（WPL）的计算； 了解树和二叉树的相互转换，了解树的存储、遍历。 、图 了解图的基本概念； 掌握图的存储结构（邻接矩阵表示法、邻接表表示法）； 掌握图的两种遍历算法（深度优先有哪些信誉好的足球投注网站遍历、广度优先有哪些信誉好的足球投注网站遍历）； 掌握图的最小生成树算法思想（Prim、Kruskal）； 掌握图的最短路径算法思想（Dijkstra）。 、查找 了解查找的基本概念（查找表、查找、平均查找长度ASL）； 掌握线性表的查找算法（顺序查找、折半查找、分块查找）。会计算查找过程中的比较次数，会分析它们的算法时间复杂度，了解它们的优点和缺点，能够根据实际情况选择适当的查找算法； 掌握二叉排序树的定义以及查找、插入等操作。了解平衡二叉树 掌握散列技术：会利用除余法构造散列函数，掌握处理冲突的两种方法（开放定址法、链地址法），会计算平均查找长度。 、排序 掌握排序的基本概念（排序算法的稳定性、排序算法性能评价）； 掌握各种内排序算法（直接插入排序、折半插入排序、、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序）； 掌握上述排序算法的时间复杂度和空间复杂度，能够根据实际情况选择适当地排序算法。