北大“数据结构与算法B”教学大纲

“数据结构与算法B”教学大纲“数据结构与算法”是一门重要的计算机类基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。通过学习，使学生能够提高用计算机解决实际问题的能力。本课程注重数据结构与算法理论和实践的结合，从问题求解的角度指导学生学习如何运用数据结构与算法知识来应用和解决实际问题，为将来利用从事计算机相关的学习、研究和开发工作打下扎实的基础。本课程是“数据结构与算法A”的替代课程，针对编程基础较弱的学生，尤其是电子微电子专业的学生开设。减少外排序和索引等知识点要求，注重数据结构与算法核心内容的讲解，同时安排助教加强对学生上机实习的辅导，为学生将来利用计算机解决相关问题打下一定的基础。1．课程基本情况学院设定课程编号01034340课程名称数据结构与算法BDataStructureAndAlgorithmB开课时间一年级二年级三年级四年级秋春夏秋春夏秋春夏秋春夏适用院系信息学院编程能力不太强的学生课程定位骨干基础课，必修课学分3学分总学时54学时先修课程计算引论，程序设计实习后续课程数据结构与算法实习，程序设计语言原理教师设定教学方式以课堂讲授为主，同时借助网络教学平台，拓展课堂讲授的相关知识，便于同学自主学习、巩固课堂所学内容。考虑到选修B类课程的学生编程能力较弱，会安排助教加强对学生上机实习的辅导。课时分配3(课堂教学)+1（教学实验）/周考核方式平时(书面作业、课堂测试)20％，上机(+报告)15％，期中20％，期末40％，考勤和态度5%。期中考试、期末考试与学院的“数据结构与算法A”和“数据结构与算法A（实验班）”有60%的基础内容统一出题、统一阅卷，另外40%独立命题。平时作业和上机作业由各班根据专业要求灵活掌握，教员协调给出成绩。注重综合能力的考评，平时表现突出、上机实践能力较强的可以得到奖励加分。主要教材1.张铭、王腾蛟、赵海燕，《数据结构与算法》，高等教育出版社，2008年6月。参考资料2.许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7月。3.张铭、赵海燕、王腾蛟，《数据结构与算法习题指导》，高等教育出版社，2005年8月。4.算法与数据结构，张乃孝主编，高等教育出版社，2006年1月5.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,MITPress,2ndedition,2001.高等教育出版社影印。其它信息2．教学目的和要求1）介绍基本数据结构和基本算法分析技术。这一部分将介绍常用基本数据结构的ADT及其应用，包括线性结构（线性表、串、栈和队列）、二叉树、树、图等；同时基于各种数据结构所实施的运算讨论算法分析的基本技术，掌握时间和空间权衡的原则。2）介绍排序、检索技术。这一部分将主要讨论插入排序、Shell排序、堆排序、快速排序、归并排序、基数排序等常用的各种排序算法及其时间和空间开销，并介绍二分检索、散列表等常见的检索技术，及其各自相应的时间和空间开销。3）通过本课程的学习，学生将基本掌握数据结构和算法的设计分析技术，提高程序设计的质量；根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。3．课程特色“数据结构与算法”是一门重要的计算机类基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，比较不同数据结构和算法的特点。本课程专门针对编程基础较弱的学生开设，删减了一些较艰深的知识点之外，注重数据结构与算法核心内容的讲解。安排助教加强对学生上机实习的辅导。为将来利用了利用计算机解决相关问题打下一定的基础。4．课程内容摘要和知识点章节课时内容摘要和知识点重要性1数据结构和算法简介4数据结构定义（逻辑结构、存储结构、运算）抽象数据类型算法及其算法度量和评价（大Ｏ表示法及其运算规则）难度▃▄▅重要性★★★★★2线性表、栈和队列10线性表（向量、链表）栈和队列（顺序、链接）、栈的应用难度▃▄▅▆重要性★★★★3字符串4字符串抽象数据类型，存储表示和类定义字符串的运算难度▃▄▅▆▇重要性字符串的模式匹配★★★4二叉树10二叉树的概念及性质，二叉树的抽象数据类型二叉树的周游二叉树的存储实现二叉检索树、堆与优先队列、Huffman编码树难度▃▄▅▆▇重要性★★★★★5树与森林4树的概念，森林与二叉树的等价转换，树的抽象数据类型树的周游树的链式存储难度▃▄▅▆重要性★★★★6图8图的基本概念，图的抽象数据类型，图的存储结构图的周游（深度优先、搜索、广度优先、拓扑排序）最短路径问题，最小支撑树（Prim算法、Kruskal算法）难度▃▄▅▆重要性★★★★★7内排序8排序问题的基本概念，三种简单排序算法（插入排序、冒泡排序、选择排序）Shell排序，快速排序，归并排序，堆排序，基数排序难度▃▄▅▆▇重要性★★★★★8检索4检索的基本概念基于线性表的检索基于集合的检索散列方法难度▃▄▅▆重要性★★★★