《数据结构》课程标准

《数据结构》课程标准

一、适用对象

五年高职学生

二、课程性质

《数据结构》课程是介于数学、计算机硬件和软件课程三者之间综合性的学科，本课程主要使学生体会“算法的设计建立于逻辑结构，算法的实现依赖于物理（存储）结构”，并能根据实际情况选择相应的数据结构和算法，所以本课程教学强调思维训练，为随后的程序设计和技能训练打好基础。

《数据结构》课程是我校信息技术系软件技术专业的一门专业技术基础课。它是计算机程序设计的重要理论基础；它所讨沦的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其它课程，还是对从事软件工程的开发，都有着不可替代的作用。

三、参考学时

64学时。

四、学分

4学分。

五、课程目标

从课程性质上讲，《数据结构》是一门软件专业技术基础课。通过本课程的教学，达到的教学目标是：

? 知道《数据结构》这门学科的性质、地位和独立价值。知道这门学科的研究范围、分析框架、研究方法、学科进展和未来方向。

? 理解这门学科的基本概念、主要结构类型和算法，尤其是数据结构的三要素、存储结构的实现和算法的评价策略。

? 学会分析研究计算机加工的数据的结构特性，以便为实际应用问题所涉及到的数据选择适当的逻辑结构、存储结构及其算法。

? 逐步理解算法的时间分析和空间分析的技术。

? 培养数据抽象能力；训练复杂程序设计的技能；要求编写的程序结构清楚和正确易读，养成良好程序设计习惯。

六、设计思路

? 按照“以能力为本位、以职业实践为主线、以项目课程为主体的模块化专业课程体系”的总体设计要求，紧紧围绕完成工作任务的需要来选择和组织课程内容，突出工作任务与知识的联系，让学生在职业实践活动的基础上掌握知识，增强课程内容与职业能力要求的相关性，提高学生的就业能力。

? 依据各项目模块的内容总量以及在该门课程中的地位分配各项目模块的学时数。 ? 学习程度用语主要使用“了解”、“理解”、“能”或“会”等用语来表述。“了解”用于表述事实性知识的学习程度，“理解”用于表述原理性知识的学习程度，“能”或“会”用于表述技能的学习程度。

七、内容纲要 模块一 绪论 1．参考学时

2学时 2．工作任务

■ 基本概念和术语 ■ 算法的描述和分析 3．学习目标 ■ 什么是数据结构

■ 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概

念；用于描述数据结构的语言 ■ 数据结构的抽象层次 ■ 算法定义

■ 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度

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

1学时 算法复杂度的分析方法 掌握算法定义 掌握性能分析与度量 性能分析与度量 掌握算法描述和分析的方法 模块二 线性表

1．参考学时

12学时

2．工作任务

■ 线性表的逻辑结构 ■ 线性表的顺序存储结构 ■ 线性表的链式存储结构 3．学习目标

■ 作为抽象数据类型的数组 ■ 顺序表的定义和特点

■ 掌握单链表、循环链表、双向链表 一 线性表的逻辑结构

1

参考学时 工作任务 学习目标 4学时 了解线性表的逻辑结构 介绍线性表的逻辑结构 掌握各种存储表示方法 掌握存储结构上实现基本运算 实践技能 知识要点 参考学时 工作任务 学习目标 实践技能 知识要点 基本运算的实现 常用的基本概念和术语 4学时 线性表的顺序存储结构 掌握顺序表的定义和特点；顺序表的类定义 掌握顺序表的查找、插入和删除； 使用顺序表的事例 顺序表的数组定义方式及实现 二 线性表的顺序存储结构 三 线性表的链式存储结构 参考学时 工作任务 学习目标 4学时 线性表的链式存储结构 掌握单链表的结构；单链表的类定义 掌握循环链表的类定义；用循环链表解约瑟夫问题 掌握双向链表的结构和定义 实践技能 知识要点

链表的游标类定义及其应用方法 单链表、循环链表及双向链表的定义及实现 模块三 栈和队列

1．参考学时

8学时

2．工作任务

■ 栈的概念、存储结构及其基本操作 ■ 队列的概念、存储结构及其基本操作 ■ 栈与队列的应用 3．学习目标

■ 掌握栈的定义、栈的存储及其实现，队列的定义、存储及其实现，循环队列的实现 ■ 理解利用栈进行算法描述 ■ 了解栈与递归算法实现

一 栈的概念、存储结构及其基本操作 参考学时 工作任务 学习目标 2学时 栈的概念、存储结构及其基本操作 掌握栈的定义 2

掌握栈的存储及其实现 实践技能 知识要点 掌握栈在两种存储结构上实现的基本运算 栈的链接存储表示 二 队列的概念、存储结构及其基本操作 参考学时 工作任务 学习目标 2学时 队列的概念、存储结构及其基本操作 掌握队列的定义 掌握队列的存储及其实现 掌握循环队列的实现 实践技能 知识要点 掌握队列在两种存储结构上实现的基本运算 循环队列中对边界条件的处理 三 栈与队列的应用 参考学时 工作任务 学习目标 实践技能 知识要点

4学时 栈与队列的应用 掌握利用栈进行算法描述 掌握栈与递归算法实现 懂得在什么样的情况下能够使用栈或队列 优先级队列的定义及链表实现 模块四 串

1．参考学时

4学时

2．工作任务 ■ 串及其运算 ■ 串的存储结构 3．学习目标 ■ 掌握串的的定义 ■ 掌握串的存储表示方法

■ 了解串的匹配查找朴素算法和改进算法 一 串及其运算 参考学时 工作任务 学习目标 实践技能 知识要点 2学时 串及其运算 掌握串的定义 掌握串上实现的模式匹配算法 掌握串上实现的模式匹配算法 串的定义 二 串的存储结构 参考学时 2学时 3

工作任务 学习目标 实践技能 知识要点

串的存储结构 掌握串的逻辑结构 掌握串的存储结构 串的匹配查找：朴素算法和改进算法 串的逻辑结构、存储结构及其中上的基本运算 模块五 数组和广义表

1．参考学时

4学时

2．工作任务 ■ 多维数组 ■ 矩阵的压缩存储 ■ 广义表的概念 3．学习目标

■ 掌握多维数组的逻辑结构特征 ■ 掌握多维数组的存储方式

■ 掌握特殊矩阵和稀疏矩阵的压缩存储方法 ■ 掌握广义表的概念 ■ 掌握广义表的表示及操作 一 多维数组 参考学时 工作任务 学习目标 实践技能 知识要点 2学时 多维数组 掌握多维数组的逻辑结构特征 掌握多维数组的存储方式 掌握多维数组的存储方式 多维数组的表示和算法 二 矩阵的压缩存储和广义表 参考学时 工作任务 学习目标 2学时 矩阵的压缩存储和广义表 掌握掌握特殊矩阵和稀疏矩阵的压缩存储方法 掌握广义表的概念 掌握广义表的表示及操作 实践技能 知识要点

稀疏矩阵的压缩存储表示下实现的算法 矩阵的压缩存储、广义表的定义及其求表头和表尾的运算 模块六 树和二叉树

1．参考学时

8学时

2．工作任务

4

■ 树和二叉树

■ 二叉树的遍历和线索化 ■ 树和森林 ■ 哈夫曼树及其应用 3．学习目标

■ 了解树和森林的概念

■ 了解线索化二叉树的特性及寻找某结点的前驱和后继的方法 ■ 掌握二叉树的概念、性质及二叉树的表示 ■ 掌握二叉树的遍历方法及树的游标类定义 ■ 掌握树与森林的实现和遍历方法

■ 掌握二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 ■ 掌握哈夫曼树的实现方法及哈夫曼编码的概念 一 树和二叉树 参考学时 工作任务 学习目标 2学时 树和二叉树 掌握树的定义；树的术语；树的抽象数据类型 掌握二叉树的定义；二叉树的性质；二叉树的抽象数据类型 掌握二叉树的数组表示；链表存储表示 实践技能 知识要点 二叉树的数组表示；链表存储表示 树和二叉树的定义 二 二叉树的遍历和线索化 参考学时 工作任务 学习目标 2学时 二叉树的遍历和线索化 掌握二叉树的遍历方法及树的游标类定义 掌握二叉树遍历算法的有关应用 掌握二叉树的线索；中序线索化二叉树；前序与后序的线索化 实践技能 知识要点 应用二叉树遍历的事例 二叉树遍历、线索化二叉树 三 树和森林 参考学时 工作任务 学习目标 2学时 树和森林 掌握树的存储表示 掌握森林与二叉树的转换 掌握树与森林的实现和遍历方法 掌握二叉树的计数 实践技能 知识要点 树与森林的实现和遍历方法 树的存储表示、森林与二叉树的转换 四 哈夫曼树及其应用

5

参考学时 工作任务 学习目标 实践技能 知识要点

2学时 哈夫曼树及其应用 掌握哈夫曼树路径长度 掌握哈夫曼编码的概念 哈夫曼树的实现方法 哈夫曼编码的概念 模块七 图

1．参考学时

8学时

2．工作任务

■ 图的基本概念和存贮结构 ■ 最小生成树的算法

■ 最短路径，拓扑排序和关键路径算法 3．学习目标

■ 掌握图的基本概念和图的存储表示

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

掌握用顶点表示活动的网络；用边表示活动的网络 掌握求解关键路径的方法 实践技能 知识要点

最短路径，拓扑排序和关键路径算法 最短路径，拓扑排序和关键路径的概念 模块八 查找

1．参考学时

8学时

2．工作任务 ■ 基本概念 ■ 线性表的查找 ■ 树的查找 ■ 散列技术 3．学习目标

■ 了解静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法 ■ 了解动态索引结构，包括b_树、b+树的搜索和构造方法 ■ 掌握静态搜索表的顺序搜索和折半搜索方法

■ 掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 ■ 掌握AVI树的构造、性能分析方法

■ 掌握散列法，包括散列函数的构造、解决冲突的方法 一 基本概念 参考学时 工作任务 学习目标 实践技能 知识要点 2学时 查找的基本概念 掌握简单的搜索结构 掌握搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索 简单的搜索结构 搜索的概念 二 线性表的查找 参考学时 工作任务 学习目标 实践技能 知识要点 2学时 线性表的查找 了解静态索引结构，线性索引、倒排索引、静态索引树的搜索和构造方法 掌握线性索引；倒排表 线性索引、倒排索引的应用 静态索引结构，线性索引 三 树的查找 参考学时 工作任务 学习目标 2学时 树的查找 了解动态索引结构，包括b_树、b+树的搜索和构造方法 7

掌握二叉搜索树的定义 掌握二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除 掌握与二叉搜索树相关的中序游标类 掌握AVI树的定义；平衡化旋转；AVI树的插入和删除；AVI树的高度 实践技能 知识要点 二叉搜索树上的搜索 二叉搜索树的定义 四 散列技术 参考学时 工作任务 学习目标 2学时 散列技术 掌握词典的抽象数据类型 掌握散列表与散列方法；散列函数 掌握处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析 实践技能 知识要点

解决冲突的方法 散列函数的构造 模块九 排序

1．参考学时

10学时

2．工作任务 ■ 插入排序 ■ 交换排序 ■ 选择排序 ■ 归并排序 ■ 基数排序和外排序 3．学习目标

■ 掌握排序的基本概念和性能分析方法

■ 掌握插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法 ■ 了解基数排序方法及其性能分析方法

■ 了解多路平衡归并等外排序方法及败者树构造方法 ■ 了解生成初始归并段及败者树构造方法 ■ 了解最佳归并树的建立方法 一 插入排序 参考学时 工作任务 学习目标 2学时 插入排序 掌握排序的基本概念和性能分析方法 掌握插入排序的方法及其性能分析方法 掌握直接插入排序；对分插入排序；链表插入排序；希尔排序 实践技能 插入排序的方法 8

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

八、实施建议

教材应由浅入深，通俗易懂。就数据结构本身而言，它具有很强的理论性，所以教材应在基本概念、基本理论阐述方面注重科学严谨，同时也应从应用出发，对各种基本算法描述应尽量详细、清晰，便于教学与实践。

本课程概念较多，因此教学形式以讲授方式和辅导为主。

9

注重理论与实践相结合。为了巩固所学的理论知识，在每章的最后都应有一定数量的习题、实训题目。

对课程中关键性概念、设计思想方面的问题可辅以课堂讨论的形式。

要采取项目教学法，以工作任务为出发点激发学生的学习兴趣，教学过程中要注重创设教育情境，采取理论实践一体化教学模式，要充分利用挂图、投影、多媒体等教学手段。

改革评价手段和办法，加强实践性技能的考核，可采用过程评价和综合评价办法相结合。 注重对学生动手能力和实践分析问题、解决问题能力的考核，对学习和实践环节上有创新的学生应特别给予鼓励，综合评价学生能力。

开发相关辅导用书、教师指导用书、网络资源，要注重仿真软件的应用及开发。

充分利用行业资源，为学生提供阶段实训，让学生在真实的环境中磨练自己，提升其职业综合素质。

要充分利用网络资源，搭建网络课程平台，开发网络课程，实现优质教学资源共享。 答疑是师生交流的主要方式，及时解决学生们在学习中碰到的问题，加强师生之间的互动，以利于提高教学效果，并通过及时反馈对教学进度与内容进行相应的调整。

（本标准撰写人：丁玲）

10

注重理论与实践相结合。为了巩固所学的理论知识，在每章的最后都应有一定数量的习题、实训题目。

对课程中关键性概念、设计思想方面的问题可辅以课堂讨论的形式。

要采取项目教学法，以工作任务为出发点激发学生的学习兴趣，教学过程中要注重创设教育情境，采取理论实践一体化教学模式，要充分利用挂图、投影、多媒体等教学手段。

改革评价手段和办法，加强实践性技能的考核，可采用过程评价和综合评价办法相结合。 注重对学生动手能力和实践分析问题、解决问题能力的考核，对学习和实践环节上有创新的学生应特别给予鼓励，综合评价学生能力。

开发相关辅导用书、教师指导用书、网络资源，要注重仿真软件的应用及开发。

充分利用行业资源，为学生提供阶段实训，让学生在真实的环境中磨练自己，提升其职业综合素质。

要充分利用网络资源，搭建网络课程平台，开发网络课程，实现优质教学资源共享。 答疑是师生交流的主要方式，及时解决学生们在学习中碰到的问题，加强师生之间的互动，以利于提高教学效果，并通过及时反馈对教学进度与内容进行相应的调整。

（本标准撰写人：丁玲）

10

本文来源：https://www.bwwdw.com/article/jml2.html