数据结构与算法设计自学考试大纲[2]

二课程内容和考核目标

第一章 绪论

本章介绍了数据结构的内容和方法几种基本数据结构以及抽象数据类型的概念阐述了问题数学模型算法与程序之间的关系对算法算法设计目标算法的描述以及算法分析方法作了较详细的介绍

知识点

()基本概念: 数据数据元素数据对象数据结构数据类型抽象数据类型算法时间复杂度空间复杂度等

()问题的分析表达与求解

()算法的描述与分析方法

()程序语言的基本语句与基本结构

()数据结构的表示与定义

()抽象数据类型的表示与定义

自学要求

()熟悉数据结构中各种基本概念和术语

()理解问题求解的全过程特别注意数据抽象表述与处理在问题求解过程中的作用

()理解算法的定义算法的设计目标算法描述的格式以及算法与程序之间的关系

()理解各种数据结构的特点及抽象数据类型的定义格式

()掌握数据结构的研究内容与研究方法

考核目标

()识记有关基本概念基本数据结构及特点

()理解数据数据结构和抽象数据类型与问题求解的关系

()理解算法和程序在问题求解中的作用

第二章 线性表

本章介绍了抽象数据类型线性表的定义及实现着重介绍了顺序表和线性链表的实现并对其中一些关键算法作了分析列举了线性表在多项式运算和动态存储管理中的应用

知识点

()基本概念:线性结构顺序表链表循环链表双向链表静态链表等

()对顺序表进行基本操作的算法

()对线性链表进行基本操作的算法

()对静态链表进行基本操作的算法

()循环链表和双向链表的特点

()表头结点的作用

自学要求

()理解顺序表与链表的优缺点

()理解带表头结点的链表的特点

()理解静态链表的特点

()掌握实现双向链表的插入删除操作的算法

()掌握一元多项式运算

考核目标

()识记有关基本概念与术语

()理解抽象数据类型线性表的定义线性表的存储结构线性表基本操作的实现

()应用线性表解决集合运算和多项式运算

()选择具体问题求解所需的适合的线性表

第三章 排序

本章介绍了五种基本的排序方法并分别给出时间复杂度为(n)的简单排序和时间复杂度为(n log n)的排序法讨论了各算法的稳定性

考核知识点

()基本概念: 排序稳定的排序

()插入排序交换排序选择排序归并排序分配排序的算法及其程序实现

()shell排序快速排序堆排序链式基数排序的算法及其程序实现

()快速排序和归并排序的非递归算法

()稳定的排序方法和不稳定的排序方法

自学要求

()熟悉各种排序的基本思想

()掌握各种排序方法的实现途径(非递归与递归方法)

()掌握各种排序算法的结构(一趟排序与整体排序)

()掌握分析排序算法时间复杂度的方法

()熟悉掌握将算法转换成相应程序的能力

考核目标

()识记有关的基本概念与术语

()理解各排序算法的模型

()分析各排序算法的稳定性

()运用希尔排序堆排序和链式基数排序思想编写相应程序

()为实际应用选择恰当的排序算法

[] [] [] [] [] [] [] [] []