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

“数据结构与算法A”教学大纲美国IEEE和ACM的教学计划CC2005和教育部计算机教指委“计算机科学与技术专业规范”2006都明确地把“程序设计”、“算法与数据结构”列入计算机以及信息技术相关学科专业的本科必修基础课程。教育部计算机专业教指委“中国计算机本科专业发展战略研究报告”、“计算机科学与技术专业规范”等明确地强调了实践教学和学生动手能力培养的重要性。数据结构是计算机系的本科核心课程之一，上承计算引论（或计算概论）与程序设计实习，下启高级算法和计算理论，向来是计算机本科教学的重中之重。作为一门重要的专业必修课程，“数据结构与算法”课程既是对以往课程的深入和扩展，也是为将来更加深入地学习其他专业课程打下基础。课程中所学习的排序问题的算法，以及基本的树、图等数据结构，是计算机科学的基本功。B+树、Hash等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等后续课程的基础。“数据结构与算法A”介绍基本数据结构、基本算法分析技术、排序、检索和索引技术。对常用的基本数据结构，讨论相应的存储实现技术和经典算法，并通过算法时间空间的效率分析，介绍时空权衡的原则。对常用的各种经典排序算法深入讨论其时间和空间开销。介绍文件管理和外排序技术，以及常见的检索和索引技术。通过该课程的学习，学生将基本掌握数据结构和算法的设计分析技术，提高程序设计的质量；根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。1．课程基本情况学院设定课程编号04830050课程名称数据结构与算法ADataStructureAndAlgorithmA开课时间一年级二年级三年级四年级秋春夏秋春夏秋春夏秋春夏适用院系信息学院全体学生课程定位骨干基础课，必修课学分3学分总学时54学时先修课程计算引论，程序设计实习，集合论与图论，概率统计A后续课程数据结构与算法实习，程序设计语言原理教师设定教学方式以课堂讲授为主，同时借助网络教学平台，拓展课堂讲授的相关知识，便于同学自主学习、巩固课堂所学内容。另外，组织3次以上的独立习题课（6小时），针对学生作业中出现年的典型问题进行深入探讨。鉴于数据结构与算法是与实践紧密结合的课程，配合理论教学，将加强上机实习的训练，通过合理、有效地设计上机题目，改进作业评核方式，调动学生的积极性，启发引导学生掌握基础理论并能创新应用,增强学生综合运用有关知识的能力。课时分配3(课堂教学)+1（教学实验）/周考核方式平时(书面作业、课堂测试)20％，上机(+报告)15％，期中20％，期末40％，考勤和态度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）介绍基本数据结构和基本算法分析技术。这一部分将介绍常用基本数据结构的ADT及其应用，包括线性结构（线性表、串、栈和队列）、二叉树、树、图等；同时基于各种数据结构所实施的运算讨论算法分析的基本技术，掌握时间和空间权衡的原则。2）介绍排序、检索和索引技术。这一部分将主要讨论插入排序、Shell排序、堆排序、快速排序、归并排序、基数排序等常用的各种排序算法及其时间和空间开销，并介绍文件管理（数据在外存中的组织形式）和外排序技术，以及自组织线性表、散列表、倒排文件、B树等常见的检索和索引技术，及其各自相应的时间和空间开销。3）通过本课程的学习，学生将基本掌握数据结构和算法的设计分析技术，提高程序设计的质量；根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。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树伸展树难度▃▄▅▆▇重要性★★★