# 112 中央資演 參考詳解
> ==採用 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hant) 許可協議共享，轉載請註明來源，禁止任何營利使用。==
> [name=SayA] [time=Fri, Feb 9, 2024 9:25 PM] [color=#4c33af]
:::warning
📢 題目和選項為直接透過OCR取得，未經過校對，如果題目和選項錯誤請以考卷為主。
:::
- [PDF手寫檔](https://drive.google.com/file/d/1hyFEs3O-xtL9DhcXaXav16AyfMnFodFi/view?usp=sharing)
# 一、複選題(50分；每題5分，答錯1題倒扣1分，倒扣至複選題0分為止)
## 1. B
### 題目
1. Which of the following isn't open addressing overflow handling?
(A) Linear probing (B) dynamic hashing \(C) rehashing (D) quadratic probing
### 解答
- Open addressing means find **next available** position. So ==Chaining== and ==dynamic hashing== is not open addressing.
## 2. AC
### 題目
2. Apply Quick sort on a Given list $[9, 7, 24, 6, 11, 4, 2, 19]$. Which of the
following two are the resulting sequences of the first phase, when the first
element or second element is chosen as pivot?
(A) $4, 7, 2, 6, 9, 11, 24, 19$
(B) $7, 6, 24, 11, 9, 4, 2, 19$
\(C) $2, 6, 4, 7, 11, 24, 9, 19$
(D) $7, 6, 4, 2, 9, 24, 11, 19$
### 解答
左往右找大，右往左找小
- for 1st element
- $[9, 7, 24^i, 6, 11^i, 4^j, 2^j, 19]$
- $[9,7,2,6,4^j,11^i,24,19]$ (swap 9, 4)
- $[4,7,2,6],9,[11,24,19] \Rightarrow (A)$
- for 2nd element
- $[9^i, 7, 24^i, 6, 11, 4^j, 2^j, 19]$
- $[2, 7, 4, 6^j, 11^i, 24, 9, 19]$ (swap 7, 6)
- $[2, 6, 4], 7, [11, 24, 9, 19] \Rightarrow (C)$
:::danger
✒️ 可以用看的：
- (A)選項中pivot只可能是9，
- (B)選項中7跟9皆不可能為pivot，可以直接排除
- \(C)選項的pivot只可能是7
- (D)選項中pivot只可能是9，但稍微跑一下應該可以發現，若9為pivot，則7不可能被換到最前面，因此也能夠排除
:::
## 3. ABC
### 題目
3. A leftist tree is a min tree satisfying that $dist(RChild(i)) <= dist(LChild(i))$, where $dist(j)$ denotes the number of edges on the shortest path from node $j$ to a leaf node, $RChild(i)$ and $LChild(i)$ denote the right child and left child of node $i$, respectively. Which of the following statements about leftist trees are correct?
(A) The length of path to rightmost leaf is $O(\log n)$ for a leftist tree with $n$ nodes.
(B) Merging two leftist trees is to merge the right subtree of one tree with the other.
\(C) Delete min takes $O(\log n)$ time.
(D) If the path to ~~leftmost~~ leaf has $x$ nodes, then the leftist tree has at least $2^x-1$ nodes.
### 解答
:::success
📌 3 Property of Leftist Tree
- Property 1: The rightmost path is a shortest path from root to external node and the length of this path is $s(root)$.
- Property 2: The number of internal nodes is at least $2^{\mathrm{s}(\mathrm{root})}-1$
- Property 3: Length of rightmost path is $O(\log n)$, where $n$ is the number of nodes in a leftist tree.
:::
leftist tree 的 leaf node 是 external node
- (A) ++[Horowizt Lemma 9.2]++
- \(C) $insert()$ and $delete()$ are both using $merge()$, which is $O(\log n)$.
- (D) at least $2^{s(x)} - 1$
**rightmost** path is shortest path from root to external node.
:::danger
✒️ 答疑
- 在計算leftist tree 的 s-value 時，考慮的是到external node的距離，但題目所述中用到leaf node的距離來定義，因此判斷題意中 的 leaf node 即為 external node。
- leaf node可以視為「internal node中沒有child的node」或是「external node」，取決如何定義。本題依照題目中s-value的定義應為後者。
:::
## 4. ABC
### 題目
4. Given the input list $[203, 16, 30, 123, 521, 63, 528, 210, 216, 941, 45]$. Which of the following statements is (are) correct?
(A) LSD radix sort is a non-comparative sorting algorithm.
(B) At the end of the second pass of LSD Radix sort, the sixth element of the resulting chain is 123.
\(C) At the end of the third pass of LSD Radix sort, the sixth element of the resulting chain is 123.
(D) At the end of the first pass of LSD Radix sort, the sixth element of the resulting chain is ~~63~~.
### 解答
- (D) 123
$$
\begin{array}{l|cccccccccc}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline \text { pass } 1 & 30 & 521 & & 203 & & 45 & 16 && 28 & \\
& 210 & 941 && \underline{123} &&& 216 && 528 & \\
& & & & 63 & & & & &
\end{array}
$$
$$
\begin{array}{l|cccccccccc}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline \text { pass } 2 & 203 & 210 & 521 & 30 & 941 & & 63 & & & \\
& & 16 & \underline{123} & & 45 \\
& & 216 & 28 & \\
& & & 528 & \\
\end{array}
$$
$$
\begin{array}{l|cccccccccc}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline \text { pass } 3 & 16 & \underline{123} & 203 & & &521 &&&& 941 \\
& 28 & & 210 & & & 528 \\
& 30 & & 216 & & & \\
& 45 & \\
& 63 & \\
\end{array}
$$
## 5. ABD / BD
### 題目
5. Which of the following statement(s) is (are) correct? (A) The time complexity of inserting an element to an n-node min-Heap is $O(n)$. (B) The time complexity of searching an element in an n-node max-Heap is $O(n)$. \(C) Building the min-Heap by inserting these nodes one by one $\{42, 9, 23, 37, 4, 34, 2\}$. The level order traversal sequence of the min-Heap is $\{2, 9, 4, 42, 37, 23, 34\}$. (D) The time complexity of deleting min in an n-node min-Heap is $O(log n)$
### 解答
- (A) $O(\log n)$, but $O(\log n)$ is in $O(n)$.
- (B) $O(n)$, target may be any node in the tree.
- \(C) level order traversal sequence is $\{2, 9, 4, 42, 37, 34, 23\}$
```graphviz
graph g5{
node [shape=circle, style=filled, fillcolor="lightblue", fixedsize=True];
2--{9,4};
9--{42,37};
4--{34,23};
}
```
- (D) $O(\log n)$
## 6. ACD
### 題目
6. In a stack structure, let X denote a push operation and let Y denote a pop operation. After 8 stack operations, consisting of 4 pushes and 4 pops, an input sequence 1234 may change its order. For example, after XYXXYYXY is performed, 1234 will
become 1324. Which of the following is (are) possible output sequences? (A) 1243 (B) 4123 \(C) 2134 (D) 4321
### 解答
- stack 的FILO性質，可以使某段序列反轉，如XXXYYY可以反轉長度為3的序列。若XYXYXYXY，則序列不變。
- (A) `XY XY XXYY`
- (B) `XXXXYYYY` $\Rightarrow 4321$
- \(C) `XXYY XY XY`
- (D) `XXXXYYYY`
## 7. ABC
### 題目
7. Given an undirected graph G, where n denotes the number of vertices and m denotes the number of edges ($m >> n$). Which ofthe following statement(s) is (are) frue about the graph
G?
(A) If G is represented by an adjacency matrix, the space complexity is $O(n^2)$.
(B) If G is represented by an adjacency list, the space complexity is $\Theta(m)$.
\(C) If G is represented by an ++adjacency multilist++, the space complexity is $\Theta(m)$.
(D) If G is represented by an adjacency matrix, the time complexity of determining whether G is connected is $O(m)$.
### 解答
:::info
📚 ++[Horowizt 6.1.3]++
- ***adjacency multilist*** ~[107清大]~
:::
- (A) trivial
- (B) $O(n+m) = O(m)$ $because$ $m >> n$
- \(C) $O(n+m) = O(m)$
- (D) $O(n^2)$
## 8. ABC / C (通靈題)
### 題目
8. Given an n-node undirected graph. Which of the following statements are correct?
(A) Single source single destination shortest path algorithm takes $O(n^2)$ time complexity.
(B) Single source multiple destination shortest path algorithm takes $O(n^2)$ time complexity.
\(C) All pair shortest path algorithm takes $O(n^3)$ time complexity.
(D) All pair shortest path algorithm takes $O(n^2)$ time complexity.
### 解答
- (A)(B) Dijkstra's algorithm without priority queue is $O(n^2)$, but with binary heap is $O((n+m)\log n)$, with Fibonacci heap is $O(n\log n + m)$.
- However, no matter what kind of heap, the time complexity of Dijkstra's algorithm is in $O(n^2)$, if we does not consider tight bound.
- \(C)(D) Floyd-Warshall algorithm is $O(n^3)$
:::danger
✒️ 答疑
- (A)(B)中的SSSP是有可能有negative edge的，但這題本身就很通靈，如果要考慮負邊的話要用Bellman-Ford。但題目只有給 $|V|$ ，沒有給 $|E|$ ，而且也不一定是simple graph，不能用$|E|=O(n^2)$去計算，因此我覺得是不考慮negative edge的。
:::
## 9. ABD
### 題目
9. Which of the following statements are correct?
(A) Inserting the first element of an n-node one-dimension array has time complexity higher than a singly linked list.
(B) Removing the third element of an n-node one-dimension array takes $O(n)$ time complexity.
\(C) Inserting the first element of a circular singly linked list has time complexity much higher than that of a singly linked list.
(D) Inserting the last element of an n-node singly linked list takes $O(n)$ time complexity.
### 解答
- (A)
- Inserting the first element of an n-node one-dimension array is $O(n)$
- Inserting the first element of a singly linked list is $O(1)$
- (B) $O(n-3) = O(n)$
- \(C) both are $O(1)$
- (D) $O(n)$
:::danger
✒️ 答疑
- 一般的Singular Linked List只會維護 `head`，所以沒有特別說維護 `tail` 就當沒有 `tail` 。
- 在Horowitz中circular linked list的實作方法，是維護 `tail` (last)，這樣做的好處是等價於同時維護 `head` 和 `tail` (tail->next = head)。因此insert first element 是 O(1) 的。 ++[Horowitz 4.4.4]++
:::
## 10. D
### 題目
10. Which of the following statements are correct?
(A) The postfix of infix expression `b+a*c/d` is `bac+d/*`.
(B) The postfix of `(a+b)/(c-d)*e` is `ab+cd-*/`.
\(C) The infix of the postfix expression `ab+c*d/ef-/` is `(a+b)*c/(d/(e-f))`.
(D) The prefix of the postfix expression `abc+d/*` is `*a/+bcd`.
### 解答
- (A) postfix of infix expression `b+a*c/d` is `bac*d/+`
- (B) postfix of `(a+b)/(c-d)*e` is `ab+cd-/e*`
- \(C) infix of the postfix expression `ab+c*d/ef-/` is `(a+b)*c/d/(e-f)`
- (D)
- infix of `abc+d/*` is `a*((b+c)/d)`
- prefix of `a*((b+c)/d)` is `*a/+bcd`
# 二、問答題(50分)，請用深色筆書寫
## 1.
### 題目
Given a directed graph $G=(V, E)$, and two vertices $u$ and $v$ in $V$, we call vertex $v$ is reachable from $u$, if there exists a directed path from $u$ to $v$. A vertex s in Vis called a ***source vertex*** if every vertex in $V$ is **reachable** from $s$.
#### (a) (8%)
(a) (8%) Given a directed gaph $G=(V, E)$, and a specified vertex $v$ in $V$, design a **linear time** algorithm (i.e. your algorithm should run in $O(|V|+|E|)$ time) to
determine if v is a source vertex. You need to describe the data structure used in
your algorithm.
#### (b) (8%)
(b) (8%) Given a ***directed acyclic graph*** (DAG; a directed graph is acyclic if it contains **no directed cycles**) $G=(V, E)$, you are asked to determine if $G$ contains a source vertex. If you apply the algorithm of subproblem (a) on every vertex of $G$, you will get an algorithm runs in $O(|V|^{2}+|V||E|)$ time. It is not desirable. Design a more efficient algorithm for this problem. Analyze the time complexity of your algorithm.
#### \(c) (9%)
\(c) (9%) Given a directed graph $G=(V, E)$, you are asked to determine if $G$ contains a source vertex. Note that the given graph **may contain directed cycles**. As in subproblem (b) an $O\left(|V|^{2}+|V||E|\right)$ time algorithm is not acceptable. Design a more efficient algorithm for this problem and analyze the time complexity of your algorithm.
### 解答
#### (a)
- 用DFS檢查從 $v$ 出發是否可以到達每個點，如果可以，則 $v$ 是source vertex。
- 標記每個點是否被訪問過，如果DFS結束後仍有點沒有被訪問過，則 $v$ 不是source vertex。
- 使用 $visited$ 來標記是否被訪問過，使用 adjacency list $g$ 來做為圖的資料結構。因為不確定節點編號是否連續，所以使用 hash table 而不是 array 來儲存這兩項資訊。
- 複雜度分析：建圖需要 $O(|V|+|E|)$ 時間，DFS需要 $O(|V|+|E|)$ 時間，所以總時間複雜度為 $O(|V|+|E|)$。
#### (b)
:::success
📚 Similar to *Kahn’s algorithm* for Topological Sorting
:::
- 由acyclic graph的特性可知，若 $v$ 是source vertex，則 $v$ 的in-degree為0，且G中必存在至少一個in-degree為0的點，否則G中存在cycle。
- 但若G中存在超過1個in-degree為0的點，則這些點無法互相到達，因此G中不存在source vertex。
- 若G中洽存在一個in-degree為0的點，則用 part (a) 中的 isSource(G, v) 來檢查 $v$ 是否為source vertex。
- 複雜度分析：初始化和計算in-degree需要 $O(|V|+|E|)$ 時間，檢查in-degree為0的點需要 $O(|V|)$ 時間，isSource(G, v)需要 $O(|V|+|E|)$ 時間，所以總時間複雜度為 $O(|V|+|E|)$。
#### \(c)
> 不是很熟SCC，psuedo code 可以參考 `CLRS 20.5`
1. 利用 Kosaraju's Algorithm 找到Strongly Connected Components (SCC)
2. 將每個 SCC 視為一個點，構建一個新的圖 $G'=(V', E')$ ，則 $G'$ 是一個DAG
3. 用 part (b) 中的方法檢查 $G'$ 是否存在source vertex
## 2.
### 題目
A __non-deterministic (ND) algorithm__ has two phases, the choosing phase and the checking phase, for solving a given problem. The former is for selecting one from a specific set of
choices iteration by iteration. The latter is for checking if all selected choices constitute a solution to the problem. If so, the algorithm returns `SUCCESS`; otherwise, `FAILURE`. It is assumed that an ND algorithm always selects choices that lead to the return of SUCCESS unless there are no such choices. A problem is called an NP problem if there exists a
polynomial time-complexity ND algorithm solving the problem. For example, the famous satisfiability (SAT) problem is an NP problem. The SAT problem is to determine if a given Boolean formula $f\left(x_{1}, \ldots, x_{n}\right)$ of $n$ Boolean variables $x_{1}, \ldots, x_{n}$ is satisfiable or unsatisfiable. A formula $f\left(x_{1}, \ldots, x_{n}\right)$ is satisfiable (resp., unsatisfiable) if there exists an (resp., no) TRUE-FALSE assignment of the n variables to make the formula TRUE. The following polynomial time-complexity ND algorithm, called __ND-SAT__, can solve the SAT problem, which is the evidence that the SAT problem is an NP problem.
In practice, we can prove a problem to be an NP problem by showing a polynomial timecomplexity ND algorithm solving the problem.
#### (a) (18%)
(a) __By this concept, please prove that the exact cover decision problem (ECDP) is an NP problem by showing a polynomial time-complexity ND algorithm solving the ECDP__ (18\%). Note that you should follow the above-mentioned ND algorithm definition and the format of the ND-SAT algorithm. That is, the ND algorithm should contain the input description, the output description, the choosing phase, the checking phase, and return statements; otherwise, you will lose some points.
#### (b) (7\%)
(b) __Furthermore, please analyze the time complexity of your ND algorithm in terms of the big $\mathrm{O}$ notation to show that it indeed. has a polynomial time complexity__ (7\%). The ECDP is defined as follows. Given a universal set $U=\left\{u_1, \ldots, u_m\right\}$ of $m$ elements, and a collection $S=\left\{S_1, \ldots, S_n\right\}$ of $n$ sets, where $S_i$ is a non-empty subset of $U, 1 \leq i \leq n$, the ECDP is to determine if there exists a collection $S^*$ of sets that is an exact cover of $U$, where $S^* \subseteq S$. A collection $S^*$ of sets is an exact cover of $U$ if every element $u$ in $U$ appears exactly once in only one set of $S^*$. For example, suppose $U=\{1,2,3,4,5,6,7\}$ is a universal set of seven elements, and $S=\{A, B, C, D, E\}$ is a collection of five sets, where $A=\{1,2,7\}, B=\{1,4\}, C=\{4,5\}, D=\{3,5,6\}$, and $E=\{4\}$. Then, $S^*=\{A, D, E\} \subseteq S$ is an exact cover of $U$. In summary, the ECDP with the input of $U=\{1,2,3,4,5,6,7\}$ and $S=\{A=\{1,2,7\}, B=\{1,4\}, C=\{4,5\}, D=\{3,5,6\}, E=\{4\}\}$ will return SUCCESS, since $S^*=\{A, D, E\} \subseteq S$ is an exact cover of $U$.
### 解答
#### (a)
- 模仿題目中的寫法即可。對每個 $S_i$ 選擇是否加入 $S^*$ (取或不取)，然後檢查是否是exact cover。
- 因為是Decision Problem，因此 $S_i$ 取或不取的選擇是確定的，不存在也不用考慮反悔的情況。因此若選擇導致不是exact cover，則可以直接回傳 `FAILURE`。
```
Algorithm: ECDP
Input: U={u1, ..., um}, S={S1, ..., Sn}
Output: SUCCESS or FAILURE
S* = {} // empty set
for i = 1 to n
tmp = choice({TRUE, FALSE}) // choose whether Si is in S* or not
if tmp == TRUE then
if (S* ⋂ Si == {}) then // check if S* is an exact cover
S* = S* ∪ {Si}
else // not an exact cover
return FAILURE
if (S* == U) then
return SUCCESS
else
return FAILURE
```
#### (b)
- for loop 執行了 $n$ 次
- 每次選擇是否加入 $S^*$ 需要 $O(1)$ 時間
- 每次檢查是否是exact cover (交集) 需要 $O(m)$ 時間，若使用bitwise operation，則可以降至 $O(1)$ 時間。
- 將Si加入S* (聯集) 需要 $O(m)$ 時間，若使用Union-Find + Path Compression + Weighted Union，則可以降至 $O(1)$ 時間。
- 檢查 $S^* == U$ 需要 $O(m)$ 時間
- 因此總時間複雜度為 $O(nm)$
<style> :root{
--markup-code: #003060;
}
.markdown-body code,
.markdown-body tt {
background-color: #b0c4de ;
color: var(--strong-code);
}
.markdown-body strong{
color: var(--strong-code);
font-weight:700
}
.markdown-body code{
color: var(--markup-code)!important
}
</style>
Sign in with Wallet
Connect another wallet