《数据结构》考试大纲 (2).doc

《《数据结构》考试大纲 (2).doc》由会员分享，可在线阅读，更多相关《《数据结构》考试大纲 (2).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构考试大纲数据结构考试大纲I I课程性质与设置目的：课程性质与设置目的：一、一、本课程的性质和特点、在本专业中的地位、设置目的与作用本课程的性质和特点、在本专业中的地位、设置目的与作用数据结构 课程是网络教育考试的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。设立本门课程的目的是通过学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还

2、应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。二、本课程的基本要求二、本课程的基本要求通过本课程的学习，学生应比较系统地从数据结构的逻辑结构、存储结构和运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构；并且掌握在各种常用的数据结构上实现得排序和查找算法，同时对算法的时间和空间复杂性有一定得分析能力；针对简单的应用问题，应能选择合适得数据结构及设计有效得算法解决之。这对于培养学生运用数据结构解决实际问题能力的培养有着重要的意义。IIII 课程内容与考核标准

3、：课程内容与考核标准：第一章第一章绪论绪论一、学习目的和要求一、学习目的和要求本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。本章要了解数据的抽象类型定义。理解算法在实际问题中的应用。重点掌握各种基本概念和术语、算法描述和分析的方法。二、课程内容二、课程内容第一节什么是数据结构第二节基本概念和术语第三节抽象数据类型的表示与实现第四节算法和算法分析三、考核知识点三、考核知识点1、合适的数据结构在解决实际应用问题中的关键性；以及学习数据结构的意义。2、数据、数据元素、数据项、数据结构等基本概念。3、数据结构的四种逻辑结构和两种存储结构表示方法。4、抽象数据类型的表示和实现5、

4、算法的五个特点。6、算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。7、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。四、考核要求四、考核要求1.识记1)数据结构的基本概念和术语。2)合适的数据结构在解决实际应用问题中的关键性，以及学习数据结构的意义。3)数据结构的四种逻辑结构和两种存储结构表示方法。2.领会1)算法的描述和分析：算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度第二章第二章线性表线性表一、学习目的和要求一、学习目的和要求本章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算

5、。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是熟练掌握顺序表和单链表上实现的各种基本运算及相关的时间性能分析，难点是在循环链表和双向链表存储结构中各种基本运算的实现。二、课程内容二、课程内容第一节线性表的类型定义第二节线性表的顺序表示和实现第三节线性表的链式表示和实现三、考核知识点三、考核知识点1、线性表的类型定义2、顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析3、链式表示和实现，单链表、双链表、循环链表链接方式上的区别；4、单链表上实现的建表、查找、插入和删除等基本算法及其时间

6、复杂度。5、双向链表的定义和相关算法。6、顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。四、考核要求四、考核要求1.识记1)线性表的逻辑结构特征；2)线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。2.领会1)顺序表和链表的比较，各自的优缺点。2)针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。3.综合应用1)顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析。2)单链表、双链表、循环链表链接方式上的区别；3)单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。4)双链表的定义和相关算法

7、。第三章第三章栈和队列栈和队列一、学习目的和要求一、学习目的和要求本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列。本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理二、课程内容二、课程内容第一节栈第二节栈的应用举例第四节队列三、考核知识点三、考核知识点1、栈的抽象数据类型的定义2、栈的表示和实现3、栈的简单应用4、抽象数据类型队列的定义5、队列的链式表示和实现6、队列的顺序表示和实现四、考核要求四、考核要求1.领会1)栈和队列的特点，栈和队列各自的使用情况

8、。2.综合应用1)栈的逻辑结构特点，栈与线性表的异同。2)顺序栈和链栈上实现进栈、退栈等基本算法。3)利用栈解决简单的实际问题。4)队列逻辑结构特点，队列与线性表的异同。5)顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。6)顺序队列的“假溢出”现象及其采用循环队列进行解决的方法。第四章第四章串串一、学习目的和要求一、学习目的和要求本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算。本章重点是掌握串的基本概念和三种表示方法，这也是难点。二、课程内容二、课程内容第一节串类型的定义第二节串的表示和实现三、考核知识点三、考核知识点1、串的定义、空串、空格串、子串、主串、串相等。

9、2、串的基本操作。3、串的顺序存储结构及在顺序存储结构下基本操作的实现。4、串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。5、串的链式存储表示四、考核要求四、考核要求1.领会1)串的有关概念及其基本运算2.简单应用1)串的三种存储表示2)使用串解决与串相关的简单的应用问题第五章第五章数组和广义表数组和广义表一、学习目的和要求一、学习目的和要求本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求熟悉这些内容。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其表头表尾的运算，难点是稀疏矩阵的压缩存储表示下转置运算。二

10、、课程内容二、课程内容第一节数组的定义第二节数组的顺序表示和实现第三节矩阵的压缩存储第四节广义表的定义第五节广义表的存储结构三、考核知识点三、考核知识点1、数组的顺序存储结构。2、二维数组的按行存储及按列存储和计算数组元素的地址计算公式。3、矩阵的压缩存储、特殊矩阵的表示。4、广义表的定义和操作(HEAD 和 TAIL)5、广义表的 2 种存储结构四、考核要求四、考核要求1.领会1)多维数组的逻辑结构特征2)多维数组的顺序存储结构及其地址计算方式3)特殊矩阵和稀疏矩阵的概念4)稀疏矩阵的压缩存储方式三元组表5)稀疏矩阵的两种转置运算算法6)广义表的概念、广义表和线性表的联系7)广义表表头和表尾

11、的概念及广义表两个特殊的基本运算，取表头和取表尾。8)广义表的两种存储结构第六章第六章树和二叉树树和二叉树一、学习目的和要求一、学习目的和要求本章的目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。本章重点是掌握二叉树及其二叉树的遍历。难点是掌握与树有关的简单应用。二、课程内容二、课程内容第一节树的定义和基本术语第二节二叉树第三节遍历二叉树和线索二叉树第四节树和森林第六节赫夫曼树及其应用三、考核知识点三、考核知识点1、树的定义和术语。2、二叉树(完全二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构顺序表示法和链

12、表表示法。3、二叉树的三种遍历方法及相应的递归算法。4、二叉树线索化的目的及其实质。5、树的存储表示法孩子表示法、双亲表示法、孩子兄弟表示法。6、树和森林及二叉树的转换方法。7、树和森林的遍历8、树的路径长度、树的带权路径长度、赫夫曼树（最优二叉树）的构造方法。9、赫夫曼编码方法四、考核要求四、考核要求1.领会1)树的逻辑结构特征2)树的不同表示方法3)树的常用术语及含义4)二叉树线索化的目的及实质5)在中序线索树中查找给定结点的中序前驱和中序后继的方法6)树和森林与二叉树之间的转换方法7)树的各种存储结构及其特点8)树的遍历方法2.简单应用1)二叉树的定义及树与二叉树的差别2)二叉树的性质，

13、了解相应的证明方法3)二叉树的两种存储结构、特点及适用范围4)最优二叉树和前缀编码的概念及特点5)赫夫曼算法的思想6)根据给定的叶结点及其权值构造出相应的最优二叉树7)根据最优二叉树构造对应的赫夫曼编码3.综合应用1)二叉树的三种遍历算法，理解其执行过程2)根据不同的遍历方法，应能得出其相应的结点访问次序3)以遍历算法为基础，设计有关算法解决简单的应用问题IIIIII 有关说明与实施要求：有关说明与实施要求：一、关于考核目标的说明一、关于考核目标的说明为了使考试内容和考试要求标准化，本大纲在列出考试内容的基础上，对各章节规定了考核目标。考核目标包含考核知识点和考核要求两项。辅导教师和学生可以通

14、过对考核目标的阅读，进一步明确考试范围、内容和要求，从而可以更为系统地学习和把握教材。同时，考核目标还能够进一步明确考试命题范围，更正确地安排试题的知识能力层次和把握试题的难易程度。本大纲在考核目标中，按照识记、领会、简单运用和综合运用等四个层次规定学生通过学习应该达到的能力层次要求。四个能力层次是递进等级关系。各能力层次的含义是：1、识记：能够了解有关的名词、概念、知识的含义，并能正确认识和表述、选择和判断。2、领会：在识记的基础上，能够比较全面地把握基本概念、基本事实、基本理论模型、基本方法，能把握有关概念、事实、理论模型、分析方法之间的区别和联系。并能根据考核的不同要求，做出正确的解释、

15、说明和论述。3、简单运用：在领会的基础上，能够运用本课程中规定的少量的知识点，分析和解释有关的一般的应用问题。例如，简单的算法设计和时间性能分析。4、综合运用：指在简单运用的基础上，能够综合运用所学习过的多个知识点，分析和解决较复杂的应用问题，例如，设计较复杂的算法。二、关于教材、参考教材和参考读物（根据课程的实际情况写内容）二、关于教材、参考教材和参考读物（根据课程的实际情况写内容）1 1、教材、教材：数据结构教程,殷人昆,清华大学出版社。2 2、参考教材、参考教材：数据结构苑森淼等，吉林科学技术出版社。数据结构 黄刘生主编，全国高等教育自学考试指导委员会组编，经济科学出版社。2、参考读物参

16、考读物：数据结构题集严蔚敏吴伟民著，清华大学出版社 1999 年版。三、关于本门课程考试命题的若干规定三、关于本门课程考试命题的若干规定1、本门课程的命题考试，根据本大纲所规定的考试内容和考试目标来确定考试范围和考核要求。考试命题会覆盖各章，并适当突出重点章节，体现本课程的内容重点。2、本课程在试题中对不同能力层次要求的分数比例一般为：识记占 20%，领会占 30%，简单应用占 30%，综合运用占 20%。3、试题合理安排难易度结构。试题难易度可分为：易、较易、较难和难四个等级。每份试卷中，不同难度试题的分数比例为：2：3：3：2。4、本课程考试的题型，一般有填空、单项选择、简答、应用、算法设计等五种类型。