目录

关于 2019T1 COMP9024 相关的

1. 课程信息

2. 知识点梳理

3. 期末试卷（回忆版）

1. 课程信息

1.1 Lecturer: Wu Hui

1.2 Programming Language: C

1.3 Assessment: Assignment 40% + Final Exam 60%

1.3.1 Assignment (1~4):

所有函数需要分析时间复杂度，代码需要注释

推荐在学校的机器上编译成功后提交（编译失败可能面临仅40%的成绩）

1. Doubly Linked Lists and Sets (10 marks)

Operations: Create, Print, Clone, Union, Intersection, Free

2. AVL Tree (10 marks + 2 bonus marks)

Operations: Create, Clone, Union, Intersection, Insert, Delete, Search, Free, Print

3. Binomial Heap-Based Priority Queue (10 marks)

Operations: Create, Insert, RemoveMin

Implementation: Deal with a task scheduling problem based on EDF (Earliest Deadline First) heuristic

4. Graph (10 marks)

Operations: CreateEmptyGraph, DeleteEdge, ReachableVertices, ShortestPath, FreeGraph, ShowGraph

1.3.2 Final Exam:

时间: Three hours (Closed book, Calculator not needed)

题型: Two Parts（简答题）

Part I: Basic data structures and algorithms （8题40分 答题纸手写，会涉及画图）

Part II: Design and analysis of algorithms （5题60分 上机在文本文件中输入伪代码）

Use pseudo code to write algorithms.

1.4 Problem Sets

每周会有1至2份 Problem Sets，一共有11份，每份的题量大概是8道左右

Problem Sets 没有任何问题的话，Final 基本上也是没问题的

所有 Problem Sets 堆积至期末再刷题也是可取的，3个整天足矣

1.5 Bonus mark

整个课程有上限为3分的Bonus marks，直接加在期末总评上

Assignment 中涉及到2分，是关于时间复杂度的，满足要求的时间复杂度会有Bonus

发现 Problem Sets 和 Assignments 中的解题 / 原题 中的错误，提出更优化的时间复杂度的算法会有Bonus

总的来说就是：大家来找茬

2.知识点梳理

2.1 基础知识

基础数据类型：Stack, Queue, Single / Double Linked List

基本操作：Create, Insert, Delete

2.2 树 Tree（重点）

1. 树的遍历：前序，后序，中序（递归实现 & 非递归实现）

2. 二叉树的定义和性质

3. 二叉搜索树的定义和性质

4. AVL树的定义和性质（树的高度；Insert-Trinode Restructuring 单旋和双旋；插入、删除和查找）

5. 伸展树的定义和性质（树的高度；Right / Left Rotation；插入、删除和查找）

6. （2，4）树的定义和性质（树的高度；插入、删除和查找；Overflow & Underflow）

2.3 优先队列 Priority Queue （重点）

1. 基于链表实现的优先队列；基于最小堆实现的优先队列

2. 堆的性质（高度；LastNode；插入 UpHeap；删除 DownHeap）

3. 构造堆（自底向上构造堆）

4. 堆排序（数组表示堆）

5. 二项堆的定义和性质（插入；删除；合并）

2.4 字符串匹配 String Match（重点）

1. Brute-Force Pattern Matching

2. Boyer-Moore Algorithm

3. KMP Algorithm

4. Tries (Standard Tries & Compressed Tries)

5. Huffman Encoding

2.5 图论 Graph （重点）

1. 图的术语和分类（有向图、无向图；Cycle；Clique；Parallel Edges；树；森林等……）

2. 图的表示（邻接矩阵 & 邻接链表）

3. DFS & BFS

4. 有向图的强连通性（Strong Connectivity Algorithm）和传递闭包（Floyd-Warshall's Algorithm）

5. 有向非循换图（DAG）的拓扑排序（Topological Sorting）

6. 最短路径问题（Dijkstra's Algorithm; Bellman-Ford Algorithm; DAG-based Topological Algorithm）

7. 最小生成树（MST）（Kruskal's Algorithm; Prim-Jarnik's Algorithm）

2.6 次重点

1. 线性规划（Dynamic Programming）

2. 贪心算法（Greedy Method）*最长公共子序列（Longest Common Subsequence）

3. Disjoint Set Union-Find Operations

2.7 Not Examinable（2019T1中明确不考）

1. C Programming Language

2. Red-Black Trees

3. Randomized algorithms

3. 期末试卷（回忆版）

考试前不会给任何 sample 试卷，也几乎无法搜索到往年试卷

这份回忆版的解题思路不一定正确，只是作者在考场时的回答

但是根据卷面的反馈，保证九成的准确率是没问题的

Part I 40分

1. 读C语言程序，回答问题（包括3个小问题）

a 根据输入，写输出

b 文字描述该段代码的作用 

c 分析代码的时间复杂度

代码涉及到的数据类型：队列，涉及到的语句结构：循环、条件

代码作用：将一个数据序列，分为几个连续递增的子序列（队列实现）

例如输入：1 3 5 7 8 2 4 0 3 5 9 7 6

输出：

1 3 5 7 8

2 4

0 3 5 9

7

6

2. 写出&分析相关操作的时间复杂度（包括4个小问题）

其中1个小问是AVL树删除操作的时间复杂度，答案是O(log(n))

2个小问是关于图论的，答案是O(m + n)

剩下1个问题记不清了

不难，Lecture Notes中都有，都是基本操作，算法的时间复杂度要知道大概的原因，不能死记硬背

3.  Heap 的插入和删除

给出2张树表示的 Heap 图，问：经过哪几步操作可以从图（1）中的堆变成图（2）中的堆，每一步需要画图显示堆的变化过程

思路：首先比较2张图的堆有哪些元素差异，对比后发现：多了一个元素（插入），少了一个元素（删除），判断是先插入还是先删除，答案是先删除后插入

相关知识点：堆的删除和插入操作（掌握 DownHeap & UpHeap 过程，知道LastNode）

4. （2，4）树的插入和删除操作

给定一棵3层高的（2，4）树，按照一串数据序列，进行插入，之后删除几个数据，每一步需要画图，显示树的变化

相关知识点：（2，4）树的插入和删除（注意如何处理Overflow & Underflow，注意保持2，3，4树的性质）

5. 二叉搜索树（Binary Search Tree）

介绍了搜索路径的概念，即在二叉搜索树中搜索某一结点所经过的路径，形成的序列

接着，给出一个搜索路径，问该搜索路径在二叉搜索树中是否正确。

答案：显然是不正确的，因为违反了一棵二叉搜索树，左子树值小，右子树值大的性质，解题时可以画图，画图后违反性质的点显而易见。

例如给出搜索路径：50 70 60 40，那么40的结点因为小于了50，但是是70的孩子而发生错误

6. 伸展树（Splay Tree）

考法简单粗暴：给一串数据序列（似乎有9个，以（key, value）的形式出现），挨个进行插入，每一步都需要画图（印象中没考删除）

相关知识点：伸展树的插入操作，通过旋转保持伸展树的性质（最新插入的点是根节点）

7. 字典树（Tries）（标准字典树和压缩字典树）

给定几串字符串，分别画出标准字典树（standard tries）和压缩字典树（compressed tries）

给的字符串类似于：aaabb, ccccc, cccaa, cccab, aabcc 此类

这里贴出一道在Problem Sets中出现的类似的题：

Q: Draw a standard trie and a compressed trie for the following set of strings:  {abab, baba,ccccc, bbaaaa, caa, bbaacc, cbcc, cbca}.

a standard trie and a compressed trie

8. 哈夫曼编码（Huffman Encoding）

给定一个字符串“Data Structures and Algorithms”，用哈夫曼编码，要求给出字符频率表和哈夫曼树

注意字符串中的空格不要遗漏

这里贴出一道在Problem Sets中出现的类似的题：

Q: Draw the frequency array and Huffman tree for the following string: “dogs do not spot hot pots or cats”.

The Frequency Array

The Huffman Tree

*哈夫曼树答案不唯一

Part II 60分（所有题目需要分析算法符合时间复杂度的原因）

1. 关于AVL树的合并（Merge）操作

给定2棵高度相同的AVL树U和T，U的所有Key值小于T的所有Key值，T的结点数量为m，要求在O(log(m))的时间复杂度内合并（Merge）U和T，合并后的树仍然是AVL树。

思路：很显然，时间复杂度是T树的树高

（1）查找T树中的最小值叶子结点（记为Q），即：从根节点开始不断查找左孩子，时间：O(log(m))

（2）删除Q，需要自底向上直至根结点检查AVL树的平衡，若出现不平衡，则执行旋转操作保持平衡，时间：O(log(m))，其中旋转是O(1)

（3）合并后的树记作M，M的根节点是Q，Q的左孩子是U的根节点，Q的右孩子为T的根节点，时间：O(1)

（4）解释为什么M树是AVL树，在删除操作后，T树的高度可能减1，但不影响M树位于根节点的高度差，且M树符合左子树值小，右子树值大的性质，所以是 AVL树

注：此题需要写出所有涉及到的算法的伪代码

2. 关于 优先队列 & 构造堆

给定一串整数型数据序列，序列的大小为n，要求找出第k个最小的整数（k < n），要求的时间复杂度是O(n + k*log(n))

例如：给定整数型数据序列：8, 5, 11, 2, 7, 10，要求找出第4个最小的整数，那么答案是输出 8，因为2 < 5 < 7 < 8 ，是第4个最小的数

思路：显然通过基于堆的优先队列实现，通过观察时间复杂度可知

（1）首先需要构造堆，构造堆有2种方法，一种是通过插入操作，一种是通过自底向上构造堆（Bottom-up Heap Construction），显然选择后者，因为后者的时间复杂度更优，是O(n)

（2）对基于堆的优先队列执行k次Remove操作，第k次的值进行return，即为所求，时间复杂度是O(k*log(n))

注：此题可以引用Lecture Notes中出现过的算法，即：提到Bottom-up Heap Construction和RemoveMin()即可，不需要抒写详细的伪代码

3. 关于字符串匹配算法

给定一个大小为 n 的文本 T（Text），给定一个大小为 m 的匹配字符串 P（Pattern），寻找能够在文本 T 中匹配成功的、P 的最长前缀（prefix），要求的时间复杂度是O(m + n)

例如：T = "abcdefghijklmn"，P = "abcabcd"，匹配成功的最长前缀是"abc"，虽然"ab"能够匹配成功，但是"abc"更长，"abca"则匹配失败，"abcd"并不是前缀，所以不会出现在比较中，在该例中为后缀（suffix）

思路：根据要求的时间复杂度，很显然能想到KMP算法，剩下的Boyer-Moore算法的时间复杂度显然不满足要求，鉴于该课程只教了KMP算法和Boyer-Moore算法，所以读完题后，实锤是基于KMP算法实现的，事实证明就是基于KMP算法进行轻微改动即可。这是这门课程的出题特色，完成Problem Sets中的题即可发现，答案中的算法大多是基于Lecture Notes中所教的算法，但是不会考一模一样的，多少就是考察你如何对已学算法进行小幅改动，考察你是否真正理解算法是如何实现的，所以不能死记硬背伪代码

答案：当KMP算法匹配失败时，设定变量，记录失败时已匹配成功的前缀的最长长度（若 P全部匹配成功，则直接return m），最后return该变量的值，基于KMP算法所做的修改是循环体内O(1)的操作，所以时间复杂度不发生变化

注：此题不需要写FailureFunction的伪代码，可直接引用

4. 关于图论 （图的搜索）

给定一张图（可能不连通，存在多个Components），写算法判断，是否每个component的所有结点可以分为2组（记作A组和B组），其中每组内部的点不存在边相连，某组内部的点与另外一组中的至少某一个点存在边相连。即：A组或B组中的点与点之间不存在边，A组中的点与B组中的至少某一个点存在边，反之亦然。要求的时间复杂度是O(m + n)，n 是结点数量，m 是边的数量

思路：

（1）直接判断很困难，只能通过寻找反例实现，查找出存在违反题干要求的情况则return false，若查找后不存在违反的情况则return true

（2）违反题干要求的情况是出现某组内部的点与点之间存在边，进而想到违反题干的最基本模型是存在3个顶点构成的三角形，即：大小为3的Clique，之后想到通过某个算法检查是否图中包含大小为3的Clique能解决原题（注意并不能完全解决），回想起Problem Sets中出现过寻找大小为3的Clique的问题，但是时间复杂度并不满足题干要求

（3）根据要求的时间复杂度，联想到BFS和DFS，想到给结点进行上色的问题，3-size Clique不能用2种颜色进行上色（上色问题是指同一条边相连的2个顶点不能有相同的颜色），显然四边形可以用2种颜色进行上色，五边形则需要3种颜色（即：图中存在四边形则满足要求，出现五边形则违反要求）可以以此类推，相关内容在COMP9020中非常完整

（4）问题的本质：是否能通过2种颜色对图进行上色，能则True，不能则False，通过BFS或DFS遍历可实现，给结点的数据结构增加一个Color的属性，属性的值可以是任意2种颜色，例如BLUE 和 RED

答案：进行BFS的同时，在原算法的基础上给结点标上BLUE 或 RED（多一个Label操作），（印证了第三问中的说法：答案中的算法大多是基于Lecture Notes中所教的算法，但是不会考一模一样的，多少就是考察你如何对已学算法进行小幅改动，考察你是否真正理解算法是如何实现的）

遍历的初始结点可以任意上色，存在边相连的结点上不同的颜色，若出现两个边相连的结点已经拥有相同的颜色时，则直接return false，遍历完成后无违反则return true，BFS的时间复杂度是O(m + n)

注：此题需要写出所有涉及到的算法的伪代码（本质是考察是否会BFS / DFS，但是题目弄得花里胡哨的）

5. 关于图论 （图的路径）

给定一个有向无循环图（DAG），寻找图中2点之间的最长路径。提示（Hints）：最长路径的起始点是没有入度（InDegree）的点，终点是没有出度（OutDegree）的点。要求的时间复杂度是O(m + n)，n 是结点数量，m 是边的数量

思路：Problem Sets中关于最长路径有原题，基于拓扑排序可实现，结合题干中的Hints对Problem Sets中的答案进行改动即可。

这里我就直接贴出Problem Sets中的那道题了：

Design an efficient algorithm for finding a longest path from a vertex u and a vertex v of an acyclic directed graph G where each edge has a weight. Specify the graph representation used and any auxiliary data structures used. Also analyse the time complexity of your algorithm.

Solution: The key idea is that in order to find the longest path from u to a vertex x, we need to find the longest path from u to each immediate predecessor of x. To do so in an efficient way, we use topological sort to reduce the time complexity. 

For each node, we introduce two variables: D(x) and prevVertex(x), where D(x) stores the longest path length from u to c, and prevVertex(x) stores the preceding vertex of x in the longest path from u to x. prevVertex(x) is used to recover the longest path from u to v.

The algorithm is shown in pseudo code as follows:

Time complexity:

1. All the initializations take O(m+n) time, where m and n are the number of edges and the number of vertices of the graph.

2. The breadth-first search (depth-first search) for all the vertices reachable from u takes O(m+n) time.

3. Removing all the vertices and edges of G1 takes O(m+n) time.

4. Performing topological sort on G1 takes O(m+n) time.

5. The whole edge relation process by the nested for loops takes O(m+n) time as each vertex x and each outgoing edge of x in G1 is visited once.

6. Recovering the longest path takes O(n) time.

Therefore, this algorithm takes (m+n) time.