北大“数据结构与算法A（实验班）”教学大纲

“数据结构与算法A（实验班）”教学大纲“数据结构与算法”是一门重要的计算机类基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。通过学习，使学生能够提高用计算机解决实际问题的能力。本课程注重数据结构与算法理论和实践的结合，从问题求解的角度指导学生学习如何运用数据结构与算法知识来应用和解决实际问题，为将来利用从事计算机相关的学习、研究和开发工作打下扎实的基础。本课程是“数据结构与算法A”的替代课程，专门为那些基础比较好、学习能力突出、学有余力的学生设置。课程将加大数据结构与算法的深度和广度，提供更多的研究和讨论机会，因材施教、培养领袖人才。作为计算机和智能专业二年级的主干基础课，参与此课程学习的学生需要有非常好的计算概论A、程序设计实习。可以不要求集合论图论、计算概论的先修基础。1．课程基本情况学院设定课程编号04830540课程名称数据结构与算法A（实验班）DataStructureAndAlgorithmA开课时间一年级二年级三年级四年级秋春夏秋春夏秋春夏秋春夏适用院系信息学院全体学生课程定位骨干基础课，必修课学分3学分总学时54学时先修课程计算引论，程序设计实习，集合论与图论，概率统计A后续课程数据结构与算法实习，程序设计语言原理教师设定教学方式以课堂讲授为主，同时借助网络教学平台，拓展课堂讲授的相关知识，便于同学自主学习、巩固课堂所学内容。另外，组织3次以上的独立习题课（6小时），针对学生作业中出现年的典型问题进行深入探讨。鉴于数据结构与算法是与实践紧密结合的课程，配合理论教学，将加强上机实习的训练，通过合理、有效地设计上机题目，改进作业评核方式，调动学生的积极性，启发引导学生掌握基础理论并能创新应用,增强学生综合运用有关知识的能力。课时分配3(课堂教学)+1（教学实验）/周考核方式平时(书面作业、课堂测试)20％，上机(+报告)15％，期中20％，期末20％，高级数据结构20%，考勤和态度5%。期中、期末考试，全学院的“数据结构与算法A”和“数据结构与算法A（实验班）”统一出题、统一阅卷。平时作业和上机作业由各班根据专业要求灵活掌握，教员协调给出成绩。注重综合能力的考评，平时表现突出、上机实践能力较强的可以得到奖励加分。主要教材1.张铭、王腾蛟、赵海燕，《数据结构与算法》，高等教育出版社，2008年6月。参考资料2.许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7月。3.张铭、赵海燕、王腾蛟，《数据结构与算法习题指导》，高等教育出版社，2005年8月。4.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,MITPress,2ndedition,2001.高等教育出版社影印。其它信息2．教学目的和要求1）掌握并巩固基础数据结构知识：线性表、树、图等常用的数据结构和算法的设计分析技术；常用的排序、检索算法及其时间空间开销；对算法复杂性进行必要分析和控制。2）理解编译栈的工作原理，熟习用栈消除递归的算法框架，并解决相关应用问题。3）初步掌握稀疏矩阵、广义表等高级线性结构技术，了解Trie结构、AVL树等高级树形结构。4）对抽象数据类型有深入的理解，能根据所求解问题的性质选择合理的数据结构，设计并完成处理海量数据的复杂应用系统。3．课程特色“数据结构与算法”是一门重要的计算机类骨干基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。通过学习，使学生能够提高用计算机解决实际问题的能力。本课程针对实验班的学生，将以问题求解为主线，从问题抽象、数据抽象和算法抽象的角度来组织数据结构与算法的设计，指导学生建立数学模型、使用不同的数据结构不同的算法分别去解决问题，最后去探讨各种数据结构和算法的优缺点，同时让学生学会怎么样根据实际问题来取舍数据结构和算法，并且在时间复杂度和空间复杂度之间进行平衡。在讲授过程中，将调动学生的积极性，采取研究式的学习方法。有些较基础的内容采用学生综述、答辩、小测验的形式，培养学生的自学能力。引导学生跟踪数据结构与算法的前沿应用技术，引入研读论文并作报告的讨论班形式，培养学生的捕捉新理论、新技术的科研能力。最后的合作大实习题由学生自己提出，并组织团队完成。由助教引导讨论，从需求分析、模块设计、编程实践、调试测试各个阶段进行引导，加强学生们综合应用数据结构和算法知识的能力。本课程将通过设置的课程网站提供课堂讲义和最新的参考材料。4．课程内容摘要和知识点章节课时内容摘要和知识点重要性1数据结构和算法简介2数据结构定义（逻辑结构、存储结构、运算）抽象数据类型算法及其算法度量和评价（大Ｏ表示法及其运算规则）难度▃▄▅重要性★★★★★2线性表、栈和队列8线性表（向量、链表）栈和队列（顺序、链接）、栈的应用根据专业选讲递归到非递归的转换机制和方法难度▃▄▅▆重要性★★★★3字符串4字符串抽象数据类型，存储表示和类定义字符串的运算字符串的模式匹配难度▃▄▅▆▇重要性★★★4二叉树10二叉树的概念及性质，二叉树的抽象数据类型二叉树的周游二叉树的存储实现二叉检索树、堆与优先队列、Huffman编码树★非递归深度优先周游二叉树和穿线二叉树难度▃▄▅▆▇重要性★★★★★5树与森林4树的概念，森林与二叉树的等价转换，树的抽象数据类型树的周游树的链式存储，树的顺序存储难度▃▄▅▆重要性★★★★6图8图的基本概念，图的抽象数据类型，图的存储结构图的周游（深度优先、搜索、广度优先、拓扑排序）最短路径问题，最小支撑树（Prim算法、Kruskal算法）难度▃▄▅▆重要性★★★★★7内排序8排序问题的基本概念，三种简单排序算法（插入排序、冒泡排序、选择排序）Shell排序，快速排序，归并排序，堆排序，基数排序★各种排序算法的理论和实验时间代价的讨论以及排序问题的下限的研究难度▃▄▅▆▇重要性★★★★★8文件管理和外排序2外排序的特点二路外排序置换选择排序难度▃▄▅▆重要性★★★9检索4检索的基本概念基于线性表的检索基于集合的检索散列方法难度▃▄▅▆重要性★★★★10索引技术2倒排索引难度▃▄▅▆B+树等动态索引组织★红黑树重要性★★★11高级数据结构2广义表字符树★AVL树★伸展树难度▃▄▅▆▇重要性★★★