《数据结构与算法》课程教学大纲.docx

《《数据结构与算法》课程教学大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》课程教学大纲.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法课程教学大纲课程英文名称：Data Structure课程编号：133991750课程类别：专业课课程性质：选修课学 分：3学 时：48 （其中：讲课学时：32实验学时：上机学时:16 ）适用专业：地理信息科学开课部门：环境与资源学院一、课程教学目的和课程性质本课程是地理信息科学专业选修课之一。通过该课程的学习，使学生掌握数 据结构领域的基础知识，特别将数据结构算法融与专业软件中。本课程系统地介绍线性表、栈 队列、字符串、数组、广义表、树、二叉树、 图、查找表等几种数据结构的基本概念，操作及其典型应用的例子，通过课堂教 学、课外练习和上机实习，使学生了解数据对象的特性，数据组织的

2、基本方法， 并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培 养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。 二、本课程与相关课程的关系先修课程：C#程序设计语言可为程序开发提供算法基础，同时包含空间分析原理局部知识。三、课程的主要内容及基本要求（-）理论学时局部第1单元 名称数据结构和算法简介（2学时）知识点数据结构的基本知识重 点数据逻辑结构、数据存储结构 数据类型的分类。难 点算法时间复杂度和空间复杂度的分析。基本要求1、识 记：数据 数据元素、数据逻辑结构、数据存储结构、数据类 型 算法，抽象数据类型。2、领 会：算法与程序的区别。3、简单应

3、用：掌握并熟悉运用抽象数据类型，描述算法所用的C+语言中 的一些有关问题。4、综合应用：算法时间复杂度的计算和空间复杂度的分析。第2单元名称解决线性表的编程问题（4学时）知识点线性表的顺序存储结构 单链存储结构 双向链存储结构。重 点线性表的存储方式。难 点单链表的查找、插入和删除，循环链表，双向链表。基本要求1、识 记：线性表的顺序存储结构，线性表的链接存储结构，单链表的 查找 插入和删除，循环链表，双向链表。2、领 会：了解线性表的基本概念和类型定义，熟悉掌握线性表的顺 序存储结构以及线性表的链接存储结构。3、简单应用：读懂程序，利用线性表存储数据。4、综合应用：运用单链表的查找、插入和删

4、除，循环链表，双向链表实现 数据的存储与应用。第3单元名称解决堆栈的编程问题（2学时）知识点栈的顺序存储和链接存储。重 点堆栈的程序实现，循环队列判满和判空的2种判断方法。难 点栈的线性表示与链表表示犯法。基本要求1、识 记：堆栈的特点、堆栈的定义、操作。2、领 会：使用堆栈解决编程中的问题。3、简单应用：使用栈存储整形数据。4、综合应用：应用栈的顺序存储和链接存储进行游戏求解的算法。第4单元名称 解决队列的编程问题（4学时）知识点队列的类型定义，掌握队列的顺序存储（循环队）和链接存储表示。重 点队列的顺序存储（循环队）和链接存储。难 点队列的顺序和链接存储的程序实现。基本要求1、识 记：队列

5、的顺序存储、和链接存储实现。2、领 会：队列的入队 出队操作。3、简单应用：应用队列实现数字型数据的存储与操作。4、综合应用：应用队列的顺序存储和链接存储，包括插入与删除功能， 进行火车游戏求解的编程；用队列解决图的遍历问题。第5单元 名称解决串的编程问题（4学时）知识点串的定义，串的插入、删除和查找。重 点串的顺序存储和链接存储。难 点串的KMP匹配算法。基本要求1、识 记：串的定义，串的顺序存储和链接存储的表示。2、领 会：串的查找算法与匹配算法。3、简单应用：编程实现串的简单查找算法。4、综合应用：给定一个字符串，编程实现串的简单匹配算法与快速匹配算 法，第6单元名称 解决数组的编程问题

6、 （4学时）知识点数组的定义，数组的顺序存储和数组的插入和删除。重 点数组的存储和压缩存储。难 点三角、对称等特殊矩阵的数组表示和存储。基本要求1、识 记：特殊矩阵的分类。2、领 会：矩阵的转置与压缩算法。3、简单应用：编程实现矩阵的简单转置算法。4、综合应用：编程实现矩阵的快速转置算法，实现数组的查找与匹配。第7单元名称解决二叉树的问题（2学时）知识点二叉树树的定义 分类 遍历。重 点二叉树的性质和存储结构以及二叉树的各种遍历方法。难 点二叉树的三种常见遍历算法：先序 中序和后序。基本要求1、识 记：二叉树、 树的度、结点的度 深度 根结点。2、领 会：二叉树的各种遍历方法及实现，建立二叉树

7、 输出二叉树 求二叉树深度等的操作方法及实现。3、简单应用：根据输入数据 建立二叉树、输出二叉树、求二叉树深度等 的操作方法及实现。4、综合应用：树的存储结构，进行先根遍历、 后根遍历和按层遍历的方法 及实现，进行树与二叉树的转换方法。第8单元 名称解决树和森林的问题（4学时）知识点树和森林的定义性质和表示方法。重 点树和森林的存储结构与遍历算法。难 点树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现, 进行树与森林的转换方法。基本要求1、识 记：树、森林的遍历及与二叉树的转换。2、领 会：树与森林的转换。3、简单应用：森林、树以及二叉树的前中后三种遍历方式。4、综合应用：在遍历基础

8、上针对树的一些统计和操作（比方结点数统计 左右子树对换等等），判断某棵树是否排序树，特别要重视非递归的算法，线索 化后树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出 Huffman编码等等。第9单元 名称 解决图的问题（2学时）知识点图的定义和术语，图的组成。重 点图的邻接矩阵、邻接表和边集数组表示。难 点图的遍历及最短路径算法。基本要求1、识 记：边 结点、无向图、有向图、入度、 出度。2、领 会：图的邻接矩阵、邻接表和边集；数组表示。3、简单应用：图的深度和广度优先搜索历。4、综合应用：根据输入的城市间距离矩阵数据，实现最短路径算法；拓扑 排序问题，关键路径问题。第10单

9、元 名称实现排序算法 （4学时） 知识点排序的概念，排序的分类及时间复杂度。重 点直接插入，冒泡排序和快排序，直接选择排序和堆排序，归并排序 的实现。难 点几种排序算法的时间复杂度计算及比拟。基本要求1、识 记：直接插入，冒泡排序和快排序，直接选择排序和堆排序，归 并排序。2、领 会：灵活选择各种排序方法对无序的数据记录进行排序。3、简单应用：给定一组数据，实现快速排序算法。4、综合应用：给定数列要求给出某种特定排序方法运行一轮后的排序结果, 或者给出初始数列和一轮排序结果要求选择采用的排序算法，给定时间、空间复 杂度要求以及数列特征要求选择合适的排序算法等。学时分配知识单元理论学时1数据结构

10、和算法简介22解决线性表的编程问题43解决堆栈的编程问题24解决队列编程问题45解决串的编程问题46解决数组的编程问题47解决二叉树的问题28解决树的编程问题49解决图的编程问题210执行排序算法4合计32（-）实验学时局部实验教学环节作用及目的通过上机程序的编制，到达更好地掌握理论课所学内容，锻炼逻辑思维能力 之目的。实验教学环节培养学生能力标准根据自身掌握的程度及查阅资料，在老师指定的侯选题目完成程序的补充或 者程序的设计，要求学生独立完成，或与同学合作完成（复杂题目）。实验工程、内容、学时分配及实验类型1、必开实验序 号实验工程实验内容学 时实验类型（演示、验证、综合、设计研究）组 数每

11、组学 生人数1数据结构 编程基础1 .面向对象程 序设计基础2设计研究5012线性表2.线性表的操 作2设计研究5013单链表3.单链表及其 基本操作2设计研究5014栈4.栈的操作2设计研究5015队列5.队列的基本 操作2设计研究5016树的操作6.二叉树和二 叉树排序树2设计研究5017图7.图的运算2设计研究5018排序8.排序算法， 实现5种排序 算法2设计研究501犯采用计算机多媒体教学的方法，课堂演示利用flash演示算法的实现过程， 结合范例程序讲解。1、坚持理论联系实际的教学方法，不断地吸收计算机科学先进理论知识和 最新的信息技术实践动态，以重构教学流程和创新教学方式为路径，

12、以情境创设 为手段，以整合教学资源和拓展教学空间为保障，通过反复探索和实践，不断提 高学生发现 分析和解决问题的能力。2、坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重点和 难点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的图像，使复 杂的理论变得简单 直观，力求化难为易，努力提高学生的学习兴趣。3、注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思考问 题、分析问题，拓展学生的思维。4、注重课后练习，大力培养学生动脑、动手、独立解决问题的能力。五、考核要求、方式与成绩评定课程考核选择百分制模式，平时考查与期末考试相结合。课程考核总评成 绩由四局部构成，具体包括期

13、末考试成绩(70%)、作业成绩(20%)、课堂讨 论(5%)和考勤(5%)四个局部。期末考试采取闭卷考试方式，主要考试内容 为教材中重要的基本原理和基本概念，亦会少量涉及到布置的参考资料内容。考核要求：考试内容为教材中重要的基本原理和基本方法考核形式：考试成绩评定：按照闭卷考试方式为主，结构评定成绩，其中：期末考试成绩占70%,课后作业占25%,平时上课提问占5%。六、选用教材、讲义和主要参考书1、教材数据结构（C#语言版），雷军环 邓文达 刘震，清华大学出版社， 2009年01月2、参考书数据结构实用教程（第二版）徐孝凯清华大学出版社，2006年09月Data Structure with C+William Ford William Topp 著，清华大学出版 社，2005.4七、大纲说明本大纲遵循2007年修订大纲制定，在内容上没有作改动。八、审核意见课程负责人签字：专业负责人签字：教研室主任签字：分管院长签字：执行日期：