北京大学《数据结构与算法》期末考试复习指南

"北京大学数据结构与算法复习提纲包含了考试的时间、地点、题型、考试范围、考场安排、考试注意事项以及复习重点。考试时间为2018年1月3日，考试形式为闭卷，允许使用计算器。考试题型包括填空、选择、辨析与简答、数据结构或算法设计和分析以及数学证明。复习内容涵盖7-12章，尤其重视标记为重点的部分。考试中不得携带与考试无关的物品，需在试卷和答题纸上签名，违反规定可能导致试卷作废。考试期间应保持安静，如有问题需举手示意监考老师。考试结束后，按照监考老师的指示整理试卷和草稿纸，不得将试卷带离考场。" 在数据结构与算法的学习中，7-12章通常涵盖了图论、树形结构、排序算法、查找算法、动态规划和高级数据结构等内容。第7章图论中，重点可能包括图的基本概念如顶点、边、邻接矩阵、邻接表，图的遍历方法（深度优先搜索DFS和广度优先搜索BFS），以及最小生成树（Prim算法或Kruskal算法）、最短路径问题（Dijkstra算法或Floyd-Warshall算法）。第8章可能涉及树和二叉树的性质、操作，如二叉搜索树、平衡树（AVL树或红黑树）等。第9章排序算法，可能会深入研究快速排序、归并排序、堆排序等经典算法的时间复杂度和稳定性。第10章查找算法可能包括哈希表、二分查找等。第11章动态规划则会讲解基本概念、最优子结构、重叠子问题等，以及解决背包问题、最长公共子序列等问题的策略。第12章的高级数据结构可能涵盖B树、B+树、Trie树、图的压缩存储等。 复习时，考生需要理解各种数据结构的特性，能够熟练设计和分析算法，特别是在处理数据结构或算法设计题时，要清晰表述基本思想，并能给出关键函数的功能、参数和返回值。数学证明部分可能涉及算法的正确性证明或复杂度分析。此外，考生还需要关注期中考过但期末可能会间接考察的内容，确保对整个课程有全面的理解和掌握。在复习过程中，积极向助教或老师提问是非常重要的，以确保对所有知识点有透彻的理解。