《数据结构及应用》教学大纲.docx

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

1、致寤绪扬及用课程教学大纲一、课程的基本信息适应对象：电子信息工程本科专业课程代码：22E00314学时分配：总学时64学时，讲授48学时, 上机实验16学时赋予学分：4分先修课程：C语言程序设计 后续课程：面向对象程序设计等二课程性质与任务数据结构及应用是电子信息工程 本科专业的一门核心课程，它与电子信息 工程本科专业的各门主课都有密切联系， 是一门实践性极强的技术基本课，其内容 随信息科学与技术的飞速开展而不断更 新。课程通过讲授、练习和课外上机实践, 培养学生根据求解的要求，选择合适的数 据结构，应用抽象数据类型的思想方法， 组织数据和算法的能力，培养良好的程序 设计方法，为学习各后继课程

2、及实际工程 开发打下良好基础。三、教学目的与要求1、理解数据结构的基本概念，包括算法、 数据类型、抽象数据类型、复杂度的分析等。 理解数据结构和程序设计方法的联系和作用。2、掌握用C描述抽象数据类型的方法，在 原有的基础上进一步理解C语言中的一些重要 概念，如动态存储结构，指针和链表等。3、掌握字符串、表、堆栈、队列、树、二 叉树、队列、散列表、图等典型的数据结构的 概念、性质、实现方法。4、了解各数据结构之间的关系，包括结构 上的关系和实现关系。5、掌握一些基本的查找和排序方法，如顺 序查找、二分查找、树查找、散列、Hash、简 单排序、快速排序、堆排序、归并排序、基数 排序等。6、掌握一些

3、重要的应用和算法，如多项式、 稀疏矩阵、表达式求值、拓扑排序、哈夫曼树、 最短路径、最小生成树、堆排和快排等。7、掌握经典的算法思想，如分治法、贪心 法、动态规划和回溯法；8、会用时间复杂性和空间复杂度，以评价 实现各数据结构的算法和各应用算法的优劣。四教学内容与安排1、课时安排本课程共48个课时（课堂讲授48课时）， 按照课程内容，分成8个教学单元，各单元的 课时安排如下表。序号单元名称讲 授讨 论实 验小 计1绪论222线性表的顺序存储及其 运算622103链表42284串225数组和广义表226树和二叉树824147图824148查找和排序62412课时合计381016642、教学内容第

4、一单元绪论【教学内容】本课程讲解内容；数据结构的课程地位、 整体安排；数据结构的基本概念和术语；算法 的描述和算法分析。【教学重点与难点】教学重点：数据结构的基本概念和术语； 算法的描述和算法分析。教学难点：算法的描述和算法分析。【基本要求】掌握数据结构的基本概念和术语；理解算法的描述和算法分析；理解数据结构的地位。【培养的能力】对算法的描述方法和评价方式。第二单元线性表的顺序存储及其运算【教学内容】线性表的逻辑结构；线性表上的运算；栈 和队列的概念；栈和队列的运算；栈和队列的 应用。【教学重点与难点】教学重点：线性表的定义、描述、操作； 栈和队列的概念、运算和应用；。教学难点：线性表的描述；

5、栈和队列的运 算和应用。【基本要求】掌握顺序表的定义及逻辑特征；掌握顺序表上的运算在两种存储结构上的 实现；会编写顺序表上制定要求的算法；掌握栈和队列的特性，并能实现栈和队列 的的基本运算；能灵活运用栈和队列解决程序设计中的问 题。完成通讯录管理的应用。（实验）【培养的能力】线性表的顺序存储结构的操作、实现和解 决相关问题的能力。第三单元链表【教学内容】线性表的链式存储；链表的逻辑结构与定 义；链式栈和链式队列的概念和运算；循环链 表；链式栈和链式队列的的应用。【教学重点与难点】教学重点：线性表的链式存储、定义、描 述、操作；链式栈和链式队列的概念、运算和 应用；循环链表。教学难点：链表的逻辑

6、结构与定义；链式 栈和链式队列的运算。【基本要求】掌握线性链表的结构特点和运算；掌握栈和队列的链式存储；掌握循环链表的结构特点和运算；能灵活运用链式栈和链式队列解决程序设 计中的问题。完成停车场管理的应用。（实验）【培养的能力】线性表的链式存储结构的操作、实现和解 决相关问题的能力。第四单元串【教学内容】串类型的定义；串的存储；串的运算实现。【教学重点与难点】教学重点：串的存储；串的运算实现。教学难点：串的运算。【基本要求】掌握串类型的定义，串的存储；理解串的运算实现。【培养的能力】串的操作、实现和解决相关问题的能力。第五单元数组和广义表【教学内容】数组的定义；数据的顺序存储和实现；特 殊矩阵

7、的压缩存储；广义表的定义和存储结构。【教学重点与难点】教学重点：数据的顺序存储和实现；特殊 矩阵的压缩存储；广义表的定义和存储结构。教学难点：特殊矩阵的压缩存储。【基本要求】掌握数组的定义；掌握特殊矩阵的压缩存储方式；了解广义表的定义和存储结构。【培养的能力】数据分析、存储和解决相关问题的能力。第六单元树和二叉树【教学内容】树的定义和基本术语；树的存储结构；二 叉树的概念、存储及遍历二叉树；哈夫曼树及 其应用；树和森林的概念；森林与树的转换； 树和森林的遍历；二叉排序树。【教学重点与难点】教学重点：树的存储结构；二叉树的概念、 存储及遍历二叉树；哈夫曼树及其应用。教学难点：遍历二叉树；哈夫曼树

8、及其应 用。【基本要求】掌握二叉树的定义；掌握二叉树存储结构的特点与适用范围；掌握二叉树的各种遍历方法；能编写二叉树的各种运算算法；掌握树与森林的定义与转换；了解哈夫曼树的特性，掌握建立哈夫曼树 和哈夫曼编码的方法；了解二叉排序树；完成家谱管理的应用；（实验）完成哈夫曼编码的应用。（实验）【培养的能力】数据分析、存储、查找、编码和解决相关 问题的能力。第七单元图【教学内容】图的定义和术语；图的存储结构与操作实 现；图的遍历；最小生成树；图的连通性问题; 最短路径；拓扑排序；图的应用。【教学重点与难点】教学重点：图的存储结构与操作实现；图 的遍历；最小生成树；最短路径。教学难点：图的存储结构；图

9、的遍历算法; 最小生成树；图的应用。【基本要求】掌握图的定义；掌握图的存储结构及实现；掌握图的遍历方法；掌握最小生成树算法；理解图的连通性问题；了解图的应用的各种算法思想，并会用这 种思想求解图的问题；完成图的遍历实验；（实验）完成图的应用实验。（实验）【培养的能力】问题分析、算法设计和解决相关问题的能 力。第八单元查找和排序【教学内容】顺序表上查找；树表上的查找；散列表构 造和查找；各种排序算法；排序算法的分析。【教学重点与难点】教学重点：顺序表上的三种查找方法；二 叉排序树的构造和查找；散列表的构造方法； 各种排序算法。教学难点：二叉排序树；散列表；各种排 序算法的特点与应用。【基本要求】

10、掌握顺序表上的三种查找方法并灵活运 用；掌握二叉排序树的构造和查找方法；掌握散列表的构造方法和散列表上的查找 方法；掌握各种排序方法的实现算法，排序过程;深刻理解各种排序算法的特点，适用范围 并灵活运用；完成教学计划安排的应用。（实验）【培养的能力】顺序、二分、索引查找与散列表构造查找 算法的实现；选择、插入、交换排序算法实现 和解决相关问题的能力。五、教学设备和设施授课使用多媒体教室。六课程考核与评估1、考试形式：闭卷笔试（120分钟）;2、考试要求：本课程根据本大纲要求 命题；3、课程成绩构成=平时（30%）+期 末考试（70%）七、附录教学参考文献目录1梅霍内等.算法与数据结构.清华大学出版社20132王曙燕.数据结构与算法.人民邮电出版社,20133徐凤生著.数据结构与算法.机械工业出版社20144李春葆主编.数据结构教程.清华大学出版社20165恰汗.合孜尔主编.C语言程序设计中国铁道出版社2014年。第四版、C语言程序设计习题集与上机指导.大纲制定人：李文彬大纲审定人：潘理