2022年计科数据结构教学大纲.docx

精选学习资料 - - - - - - - - - 数据结构理论教案大纲课程编号： 404511043 课程中文名称 ：数据结构课程英文名称 ：Data Structures 课程类别： 专业基础必修课总 学 时： 84 学时 <其中理论 48 学时,试验16 学时,课外20 学时）总 学 分： 5 适用专业： 运算机科学与技术一、课程的性质、位置与任务 数据结构运算机科学与技术专业中一门重要的专业基础课程；当用运算机来解决实际 问题时,就要涉及到数据的表示及数据的处理,而数据表示及数据处理正是数据结构课程 的主要讨论对象,通过这两方面内容的学习,为后续课程,特殊是软件方面的课程打下了 厚实的学问基础,同时也供应了必要的技能训练；因此,数据结构课程在运算机应用专业 中具有举足轻重的作用；本课程的任务是：在基础方面,要求同学把握常用数据结构的基本概念及其不同的实 现方法；在技能方面,通过系统学习能够在不同储备结构上实现不同的运算,并对算法设 计的方式和技巧有所体会；二、课程的基本要求 把握重要数据结构的概念、使用方法及实现技术；学会做简洁的算法分析,包括算法 的时间代价和空间代价；三、本课程与其他课程的联系 1> 本课程先修课程 高级语言程序设计 > 2> 本课程的后续课程 操作系统、数据库原理 >四、教案内容、基本要求及学时支配第一章 概论1. 教案目的及要求 领悟数据、数据元素和数据项的概念及其相互间的关系； 清晰数据结构的规律结构、储备结构的联系与区分,以及在数据结构上施加的运算 及其实现； 懂得抽象数据类型的概念； 2. 教案重点 数据、数据元素、数据项；1 / 9 名师归纳总结 - - - - - - -第 1 页,共 9 页精选学习资料 - - - - - - - - - 规律结构和数据结构在概念上的联系与区分； 运算的概念； 储备结构及其三个组成部分； 抽象数据类型和数据抽象； 评判算法优劣的标准及方法；3. 教案难点 区分算法与程序； 规律结构、储备结构的联系与区分； 抽象数据类型与数据抽象； 算法的时间复杂度分析；4. 教案内容及进度支配 4学时 > 1.1 数据结构的概念 1.2 抽象数据类型 1.3 算法和算法分析其次章 线性表1. 教案目的及要求 懂得线性表的定义及其运算； 懂得次序表和链表的定义、组织形式、结构特点和类型说明； 把握在这两种表上实现的插入、删除和按值查找的算法； 明白循环链表、双 2. 教案重点 循环 >链表的结构特点和在其上施加的插入、删除等操作； 线性表的定义及规律上的特点； 次序表上插入、删除和定位运算的实现； 单链表的结构特点及类型说明； 头指针和头结点的作用及区分； 指针操作； 定位、删除、插入运算在单链表上的实现； 循环链表、双链表的结构特点； 循环链表、双链表上删除与插入运算的实现；3. 教案难点 线性表与线性结构的联系与区分； 头结点在链表中的作用；指针操作； 删除、插入运算中的指针操作次序； 双链表上指针的操作次序4. 教案内容及进度支配 < 8学时 ）2 / 9 名师归纳总结 - - - - - - -第 2 页,共 9 页精选学习资料 - - - - - - - - - 2.1 线性表规律结构 2.2 线性表的次序储备及运算实现 2.3 线性表的链式储备和实现第三章 栈和队列1. 教案目的及要求 懂得栈的定义、特点及在其上所定义的基本运算； 把握在两种储备结构上对栈所施加的基本运算的实现； 懂得队列的定义、特点及在其上所定义的基本运算； 把握在两种储备结构上对队列所施加的基本运算的实现；2. 教案重点 栈的定义及规律特点； 栈上的基本运算； 栈的次序储备结构及运算实现； 栈的链式储备结构； 入栈、出栈等运算在链栈上的实现； 队列的定义及规律特点； 队列上的基本运算； 队列的次序储备结构及其上的运算实现； 队列的链式储备结构； 入队、出队等运算在链队列上的实现；3. 教案难点 次序栈的溢出判定条件； 循环队列的队空、队满判定条件； 循环队列上的插入、删除操作；4. 教案内容及进度支配 < 4 学时 ）3.1 栈 3.2 栈应用举例 3.3 队列 3.4 队列应用举例第四章 串1. 教案目的及要求 明白串的定义； 懂得和领悟串的储备方式；3 / 9 名师归纳总结 - - - - - - -第 3 页,共 9 页精选学习资料 - - - - - - - - - 把握常用的串运算；2. 教案重点 串的基本概念、基本运算； 串的两种储备方式； 串的模式匹配算法；3. 教案难点 串的模式匹配算法； 串的基本运算的综合应用 4. 教案内容及进度支配 < 2 学时 ）4.1 串及其基本运算 4.2 串的定长次序储备及基本运算 4.3 串的堆储备结构第五章 数组和广义表1. 教案目的及要求 懂得多维数组的结构特点和在内存中的两种次序储备方式； 懂得并把握矩阵和特殊矩阵元素在储备区中地址的运算； 领悟稀疏矩阵的压缩方式和简洁运算； 明白广义表的定义和基本运算；2. 教案重点 多维数组的规律结构； 多维组的两种次序储备方式； 运算给定元素在储备区中的地址； 对称矩阵、三角矩阵的压缩储备方式； 运算给定元素在储备区中的地址； 稀疏矩阵的三元组表表示方法；3. 教案难点 稀疏矩阵的压缩储备表示下的运算的实现 4. 教案内容及进度支配 < 4 学时 ）5.1 多维数组 5.2 特殊矩阵的压缩储备 5.3 稀疏矩阵 5.4 广义表第六章 树与二叉树4 / 9 名师归纳总结 - - - - - - -第 4 页,共 9 页精选学习资料 - - - - - - - - - 1. 教案目的及要求 深刻懂得二叉树的定义、性质及其储备方法； 娴熟把握二叉树的二叉链表储备方式、结点结构和类型定义； 懂得并把握二叉树的三种遍历算法； 把握二叉树的线索化方法； 敏捷运用二叉树的遍历方法解决相关的应用问题； 深刻懂得树的定义、术语； 领悟并把握树的各种储备结构； 娴熟把握森林与二叉树间的相互转换； 领悟树和森林的遍历； 明白树的简洁应用；2. 教案重点 二叉树的定义、规律特点及五种基本形状； 二叉树的五个性质； 在二叉树上定义的基本运算； 二叉树的链式储备结构及其类型说明； 二叉树的次序储备结构及其类型说明； 二叉树链式储备结构的组织方式； 二叉树的三种遍历方法及其算法； 以遍历为基础在二叉树上实现的几种运算； 哈夫曼树和哈夫曼算法； 树的储备结构；11> 森林与二叉树的转换；3. 教案难点 二叉树的递归定义； 二叉树链式储备结构的组织方式； 三种遍历的主要区分； 二叉树上的复杂运算； 哈夫曼算法及其应用； 森林与二叉树的转换； 判定树； 等价关系与等价类问题；4. 教案内容及进度支配 < 6 学时 ）6.1 二叉树定义与性质 6.2 储备实现基本操作的实现 6.3 二叉树的遍历5 / 9 名师归纳总结 - - - - - - -第 5 页,共 9 页精选学习资料 - - - - - - - - - 6.4 线索二叉树 6.5 二叉树的应用 6.6 树的概念、基本操作与储备 6.7 树、森林与二叉树的转换 6.8 树或森林的遍历 6.9 树的应用第七章 图1. 教案目的及要求 懂得图的基本概念及术语； 把握图的两种储备结构 邻接矩阵和邻接表>的表示方法；>的算法思想、步 娴熟把握图的两种遍历 深度优先搜寻遍历和广度优先搜寻遍历骤,并能列出在两种储备结构上按上述两种遍历算法得到的序列； 懂得最小生成树的概念,能按Prim 算法构造最小生成树； 领悟并把握拓扑排序、关键路径、最短路径的算法思想；2. 教案重点 懂得图的定义、术语及其含义； 把握各种图的邻接矩阵表示法及其类型说明； 懂得并把握图的按深度优先搜寻遍历方法和按广度优先搜寻遍历方法； 领悟生成树和最小生成树的概念； 把握由 Prim 算法思想构造最小生成树按 Prim 算法思想； 领悟拓扑序列和拓扑排序的概念； 懂得并把握拓扑排序的算法思想； 懂得并把握关键路径的算法思想； 懂得并把握最短路径的算法思想；3. 教案难点 正确懂得与区分图的常用术语； 区分图的两种储备结构的不同点及其应用场合； 关键路径的算法思想； 最短路径的算法思想；4. 教案内容及进度支配 < 8 学时 ）7.1 图的基本概念 7.2 图的储备表示 7.3 图的遍历 7.4 图的连通性 7.5 最小生成树6 / 9 名师归纳总结 - - - - - - -第 6 页,共 9 页精选学习资料 - - - - - - - - - 7.6 最短路径 7.7 有向无环图及其应用第八章 查找1. 教案目的及要求 明白查找的基本思想及查找胜利和不胜利的概念； 把握在次序表、有序表、索引表、散列表等上的查找方法和算法,并能求出相应的 平均查找长度； 懂得并把握二叉排序树、平稳二叉树 B-树的各种算法；2. 教案重点 查找表的基本概念及查找原理； 查找表的次序储备结构、次序表及其类型说明； 查找运算在查找表和有序表上的实现； 二叉排序树的定义、性质及各结点间的键值关系； 二叉排序树的查找算法和基本思想； 平稳二叉排序树的概念； B- 树和 B+树的概念； 散列表及散列储备和散列查找的基本思想； 各种散列表的组织、解决冲突的方法； 在散列表上实现查找、插入和删除运算的算法；3. 教案难点 懂得查找表的规律结构是集合,它的运算以查找为核心； 二叉排序树上的插入算法； 平稳二叉树的旋转平稳算法； 散列表上的有关算法4. 教案内容及进度支配<6 学时）8.1 基本概念与术语 8.2 静态查找表 8.3 动态查找表 8.4 哈希表查找 杂凑法 > 第九章 排序1. 教案目的及要求 领悟排序的基本思想和基本概念； 懂得并把握插入排序、冒泡排序、快速排序、直接挑选排序、堆排序、归并排序和7 / 9 名师归纳总结 - - - - - - -第 7 页,共 9 页精选学习资料 - - - - - - - - - 基数排序的基本思想、步骤、算法准时空效率分析； 明白外排序的定义和基本方法；2. 教案重点 排序基本概念及内排序和外排序、稳固排序和非稳固排序的区分； 插入排序的基本思想、基本步骤和算法； 冒泡排序的基本思想、基本步骤、算法和算法分析； 快速排序的基本思想、基本步骤和算法； 直接挑选排序的基本思想、基本步骤、算法和算法分析； 堆排序的基本思想、基本步骤和算法； 归并排序的思想； 两个有序文件合并的方法和算法； 二路归并排序的算法和时空性能 3. 教案难点 快速排序算法； 堆排序方法 < 6 学时 ）4. 教案内容及进度支配 9.1 基本概念 9.2 插入排序 9.3 交换排序 9.4 挑选排序 9.5 二路归并排序 9.6 基数排序 9.7 外排序五、实践性教案环节 数据结构是信息与运算科学专业中一门重要的专业基础课程；当用运算机来解决实际 问题时,就要涉及到数据的表示及数据的处理,而数据表示及数据处理正是数据结构课程 的主要讨论对象,通过这两方面内容的学习,为后续课程,特殊是软件方面的课程打下了 厚实的学问基础,同时也供应了必要的技能训练；因此,数据结构课程在运算机应用专业 中具有举足轻重的作用；本课程的任务是：通过实践,同学对常用数据结构的基本概念及其不同的实现方法的 理论得到进一步的把握,并对在不同储备结构上实现不同的运算方式和技巧有所体会；六、教案方法与手段课堂讲授为主,结合辅导、答疑,进行必要的上机试验；课外 支配,可以到试验室上机,为试验课作预备；七、考核与成果评定20 学时主要由同学自行1、考核目的：本课程是以有用为最终目的,因此,考核的重点是考察同学对各种数据8 / 9 名师归纳总结 - - - - - - -第 8 页,共 9 页精选学习资料 - - - - - - - - - 结构的懂得程度和基于这些数据结构进行算法设计的才能；不要求同学死记详细的定义,但需要同学在实践过程中逐步娴熟运用；2、考核形式：采纳试验考核、期末考核与平常成果相结合的方式；其中 , 平常考核：平常作业占考核总成果的 5%,平常考勤占考核总成果的 5%,试验成果占考核总成果的 50%,期末考核：采纳笔试,它占总成果的 40%,考试方式为闭卷,答题时限 100 分钟；以上三个成果累计 60 分以上 <包括 60 分）算考核通过；3、主要考核内容：数据结构的概念,线性表,栈,队列,递归概念,广义表,树和二叉树,图,查找,排序；4、考核题型：有单项题、填空题、应用题、程序填空题和综合编程题等五种题型；5、成果评定：试验考核 50%,平常 10%,期未 40% 八、教材及参考书教材：1 严蔚敏 , 吴伟民 . 数据结构 <C 语言版） M . 第一版 >北京：清华高校出版社.1997 参考书：2 Sartaj Sahni. Data Structure, Algorithms, and Application in C+. The McGraw-Hill Company Inc.1998 M 第一版 > 数据结构、算法与应用C+语言描述 .北京 : 机械工业出版社 .1999 3 Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996 语言描述 . 北京 : 清华高校出版社,1997 M 第一版 > 数据结构 C+4 徐孝凯 . 数据结构有用教程 <C/C+描述） M . 第一版 >北京 : 清华高校出版社 .1999 5 陈慧南 . 数据结构 <使用 C+语言描述） M . 第一版 >南京 : 东南高校出版社 .2001 6 殷人昆 , 陶永雷 , 谢如阳等 . 数据结构 <用面对对象方法与 C+描述） M . 第一版 >北京 :清华高校出版社 .1999 执笔人：祁文青审核人：祁文青 <盖章）2022 年 9 月 1 日9 / 9 名师归纳总结 - - - - - - -第 9 页,共 9 页