《数据结构》课程教学大纲(三套)_4348.docx
《《数据结构》课程教学大纲(三套)_4348.docx》由会员分享,可在线阅读,更多相关《《数据结构》课程教学大纲(三套)_4348.docx(16页珍藏版)》请在三一文库上搜索。
1、数据结构课程教学大纲(三套)数据结构课程教学大纲(36/36 课时)一、课程的性质和任务数据结构是计算机及应用专业中一门重要的专业基础课程, 在计算机软件的各个领域中均会使用到数据结构的有关知识。 当用计算机来解决实际问题时, 就要涉及到数据的表示及数据的处理, 而数据表示及数据处理正是数据结构课程的主要研究对象,通过这两方面内容的学习, 为后续课程, 特别是软件方面的课程打开厚实的基础。因此,数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是: 在基础方面, 要求学员掌握常用数据结构的基本概念及其不同的实现方法; 在技能方面,通过系统学习能够在不同存储结构上实现不同的运算,并对
2、算法设计的方式和技巧有所体会。 总言之,使应用者较全面的掌握各种常用的数据结构,提高运用数据结构解决实际问题的能力。二、课程的基本要求本课程的教学基本要求如下:本课程要求理论必须与上机实践操作相结合,多做题和调试算法,实现算法。实践项目只利用课堂时间是不够的,必须提前布置给学生。 通过本课程的学习与实践,学生应达到:1、掌握数据结构的基本概念和基本理论;2、熟练掌握顺序表、链表、队列、栈、树以及二叉树、图等基本数据结构的设计和分析;3、熟练地掌握常用算法(递归、遍历、查找、排序)的知识;4、能对所求解的问题进行分析,抽象出逻辑结构,选择合适的存储结构,定义所需的运算,设计相应的算法;5、对算法
3、进行分析和评价。三、教学内容(一)理论教学序单主要内容号元理 论数据结构的基本概念(数据、数据元素、数据1绪论类型和数据结构、逻辑结构、存储结构)教学2算法描述和算法评价1线性表的概念及运算线性理 论2顺序表及基本运算23单链表及基本运算表教学4循环链表和双链表5顺序存储结构与链式存储结构的比较栈和理 论1栈和队列的概念及运算;32栈和队列的顺序、链接存储队列教学3栈和队列的插入、删除算法及其应用4串理 论1串及其运算、串的存储结构;教学树的定义和表示;理 论二叉树的定义、重要性质、存储结构和运算;5树二叉树的遍历、线索、排序;教学二叉树与树和森林的转换;树的应用: 二叉排序树、哈夫曼树及其应
4、用图的定义和术语图的存储结构6图理 论图的建立和遍历教学图的生成树最短路径图的遍历、图的生成算法学教学要求时了解数据的逻辑结构和物理结构,算法的基本概念;2掌握算法复杂度的概念及分析方法熟练掌握:线性表的基本运算;单链表和循环链表的结构特点、基本运算并能设计4简单算法熟练掌握栈和队列的特征、基本运算并能设计简单算4法熟练掌握串的逻辑结构、存储结构2熟练掌握:1.树形结构的基本概念和术语;.二叉树定义和存储结 6 构; .二叉树的遍历次序及算法熟练掌握图的存储结构和遍历算法,以及生成最小生 6 成树的方法序单主要内容号元1查找的基本概念2顺序查找、7查找理 论3索引查找教学4树表查找 (二叉排序
5、树定义及查找,二叉平衡树的定义 )5散列查找1排序的基本概念2插入排序(直接插入排序、折半插入排序、8排序理 论希尔排序)教学3交换排序(冒泡排序、快速排序)4.选择排序(简单选择排序、* 堆排序)5各种排序方法比较学时合计72学教学要求时熟练掌握顺序查找、 二分查找、分块查找、 二叉排序树查找的基本思想和算法;散列法基本思想、 散列函数的6常用构造方法及解决冲突方法熟悉各种内部排序方法的基本思想和特点; 各种排序方法的优缺点、 时、空性能 6 和适用场合理论教学36实践教学36(二)实践环节序单主要内容教学要求学号元时分析算法的时间复杂度,并用程序验证。例如:求下列算法段的语句频度1实践项掌
6、握分析算法段的语句频度及2绪论for(i=1; i<=n; i+)时间复杂度, 并用程序加以验证目for(j =1; j <=i ; j+)x=x+1;设计一个通信录信息管理程序, 程序要求用结构体定利用单链表的各种运算的算法义记录,用单链表存放数据,并具有如下功能:线性实践项来解决实际问题; 要求学生自己42表打开文件(读入文件中记录到链表) ;添加、插入、删查阅 C 语言书本,调试完善实目除、查找一个记录;显示所有记录;存盘(保存链表践项目。中记录到文件)和退出。栈和实践项1、栈和队列的顺序存储结构的所有操作算法的实现;43掌握栈和队列的实际应用队列目2、栈和队列的链式存储结构
7、的所有操作算法的实现;4实践项2串串中字符及子串的查找和匹配掌握串的实际应用目序单主要内容号元用模块化的方法设计一个程序进行二叉树的建立和遍历。主菜单中包括如下功能选项:1.建立二叉树实践项5树2.先序非递归遍历目3.先序递归遍历4.中序递归遍历5.后序递归遍历,求叶节点数6.退出用模块化的方法设计一个程序建立无向图的邻接表并实践项遍历该图。主菜单中包括如下功能选项:6 图目1 建立无向图的邻接表 2 按深度优先遍历 3 按广度优先遍历 4 退出用模块化的方法编一程序测试顺序查找、 折半查找、杂凑查找三种算法。其功能菜单如下:实践项1 顺序查找7 查找目2 折半查找 3 杂凑查找0 退出教学要
8、求主要掌握二叉树的几种遍历的递归算法,先序的非递归遍历算法掌握图的生成和遍历算法写出顺序查找、 折半查找(二分查找)的算法并调试通过学时666用模块化的方法编一程序测试几种排序算法的运行时间。其功能菜单如下:1 选择排序8排序实践项2冒泡排序目3希尔排序4快速排序0退出学时合计72写出几种插入排序算法、交换排序算法和简单选择排序算法并 6 调试理论教学36实践教学36四、课时分配数据结构课程共4 学分,课内 72 学时,其中理论课36 学时,上机 36学时。五、大纲说明本课程必须理论与上机实践操作相结合,并要教、学、练相结合,讲清基本概念,指出知识要点、重点和难点,并通过实例分析解决算法难点;
9、要求学生认真预习、认真听课、认真思索、认真做实验,通过对算法的编程实现来提高学生的理解和动手能力。由于内容多、难度大,要特别注重精讲多练,实践项目一定要提前布置给学生,启发学生独立思考、调动学生的主观能动性, 鼓励学生多提问题、共同探讨和解决问题。重点:线性表的存储和运算;栈和队列的运算;二叉树的遍历和线索,哈夫曼树及应用,二叉排序树;图的生成树,最短路径;散列查找和树表查找;几种排序算法及排序过程。难点:链表的运算;后序遍历二叉树;线索二叉树;最短路径等。六、考核方式理论考核与实践考核相结合,理论考核(主要考基本概念、基本理论、基本算法 ,闭卷考试)占40;实践考核(主要是平时布置的实践项目
10、)占40;平时(出勤、作业、课堂提问等)占20%。七、参考教材教材:数据结构 (C 语言版 ) , 邵增珍杨品林 编著 , 清华大学出版社, 2012年 9月。参考教材 :1. 数据结构 - 用 C语言描述唐策善、李龙澍、黄刘生高等教育出版社 19952.数据结构 (C 语言篇 ) 习题与解析李春葆清华大学出版社 20003.数据结构( C语言版) 严蔚敏、吴伟民清华大学出版社 1997数据结构A课程教学大纲( 56/16 课时)Data Structure A课程代码:课程性质:专业基础理论课/ 必修适用专业:信息计算、信息安全开课学期: 5总学时数: 72总学分数: 4.5编写年月:修订年
11、月:执笔:高学军、刘科峰、李小英数据结构是信息与计算科学专业的一门重要专业基础课程。 当用计算机来解决实际问题时, 就要涉及到数据的表示及数据的处理, 而数据表示及数据处理正是数据结构课程的主要研究对象,通过这两方面内容的学习,为后续课程, 特别是软件方面的课程打下了厚实的知识基础, 同时也提供了必要的技能训练。 因此,数据结构课程在信息与计算科学专业中具有举足轻重的作用。二、课程教学内容及学时分配第1 章绪论(4学时)理解数据、数据元素和数据项的概念及其相互间的关系。 理解数据结构的逻辑结构、存储结构的联系与区别, 以及在数据结构上施加的运算及其实现。 掌握简单的算法分析方法。本章知识点为:
12、数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义;抽象数据类型的定义、表示和实现方法;描述算法的类 C 语言;算法设计的基本要求以及从时间和空间角度分析算法的方法。第 2 章 线性表 ( 10 学时, 2 个学时实验上机)理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明,掌握在这两种表上实现的插入、删除和按值查找的算法。 了解循环链表、双向 ( 循环 ) 链表的结构特点和在其上施加的插入、删除等操作。掌握稀疏多项式在线性表的两种存储结构上的实现方法。本章知识点为: 线性表的逻辑结构定义、 抽象数据类型定义和各种存储结构的描述方法;在线性表
13、的两类存储结构(顺序的和链式的 ) 上实现基本操作;稀疏多项式的抽象数据类型定义、表示和加法的实现。第 3 章栈和队列(6 学时, 2 个学时实验上机)理解栈和队列的定义、 特征及在其上所定义的基本运算。 掌握在两种存储结构上对栈和队列所施加的基本运算的实现。 熟练掌握循环队列和链队列的基本操作实现算法,尤其是队满和队空的描述方法。本章知识点为:抽象数据类型栈的定义;栈的表示和实现;栈的应用;抽象数据类型队列的定义;链队列;循环队列。第 4 章 串 (4 学时, 2 个学时实验上机)熟悉串的七种基本操作的定义, 并能利用这些基本操作来实现串的其它各种操作的方法。 熟练掌握在串的定长顺序存储结构
14、上实现串的各种操作的方法。掌握串的堆存储结构以及在其上实现串操作的基本方法。本章知识点为:串的数据类型定义; 串的三种存储表示: 定长顺序存储结构、块链存储结构和堆分配存储结构;串的各种基本操作的实现及其应用;第 5 章数组和广义表( 6 学时, 2 个学时实验上机)了解数组的两种存储表示方法, 并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。 了解稀疏矩阵的两种压缩存储方法的特点和适用范围, 领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法。本章知识点为: 数组的类型定义和表示方式; 特殊矩阵和稀疏矩阵的压
15、缩存储方法及运算的实现;广义表的逻辑结构和存储结构和广义表的操作。第 6 章树和二叉树(12 学时, 2 个学时实验上机)深刻理解树的定义、 性质及其存储方法, 熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义, 并能画出给定二叉树的二叉链表的结构示意图;理解并掌握二叉树的三种遍历方法,并能写出该三种遍历的算法;会完成树、 森林与二叉树间的相互转换; 理解哈夫曼树的构造方法, 并能对给定的数据集合构造出哈夫曼树。本章知识点为: 二叉树的定义、性质和存储结构;二叉树的遍历和线索化以及遍历算法的各种描述形式;树和森林的定义、存储结构、与二叉树的转换、遍历;树的多种应用。第 7 章图(12 学时
16、, 2 个学时实验上机)理解图的基本概念及术语, 掌握图的两种存储结构 ( 邻接矩阵和邻接表 ) 的表示方法;熟练掌握图的两种遍历 ( 深度优先搜索遍历和广度优先搜索遍历 ) 的算法思想、步骤,并能列出在两种存储结构上按上述两种遍历算法得到的序列; 理解最小生成树的概念,能按 Prim 算法构造最小生成树;了解并掌握拓扑排序、关键路径、最短路径的算法思想。本章知识点为: 图的定义和术语; 图的四种存储结构: 数组表示法、 邻接表、十字链表和邻接多重表;图的两种遍历策略: 深度优先搜索和广度优先搜索; 图的连通性:连通分量和最小生成树; 拓扑排序和关键路径; 两类求最短路径问题的解法。第 8 章
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程 教学大纲 _4348
链接地址:https://www.31doc.com/p-12831848.html