《程序设计方法学》.docVIP

福建农林大学成人教育（函授）学位 课程《》考试大纲 （一）课程性质与考核目的 是国家高等教育自学考试（本科）（二）指定教材 —用C语言描述 中国水利水电出版社，北京，2000.6. 参考书：严蔚敏、吴伟民编著，《数据结构》，清华大学出版社，北京，1997.4. （三）复习方法 （四）内容分类 从自学考试的基本目的和考生的实际情况出发，本大纲将各章节内容划分为重点把握、基本领会、一般了解和不作要求四个层次。考核内容不超出本大纲所列的基本范围。 1、掌握：能熟练掌握本课程中有关概念、基本原理和知识点的含义，并能正确地识记和表述。 2、基本领会：初步熟悉本课程的有关概念、原理和方法间的区别和联系，基本掌握的一般。考核目标的重要程度仅次于重点把握。 3、了解：内容作一般性了解，起系统性学习作用。 4、不作要求：难度过大或与其它课程有所重复，不符合自考考生实际情况的均不作要求。 1．1 数据结构在计算机科学与技术中所处的地位 1．1．1 什么是数据结构 1．1．2 《数据结构》课程的地位 1．2 基本概念和术语 1．3 数据类型和抽象数据类型　 4算法描述与算法评价 1．4．1 算法描述 1．4．2 算法的设计要求 1．4．3 算法的评价 3、本章重点：基本概念及抽象数据类型 4、本章难点：抽象数据类型与数据结构、数据类型等概念之间的联系与区别；算法复杂性概念、算法分析的基本方法 第二章 线性表（4学时） 1、目的要求 理解线性表的概念； 掌握线性表的基本运算 掌握线性表的存储结构 理解循环链表结构； 循环链表的概念； 空循环链表； 遍历循环链表； 循环链表的和并。 理解双链表的结构； 双链表的概念； 双链表中元素的位置； 双链表中元素的插入方法； 双链表中元素的删除方法； 5) 双链表中元素的定位方法。 2、要点 2．1线性表的基本概念 2．1．1 线性表的逻辑结构 2．1．2 线性表的运算 2线性表的顺序存储结构 2．2．1 顺序表 2．2．2 顺序表上的基本运算 2．3 线性表的链式存储结构 2．3．1 单链表及单链表上的基本运算 2．3．2 循环链表 2．3．3 双向链表 2．4 线性表顺序存储结构和链式存储结构 2．5 线性表的应用举例 3、本章重点：线性表的运算 4、本章难点：算法复杂度的估算 第三章 栈和队列（4学时） 1、目的要求 （1）深刻理解栈的概念； 栈的数学模型； 栈的逻辑特征； 3）栈的五种基本运算。 （2）掌握栈的数组实现方法； 类型说明； 压栈运算； 弹栈运算； （3）掌握栈的指针实现方法； 1）类型说明； 2）压栈运算； 弹栈运算； （4）掌握栈的应用 1）表达式求值； 2）递归的实现； （5）理解队列的概念； 1）队列的数学模型； 2）队列的逻辑特征； 3）队列所支持的5种基本运算； （6）掌握用指针实现队列的方法； 1）类型说明； 2）入队运算； 3）出队运算； （7）掌握用循环数组实现队列的方法； 类型说明； 队列满状态； 队列空状态； 入队运算； 出队运算； 2、要点 　3．1 栈 3．1．1 栈的定义和操作 3．1．2 栈的顺序存储结构 3．1．3 栈的链式存储结构 3．2 栈的应用举例 3．2．1 表达式求值 3．2．2 递归的实现 3．3 队列 3．1．1队列的定义和操作 3．1．2 队列的顺序存储结构 3．1．3队列的链式存储结构 3．4 队列的应用举例 3、本章重点：栈、队列的特点及其运算 4、本章难点：栈的应用（表达式求值、递归的实现）；循环队列的队满、队空条件 第四章 串（2学时） 1、目的要求 深刻理解串的概念： 1）串的数学模型； 2）串的逻辑特征； 3）串所支持的9种基本运算。 掌握用数组实现串的方法： 类型说明； 存储结构。 掌握用指针实现串的方法； 类型说明； 存储结构。 理解串的模式匹配运算： 模式匹配的定义； 朴素模式匹配的算法； KMP 算法的思想（不作要求Next(i) 函数的计算方法（不作要求KMP算法）（不作要求不作要求不作要求不作要求不作要求不作要求不作要求m元多项式的表示 3、本章重点：矩阵压缩存储及广义表 4、本章难点：稀疏矩阵的乘法、加法算法、广义表的存储 第六章 树 （8学时） 1、目的要求 深刻理解树的概念： 树的定义； 关于树的常用术语的意义； 树的结构特征。 深刻理解二叉树的概念和基本性质： 二叉树的定义； 二叉树的重要性质； 满二叉树与近似满二叉树的特征。 二叉树的存储结构 掌握树