《数据结构》课程标准

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

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

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

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

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

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

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

8、与队列的应用4 -4-Z 八rr . 参考学时4学时工作任务栈与队列的应用学习目标掌握利用栈进行算法描述 掌握栈与递归算法实现实践技能懂得在什么样的情况下能够使用栈或队列知识要点优先级队列的定义及链表实现模块四串1 .参考学时4学时2 .工作任务串及其运算串的存储结构3 .学习目标掌握串的的定义掌握串的存储表示方法 了解串的匹配查找朴素算法和改进算法串及其运算4 -4-Z 八rr . 参考学时2学时工作任务串及其运算学习目标掌握串的定义掌握串上实现的模式匹配算法实践技能掌握串上实现的模式匹配算法知识要点串的定义二串的存储结构4 -4-Z 八rr . 参考学时2学时工作任务串的存储结构学习目标掌

9、握串的逻辑结构掌握串的存储结构头践技能串的匹配查找：朴素算法和改进算法知识要点串的逻辑结构、存储结构及其中上的基本运算模块五数组和广义表1 .参考学时4学时2 .工作任务多维数组矩阵的压缩存储广义表的概念3 .学习目标掌握多维数组的逻辑结构特征掌握多维数组的存储方式掌握特殊矩阵和稀疏矩阵的压缩存储方法掌握广义表的概念掌握广义表的表示及操作多维数组4 -4-Z 八rr . 参考学时2学时工作任务多维数组学习目标掌握多维数组的逻辑结构特征 掌握多维数组的存储方式头践技能掌握多维数组的存储方式知识要点多维数组的表示和算法矩阵的压缩存储和广义表4 -4-Z 八rr . 参考学时2学时工作任务矩阵的压缩

10、存储和广义表学习目标掌握掌握特殊矩阵和稀疏矩阵的压缩存储方法掌握广义表的概念掌握广义表的表示及操作头践技能稀疏矩阵的压缩存储表示下实现的算法知识要点矩阵的压缩存储、广义表的定义及其求表头和表尾的运算模块六树和二叉树1 .参考学时8学时2.工作任务树和二叉树二叉树的遍历和线索化树和森林哈夫曼树及其应用3 学习目标 了解树和森林的概念 了解线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握二叉树的概念、性质及二叉树的表示掌握二叉树的遍历方法及树的游标类定义掌握树与森林的实现和遍历方法掌握二叉树的计数方法及从二叉树遍历结果得到二叉树的方法掌握哈夫曼树的实现方法及哈夫曼编码的概念树和二叉树4 -4-

11、Z 八rr . 参考学时2学时工作任务树和二叉树学习目标掌握树的定义；树的术语；树的抽象数据类型掌握二叉树的定义；二叉树的性质；二叉树的抽象数据类型 掌握二叉树的数组表示；链表存储表示实践技能二叉树的数组表示；链表存储表示知识要点树和二叉树的定义二叉树的遍历和线索化4 -4-Z 八rr . 参考学时2学时工作任务二叉树的遍历和线索化学习目标掌握二叉树的遍历方法及树的游标类定义掌握二叉树遍历算法的有关应用掌握二叉树的线索；中序线索化二叉树；前序与后序的线索化实践技能应用二叉树遍历的事例知识要点二叉树遍历、线索化二叉树树和森林4 -4-Z 八rr . 参考学时2学时工作任务树和森林学习目标掌握树的

12、存储表示掌握森林与二叉树的转换掌握树与森林的实现和遍历方法掌握二叉树的计数实践技能树与森林的实现和遍历方法知识要点树的存储表示、森林与二叉树的转换四哈夫曼树及其应用4 -4-Z 八rr . 参考学时2学时工作任务哈夫曼树及其应用学习目标掌握哈夫曼树路径长度掌握哈夫曼编码的概念头践技能哈夫曼树的实现方法知识要点哈夫曼编码的概念模块七图1.参考学时8学时2.工作任务图的基本概念和存贮结构最小生成树的算法最短路径，拓扑排序和关键路径算法3 .学习目标 掌握图的基本概念和图的存储表示掌握图的两种遍历方法与求解连通性问题的方法 掌握构造最小生成树的 prim和kruskal方法掌握活动网络的拓扑排序方法

13、 掌握求解关键路径的方法图的基本概念和存贮结构4 -4-Z 八rr . 参考学时2学时工作任务图的基本概念和存贮结构学习目标掌握图的基本概念掌握图的存储表示：邻接矩阵；邻接表；邻接多重表 掌握图的两种遍历方法与求解连通性冋题的方法实践技能图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量知识要点图的定义，有关术语和存贮结构，图的两种遍历算法最小生成树的算法4 -4-Z 八rr . 参考学时2学时工作任务最小生成树的算法学习目标掌握最小生成树的两种算法：克鲁斯卡尔算法；普里姆算法实践技能构造最小生成树的prim和kruskal方法知识要点最小生成树的两种算法三 最短路径，拓扑排序

14、和关键路径算法4 -4-Z 八rr . 参考学时4学时工作任务最短路径，拓扑排序和关键路径算法学习目标掌握活动网络的拓扑排序方法掌握用顶点表示活动的网络；用边表示活动的网络 掌握求解关键路径的方法头践技能最短路径，拓扑排序和关键路径算法知识要点最短路径，拓扑排序和关键路径的概念模块八查找1 .参考学时8学时2.工作任务基本概念线性表的查找树的查找散列技术3 .学习目标 了解静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法 了解动态索引结构，包括 b_树、b+树的搜索和构造方法掌握静态搜索表的顺序搜索和折半搜索方法 掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法掌握A

15、VI树的构造、性能分析方法 掌握散列法，包括散列函数的构造、解决冲突的方法基本概念4 -4-Z 八rr . 参考学时2学时工作任务查找的基本概念学习目标掌握简单的搜索结构掌握搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索头践技能简单的搜索结构知识要点搜索的概念线性表的查找4 -4-Z 八rr . 参考学时2学时工作任务线性表的查找学习目标了解静态索引结构，线性索引、倒排索引、静态索引树的搜索和构造方法 掌握线性索引；倒排表头践技能线性索弓1、倒排索引的应用知识要点静态索引结构，线性索引三树的查找4 -4-Z 八rr . 参考学时2学时工作任务树的查找学习目标了解动态索引结构，包括

16、 b 树、b+树的搜索和构造方法掌握二叉搜索树的定义掌握二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除掌握与二叉搜索树相关的中序游标类掌握AVI树的定义；平衡化旋转；AVI树的插入和删除；AVI树的高度头践技能二叉搜索树上的搜索知识要点二叉搜索树的定义四散列技术4 -4-Z 八rr . 参考学时2学时工作任务散列技术学习目标掌握词典的抽象数据类型掌握散列表与散列方法；散列函数掌握处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析头践技能解决冲突的方法知识要点散列函数的构造模块九排序1 .参考学时10学时2 .工作任务插入排序交换排序选择排序归并排序基数排序和外排序3 .学习目标掌握

17、排序的基本概念和性能分析方法掌握插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法 了解基数排序方法及其性能分析方法 了解多路平衡归并等外排序方法及败者树构造方法 了解生成初始归并段及败者树构造方法 了解最佳归并树的建立方法插入排序4 -4-Z 八rr . 参考学时2学时工作任务插入排序学习目标掌握排序的基本概念和性能分析方法掌握插入排序的方法及其性能分析方法掌握直接插入排序；对分插入排序；链表插入排序；希尔排序头践技能插入排序的方法知识要点内部排序方法的基本思想交换排序4 -4-Z 八rr . 参考学时2学时工作任务交换排序学习目标掌握交换排序的方法及其性能分析方法 掌握起

18、泡排序；快速排序等交换排序实践技能交换排序的方法知识要点交换排序的分类三选择排序4 -4-Z 八rr . 参考学时2学时工作任务选择排序学习目标掌握选择排序的方法及其性能分析方法 掌握直接选择排序；锦标赛排序；堆排序实践技能选择排序的方法及其性能分析知识要点选择排序的分类四归并排序4 -4-Z 八rr . 参考学时2学时工作任务归并排序学习目标掌握归并排序的方法及其性能分析方法掌握迭代的归并排序算法掌握递归的表归并排序了解生成初始归并段及败者树构造方法实践技能归并排序的方法及其性能分析知识要点迭代的归并排序算法五基数排序和外排序4 -4-Z 八rr . 参考学时2学时工作任务基数排序和外排序学习目标了解基数排序和外排序的方法及其性能分析方法了解多关键码排序；链式基数排序了解外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树实践技能最佳归并