香港大学COMP2119考试攻略：数据结构与算法期中重点解析与备考指南

　　如果你正在准备4月16日的期中考试，或者还没理清这门课的整体结构，本文会从考试形式、主要内容和复习方法这几个方面，帮你梳理一下备考思路。

　　COMP2119的考试形式

　　在香港大学，COMP2119一般是“平时成绩加期末考试”综合评分：

　　课程作业占40%

　　其中书面作业15%

　　编程作业10%

　　测验15%

　　期末考试占60%

　　也就是说，即使期中或者某一部分没发挥好，后面调整好了还是有机会拉回整体分数的。

　　COMP2119的考试重点和难点

　　难点不在知识点多，而是要抽象理解和实际应用结合起来。考试常考的内容有：

　　1.算法分析

　　这是最基础也最重要的部分。主要内容包括时间复杂度的各种表示：大O、大Omega、Theta，还有严格界的小o和小ω。考试会考你判断算法复杂度、比较不同算法效率。

　　必须掌握的工具有主定理和递归树分析方法。

　　如果这一块没搞懂，后面的题会很难拿分。

　　2.递归与分治

　　这部分既是基础也是常考点。常见题目有阶乘、斐波那契数列、汉诺塔。

　　进阶内容包括分治算法思想、递归式推导，还会涉及矩阵快速幂解决递推关系。

　　重点不是死记代码，而是理解递归调用过程，能自己写出递归逻辑。

　　3.基础数据结构

　　这是很容易得分的部分，但细节没弄清楚也会丢分。

　　要掌握栈(后进先出)、队列(先进先出)、链表的插入、删除、遍历。

　　重点是哈希表，包括平均时间复杂度为O(1)，以及链地址法和开放寻址法的区别。

　　考试会有操作流程题、时间复杂度分析和场景应用选择。

　　4.树与图

　　这块是后期重点，也是不少人觉得难的部分。

　　树的部分要会前序、中序、后序遍历，二叉搜索树的操作，和霍夫曼编码的构造。

　　图的内容包括邻接表表示方法，广度优先搜索(BFS)和深度优先搜索(DFS)。

　　考试常让手写遍历过程，判断输出顺序，写简单算法。

　　5.排序和综合应用

　　排序算法几乎每年都会考，重点有比较排序的下界O(n log n)和常见排序算法，比如快速排序、归并排序，还有计数排序的适用条件。

　　另外会有让你根据场景选择合适的数据结构或算法，并说明理由的题，考查综合理解。

　　复习建议

　　1. 先抓必考模块

　　建议重点复习时间复杂度分析、基础数据结构操作、BFS/DFS和排序算法，这几部分性价比最高。

　　2. 多做题，不只是看笔记

　　COMP2119属于“刷题型”的课程，看懂和能写代码是两码事，一定得手写代码或者模拟解题过程。

　　3. 重视历年试题

　　香港大学很多考试题型会重复或很像，建议至少做两三套历年试题，归纳总结常考题型。

　　4. 编程别临时抱佛脚

　　虽然编程作业占比不最高，但练习代码对理解算法很有帮助。建议平时多练基础数据结构实现和简单算法题。

　　常见问题

　　Q：这门课难吗?

　　A：在港大算中等偏难，难点主要是算法理解和应用，不是单纯死记。

　　Q：没有基础能学吗?

　　A：可以，但是需要花更多时间。尤其没有编程基础的，最好提前学Python或C语言，不然前期会比较吃力。

　　Q：考试偏理论还是编程?

　　A：考试主要考理论和手写算法逻辑，不是完整编程项目，但代码逻辑必须理解。

　　Q：复习跟不上怎么办?

　　A：如果算法不懂、数据结构不会用、做题没思路，可以考虑额外辅导。有些留学生会参考像海马课堂这样的辅导资源，针对重点内容做讲解，帮助快速理清解题思路，提高备考效率。