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

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

1、数据结构与算法课程教学大纲课程代码：12281030适用专业：计算机应用技术总学时数： 68学时，其中：理论教学34学时，实践教学34学时。学分：4.5先修课程：C语言程序导论、程序设计导论考核方式：机试一、制订大纲的依据本大纲根据2013年软件技术专业教学计划制订。二、课程简介数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。数据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的若干基本问题。此外，为了构

2、造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括抽象、实现和评价三个层次，从数据表示和数据处理上看有五个基本组成“要素”分别是逻辑结构，存储结构、基本运算、算法及不同数据结构的比较与算法分析。三、课程性质、教育目标(一)性质：本课程为计算机系软件技术专业的专业课。（二）教育目标：通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。四、课程教学内容与基本要求第一部分 绪论 (一)教学内容数据结构的基本概念和术语；抽象数据类型

3、的表示；算法和算法分析。(二)重点、难点重点：数据结构的基本概念及相关术语。难点：算法的时间复杂度分析。(三)教学基本要求知识要求：了解：抽象数据类型及面向对象概念；理解：算法的定义及算法的特性；掌握：数据结构的基本概念、算法的性能分析与度量方法。第二部分 线性表 (一)教学内容1线性表的定义及操作；2线性表的顺序存储定义及操作实现；3单链表的定义；单链表中的插入与删除；带表头结点的单链表；静态链表；4循环链表的类定义及运算； 5双向链表的类定义及运算；6线性表的应用：多项式及其相加。(二)重点、难点重点：顺序表的数组定义方式及实现，单链表的定义及实现。难点：循环链表和双向链表的定义及实现。(

4、三)教学基本要求知识要求：了解：静态链表。理解：线性表的定义及操作。掌握：顺序表的数组定义方式及实现，单链表、循环链表和双向链表的定义及实现。第三部分 栈和队列 (一)教学内容1栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示；栈的两种存储表示上的基本运算；2栈的应用；3队列的抽象数据类型；队列的顺序存储表示及基本运算；队列的链式存储表示及基本运算；4队列的应用举例。(二)重点、难点重点：栈的定义及实现；队列的定义及实现。难点：栈的应用中的表达式求值；循环队列（队列的顺序存储）。(三)教学基本要求知识要求：了解：队列的应用。理解：栈的应用中的递归算法。掌握：栈的定义及实现；队列的定义及实现

5、。栈的应用中的表达式求值；循环队列（队列的顺序存储）。第四部分 串、数组和广义表(一)教学内容1字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配2数组的逻辑结构定义和存储方法；特殊矩阵和稀疏矩阵的压缩存储方法； 3广义表的概念；广义表的表示及操作；广义表存储结构的实现；4广义表的访问算法；广义表的递归算法。(二)重点、难点重点：串和数组的基本概念、存储结构。广义表的概念和存储结构及其相关运算的实现。难点：串的模式匹配算法，特殊矩阵和稀疏矩阵的压缩存储。(三)教学基本要求知识要求：了解：串的一些基本处理操作、矩阵的相关运算。理解：广义表的递归算法。 掌握：串和数组的基本概念、存储结构。广

6、义表的概念和存储结构及其相关运算的实现。串的模式匹配算法，特殊矩阵和稀疏矩阵的压缩存储。第五部分 树和二叉树(一)教学内容1树的基本概念； 2二叉树的定义、性质、存储表示及相关运算；二叉树的遍历；线索二叉树； 3森林和二叉树的相互转换；4哈夫曼树及哈夫曼编码。(二)重点、难点重点：二叉树的定义、性质、存储表示；二叉树的遍历；难点：二叉树的相关运算。(三)教学基本要求知识要求：了解：线索二叉树上的复杂运算实现。 理解：二叉树的相关运算。 掌握：二叉树的定义、性质、存储表示；二叉树的遍历；森林和二叉树的相互转换；哈夫曼树及哈夫曼编码。第六部分 图(一)教学内容1图的基本概念、存储表示（邻接矩阵、邻

7、接表、十字链表，邻接多重表）； 2图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量；3最小生成树：克鲁斯卡尔算法；普里姆算法；4最短路径；5拓扑排序、关键路径。(二)重点、难点重点：图的存储表示；图的遍历；最小生成树；最短路径；难点：关键路径的求解。(三)教学基本要求知识要求：了解：图的存储结构中的邻接多重表。 理解：图的遍历算法。 掌握：图的存储表示（邻接矩阵、邻接表）；图的遍历；最小生成树；最短路径；拓扑排序、关键路径。第七部分 查找(一)教学内容1静态查找（顺序查找、折半查找、分块查找）；2动态查找（二叉排序树）； 3哈希查找。(二)重点、难点重点：静态查找；二叉排序树

8、的建立。难点：二叉排序树的删除；平衡二叉树的调整。(三)教学基本要求知识要求：了解：查找的相关概念、作用。 理解：哈希函数的构造。 掌握：静态查找；二叉排序树的相关知识；哈希查找法和解决冲突的方法。 第八部分 排序(一)教学内容1排序概念；2插入排序、交换排序、选择排序、归并排序、基数排序；3各种排序方法的比较。(二)重点、难点重点：交换排序、选择排序。难点：堆排序。(三)教学基本要求知识要求：了解：各种排序方法的时间复杂度的分析方法。 理解：排序方法“稳定”或“不稳定”的含义。 掌握：各种方法的排序过程及其依据的原则。 第九部分 文件(一)教学内容1基本概念；2文件组织；3顺序文件、随机文件

9、、索引文件、倒排文件。 (二)重点、难点重点：基本概念；顺序文件；索引文件。难点：文件的使用。能力要求：即通过本课程的学习，学生具备基本的、良好的程序设计技能，能够编制高效可靠的程序。素质要求：具备良好的编程习惯和能力。五、学时（理论和实践）分配表序号教学内容课时分配理论教学实践教学考核权重1绪论225%2线性表4422%3栈和队列555%4串、数组和广义表43%5树和二叉树5625%6图4420%7查找4410%8排序448%9文件222%总 计3434100%六、学习教学场地、设施要求（课程中的实践部分）序号项目（实验）名称学习教学场地、设施要求1线性表的应用实践教学在机房进行，机器需要安

10、装有C语言环境。2栈和队列的应用3串的简单操作4二叉树的算法实现5图的遍历6分块查找7冒泡排序说明：分实践项目列出场地、设施要求，如每个实践项目的场地和设施基本相同，也可以一次性描述。七、考核及评分办法考核的原则：闭卷考试。考核方式：考试；期末考试；笔试（闭卷）；各教学环节占总分的比例：实验、作业占30%，期末考试占70%。八、学习资源的选用建议使用教材：实用数据结构基础，陈元春编著，中国铁道出版社，版别（2007年6月，第1版）建议参考书：(一) 数据结构严蔚敏等著 清华大学出版社 1997(二) 数据结构 安训国著 大边理工出版社 版别（2015年9月，第5版）大纲执笔人：方新丽 专业大纲

11、编写组组长审阅： 冯川放 系主任审定： 制定日期： 8 期 定放冯：长编丽方笔版 （ 出边大国数 社学清著蔚构数书考版第月0（，出铁中编，础据：选选% 考期 作、比分环各；（笔期考试考：办评述性以可本施场目个如施、出项实排查遍实法操操应列境环有安需，在应的要施场名）实序分分中课施、教0 文 排0查0 叉 义和组 队 性 绪权教教分内序配分和理力能程编良求序程可编能能序良本基学的本通用的件文；文；基难点件件件引文、件织织念概内教文 。则依程排法。义定不定“排。方的杂时方各求要学序排序择序交难、较比方种序排、并排选换、入；概内学排 。法冲和查哈关的序找静。造函希。作概的查求要学整的二平除排二立建排

12、二态难难找查；）排二；找分查、序（态内教查 分径键序拓路；成小遍；接矩（储存。算的。接构储图求要本解求路径径；生历的示存难、径路序径径法姆普算斯克小量分；量索优；先度性与；）重，字接邻矩示存本内学 分码编及曼哈相树林；树；表质、树二。算的树。现杂上树求要学算运的历遍二；储性定二难、重码编哈曼换转树和林；树索；树；关示存性定；念的内教叉和 分储存压稀矩殊算式。现关及储和的。结存基组和。算的表算运相矩操本一求要本储缩压疏阵特配模串现现关相结念的。储、基数难点法归表义问的现现储存；及表广概；方存阵稀矩殊储义定的匹模符字作符型类的内教义义、 ）存的列列值达中的。及列队及定法归递应用应求要学）存的（环；

13、达表应现及的；及的难点例用列算运及储的；本及存的；类抽用用算运的表种；储链；储序；据抽的内教) 栈分现现的向和环链现及定数表握及的线求 要本现及 定 表表环 现实的定单现方：组数序难点笔加版其项： 的算及类链大；国运定的表态 表单学点；著与的表；的考现作第义存顺（作操的表中内教， 据 选表性法量析期分 算念的结分性的各算定念笔象对类试数求要学评析分性间的语关施相基目构难、析、法示表类排语语遍概构法内学 列 环 需分要本内的程础定场课据）理原系操，中的效施编技教序的良 基，算 念基的排物辑构0据理透使义学本组：标课 专业术系为教程性目内教序性析分较理构数能不、运良、储，逻”编“本能五看良处和数学

14、次三评、括的包结，；此与；评其构虑件考件现及据文好构外织题本的析内码设文、阶设程软程中课结。数义术种以定数程系科方于应杂广构据各。基课学数系操序原编计交序，心核比技学计序的件、算和算选学介构入简简课内订制教 专软 据和依依哈机式论导序静序造言 程。. 概：时 求教践 整教理其学除 数二技应计排： 0难 ：大教；与排构 找 、-大 ：数教其查 践：程键言论依路 专制构遍算件接学心（计原数。据构系。以数中设储阶的求外据考其与路结径、次看“历”、不分难教、性术专标透径构法辑念基算技效操小据础本 量 内；语表、性难语；间要求，念的的邻念析 教内操存 现表的表及表曼运及：树其序方的；环表质本求表二表链向的现栈 现 教；链要的学算用存本历储算二点难及性表环存要应重应码法队的值换存、树义的符；模的储；阵方广存示现的性法数储的的关串配叉压本要分矩相存算组-矩 8 -存