《数据结构与算法》课程教案
课程代码：0806302024
课程名称：数据结构与算法
英文名称：Data Structure and Algorithm
学    分：4.5        总 学 时：72
讲课学时：56        实验学时：0        上机学时：16
适用对象：计算机类专业本科
先修课程：C/C++程序设计I、C/C++程序设计II（可选）、JAVA语言程序设计、离散数学
一、课程目标
“数据结构与算法”课程是高等学校计算机类各专业本科的专业基础课程，是进行程序设计训练的核心课程，是培养软件设计能力不可或缺的重要环节，在计算机学科本科的培养体系中具有
非常重要的地位。
本课程的目标是，培养学生掌握处理数据和编写高效率软件的基本方法，培养算法分析和软件设计能力。任务是，研究数据的各种逻辑结构，在计算机中的存储结构以及各种操作的算法设计。
“数据结构与算法”课程是理论与实践并重的课程，既要掌握数据结构的基础理论知识和算法设计方法，又要掌握运行和调试程序的基本技能。
本课程教学的基本要求说明如下。
1、理解和掌握各种数据结构（物理结构和逻辑结构）的概念及其有关的算法；熟悉并了解目前常用数据结构在计算机诸多领域中的基本应用。（支撑毕业要求1-2H）
2、要求学生从算法和数据结构的相互依存关系中把握应用算法设计的艺术和技能；培养良好的软件工程习惯和面向对象的软件思维方法。（支撑毕业要求1-3H）
二、课程目标与毕业要求指标点的对应关系
毕业要求
指标点
课程目标
1. 工程知识：能够将数学、自然科学、工程基础和专业知识用于解决软件工程领域复杂工程问题。
1-2掌握软件工程领域专业知识，包括计算机系统、网络、数据库、算法等方面内容，具备识别、理解软件工程领域复杂工程问题的能力；
课程目标1
1-3 能够运用数学、自然科学、工程基础和专业知识对软件工程领域复杂工程问题构建形式化模型，具备对复杂问题的抽象分析的能力，并能根据具体工程进行分解以降低问题的复杂性。
课程目标2
三、课程目标与教学内容和方法（环节）对应关系表
序号
课程目标
教学内容
教学方法（环节）
课堂教学
平时
实验
上机
1
理解和掌握各种数据结构（物理结构和逻辑结构）的概念及其有关的算法；熟悉并了解目前常用数据结构在计算机诸多领域中的基本应用。
1、线性表的顺序逻辑结构和实现
2、线性表的链式逻辑结构和实现
3、字符串操作和模式匹配算法
4、栈的存储结构、设计方法和应用
5、队列存储结构、设计方法和应用
6、数组的存储结构、操作和应用
7、广义表的概念和存储结构
8、二叉树定义、存储结构和设计方法
9、树的定义、存储结构和设计方法
10、Huffman算法，二叉树应用。
11、图概念、存储结构和遍历算法，构造最小生成树，求解最短路径。
＋
二叉树的遍历及应用实验报告＋
2
要求学生从算法和数据结构的相互依存关系中把握应用算法设计的艺术和技能；培养良好的软件工程习惯和面向对象的软件思维方法。
12、算法定义、算法描述、算法设计目标和算法分析方法。
13、递归定义和递归算法设计方法。
14、各种数据结构的查算法。
15、插入、交换、选择、归并等排序算法。
16、分治法、贪心法、动态规划法和回溯法等算法设计策略。
＋
＋
四、教学内容
1、绪论（支撑课程目标1和课程目标2）
教学要求：了解数据结构的基本概念；了解算法、算法描述、算法设计目标和算法分析方法。
教学内容：
（1）了解数据结构的基本概念，数据的逻辑结构、数据的存储结构和数据操作，了解抽象数据类型与数据结构的关系。
（2）了解算法、算法描述、算法设计目标和算法分析方法，掌握算法的时间复杂度和空间复杂度的分析方法。
2、线性表（支撑课程目标1）
教学要求：理解线性表的逻辑结构和基本操作，掌握线性表抽象数据类型的描述方法。
教学内容：
（1）掌握线性表的顺序存储结构和实现方法。
（2）掌握线性表的链式存储结构及其特点，掌握实现单链表、循环单链表、双链表、循环双链表基本操作的设计方法。比较各种存储结构的特点和性能。
（3）掌握排序线性表的实现方法。
3、串（支撑课程目标1）
教学要求：理解字符串的概念和基本操作，掌握串的模式匹配算法及其应用。
教学内容：
（1）理解串的概念和基本操作，熟悉串的顺序存储结构和链式存储结构。
（2）掌握串类的定义和基本操作的实现方法。
（3）掌握两种串的模式匹配算法：Brute-Force和KMP算法，以及算法应用。
4、栈和队列（支撑课程目标1）
教学要求：理解栈和队列概念、存储结构和设计方法；理解递归定义，掌握递归算法设计方法。
教学内容：
（1）理解栈的概念和作用，掌握顺序栈和链式栈的设计方法，熟悉使用栈的算法设计方法。
（2）理解队列的概念和作用，掌握顺序循环队列和链式队列的设计方法，熟悉使用队列的算法设计方法。熟悉优先队列的概念、设计和使用方法。
（3）理解递归定义，掌握递归算法设计方法。
5、数组和广义表（支撑课程目标1）
教学要求：理解数组的概念、存储结构和操作；了解广义表的概念和存储结构。
教学内容：
（1）理解数组的概念，理解一维数组和二维数组的存储结构。
（2）熟悉三角矩阵等特殊矩阵的压缩存储方法；掌握稀疏矩阵的各种压缩存储方法，包括稀疏矩阵三元组顺序表、单链表、行的单链表和十字链表存储结构。
（3）了解广义表的概念和存储结构。
6、二叉树和树（支撑课程目标1）
教学要求：掌握二叉树的定义、存储结构和设计方法；掌握树的定义、存储结构和实现方法；作为二叉树的应用，理解Huffman算法，理解表达式二叉树。
教学内容：
（1）理解二叉树的定义、性质、遍历规则和存储结构，掌握采用二叉链表或三叉链表存储结构存储二叉树的特点，掌握二叉树的遍历、构造、插入、删除等操作算法，比较二叉树遍历的递归算法与非递归算法的特点。
（2）理解树的定义、术语、表示方法、遍历规则和多种存储结构，掌握采用树的孩子兄弟链表存储树并实现树的遍历、插入、删除等操作，熟悉横向凹入表示法等树的构造算法。
（3）理解Huffman树的概念，理解Huffman算法实现构造Huffman树。
（4）理解建立表达式二叉树，计算机表达式值。
7、图（支撑课程目标1）
教学要求：理解图的基本概念和存储结构，理解图的遍历算法，理解最小生成树的构造算法，理解最短路径的求解算法。
教学内容：
（1）理解图的基本概念和术语。
（2）掌握图的邻接矩阵和邻接表存储结构。
（3）实现图的深度优先遍历和广度优先遍历算法。
（4）理解最小生成树的概念，掌握Prim算法构造图的最小生成树算法，了解Kruskal算法。
（5）理解最短路径问题的概念，掌握求单源最短路径的Dijkstra算法，了解求所有最短路径的Floyd算法。
8、查（支撑课程目标2）
教学要求：理解各种数据结构的查操作要求，掌握在线性表、二叉树中采用的查算法及查效率的分析方法。
教学内容：
（1）理解查的基本概念和查算法效率的分析方法。
（2）掌握二分法查算法，熟悉基于索引机制的分块查算法。
（3）理解散列的概念，熟悉散列函数的构造方法，熟悉解决冲突的多种方法，掌握链地址法散列表的构造、插入、删除、查等操作算法。
（4）理解二叉排序树的概念和作用，掌握二叉排序树的查、插入和删除等操作算法。了解平衡二叉树的基本概念和保持平衡性的调整规则。
（5）理解映射概念和接口，熟悉散列映射和树映射的实现，熟悉映射的应用。
9、排序（支撑课程目标2）
教学要求：掌握插入、交换、选择、归并等排序算法及算法效率分析方法。
教学内容：
（1）理解排序的基本概念和排序算法效率的分析方法。
（2）掌握直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序算法；比较各排序算法的特点、算法设计思想和适用的存储结构，分析各排序算法的时间效率和空间效率。
（3）掌握适用于单/双链表的各种排序算法。
10、综合应用设计（支撑课程目标2）
教学要求：理解多种算法设计策略及应用，包括分治法、贪心法、动态规划法和回溯法等。
教学内容：
（1）理解分治法、贪心法、动态规划法和回溯法等算法设计策略，理解每种策略的要求、特点、应用场合和典型应用案例等。
五、各教学环节学时分配表
本课程学时为72，其中讲课56学时，上机实验16学时。学时分配见下表。

教学单元名称
讲课
实验
习题
研讨
绪论
2
0
线性表
8
2
串
6
2
栈、队列和递归
6
2
数组和广义表
2
0
二叉树和树
8
4
图
8
2
查
6
2
排序
6
2
综合应用设计
4
0
合        计
六、教学组织与方法
本课程采取理论讲授与实践环节相结合的教学方法，通过课堂讲授、课外练习、上机实验等各环节，对学生进行系统的程序设计训练，达到高质量的教学要求。各环节教学方法与要求说明如下。
（1）通过课堂讲授，使学生熟悉课程内容，理解基础理论；通过例题，演示各章内容和设计结果；通过课堂练习，及时发现学生理解的偏差；通过课堂讨论，及时改正错误，使学生加深理解。
课堂教学采取板书与多媒体相结合的方式进行。本课程配有多媒体课件，其中包含课程主要内容和重点；讲课过程中，需要采用多媒体方式演示如何使用高级语言集成开发环境和程序运行情况。
（2）通过课外练习，使学生深入理解理论知识，熟练操作。
（3）通过上机实验和课程设计等各实践环节，对学生进行系统的程序设计训练，逐步提高程序设计能力。
所有例题、课堂练习题、课外习题、上机实验题都是精心挑选的，由浅入深，环环相扣，步步推进，调动学生的主动性和自觉性并培养学生写程序的兴趣和能力。
上机实验在计算机实验室进行。在实验课之前，学生选择实验题，根据实验要求编写程序并调试；在实验课上，针对学生程序出现的各种问题，教师进行辅导，指出问题所在，提出改进意见。
七、课程目标达成度评价
1、课程目标1的达成度通过结课考试成绩、平时成绩综合考评；
2、课程目标2的达成度通过结课考试成绩、平时成绩综合考评。
八、课程考核与成绩评定
课程的考核应以考核学生对课程目标的达成为主要目的，以检查学生对各知识点的掌握程度为重要内容，课程成绩包括2大部分，分别为平时成绩（30%）和期末考试（70%），其中平时成绩包括考勤、课堂表现，作业和单元测验（10%），实验（20%）。具体要求及成绩评定方法如下。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。