| 课程号 |
04830050 |
学分 |
3 |
| 英文名称 |
Data Structure and Algorithm (A) |
| 先修课程 |
计算概论、离散数学 |
| 中文简介 |
培养学生掌握数据结构和算法的设计分析技术，提高程序设计的质量，根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。使得学生在将来的学习、研究和工作中，具备设计和实现高效的数据结构和算法的能力。
本课程方案的基本设计原则可以概括为以下三个方面：
（1）强调基础数据结构与算法的训练，从问题求解的角度，培养学生运用数据结构和算法基本理论来分析和解决问题的能力。
（2）注重实践能力和工程能力的培养，使得学生遵从软件开发的规范性，并建立起数据结构与算法设计和问题求解的知识体系。
主要的关注点，是数据知识与算法知识体系以及问题求解的计算思维能力。课程的重点：从广度和深度上把握数据结构与算法的知识体系，了解基本数据结构和经典算法，掌握理论、抽象和设计方法。课程的难点：问题抽象、算法抽象、数据结构抽象等数学抽象能力的培养；树和图结构中搜索和回溯思想；排序等算法的时空效率分析和权衡；检索和索引的效率；AVL、伸展树、红黑树等平衡树、B/B+树等数据结构中的平衡问题；根据实际问题，选择合适的数据模型，设计合适的算法，运用所学理论知识来求解；各种数据结构和算法在学科前沿中的应用和发展。
针对上述重点和难点，本课程从理论、抽象和设计的三个层次展开数据结构与算法教学，注重数据结构基本概念和抽象数据类型表述，使得学生可以在不同的设计阶段采用不同的抽象数据类型作为设计的基础，在适当的抽象层次上考虑程序的结构和算法。对每种数据结构都从其数学特性入手，先介绍其抽象数据类型；再讨论其不同的存储方法，与学生一起讨论研究不同存储实现下的可能算法；然后结合算法分析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法。这样，充分调动学生主动学习的积极性，使得学生学到数据结构与算法所涉及的计算思维方法。 |
| 英文简介 |
Understand principles and theories of Data Structures and Algorithms; complexity analysis and tradeoff, able to design and implement efficient and effective data structures and algorithms to solve problems.
Covers programming, data structures, and algorithm analysis.
Topics include the organization and implementation of fundamental data structures such as list, binary tree, tree and forest, graph; the efficient sorting and searching algorithms; complexity analysis and tradeoff; data abstraction and problem solving.
|
| 开课院系 |
信息科学技术学院 |
| 通选课领域 |
|
| 是否属于艺术与美育 |
否 |
| 平台课性质 |
|
| 平台课类型 |
|
| 授课语言 |
中文 |
| 教材 |
数据结构与算法,张铭、王腾蛟、赵海燕,高等教育出版社,2008.6,1,9787040239614；
数据结构与算法实验教程,张铭、赵海燕、王腾蛟、宋国杰,高等教育出版社,2011.1,数据结构与算法——学习指导与习题解析,张铭、赵海燕、王腾蛟,高等教育出版社,2005.10, |
| 参考书 |
1,9787040302141；
1；
|
| 教学大纲 |
1. 介绍基本数据结构和基本算法分析技术。这一部分将介绍常用基本数据结构的ADT及其应用，包括线性结构（线性表、串、栈和队列）、二叉树、树、图等；同时基于各种数据结构所实施的运算讨论算法分析的基本技术，掌握时间和空间权衡的原则。
2. 介绍排序、检索和索引技术。这一部分将主要讨论插入排序、Shell排序、堆排序、快速排序、基数排序等常用的各种排序算法及其时间和空间开销，并介绍文件管理（数据在外存中的组织形式）和外排序技术，以及自组织线性表、散列表、倒排文件、B树等常见的检索和索引技术，及其各自相应的时间和空间开销。
3. 通过本课程的学习，学生将基本掌握数据结构和算法的设计分析技术，提高程序设计的质量；根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。
1. 数据结构和算法简介（2学时）
数据结构定义（逻辑结构、存储结构、运算），抽象数据类型，算法及其算法度量和评价（大Ｏ表示法及其运算规则）。
2. 线性表（2学时）
线性表（向量、链表）
3. 栈和队列（8学时）
栈和队列（顺序、链接）、栈的应用。
根据专业选讲递归到非递归的转换机制和方法。
4. 字符串（4学时）
字符串抽象数据类型，存储表示和类定义，字符串的运算，字符串的模式匹配/
5. 二叉树 （8学时）
二叉树的概念及性质，二叉树的抽象数据类型，二叉树的周游，二叉树的存储实现、二叉检索树、堆与优先队列、Huffman编码树。
此外，根据学生的情况，选讲非递归深度优先周游二叉树和穿线二叉树。
6. 树与森林（4学时）
树的概念，森林与二叉树的等价转换，树的抽象数据类型，树的周游，树的链式存储，树的顺序存储。
期中考试（2学时）
7. 图 （6学时）
图的基本概念，图的抽象数据类型，图的存储结构，图的周游（深度优先、搜索、广度优先、拓扑排序），最短路径问题，最小支撑树（Prim算法、Kruskal算法）。
8. 内排序（6学时）
排序问题的基本概念，三种简单排序算法（插入排序、起泡排序、选择排序），Shell排序，快速排序，归并排序，堆排序，基数排序。
根据专业，选讲各种排序算法的理论和实验时间代价的讨论以及排序问题的下限的研究。
9. 文件管理和外排序（2学时）
介绍外排序的特点，二路外排序、置换选择排序。
10. 检索（4学时）
检索的基本概念，介绍基于线性表的检索，基于集合的检索、散列方法。
11. 索引技术（2学时）
倒排索引，B+树等动态索引组织。
12. 高级数据结构（2学时）
根据专业，选讲广义表、AVL树等。
以课堂讲授为主，同时借助网络教学平台，拓展课堂讲授的相关知识，便于同学自主学习、巩固课堂所学内容。另外，组织3次独立的习题课（6小时），针对学生作业中出现年的典型问题进行深入探讨。
鉴于数据结构与算法是与实践紧密结合的课程，配合理论教学，将加强上机实习的训练，通过合理、有效地设计上机题目，改进作业评核方式，调动学生的积极性，启发引导学生掌握基础理论并能创新应用,增强学生综合运用有关知识的能力。
平时(书面作业、上机作业+报告、课堂测试、考勤)30％，POJ在线测试10％，期中30％，期末30％。
期中、期末考试，全学院的《数据结构与算法A》和《数据结构与算法A（实验班）》统一出题、统一阅卷。平时作业和上机作业由各班根据专业要求灵活掌握，教员协调给出成绩。
注重综合能力的考评，平时表现突出、上机实践能力较强的可以得到奖励加分。
|
| 教学评估 |
赵海燕：
学年度学期：16-17-1，课程班：数据结构与算法 (A)1，课程推荐得分：3.78，教师推荐得分：3.63，课程得分分数段：80及以下；
学年度学期：17-18-1，课程班：数据结构与算法 (A)1，课程推荐得分：3.85，教师推荐得分：3.38，课程得分分数段：80-85；
学年度学期：18-19-1，课程班：数据结构与算法 (A)1，课程推荐得分：0.0，教师推荐得分：7.64，课程得分分数段：80-85；
学年度学期：19-20-1，课程班：数据结构与算法 (A)1，课程推荐得分：0.0，教师推荐得分：7.14，课程得分分数段：80-85；
学年度学期：20-21-1，课程班：数据结构与算法 (A)1，课程推荐得分：0.0，教师推荐得分：4.08，课程得分分数段：80及以下；
学年度学期：21-22-1，课程班：数据结构与算法 (A)1，课程推荐得分：0.0，教师推荐得分：6.56，课程得分分数段：80及以下；
|
|