# 交大 112 資演
###### tags: `考古`

## 施工中

## 選擇題

### 1.
Insert the following nodes 4, 5, 6, 1, 2, 3, 7 in sequence into an AVL tree. Which of the following statement(s) is(are) true ?

$(A)$ Node of 4 is the root node.
$(B)$ Node of 5 and Node 7 are at the same level.
$(C)$ Node of 6 is the ancestor of Node 7.
$(D)$ Node of 7 has no sibling.

:::spoiler 參考答案
**A, B, C**

Sibling of node 7 is node 5.
:::

### 2.
Given the resultant time complexity of $T(n)$ in big-O notation, where in all cases, $T(1) = 1$, which of the following statement(s) is(are) true ?

$(A)$ Let $T(n) = 2T(n - 1) + O(1)$. Then $T(n) = O(2^n)$
$(B)$ Let $T(n) = T(\frac{n}{2}) + O(1)$. Then $T(n) = O(log(n))$
$(C)$ Let $T(n) = T(n - 1) + O(n)$. Then $T(n) = O(n^2)$
$(D)$ Let $T(n) = 2T(\frac{n}{2}) + O(n)$. Then $T(n) = O(nlog(n))$

:::spoiler 參考答案
**A, B, C, D**

### A.
$T(n) = 2T(n - 1) + c$, c is constant
$T(n - 1) = 2T(n - 2) + c$

Replacing $T(n - 1)$
$T(n) = 2(2T(n - 2) + c) + c$.

Replacing $T(n - 2)$
$T(n) = 2^2(2T(n - 3) + c) + 2c + c$.

In general
$T(n) = 2^kT(n - k) + 2^{k-1}c + 2^{k-2}c + ... + c$.

Consider $k = n - 1$

### B.
Classic Master Theorem

### C.

$T(n) = T(n - 1) + n$
$T(n - 1) = T(n - 2) + n - 1$

$T(n) = T(n - k) + kn - k(k-1)/2$

Consider $k = n - 1$
$T(n) = T(1) + \frac{n-1}{n} - \frac{(n - 1)(n-2)}{2}$

### D.
Classic Master Theorem

:::
### 3.
Please refer to the following graph and solve the minimum spanning tree (MST) using **Kruskal's algorithm**. Which of the following statement(s) is(are) true ?


$(A)$ The sum of the weight of all edges in the MST is $110$.
$(B)$ Node 'a' connects to node e through node 'b' and 'd' in the MST.
$(C)$ The sum of the weight of all edges connecting node 'd' in MST is 50.
$(D)$ There are 4 edges in total in the MST

:::spoiler 參考答案
**A, B, D**

MST : $ \overline{ab}, \xoverline{bd}, \overline{de}, \overline{cd} $
C. $19 + 31 + 51 = 101$.
:::

### 4.
Which of the following statement(s) about Kruskal algorithm and Prim's algorithm is(are) correct ?

$(A)$ Kruskal algorithm's concentration is on vertices.
$(B)$ Prim's algorithm is better when there are many more edges than vertices
$(C)$ Kruskal algorithm can't use on negative-weighted-undirectedd graph.
$(D)$ For Prim's algorithm, choose different vertex as start vertex may get different total weight of the minimum spanning tree.

:::spoiler 參考答案
**B**

A. Concentration is on **edges**.
C. Kruskal can use on negative-weighted-undirected graph.
D. Different start vertex will eventually get **same** total weight of MST.

:::

### 5.
Insert the following nodes {6, 15, 3, 9, 4, 10, 8} in order into a binary search tree. Which of the following is(are) correct ?

$(A)$ Pre-order: 4, 3, 8, 10, 9, 15, 6
$(B)$ In-order: 3, 4, 6, 8, 9, 10, 15
$(C)$ Finding the node of 8 will go through three edges
$(D)$ The nodes of 4 and 9 are at the same level

:::spoiler 參考答案
**B, C, D**

A. 6,3,4,15,9,8,10
:::

### 6.
The hash function [h(k) = k mod m] is used to map an integer key to one of the slots, indexed 0, ..., m-1, of a hash table of m slots. Let m = 7. The table is initially empty. After inserting the keys 8, 12, 3, 11, 1, 2 into the table in the given order, which of the following is(are) correct ?

$(A)$ Consider using linear probing to handle collisions, then key 2 will be in the slot indexed 6.
$(B)$ Consider using quadratic probing to handle collisions, i.e., let the i-th probe position for a value k be given by the function $h(k, i) = h(k) + i^2$, then the key 2 will be in the slot indexed 2.
$(C)$ Consider using the function $h(k, i) = h(k) + i + i^2$ to handle collision, then key 2 will be in the slot indexed 2.
$(D)$ Consider using chaining to handle collision, then key 2 will be in the slot indexed 2.

### 7.
Which of the following statement(s) is(are) true ?

$(A)$ A directed graph can be reprensented as either using an adjacency matrix or an adjacency list.
$(B)$ Bread-first search (BFS) and Depth-first search (DFS) are algorithm for traversing a graph or tree. BFS typically uses a queue to store the nodes that need to be visited, while DFS typically uses a stack.
$(C)$ BFS can be used to find the shortest path between two nodes in a graph.
$(D)$ DFS can be used to determine whether a graph is strongly connected and to check whether a graph contains a cycle.

### 8.
Refer to the directed weighted graph below, and use the Bellman Ford's algorithm to find the shortest paths from node 0 to any other nodes in the graph. Which of the following statement(s) is(are) true ?

$(A)$ The total weight of the minimal shortest path is -31.
$(B)$ The total weight of the maximal shortest path is 10.
$(C)$ The total weight of all shortest paths from node 0 to the other nodes is -49.
$(D)$ The total weight of the last second minimal shortest path is -20.

:::spoiler Ref answer
A, C, (D)

D. 疑義後可選可不選，推測是 last second minimal 意思上有問題
:::

### 9.
送分

### 10.
The following question is about a red-black tree with M nodes, where M >= 3. Node definition is used. For the M nodes, the external and internal nodes are included. The function ceil(x) returns the smallest possible integer value which is greater than or equal to the given argument x. Which of the following statement(s) is(are) true ?

$(A)$ There are at least $ceil(\frac{M - 1}{3})$ red nodes.
$(B)$ There are at least $ceil(\frac{M}{2})$ black nodes.
$(C)$ The height difference is at most one between the left and right subtrees of a given internal node.
$(D)$ It is impossible to delete all the black inodes until the root is deleted.

### 11.
There is a max binary heap with height h, where h >= 2. The height of the root is 0. The pop operation is used to remove an element. After 15 elements are stored to the heap, the new height of the heap is H. The function ceil(x) returns the smallest possible integer value which is greater than or equal to the given argument x. Which of the following statement(s) is(are) correct ?

$(A)$ It takes at most ($2^{H + 1} - 1$) pop operations to remove all the nodes.
$(B)$ Let G = $ceil(\frac{H}{2})$. It takes at most $2^G$ pop operations to remove three levels of the heap.
$(C)$ To remove the second smallest element, it takes N pop operations, where N is inside [$2^{H-1}, 2^{H}$]
$(D)$ $|H - h|$ is smaller than or equal to 2.

### 12.
A min binary heap has one element which is 10. Now the following elements are stored to the heap in order: 5, 4, 3, 2, 9, 7, 8, 6. After that, node 5 is deleted. Which of the following statement(s) is(are) correct ?

$(A)$ The parent of node 9 is 7 and 8 is the child of 6.
$(B)$ Node 4 is the child of node 5 and 7 is not the parent of node 8.
$(C)$ The children of node 3 are nodes 4 and 6.
$(D)$ Node 2 does not have a parent and node 8 does not have any children.