数据结构与算法教学大纲

1、数据结构与算法教学大纲适用专业：计算机网络技术课程编号： 总学时：60 实验学时： 上机学时： 12 学分：7.5第一部分 使用说明一、课程的性质、地位和教学目标1、课程的性质、地位本门课程是计算机网络技术专业中一门重要的专业基础课。用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是数据结构要研究的内容。本课程主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。2、教学目标通过本门课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理

2、和数据库等课程奠定基础。二、教学要求通过教学，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用。对同一种逻辑结构的数据，讨论其不同的物理结构和相应的有关算法，掌握查找和排序的各种方法。培养、训练学生选用合适的数据结构和编写质量高、风格好的算法设计和程序设计应用程序的能力，并为后续课程的学习打下良好的理论基础和实践基础。要求学生能够掌握数据的逻辑结构、物理结构以及各种结构所定义的运算和应用。三、实施说明1、成绩考核方法本课程为考试课。平时成绩（含到课率、课堂表现、作业、小论文、单元测试、期中测试）占10%，实践成绩占30%，期末课程结课考试成绩占60%。2、教学方

3、法、教学手段（1）能够在教师边讲解边演示，学生边操作的计算机机房上课。（2）开发一些多媒体课件或网页课件，为课堂教学和案例分析所使用。四、课内实践环节的要求1、名称：课内实验2、主要内容与要求课内实验共14学时，至少应包括下列内容：线性表、栈和队列、二叉树等内容，并且至少应包含一个4学时以上的综合实验。五、作业要求至少安排7次作业，但作业不一定非要是纸面作业。六、本课程与其它课程的联系在学习这门课之前，要先学习高等数学、C程序设计、离散数学。 七、教材和参考书目  数据结构 严蔚敏等著 清华大学出版社 2006年7月 数据结构算法与教程（第二版） 李春葆，陶红艳 清华大学出

4、版社 2007年10月 数据结构（第二版） 张世和，徐继延 清华大学出版社 2007年9月第二部分 教学内容纲要第一部分标题绪论2、具体内容 数据、数据元素、数据结构、数据类型、抽象数据类型的概念；算法、算法描述与算法分析。3、教学要求了解数据结构所研究的问题，理解数据结构的基本概念，及抽象数据类型和软件构造方法，掌握算法的概念、算法设计的要求和算法效率的度量方法。了解算法的书写规范。4、教学重点和难点 算法及算法分析第二部分1、 标题线性表2、具体内容 线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；链表；用线性表表示一元多项式及实现稀疏多项式的相加等运算。3、教学

5、要求了解线性表的逻辑结构定义掌握物理存储结构掌握线性表的链式存储结构及顺序存储结构的基本操作线性表的应用4、教学重点和难点基本操作及应用第三部分1、标题栈和队列2、具体内容栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用、递归算法的设计。3、教学要求了解栈和队列的基本特性掌握两种存储结构上栈和队列的基本操作掌握栈和队列的基本应用4、教学重点和难点栈和队列的基本操作和应用第四部分1、 标题串2、具体内容 串的逻辑结构定义、串的基本运算及其实现；串的匹配算法。3、教学要求了解串的逻辑结构的定义掌握串的基本运算了解串的匹配算法 第五部分1、标题数组和广义表2、具体内容数组

6、的逻辑结构定义和存储方法；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的逻辑结构和存储结构以及广义表运算的递归算法。3、教学要求了解数组的逻辑结构的定义及存储方法掌握特殊矩阵和稀疏矩阵的压缩存储方法了解广义表的基本知识 第六部分1、标题树和二叉树2、具体内容 树的基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；线索二叉树；森林和二叉树的相互转换；树的应用；哈夫曼树及哈夫曼编码3、教学要求了解树的基本概念 掌握二叉树的定义、性质、存储表示、遍历掌握树的应用掌握哈夫曼树及哈夫曼编码4、教学重点和难点重点掌握二叉树相关的操作，难点哈夫曼树及哈夫曼编码第七部分1、 标题图2、具体内容 图的基本概念、

7、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；拓扑排序、关键路径；最短路径3、教学要求掌握图的存储表示掌握图的遍历，连通性问题了解拓扑排序掌握关键路径和最短路径4、教学重点和难点关键路径和最短路径第八部分1、 标题查找2、具体内容在顺序表、有序顺序表、索引顺序表结构上的查找算法；二叉排序树的操作算法及性能分析；B树的概念及相关算法；哈希冲突解决方法（线性探查法、链表法）。3、教学要求掌握各种查找算法 4、教学重点和难点二叉排序树的操作算法及性能分析；B树的概念及相关算法第九部分1、 标题排序2、具体内容内部排序介绍插入排序、快速排序（交换排序）、选择排序、归并排

8、序；排序的基本思想和算法分析。外部排序介绍外存储器（磁带、磁盘）简介；多路平衡归并、置换选择排序、最佳归并树及磁带归并排序。3、教学要求掌握各种排序算法4、教学重点和难点重点掌握内部排序第三部分 学时分配内容学时讲课实验上机备注绪论220线性表862栈和队列862串220数组和广义表440 树和二叉树1082 图440 查找880排序880综合实验606合 计604812第四部分 实验学时分配序号实 验 项 目实验学时实验类型实验要求内 容 提 要1线性表2验证掌握线性表的顺序存储及链式存储的应用顺序表的归并链式存储中的集合差 2栈和队列 2验证掌握栈和队列的应用算术表达式求值 3二叉树2验证掌握二叉树