中央广播电视大学计算机应用专业(20).doc

中央广播电视大学计算机应用专业
数据结构课程考核说明修改版（2006年）
第一部分考核说明

《数据结构》是全国电大计算机应用专业的一门核心课程，起到承上启下的作用和地位，主要任务是讨论数据的各种逻辑结构、存储结构以及相应运算的算法。
考核对象：全国电大系统计算机应用专业“开放教育试点”的学生。
教学媒体：
主教材《数据结构》许卓群主编中央广播电视大学出版社出版。
实验教材《数据结构实验》徐孝凯编中央广播电视大学出版社出版。
录像教材《数据结构》20讲刘杰主讲中央电大音像出版社出版。
辅助教材《数据结构习题解析》徐孝凯编中央电大教育杂志社出版，通过各地电大教材发行部门统一征订发行。
命题依据：本考核说明严格按照中央电大计算机应用专业《数据结构》课程教学大纲编写。
考核要求：考核学生掌握和运用数据结构基本概念和知识分析和编写数据处理算法的能力。具体考核要求分为以下3个层次：
了解：了解数据结构的一些基本概念。包括线性表、栈、队列、链表、树、二叉树、二叉搜索树、堆、哈夫曼树、图、网、二分查找、索引查找、分块查找、散列查找、堆排序、快速排序、归并排序等概念。
掌握：能够分析现成程序和算法，即指出功能或写出运行结果；能够写出对已知数据进行相应运算的数据变化过程和最终结果。
应用：能够根据解决问题的需要选择数据结构和编写算法。
命题原则：
1.严格按照该课程教学大纲和考核说明的要求命题。
2.试题的覆盖面较广，并适当突出重点。
3．试题的难易程度和题量适当，按难易程度分为三个层次：容易占40%，一般占40%，较难占20%。
4．题型有六种：单选题、填空题、运算题、阅读算法并回答问题、算法填空、编写算法。
考核形式：
采用期末卷面考核与形成性考核相结合的方式。形成性考核占20分，视平时上机和作业完成情况而定，由所在班级的任课教师给定，由省（市、自治区）级电大认定；期末卷面考核占80分，由中央电大统一命题并采用闭卷方式，答卷时限从2006年下学期开始为90分钟。两方面成绩累计达到60分者为及格。

第二部分考核内容及要求

第一章绪论
重点掌握的内容：
1.数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。
2.集合结构、线性结构、树结构和图结构的特点。
3.抽象数据类型的定义和表示方法。
4.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。
5.普通函数重载和操作符函数重载的含义，定义格式和调用格式。
6.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。
7.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。
对于本章的其余内容均作一般掌握。

第二章线性表
重点掌握的内容：
1.线性表的定义和抽象数据类型的描述，线性表中插入、删除等操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。
3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4.单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。
5.带表头附加结点的链表、循环链表、双向链表的结构特点。
6.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。
7.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。
对于本章的其余内容均作一般掌握。

第三章稀疏矩阵和广义表
重点掌握的内容：
1.稀疏矩阵的定义和三元组线性表表示。
2.稀疏矩阵的顺序存储、带行指针向量的链接存储，它们中非零元素结点的结构。
3.稀疏矩阵的转置运算和算法描述。
4.广义表的定义和表示，广义表长度和深度的计算。
5.广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法。
对于本章的其余内容均作一般了解。

第四章栈和队列
重点掌握的内容：
1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。
3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。
5.算术表达式的中缀表示和后缀表示，以及相互转换的规则。
6.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
7.队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。
8.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。
9.利用栈和队列解决简单问题的算