数据结构专升本考试大纲.doc

数据结构专升本考试大纲一、考试的基本要求数据结构课程是计算机科学与技术专业的必修专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重实践能力,通过实践验证算法的正确性,掌握和巩固所学理论知识。设立本门课程的目的是通过学习，使学生学会分析研究数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件开发设计课程打下坚实的知识基础。二、考试的范围和内容考核知识点一：数据结构与算法的概述本章目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。本章要了解数据的抽象类型定义。理解算法在实际问题中的应用。重点掌握各种基本概念和术语、算法描述和分析的方法考核要求：识记：运算的概念、存储结构和运算实现、算法分析掌握：数据、数据元素、数据项、数据类型、数据结构、抽象数据类型应用：算法及其描述 考核知识点二：线性表本章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。考核要求：识记：线性结构的概念、线性表的概念掌握：线性表的链式存储结构、顺序表与链表的比较应用：线性表的顺序存储结构，插入、删除和定位运算在单链表上的实现考核知识点三：栈和队列本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列。考核要求：识记：栈的定义、队列的定义掌握：栈的顺序实现、栈的链接实现、队列的顺序实现应用：循环队的组织方法及在其上进行人队、出队运算的方法和队满、队空的条件。考核知识点四：串本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算。本章重点是掌握串的基本概念和三种表示方法。考核要求：识记：串的定义掌握：串的定长顺序实现考核知识点五：数组与广义表本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求熟悉这些内容。考核要求：识记：数组元素地址的计算、广义表的特点和结构掌握：特殊矩阵的压缩存储考核知识点六、树和二叉树本章的目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。考核要求：识记：树形结构的基本概念和术语、树和森林、二叉树的定义、二叉树的顺序存储结构掌握：二叉树的链式存储结构、哈夫曼树的概念、构造哈夫曼树的方法应用：二叉树的遍历考核知识点七、图本章的目的是介绍图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。本章重点是掌握图的两种存储结构上实现的遍历算法。难点是图的应用算法：最小生成树，求最短路径以及拓扑排序。只要求掌握这些算法的基本思想及时间性能。考核要求：识记：树形结构的基本概念和术语、树和森林掌握：图的遍历，拓扑排序、关键路径、图的概念、图的存储结构最小生成树应用：Prime算法、迪杰斯特拉方法的基本思想考核知识点八、 查找本章的目的是介绍线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。重点掌握顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。难点是二叉排序树上的删除算法。考核要求：识记：查找表的基本概念掌握：静态查找表的实现、二叉排序树的查找算法及其基本思想应用：哈希表、在开散列表上实现查找、插入和删除运算的思想和算法考核知识点九、 排序本章的目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序、堆排序、归并排序和基数排序的基本思想和排序过程。难点是这四类排序算法的实现。考核要求：识记：排序的基本概念、归并排序掌握：堆的定义、堆的调整方法和“筛选”过程，建堆的方法、冒泡排序算法、直接选择排序基本思想应用：直接插入排序的算法和性能、折半插入排序算法、快速排序的算法和性能