112 年 國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》

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

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

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

(A) Let $T(n)=2T(n-1)+O(1)$. Then $T(n)=O(2^n)$.
(B) Let $T(n)=T(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(n/2)+O(n)$. Then $T(n)=O(n\log n)$.

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

🖼️【此處有附圖，見下方】

(A) The sum of the weights of all edges in the MST is 110.
(B) In the MST, node $a$ connects to node $e$ through nodes $b$ and $d$.
(C) The sum of the weights of all edges connected to node $d$ in the MST is 50.
(D) There are 4 edges in total in the MST.

Which of the following statements about Kruskal's algorithm and Prim's algorithm is (are) correct?

(A) Kruskal's algorithm focuses on vertices.
(B) Prim's algorithm is better when there are many more edges than vertices.
(C) Kruskal's algorithm cannot be used on a negative-weight undirected graph.
(D) For Prim's algorithm, choosing different vertices as the starting vertex may result in different total weights for the minimum spanning tree.

Insert the following nodes, in order, into a binary search tree: $\{6,15,3,9,4,10,8\}$. 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 node 8 will go through three edges.
(D) Nodes 4 and 9 are at the same level.

The hash function $h(k)=k\bmod m$ maps an integer key to one of the slots indexed $0,\ldots,m-1$ in 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) With linear probing to handle collisions, key 2 will be in the slot indexed 6.
(B) With quadratic probing to handle collisions, let the $i$th probe position for a value $k$ be given by $h(k,i)=h(k)+i^2$. Then key 2 will be in the slot indexed 2.
(C) With the function $h(k,i)=h(k)+i+i^2$ to handle collisions, key 2 will be in the slot indexed 2.
(D) With chaining to handle collisions, key 2 will be in the slot indexed 2.

Which of the following statements is (are) true?

(A) A directed graph can be represented using either an adjacency matrix or an adjacency list.
(B) Breadth-first search (BFS) and depth-first search (DFS) are algorithms 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.

Refer to the directed weighted graph below, and use Bellman-Ford's algorithm to find the shortest paths from node 0 to any other nodes in the graph. Which of the following statements 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 second-to-last minimal shortest path is $-20$.

The following pseudocode sorts the elements of array $Y$ in ascending order and stores the sorted elements in array $Z$. Array $Y$ has $2n$ numbers, where $n>0$. Let $Y[i]=\{1,2,3,\ldots,n,1,2,3,\ldots,n\}$. The array index is zero-based. The pseudocode is as follows:

Which instructions should be placed in (a) and (b), respectively?

(A) (a) $Y[i]<Y[j]$; (b) $Z[k]=Y[i+1]$
(B) (a) $Y[i]\leq Y[j]$; (b) $Z[k]=Y[i]$
(C) (a) $Y[i]<Y[j]$; (b) $Z[k]=Y[i]$
(D) (a) $Y[i]\leq Y[j]$; (b) $Z[k+1]=Y[i]$

The following question is about a red-black tree with $M$ nodes, where $M\geq 3$. The node definition is used. For the $M$ nodes, the external and internal nodes are included. The function $\operatorname{ceil}(x)$ returns the smallest possible integer value that is greater than or equal to $x$. Which of the following statements is (are) true?

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

There is a max binary heap with height $h$, where $h\geq 2$. The height of the root is 0. The pop operation removes an element. After 15 elements are stored in the heap, the new height of the heap is $H$. The function $\operatorname{ceil}(x)$ returns the smallest possible integer value that is greater than or equal to $x$. Which of the following statements is (are) correct?

(A) It takes at most $2^{H+1}-1$ pop operations to remove all the nodes.
(B) Let $G=\operatorname{ceil}(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.

A min binary heap initially contains one element, 10. The following elements are then stored in the heap in order: $5,4,3,2,9,7,8,6$. After that, node 5 is deleted. Which of the following statements is (are) correct?

(A) The parent of node 9 is 7, and 8 is the child of 6.
(B) Node 4 is not 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.

$S$ is an ordered sequence of numbers formed by two ordered sequences: $\{2n-1,2n-3,\ldots,1\}$ and $\{2,4,6,\ldots,2n\}$. Let

where $n\geq 10$. The elements of $S$ are stored into an empty stack one by one in the given order. After the elements are popped from the stack one by one, at the $X$th step, $(n-1)$ is popped from the stack, while $(n+1)$ is popped from the stack at the $Y$th step. Assume that $s$ and $t$ are two different positive elements of $S$, and $s+t=2n$. Which of the following statements is (are) correct?

(A) $X=n$ or $Y=n$.
(B) $|Y-X|=2$.
(C) $X$ must be larger than $Y$ for any positive integer $n$.
(D) It takes at most $n$ pop operations to pop one of the two elements, $s$ and $t$.

The following question is about a binary tree. Denote $x$ as a node. The function $\operatorname{parent}(x)$ returns the parent of $x$. Furthermore, $\operatorname{left}(x)$ and $\operatorname{right}(x)$ return the left child and right child of node $x$, respectively. $w$ and $y$ are nodes of the binary tree shown below. Given that

and

what are $w$ and $y$?

🖼️【此處有附圖，見下方】

(A) $w=3$ and $y=8$.
(B) $w=1$ and $y=5$.
(C) $w=1$ and $y=8$.
(D) $w=3$ and $y=7$.

This question considers binary trees with 5 nodes. The preorder and postorder traversal results are stored in the ordered lists $\{x_1,x_2,x_3,x_4,x_5\}$ and $\{y_1,y_2,y_3,y_4,y_5\}$, respectively. Furthermore,

Which of the following binary trees satisfies the condition?

🖼️【此處有附圖，見下方】

Initially, array $X[]=\{n,2,3,4,5,\ldots,n-1,n\}$, where $n\geq 4$. The array index is zero-based. Insertion sort is used to sort the elements of $X$ in descending order. Given the following pseudocode, how many times is Line L performed?

(A) $n+2$
(B) $n(n-1)/2$
(C) $(n-1)(n-2)/2$
(D) $n^2$

Consider processing a set of $n$ items. The algorithm consists of two parts: the first part takes $O(n\log n)$ time, and the second part takes $\Theta(n\log n)$ time. What is the total time for processing the set of $n$ items? Give your reasons. Use the most precise asymptotic notation to present the time required.

Linear-time algorithm for the selection problem (the computational problem of finding the $k$th largest number among $n$ numbers):

(a) A typical implementation divides the $n$ numbers into $\lceil n/5\rceil$ groups. We then find the medians of the $\lceil n/5\rceil$ groups, and then find the median of those medians. After $\Theta(n)+T(\lceil n/5\rceil)$ time, we can drop a set $S$ of numbers because $S$ does not contain the answer. Show that $|S|\geq n/4$, where $|S|$ is the size of $S$. (4%)

(b) Can we divide the $n$ numbers into $\lceil n/7\rceil$ groups instead of $\lceil n/5\rceil$ groups? Why or why not? (5%)

Given $n$ points on a line, the $n$ points are the $n$ users who need Wi-Fi signal. Suppose that we have only one kind of Wi-Fi router and we do not care about the number of Wi-Fi routers needed, but we have to minimize the power consumption of the routers. Power consumption is represented by the distance that the signal of a router can reach.

(a) Design a divide-and-conquer algorithm to determine the minimum power consumption. (4%)

(b) What is the time required for your divide-and-conquer algorithm? (2%)

Stack operations are:

• $\operatorname{Push}(\text{item})$: $S.\operatorname{push}(\text{item})$ pushes item into stack $S$.
• $\operatorname{Pop}()$: $S.\operatorname{Pop}()$ removes the top of stack $S$.
• $\operatorname{isEmpty}()$: $S.\operatorname{isEmpty}()$ answers whether stack $S$ is empty.

The following questions are about implementing a FIFO queue $Q$ by using two stacks $S1$ and $S2$.

(a) (2%) Describe the algorithm $\operatorname{enQueue}(\text{item})$ (insert item into $Q$) using pseudocode.

(b) (2%) Describe the algorithm $\operatorname{deQueue}()$ (delete an item from $Q$) using pseudocode.

(c) (4%) Show that $\operatorname{deQueue}$ takes $O(1)$ amortized cost.

Let $G=(V,E)$ be an undirected graph. A vertex cover $U$ is a vertex subset such that any edge in $E$ has at least one endpoint vertex in $U$.

(a) Let $U$ be a vertex cover and $M$ be a matching for $G$. Prove or disprove that $|M|\leq |U|$. (2%)

(b) Consider the following graph. Identify a maximum-size matching and a minimum-size vertex cover for it. (2%)

🖼️【此處有附圖，見下方】

Consider the residual flow network with a source vertex $S$ and a sink vertex $T$ given in the following figure. Apply the Ford-Fulkerson algorithm to it.

🖼️【此處有附圖，見下方】

(a) (2%) Write down the augmenting paths used by the Ford-Fulkerson algorithm.

(b) (2%) Identify a minimum $S$-$T$ cut for the network.