南京大学软件工程考研复习重点：数据结构与算法分析

"南京大学软件工程842复习提纲，涵盖了数据结构和算法分析的主要知识点，强调基础概念理解和重点算法的掌握，特别是递归和时间复杂度分析。" 在准备南京大学软件工程842的考试时，数据结构是核心部分，占总分的45分。这部分主要考察对基础概念的理解，如数据、数据结构、基本类型和抽象数据类型的掌握。特别是要熟悉Java语言的面向对象编程，并对递归有深入的理解和实践。递归在算法题中常被考查，不仅在笔试中，也可能出现在复试的机试环节。例如，编写一个递归函数来寻找数组或链表中的最大值。 在数据结构的具体内容中，以下主题是重点： 1. 递归：如何实现和应用递归，例如上述的最大值查找问题。 2. 时间复杂度：理解最佳、最差和平均情况下的复杂度差异，以及大O、Ω和θ符号的使用。 3. 树的遍历：包括前序、中序和后序遍历。 4. 散列表：理解其工作原理和冲突解决方法。 5. 堆排序：学习其特性并能进行相关操作。 6. 排序算法：掌握各种排序算法（如冒泡、选择、插入、快速、归并等）的特点和时间复杂度。 7. 平衡树：了解如何进行平衡树的调整，如AVL树和红黑树。 8. 二叉搜索树：理解其性质和操作。 9. 图的最小生成树算法：如Prim或Kruskal算法。 10. 图的最短路径：Dijkstra算法或Floyd-Warshall算法。 算法分析部分，需要能够分析单个语句或程序段的执行次数（频度），并推导出其时间复杂度，例如给出的代码段： ```java int x = 91; int y = 100; while (y > 0) { if (x > 100) { x -= 10; y--; } else x++; } ``` 分析这段代码的时间复杂度，需要考虑循环条件和内部操作，计算循环执行的次数。 复习时，不仅要掌握这些理论知识，还要通过历年真题和期末试卷进行实践练习，特别关注那些经常出现的题目和考点。对于一些较少出现或从未考过的知识点，如KMP算法、图的存储结构和外部排序，虽然不是每次必考，但全面复习仍然是必要的，以防万一。 总结来说，南京大学软件工程842的复习应该以数据结构和算法分析为重点，强调基础概念的理解和实际编程能力，尤其是递归和时间复杂度分析。通过系统学习和充分练习，可以有效地为考试做好准备。