课程编码：044078

课程类别：专业基础课（必修）,

先修课程：程序设计基础，离散数学

适用专业：软件工程(卓越计划班),

开课院部：计算机与网络安全学院

课程负责人：曲超

《算法与数据结构》是计算机科学与技术专业的必修课程之一，是重要的专业基础课程。主要讲授数据的结构、类型及相互联系，定义其规范的处理方法，分析数据的逻辑结构在计算机内的典型存储结构以及在此之上的一系列重要算法。主要讲授内容包括：数据、数据结构和抽象数据类型等概念；从抽象数据类型的角度，分别讨论了线性表、栈、队列、串、数组、广义表、树和二叉树及图等基本类型的数据结构及其应用；讨论了数据的查找和排序等算法。本课程的教学目标是培养学生理解和掌握设计和应用数据结构的主要方法，对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。

1. 知识与技能目标：通过本课程的学习，使学生掌握线性表、堆栈和队列、串、数组、广义表、树和二叉树、图等基本数据组织结构；理解其基本概念和基本原理；掌握递归算法、排序、查找等基本算法；能够将实际问题转换为正确的算法和数据结构描述，并对问题加以求解，养成较好的编程能力。

2. 过程与方法目标：通过对数据结构和算法的系统学习与研究使学生学会分析研究数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法；初步掌握算法的时间分析和空间分析技术，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础；本课程的学习也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易懂，符合软件工程的规范。

3. 情感、态度与价值观发展目标：通过本课程的学习，培养作为一个软件开发人员必须具备的坚持不懈的学习精神，严谨治学的科学态度和积极向上的价值观，为未来的学习、工作和生活奠定良好的基础。

绪论	2	数据及数据结构的基本概念，算法与算法分析；	授课
线性表	8	线性表的基本概念，顺序表的存储结构、基本操作；单链表的存储结构、基本操作。	授课	顺序线性表的基本操作；单线性链表的基本操作。
堆栈和队列	6	顺序栈（队列）、链栈（队列）的基本操作；循环顺序队列、链队列的基本操作；链栈的基本操作；	授课	循环顺序队列的基本操作。优先级队列算法设计，队列及堆栈综合应用。
串	2	串的基本操作，模式匹配算法BF、KMP	授课
数组、递归算法	4	矩阵的压缩存储，包括特殊矩阵、稀疏矩阵的压缩存储；递归算法的概念及执行过程；递归程序设计方法；递归算法与动态规划。	授课	线性结构的递归算法设计、复杂问题求解
树和二叉树	10	树的定义、基本术语；二叉树的定义、性质、存储结构、二叉树的遍历。二叉树存储效率分析。线索二叉树、Huffman树及其构造。决策树的基本概念及应用。	授课	二叉树的应用，Huffman编码的设计
图	10	图的数组、邻接链表存储结构；图的遍历算法；最小生成树及其构造算法，最短路径；拓扑排序、关键路径。AOE，AOV网。TPS问题及贪心算法概述。	授课	最小生成树、拓扑排序、最短路径的引用，拓扑排序、关键路径的设计
排序	6	插入排序，选择排序，交换排序，归并排序，基数排序；排序效率分析。	授课	排序算法应用
查找	6	顺序表、有序表的查找，静态树表、索引顺序表的查找，二叉排序树，平衡二叉树，哈希查找。B树，B+、B-树。	授课	高效查找算法设计

考核形式	评价标准	权重
考勤	缺勤一次扣1分	5%
作业	作业上交即给分数，根据完成质量上下浮动。	10%
实验	能够设计出算法，独立实现程序，运行结果正确，按照要求完成实验报告。实验报告上交即给分数，根据完成质量上下浮动。	10%
期中考试	参考答案及评分标准	5%
期末考试	参考答案及评分标准	70%

使用教材：《数据结构——使用C语言（第5版）》，朱战立，电子工业出版社，2014年出版

教学参考资料：

[1]《Introduction to Algorithms》,Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein,机械工业出版社.

[2]《数据结构与算法分析》,Mark Allen Weiss,人民邮电出版社.

[3]《Algorithmics The Spirit of Computing》, David Harel.

[4] 《数据结构与算法分析》, Clifford A. Shaffer著，张铭、刘晓丹 译, 电子工业出版社.

[5] 《数据结构(C语言版)》，严蔚敏、吴伟民，清华大学出版社.

[6] 《数据结构与算法》，齐德昱，清华大学出版社.

[7] 《数据结构与算法学习辅导及习题详解》，张乃孝，电子工业出版社.