《数据结构》课程标准

《《数据结构》课程标准》由会员分享，可在线阅读，更多相关《《数据结构》课程标准（19页珍藏版）》请在金锄头文库上搜索。

1、数据结构数据结构课程标准课程标准数据结构课程标准一、适用对象五年高职学生二、课程性质数据结构课程是介于数学、计算机硬件和软件课程三者之间综合性的学科，本课程主要使学生体会“算法的设计建立于逻辑结构，算法的实现依赖于物理（存储）结构“，并能根据实际情况选择相应的数据结构和算法，所以本课程教学强调思维训练，为随后的程序设计和技能训练打好基础。数据结构课程是我校信息技术系软件技术专业的一门专业技术基础课。它是计算机程序设计的重要理论基础；它所讨沦的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其它课程，还是对从事软件工程的开发，都有着不可替代的作用。三、参考学时64 学时。四、学分4 学分。

2、五、课程目标从课程性质上讲， 数据结构是一门软件专业技术基础课。通过本课程的教学，达到的教学目标是： 知道数据结构这门学科的性质、地位和独立价值。知道这门学科的研究范围、分析框架、研究方法、学科进展和未来方向。 理解这门学科的基本概念、主要结构类型和算法，尤其是数据结构的三要素、存储结构的实现和算法的评价策略。 学会分析研究计算机加工的数据的结构特性，以便为实际应用问题所涉及到的数据选择适当的逻辑结构、存储结构及其算法。 逐步理解算法的时间分析和空间分析的技术。 培养数据抽象能力；训练复杂程序设计的技能；要求编写的程序结构清楚和正确易读，养成良好程序设计习惯。六、设计思路 按照“以能力为本位、

3、以职业实践为主线、以项目课程为主体的模块化专业课程体系“的总体设计要求，紧紧围绕完成工作任务的需要来选择和组织课程内容，突出工作任务与知识的联系，让学生在职业实践活动的基础上掌握知识，增强课程内容与职业能力要求的相关性，提高学生的就业能力。 依据各项目模块的内容总量以及在该门课程中的地位分配各项目模块的学时数。 学习程度用语主要使用“了解“、“理解“、“能“或“会“等用语来表述。“了解“用于表述事实性知识的学习程度，“理解“用于表述原理性知识的学习程度，“能“或“会“用于表述技能的学习程度。七、内容纲要模块一 绪论 1参考学时 2 学时2工作任务 基本概念和术语 算法的描述和分析3学习目标 什

4、么是数据结构 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言 数据结构的抽象层次 算法定义 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂一 基本概念和术语参考学时1 学时工作任务了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系学习目标理解数据结构的概念抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言数据结构的抽象层次实践技能专业对课程需求发展知识要点常用的基本概念和术语二 算法的描述

5、和分析参考学时1 学时工作任务算法复杂度的分析方法学习目标掌握算法定义掌握性能分析与度量实践技能性能分析与度量知识要点掌握算法描述和分析的方法模块二 线性表 1参考学时 12 学时2工作任务 线性表的逻辑结构 线性表的顺序存储结构 线性表的链式存储结构3学习目标 作为抽象数据类型的数组 顺序表的定义和特点 掌握单链表、循环链表、双向链表一 线性表的逻辑结构参考学时4 学时工作任务了解线性表的逻辑结构学习目标介绍线性表的逻辑结构掌握各种存储表示方法掌握存储结构上实现基本运算实践技能基本运算的实现知识要点常用的基本概念和术语二 线性表的顺序存储结构参考学时4 学时工作任务线性表的顺序存储结构学习目

6、标掌握顺序表的定义和特点；顺序表的类定义掌握顺序表的查找、插入和删除；实践技能使用顺序表的事例知识要点顺序表的数组定义方式及实现三 线性表的链式存储结构参考学时4 学时工作任务线性表的链式存储结构学习目标掌握单链表的结构；单链表的类定义掌握循环链表的类定义；用循环链表解约瑟夫问题掌握双向链表的结构和定义实践技能链表的游标类定义及其应用方法知识要点单链表、循环链表及双向链表的定义及实现模块三 栈和队列 1参考学时 8 学时2工作任务 栈的概念、存储结构及其基本操作 队列的概念、存储结构及其基本操作 栈与队列的应用3学习目标 掌握栈的定义、栈的存储及其实现，队列的定义、存储及其实现，循环队列的实现

7、 理解利用栈进行算法描述 了解栈与递归算法实现一 栈的概念、存储结构及其基本操作参考学时2 学时工作任务栈的概念、存储结构及其基本操作学习目标掌握栈的定义掌握栈的存储及其实现实践技能掌握栈在两种存储结构上实现的基本运算知识要点栈的链接存储表示二 队列的概念、存储结构及其基本操作参考学时2 学时工作任务队列的概念、存储结构及其基本操作学习目标掌握队列的定义掌握队列的存储及其实现掌握循环队列的实现实践技能掌握队列在两种存储结构上实现的基本运算知识要点循环队列中对边界条件的处理三 栈与队列的应用参考学时4 学时工作任务栈与队列的应用学习目标掌握利用栈进行算法描述掌握栈与递归算法实现实践技能懂得在什么

8、样的情况下能够使用栈或队列知识要点优先级队列的定义及链表实现模块四 串 1参考学时4 学时2工作任务 串及其运算 串的存储结构3学习目标 掌握串的的定义 掌握串的存储表示方法 了解串的匹配查找朴素算法和改进算法一 串及其运算参考学时2 学时工作任务串及其运算学习目标掌握串的定义掌握串上实现的模式匹配算法实践技能掌握串上实现的模式匹配算法知识要点串的定义二 串的存储结构参考学时2 学时工作任务串的存储结构学习目标掌握串的逻辑结构掌握串的存储结构实践技能串的匹配查找：朴素算法和改进算法知识要点串的逻辑结构、存储结构及其中上的基本运算模块五 数组和广义表1参考学时4 学时2工作任务 多维数组 矩阵的

9、压缩存储 广义表的概念3学习目标 掌握多维数组的逻辑结构特征 掌握多维数组的存储方式 掌握特殊矩阵和稀疏矩阵的压缩存储方法 掌握广义表的概念 掌握广义表的表示及操作一 多维数组参考学时2 学时工作任务多维数组学习目标掌握多维数组的逻辑结构特征掌握多维数组的存储方式实践技能掌握多维数组的存储方式知识要点多维数组的表示和算法二 矩阵的压缩存储和广义表参考学时2 学时工作任务矩阵的压缩存储和广义表学习目标掌握掌握特殊矩阵和稀疏矩阵的压缩存储方法掌握广义表的概念掌握广义表的表示及操作实践技能稀疏矩阵的压缩存储表示下实现的算法知识要点矩阵的压缩存储、广义表的定义及其求表头和表尾的运算模块六 树和二叉树1

10、参考学时8 学时2工作任务 树和二叉树 二叉树的遍历和线索化 树和森林 哈夫曼树及其应用3学习目标 了解树和森林的概念 了解线索化二叉树的特性及寻找某结点的前驱和后继的方法 掌握二叉树的概念、性质及二叉树的表示 掌握二叉树的遍历方法及树的游标类定义 掌握树与森林的实现和遍历方法 掌握二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握哈夫曼树的实现方法及哈夫曼编码的概念一 树和二叉树参考学时2 学时工作任务树和二叉树学习目标掌握树的定义；树的术语；树的抽象数据类型掌握二叉树的定义；二叉树的性质；二叉树的抽象数据类型掌握二叉树的数组表示；链表存储表示实践技能二叉树的数组表示；链表存储表示知识

11、要点树和二叉树的定义二 二叉树的遍历和线索化参考学时2 学时工作任务二叉树的遍历和线索化学习目标掌握二叉树的遍历方法及树的游标类定义掌握二叉树遍历算法的有关应用掌握二叉树的线索；中序线索化二叉树；前序与后序的线索化实践技能应用二叉树遍历的事例知识要点二叉树遍历、线索化二叉树三 树和森林参考学时2 学时工作任务树和森林学习目标掌握树的存储表示掌握森林与二叉树的转换掌握树与森林的实现和遍历方法掌握二叉树的计数实践技能树与森林的实现和遍历方法知识要点树的存储表示、森林与二叉树的转换四 哈夫曼树及其应用参考学时2 学时工作任务哈夫曼树及其应用学习目标掌握哈夫曼树路径长度掌握哈夫曼编码的概念实践技能哈夫

12、曼树的实现方法知识要点哈夫曼编码的概念模块七 图1参考学时8 学时2工作任务 图的基本概念和存贮结构 最小生成树的算法 最短路径，拓扑排序和关键路径算法3学习目标 掌握图的基本概念和图的存储表示 掌握图的两种遍历方法与求解连通性问题的方法 掌握构造最小生成树的 prim 和 kruskal 方法 掌握活动网络的拓扑排序方法 掌握求解关键路径的方法一 图的基本概念和存贮结构参考学时2 学时工作任务图的基本概念和存贮结构学习目标掌握图的基本概念掌握图的存储表示：邻接矩阵；邻接表；邻接多重表掌握图的两种遍历方法与求解连通性问题的方法实践技能图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连

13、通分量知识要点图的定义，有关术语和存贮结构，图的两种遍历算法二 最小生成树的算法参考学时2 学时工作任务最小生成树的算法学习目标掌握最小生成树的两种算法：克鲁斯卡尔算法；普里姆算法实践技能构造最小生成树的 prim 和 kruskal 方法知识要点最小生成树的两种算法三 最短路径，拓扑排序和关键路径算法参考学时4 学时工作任务最短路径，拓扑排序和关键路径算法学习目标掌握活动网络的拓扑排序方法掌握用顶点表示活动的网络；用边表示活动的网络掌握求解关键路径的方法实践技能最短路径，拓扑排序和关键路径算法知识要点最短路径，拓扑排序和关键路径的概念模块八 查找1参考学时8 学时2工作任务 基本概念 线性表

14、的查找 树的查找 散列技术3学习目标 了解静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法 了解动态索引结构，包括 b_树、b+树的搜索和构造方法 掌握静态搜索表的顺序搜索和折半搜索方法 掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 掌握 AVI 树的构造、性能分析方法 掌握散列法，包括散列函数的构造、解决冲突的方法一 基本概念参考学时2 学时工作任务查找的基本概念学习目标掌握简单的搜索结构掌握搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索实践技能简单的搜索结构知识要点搜索的概念二 线性表的查找参考学时2 学时工作任务线性表的查找学习目标了解静态索引

15、结构，线性索引、倒排索引、静态索引树的搜索和构造方法掌握线性索引；倒排表实践技能线性索引、倒排索引的应用知识要点静态索引结构，线性索引三 树的查找参考学时2 学时工作任务树的查找学习目标了解动态索引结构，包括 b_树、b+树的搜索和构造方法掌握二叉搜索树的定义掌握二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除掌握与二叉搜索树相关的中序游标类掌握 AVI 树的定义；平衡化旋转；AVI 树的插入和删除；AVI 树的高度实践技能二叉搜索树上的搜索知识要点二叉搜索树的定义四 散列技术参考学时2 学时工作任务散列技术学习目标掌握词典的抽象数据类型掌握散列表与散列方法；散列函数掌握处理溢出的闭散列

16、方法；处理溢出的开散列方法；散列表分析实践技能解决冲突的方法知识要点散列函数的构造模块九 排序1参考学时10 学时2工作任务 插入排序 交换排序 选择排序 归并排序 基数排序和外排序3学习目标 掌握排序的基本概念和性能分析方法 掌握插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法 了解基数排序方法及其性能分析方法 了解多路平衡归并等外排序方法及败者树构造方法 了解生成初始归并段及败者树构造方法 了解最佳归并树的建立方法一 插入排序参考学时2 学时工作任务插入排序学习目标掌握排序的基本概念和性能分析方法掌握插入排序的方法及其性能分析方法掌握直接插入排序；对分插入排序；链表插入排序；希尔排序实践技能插入排序的方法知识要点内部排序方法的基本思想二 交换排序参考学时2