作为一门重要的专业必修课程，“数据结构与算法”课程既是对以往课程的深入和扩展，也是为将来更加深入地学习其他专业课程打下基础。课程中所学习的排序问题的算法，以及基本的树、图等数据结构，是计算机科学的基本功。B+树、Hash等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等后续课程的基础。
1．课程基本情况
学
院
设
定
课程编号
04830540
课程名称
数据结构与算法A（实验班）
DataStructureAndAlgorithmA
一年级
二年级
三年级
四年级
秋
春
夏
适用院系
信息学院全体学生
课程定位
骨干基础课，必修课
学分
3学分
总学时
54学时
先修课程
计算引论，程序设计实习，集合论与图论，
概率统计A
后续课程
数据结构与算法实习，程序设计语言原理
教
师
教学方式
本课程是“数据结构与算法A”替代课程，针对基础比较好、学习能力突出、学有余力的实验班学生设置。课程将加大“数据结构与算法A”的深度和广度，提供更多的研究和讨论机会，因材施教、培养领袖人才。
鉴于数据结构与算法是与实践紧密结合的课程，配合理论教学，将加强上机实习的训练，通过合理、有效地设计上机题目，改进作业评核方式，调动学生的积极性，启发引导学生掌握基础理论并能创新应用,增强学生综合运用有关知识的能力。
课时分配
3(课堂教学)+1（教学实验）/周
考核方式
平时(书面作业、课堂测试)20％，上机(+报告)15％，期中20％，期末20％，高级数据结构20%，考勤和态度5%。
期中、期末考试，全学院的“数据结构与算法A”和“数据结构与算法A（实验班）”统一出题、统一阅卷。平时作业和上机作业由各班根据专业要求灵活掌握，教员协调给出成绩。
注重综合能力的考评，平时表现突出、上机实践能力较强的可以得到奖励加分。
主要教材
参考资料
其它信息
2．教学目的和要求
3）初步掌握稀疏矩阵、广义表等高级线性结构技术，了解Trie结构、AVL树等高级树形结构。
4）对抽象数据类型有深入的理解，能根据所求解问题的性质选择合理的数据结构，设计并完成处理海量数据的复杂应用系统。
3．课程特色
“数据结构与算法”是一门重要的计算机类骨干基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。通过学习，使学生能够提高用计算机解决实际问题的能力。
在讲授过程中，将调动学生的积极性，采取研究式的学习方法。有些较基础的内容采用学生综述、答辩、小测验的形式，培养学生的自学能力。引导学生跟踪数据结构与算法的前沿应用技术，引入研读论文并作报告的讨论班形式，培养学生的捕捉新理论、新技术的科研能力。
最后的合作大实习题由学生自己提出，并组织团队完成。由助教引导讨论，从需求分析、模块设计、编程实践、调试测试各个阶段进行引导，加强学生们综合应用数据结构和算法知识的能力。
本课程将通过设置的课程网站提供课堂讲义和最新的参考材料。
4．课程内容摘要和知识点
章节
课时
内容摘要和知识点
重要性
1
数据结构和算法简介
2
数据结构定义（逻辑结构、存储结构、运算）
抽象数据类型
算法及其算法度量和评价（大Ｏ表示法及其运算规则）
难度
▃▄▅
★★★★★
线性表、栈和队列
8
线性表（向量、链表）
栈和队列（顺序、链接）、栈的应用
根据专业选讲递归到非递归的转换机制和方法
▃▄▅▆
★★★★
3
字符串
4
字符串抽象数据类型，存储表示和类定义
字符串的运算
字符串的模式匹配
▃▄▅▆▇
★★★
二叉树
10
二叉树的概念及性质，二叉树的抽象数据类型
二叉树的周游
二叉树的存储实现
二叉检索树、堆与优先队列、Huffman编码树
★非递归深度优先周游二叉树和穿线二叉树
5
树与森林
树的概念，森林与二叉树的等价转换，树的抽象数据类型
树的周游
树的链式存储，树的顺序存储
6
图
图的基本概念，图的抽象数据类型，图的存储结构
图的周游（深度优先、搜索、广度优先、拓扑排序）
最短路径问题，最小支撑树（Prim算法、Kruskal算法）
7
内排序
排序问题的基本概念，三种简单排序算法（插入排序、冒泡排序、选择排序）
Shell排序，快速排序，归并排序，堆排序，基数排序
文件管理和外排序
外排序的特点
二路外排序
置换选择排序
9
检索
检索的基本概念
基于线性表的检索
基于集合的检索
散列方法
索引技术
倒排索引
B+树等动态索引组织
★红黑树
11
高级数据结构
广义表
字符树
★AVL树
★伸展树
1）课程基本情况
04830050
数据结构与算法
平时(书面作业、课堂测试)20％，上机(+报告)15％，期中20％，期末40％，考勤和态度5%。
1.张铭、王腾蛟、赵海燕，《数据结构与算法》，高等教育出版社，2008年6月。
2.许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7月。
3.张铭、赵海燕、王腾蛟，《数据结构与算法习题指导》，高等教育出版社，2005年8月。
4.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,MITPress,2ndedition,2001.高等教育出版社影印。
2）教学目的和要求
4.对抽象数据类型有深入的理解，能根据所求解问题的性质选择合理的数据结构，设计并完成处理海量数据的复杂应用系统。
3）课程特色
最后的合作大实习题由教师指导学生自己提出，并组织团队完成。由助教引导讨论，从需求分析、模块设计、编程实践、调试测试各个阶段进行引导，加强学生们综合应用数据结构和算法知识的能力。
课程通过设置的课程网站提供课堂讲义和最新的参考材料。
4）课程内容摘要和知识点
★选讲递归到非递归的转换机制和方法
★选讲非递归深度优先周游二叉树和穿线二叉树
★选讲置换选择排序、多路归并选择树
★选讲红黑树
12
★选讲AVL树
★选讲伸展树
数据结构与算法B
DataStructureAndAlgorithmB
信息学院编程能力不太强的学生
计算引论，程序设计实习
考虑到选修B类课程的学生编程能力较弱，会安排助教加强对学生上机实习的辅导。
期中考试、期末考试与学院的《数据结构与算法A》和《数据结构与算法A（实验班）》有60%的基础内容统一出题、统一阅卷，另外40%独立命题。平时作业和上机作业由各班根据专业要求灵活掌握，教员协调给出成绩。
4.算法与数据结构，张乃孝主编，高等教育出版社，2006年1月
5.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,MITPress,2ndedition,2001.高等教育出版社影印。
“数据结构与算法”是一门重要的计算机类基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。
树的链式存储
048305170
数据结构与算法实习
PracticeofDataStructuresandAlgorithms
计算机系和智能系
专业必修
2学分
32+80(理论+上机实习)
数据结构与算法A
算法分析与设计
理论与实践结合
理论32学时：教员课堂讲授26小时，学生编程经验交流6小时
学生独立实践80学时：数据结构与算法实验50小时，综合上机实习30小时
平时20%，算法实验20%，综合上机题40%，期末考试20%。
1.张铭、赵海燕、王腾蛟，《数据结构与算法习题指导》，高等教育出版社，2005年8月。
2.张铭、王腾蛟、赵海燕，《数据结构与算法》，高等教育出版社，2008年6月。
3.许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7月。
5.M.H.Alsuwaiyel,AlgorithmsDesignTechniquesandAnalysis,电子工业出版社影印，2003年1月。
6.B.Kernighan&R.Pike,ThePracticeofProgramming,Addison-Wesley,1999.(中译本：《程序设计实践》，裘宗燕译，机械工业出版社，2000年8月
同修课程：数据结构与算法A
配合“数据结构与算法”理论课程的学习，介绍一些程序风格、设计、测试和排错等软件工程的基本知识和方法；通过一些趣味例题，系统地介绍“数据结构与算法”理论课程涉及到的穷举法、回溯法、贪心法、分治法、动态规划等算法基本思想；介绍图和问题建模、数据结构与算法的应用和实践。
培养学生独立地实现常用基本数据结构的ADT以及相应的STL数据结构，解决一些实际问题，独立编写中小型应用程序。灵活应用基本数据结构，并结合排序、检索、文件、索引等技术，合作编写比较综合的大型应用程，提高学生的实际动手能力。通过本课程的学习，为后续的专业基础课和专业课程打下坚实的基础。
把《数据结构与算法实习》作为辅助《数据结构与算法》的计算机系学生必修课，强化了计算机系学生的实践能力训练。实习课内容划分为C/C++基本程序技巧训练、界面排错和测试、基本数据结构训练、基本算法、数学建模训练5个模块。
从问题求解的角度，培养学生数据结构理论基础、问题数据和算法抽象、数据结构与算法设计的能力。在培养基本问题求解能力的同时，注重实践能力和工程能力的培养，使得学生遵从软件开发的规范性。以项目驱动，从软件工程的角度对学生系统地进行需求分析、数学建模、数据结构与算法设计、程序实现测试调试、文档编写训练。不仅要求进行简单的实现，更要求进行工程实现的设计。学生不仅仅能完成自己承担的开发任务，还能从系统级认识整个项目，积累重大项目的组合、合作协调经验，培养项目组织和管理能力，创造性地解决工程中遇到的问题。
通过典型案例教学，引导学生深入思考，激发创新思想火花，充分调动学生学习的主动性，实现教与学的互动。学生从案例中进行研究型学习，并在研究性学习过程中主动运用所学知识来分析问题、解决问题，根据问题的需求来主动获取新知识，从而强化创新意识和创新能力，相应地提高理论联系实际能力、实践动手能力和科研能力。
简介
数据结构与算法实习简介
C/C++基本程序技巧
界面排错和测试
问题空间和典型的算法思想
数学建模基本思想
程序设计风格
程序的良好风格
程序设计和实现技巧
面向对象技术
STL的基本概念和常用容器
界面技术
人机界面基本原则
排错的技巧
测试
性能
可扩展性
项目管理
项目需求分析
项目开发计划
软件项目的实施（控制）
基本算法与枚举法
问题状态空间的建立
枚举的思想
例题：百钱百鸡、猴子分桃、宴会彩灯、质数方阵
回溯法
递归思想强化
搜索解空间的思想
DFS和BFS搜索策略，分枝限定思想
例题：八皇后，0-1背包，火车进出栈
贪心法
最优子结构分解
最优解的正确性证明
例题：活动安排、可分割背包、区间覆盖
分治法
分-治-合的分治法原理思想
算法复杂性问题
例题：统计逆序对、导线与开关、二进制大整数乘法
动态规划
最优子结构和重复子问题，备忘录方法
各种算法的比较
例题：最优二叉搜索树、最长子序列、邮局问题、最大全1正方形
问题建模
问题建模专题讨论
数学模型
13
图的应用
图模型的建立
图的有效搜索
回溯高级技巧
14
数据结构综合应用
搜索引擎和数据库等应用系统中的线性表、字符串、图等基本数据结构