附表1-1 理论课程教学大纲

《附表1-1 理论课程教学大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、理论课程教学大纲课程名称数据结构英文名称DataStructures课程编号不填总学时60学分不填预修课程C语言开课学期不填大纲撰写人黄刘生一、教学目标和基本要求l目的：使学生较全面地掌握各种常用的数据结构，提高其数据抽象和程序设计能力,为学习后续软件课程提供坚实的基础。l基本要求：使学生能够从逻辑结构、存储结构和数据的运算三个方面去掌握各种数据结构的特性,对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题，选择合适的数据结构及设计结构清晰、正确有效的算法解决之。二、课程简介数据结构是计算机学科一门重要的专业基础课，该课程系

2、统地讨论各种常用的数据结构及其应用，以及查找和排序的各种方法及其综合分析比较，培养学生数据抽象和程序设计的能力，算法时、空复杂性的分析能力。三、教学重点、难点1．概论：重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及其相互关系，难点是抽象数据类型和算法复杂度的分析方法。2．线性表：重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用所学到的基本知识设计有效算法解决与线性表相关的应用问题。3．栈和队列：重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。4．串：

3、重点是掌握串上实现的模式匹配算法，这也是本章的难点。5．树：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法解决与树或二叉树相关的应用问题。6．图：重点掌握图在邻接矩阵与邻近表上实现的遍历算法。难点是求图的最小生成树、最短路径、拓扑排序等应用算法及其时间性能分析。7．动态存储管理:重点是内存空间的分配与回收算法，以及可利用空间表的结构。本章难点是无用单元收集算法的理解与掌握。8．查找：重点掌握顺序查找、二分查找、二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及B-树上

4、的插入和删除算法。9．文件：本章重点是介绍存储在外存上的数据结构（文件）的有关概念、各种文件的特点、组织方法及查询和更新操作。四、教材名称及主要参考书《数据结构C语言版》严蔚敏、吴伟民，清华大学出版社，2000。《数据结构第2版》黄刘生、唐策善，中国科技大学出版社，2001。"DataStructureswithC++"WilliawFordetal.,PrenticeHallInc.,1996."DataStructures&ProgramDesigninC,2ndEd."RobertKruseetal.,PrenticeHallInc

5、.,1997.五、课程章节主要内容及学时分配第一章概论（3学时）第一节基本概念和术语第二节学习数据结构的意义第三节抽象数据类型第四节算法的描述和分析第二章线性表（6学时）第一节线性表的逻辑结构第二节线性表的顺序存贮结构第三节线性表的链式存贮结构第四节顺序表和链表的比较第三章栈和队列（6学时）第一节栈第二节队列第三节栈与队列的应用实例第四章串（4学时）第一节串及其运算第二节串的存贮结构第三节串的模式匹配第六章树（10学时）第一节树的概念第二节二叉树第三节二叉树的遍历第四节线索二叉树第五节树和森林第六节哈夫曼树及其应用第七节树与等价问题、树的

6、计数第六章图（10学时）第一节图的概念第二节图的存贮结构第三节图的遍历第四节图的连通性问题第五节最短路径第六节有向无环图及其应用第七章动态存储管理（5学时）第一节概述第二节可利用空间表及分配算法第三节边界标识法第四节伙伴系统第五节无用单元收集第八章查找（8学时）第一节基本概念第二节静态查找第三节动态查找第四节散列查找第九章文件简介（2学时）第一节文件基本概念第二节顺序文件与索引文件第三节ISAM和VSAM文件第四节散列文件六、系教学委员会意见组长签字：年月日七、系主任意见系主任签字：年月日