数据结构与算法 教学大纲.docx

1、数据结构与算法课程教学大纲一、基本信息课程编码：英文名称：Data structures and algorithms授课语言：汉语学分：4学 时：56学时（授课48，实验8，上机0，课外0）适用对象：面向计算机大类课程性质：学科基础必修课先修课程：C/C+程序设计开课院系：信息工程学院使用教材(或讲义)： 主教材：数据结构与算法C+实现，慕晨等编著，清华大学出版社，2022年5月辅助教材：严蔚敏，吴伟民编著，数据结构（C语言版），清华大学出版社，2011年11月参考教材：无二、课程简介 “数据结构与算法”是计算机专业的核心基础课程之一，在整个专业教学中占有十分重要的地位。本课程既具有较强的理

2、论性，同时又注重实际动手能力的培养。通过课堂教学、课外练习和课程设计，使学生了解数据对象的特性，掌握数据的逻辑结构与存储结构，初步具备数据组织和算法设计能力，从而提高学生的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。三、课程任务、目的与要求课程任务：数据结构重点培养学生分析和解决非数值问题的能力，能够独立设计和开发相应的解决方案；了解数据结构在实际工程项目和社会领域的应用，训练学生认识工程与社会的关系；了解计算机学科的新领域，认识各种算法在这些领域的可能应用，培养终身学习的能力。课程目的：1） 通过本课程的学习，使学生对基本数据结构具备分析、设计和复用的能力，并初步具备算法分

3、析和设计能力，能够使用合适的数据结构进行程序设计与开发2） 本课程培养学生达到以下能力要求，并支撑对应的毕业要求指标点。1、能够运用数据结构知识将复杂工程问题转化为计算机能够识别和处理的问题，并进行分析和推演。2、理解不同存储结构、不同排序和查找算法的优缺点及应用场景，对于实际工程问题，能够设计多种解决方案，并结合文献查阅及研究，比较、寻求可替代的解决方案。3、理解各种查找、排序和其他算法的原理、方法和局限性，具备开发相应的信息检索工具的能力。4、能够分析和评价基于不同存储结构、不同的算法思想和不同的算法复杂度设计出的解决方案对于社会、健康、安全、法律以及文化的影响，具备在工程实践中考虑上述制

4、约因素的意识。课程要求：1） 要求学生掌握线性表、树、图等各种数据结构的逻辑特点、存贮方法以及基本运算，掌握大批量数据的组织方法。2） 要求学生初步掌握算法分析与设计能力。3） 要求学生掌握常用的查找，排序的原理与技术方法。 4） 要求学生能够对具体问题选择适当的结构，并编写出结构清晰的程序。四、教学内容及要求序号章 节参考学时教学内容基本要求1第1章 绪论4本章学习数据结构算法有关的基本概念和基本方法。本章难点是算法分析的基本思想以及算法复杂度的计算。掌握以下概念：逻辑结构、存储结构、抽象数据类型等基本概念，能够运用大O符号描述算法时间复杂度。2第2章 线性表8本章重点介绍数据的线性结构，包

5、括：1）线性表的逻辑结构2）线性表的顺序存储及实现3）线性表的链接存储及实现4）顺序表和单链表的比较5）线性表的其他存储方法本章难点在于链表的实现、模版类的作用以及静态链表的设计思想。掌握以下知识：1）掌握线性表的逻辑结构与存储结构2）掌握顺序表、单链表的特点、类定义、基本操作、实现方法及时间性能3）能够利用线性表编程解决较简单的实际问题4）理解构造函数、析构函数、模板类的作用及设计思想5）理解循环链表、双链表、静态链表以及间接寻址的应用目标及设计思想第3章 栈和队列4本章主要介绍两类操作受限的线性表：栈和队列1）栈和队列的逻辑结构以及抽象数据类型定义2）分别用顺序结构和单链表结构实现栈和队列

6、3）栈和队列的典型应用，栈与递归本章难点在于递归的理解以及前缀、中缀、后缀表达式的转换。掌握以下知识：1） 掌握栈和队列的逻辑结构2） 掌握顺序栈、链栈、循环队列和链队列的特点、类定义、基本操作、实现方法及时间性能3） 掌握递归的思想方法，能够使用递归解决问题4） 理解前缀、中缀、后缀表达式的转换，以及计算机处理表达式求值的方法。第4章 字符串和多维数组4本章主要介绍两类特殊的线性表：字符串与数组1）字符串的存储结构2）字符串的模式匹配3）数组的存储方式及寻址方法4）特殊矩阵和稀疏矩阵的压缩存储方法本章难点在于模式匹配的BF算法以及KMP算法掌握以下知识：1） 掌握串的逻辑结构和存储结构2）

7、掌握模式匹配原理以及BF算法，理解KMP算法思想3） 理解多维数组的存储思想和寻址方法4） 了解特殊矩阵和稀疏矩阵的压缩存储思想第5章 树和二叉树9本章学习树的逻辑结构和存储结构1）树的逻辑结构2）树的存储结构3）二叉树的逻辑结构4）二叉树的存储结构及实现5）树、森林与二叉树的转换6）二叉树的应用本章难点在于二叉树的非递归遍历以及线索链表掌握以下知识：1） 了解树的逻辑结构与存储结构2） 掌握二叉树的逻辑结构与存储结构3） 掌握二叉链表的构造、析构、遍历等操作的实现4） 理解线索链表的设计方法5） 理解非递归遍历的思想和实现6） 掌握树、森林与二叉树的转换7） 掌握哈夫曼树及哈夫曼编码第6章

8、图9本章学习图的逻辑结构和存储结构实现以及图的应用。1）图的逻辑结构2）图的存储结构及实现3）图的应用l 最小生成树l 最短路径l AOV网与拓扑排序l AOE网与关键路径本章难点在于最短路径的迪杰斯特拉算法。掌握以下知识：1） 掌握图的逻辑结构2） 掌握邻接矩阵和邻接表的存储方法与遍历操作3） 掌握最小生成树与prim算法4） 掌握最短路径与迪杰斯特拉算法5） 理解AOV网与AOE网第7章 查找5本章学习查找概念和查找算法1）查找的基本概念2）线性表的查找技术3）树表的查找技术4）散列表的查找技术掌握以下知识：1） 掌握线性表的查找技术2） 掌握二叉排序树的构造、插入、删除和查找思想3） 理

9、解二叉平衡树和B树的构造思想4） 掌握哈希表的查找思想，掌握基本的散列函数和冲突处理方法5） 能够熟练运用三种以上的查找算法第8章 排序5本章学习排序概念和排序算法1）排序的基本概念2）插入排序3）交换排序4）选择排序5）归并排序6）分配排序掌握以下知识：1） 掌握各类排序算法的总体思路2） 掌握并熟练运用各类简单排序算法3） 理解各类改进排序的思想4） 掌握快速排序、堆排序的实现方法5） 掌握分配排序的思想方法6） 能够熟练运用至少一种高效的排序方法五、课内实验（上机）名称及基本要求序号参考学时实验（上机）名称基本要求14线性表基本操作自行设计并编程实现顺序表与单链表的构造、查找、插入、删除、输出等基本操作，掌握线性表的存储原理和基本操作。选做：根据查找频率重排单链表22二叉树基本操作利用二叉树解决实际问题，编程实现二叉树的构造、遍历、查找、输出等基本操作，掌握树结构的处理方法。选做：二叉树的重构22图的基本操作选用邻接矩阵和邻接表实现以下操作：图的构造、遍历，掌握图的常用存储结构和基本操作。选做：最短路径与最小生成树六、课外学时分配、考核和评价方式本课程采用课堂讲授结合实验和课程设计，注重思维方式和实际编程能力的训练。平时成绩占15%，包括考勤、作业等，实验成绩占15%，期末考试占70%。其中，期末考试以能力测试题型为主，计算、综合应用、编程类题目占比不少于70%。 5