114 年 國立中央大學資訊工程學系碩士班《資料結構與演算法》

An empty 11-bucket hash table has hash function $h(k)=k\%11$ and adopts quadratic probing (i.e., $(h(k)+i^2)\%11$, $(h(k)-i^2)\%11$ for $i=1, 2, \dots$). Below is the resulting hash table after inserting 8 items.

Which of the following is/are the possible input sequence of these 8 items?
(A) 27 37 16 17 59 15 25 38
(B) 27 37 16 59 15 25 38 17
(C) 37 27 16 59 25 15 17 38
(D) 27 16 37 38 59 15 17 25

Which of the following statements are correct?
(A) The postfix of $(a+b)/(c-d)+e$ is $ab+cd-/e+$.
(B) The postfix of infix expression $b+a/c*d$ is $bac+d/*.$
(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$.

Given the input list is L = [28, 203, 16, 37, 127, 521, 63, 528, 210, 216, 941, 45].
Which of the following statements is (are) correct?
(A) At the end of second pass of LSD Radix sort, the 6-th element of the resulting
chain is 45.
(B) At the end of second pass of LSD Radix sort, the 8-th element of the resulting
chain is 528.
(C) At the end of second pass of LSD Radix sort, the 6-th element of the resulting
chain is 127.
(D) At the end of first pass of LSD Radix sort, the 8-th element of the resulting chain
is 216.

A binary tree has inorder traversal ILOVENCU, and postorder traversal ILVNCUEO. Which of the following statements is (are) true?
(A) The fifth letter in the level-order traversal is V
(B) The height of the binary tree is 4
(C) C is a leaf node
(D) The sixth letter in the level-order traversal is U

Consider the code fragment below.
container.push('l');
container.push('L');
container.push('O');
container.push('V');
container.pop();
container.push('E');
container.pop();
container.push('N');
container.pop();
container.push('C');
container.push('U');

Which of the following statements is (are) true?
(A) If the "container" is an empty standard stack. The sequence of elements inside the
"container" from its top to the bottom is ILOCU
(B) If the "container" is an empty standard queue. The sequence of elements inside
the "container" from its front to its rear is VENCU
(C) If the "container" is an empty min heap, the level order traversal of the heap is
CNOVU
(D) If the "container" is an empty max heap, the level order traversal of the heap is
ULEIC

Consider a red-black tree with level order 50, 30, 80, 90. Which of the following statements is (are) true?
(A) node 30 is red.
(B) After inserting 70 and 75, the level order traversal of the resulting red-black tree is
50, 30, 80, 70, 90, 75
(C) After inserting 70 and 75, node 90 in the resulting red-black tree is black.
(D) After inserting 70, 60, and 65, node 65 in the resulting red-black tree is black.

Given a directed weighted graph G=(V, E), where each edge (i,j) ∈ E has weight w(i,j).
The adjacency matrix W is defined as below

Below is an algorithm for finding shortest paths of all vertex pairs in a directed weighted graph.

F (G,W)
{
  n=|V|
  D(0)=W
  for (k = 1; k<= n; k=k+1)
    for (i = 1; i<=n; i=i+1)
      for (j = 1; j<= n; j=j+1)
        if D(k-1)[i,j] > D(k-1)[i,k] + D(k-1)[k,j]
          then D(k)[i,j] = D(k-1)[i,k] + D(k-1)[k,j]
          else D(k)[i,j] = D(k-1)[i,j]
  return D(n)
}

Which of the following statements are true?
(A) k is on the shortest path if $D^{(k)}[i,j] = D^{(k-1)}[i,k] + D^{(k-1)}[k,j]$
(B) if k is on the shortest path then $D^k [i,j] = D^{(k-1)}[i,k] + D^{(k-1)}[k,j]$
(C) if k is on the shortest path then $D^{(k-1)}[i,j] > D^{(k-1)}[i,k]+D^{(k-1)}[k,j]$
(D) k is on the shortest path if $D^{(k-1)}[i,j] > D^{(k-1)}[i,k]+D^{(k-1)}[k,j]$

Consider a UAV (Unmanned Aerial Vehicle) with F unit of fuel travels from NCU to a
destination "target" km away. There are n gas stations along the way. When the UAV
refuels at a gas station, all the fuel of the gas station is transferred into the UAV.
Suppose that the UAV consumes one unit of fuel for every kilometer it travels. Let the
position and fuel of a gas station indicate the distance between the gas station and NCU and
its volume of fuel, respectively. Return the minimum number of refueling stops the UAV
must make in order to reach its destination.
typedef struct {
int position;
int fuel;
} stop_info;
int Refuel(int target, int F, int n, stop_info s[]) {
int N_R = 0; // number of refuel
int i; //gas stations ID
stop_info X;
while (F <target) {
for (i=0; L1; ++i)
Q.push(s[i].fuel);
if (Q.empty()) return -1;
X=Q.pop();
F += X.fuel
N_R++;
}
return N_R;
}
What should be filled in blank L1?
(A) (i<n) && (s[i].position <=F)
(B) (i<n) && (s[i].fuel <=F)
(C) (i<n) && (s[i].position <=target)
(D) i<n

Consider Refuel algorithm above. Which of the following statements are true?
(A) Q could be a stack
(B) Q could be a priority queue
(C) Q could be a max heap
(D) Q could be min heap

Consider Refuel algorithm above. Which of the following statements is true?
(A) The time complexity of Refuel algorithm above is $O(n^2 \log n)$
(B) The time complexity of the minimum number of refuel problem is $O(n^2 \log n)$
(C) The time complexity in Refuel algorithm above is $O(n \log n)$
(D) The time complexity of the minimum number of refuel problem is $O(n \log n)$

Which of the following statements about hashing algorithms are incorrect?
(A) A good hash function should distribute the keys uniformly into the slots of the table.
(B) The load factor of a hash table is the average number of keys per slot.
(C) Assume all keys are integers, and define $h(k) = k \pmod m$. If $m$ has a divisor $d$, a preponderance of keys that are congruent modulo $d$ can favorably affect uniformity.
(D) If open addressing is used for resolving collisions, the probe sequence $h(k, 0), h(k, 1), \dots, h(k,m-1)$ should be a permutation of $\{1, 2, \dots, m\}$.
(E) Theoretically speaking, there is no perfect hashing.

The Longest Common Subsequence (LCS) problem finds a longest subsequence
common to two given sequences x[1..m] and y[1..n]. Which of the following
statements are incorrect?
(A) If we simply check every subsequence of x[1.. m] to see if it is also a subsequence
of y[1..n], the worst-case running time is $O(n^2m)$.
(B) If we define $c[i,j] = |LCS(x[1.. i], y[1..j])|$, where $|.|$ denotes the length of
the string, then $c[m, n] = |LCS(x, y)|$.
(C) $c[i,j] = c[i-1,j-1] + 1$ if $x[i] = y[j]$; Otherwise,
$c[i,j] = c[i-1,j] + c[i,j - 1]$.
(D) The recursive formulation of LCS indicates that the complexity of its dynamic
algorithm is potentially exponential.
(E) If $z = LCS(x, y)$, then any prefix of $z$ is an LCS of a prefix of $x$ and a prefix of $y$.

Which of the following statements about Minimum Spanning Tree are incorrect?
(A) The spanning tree of a graph exists uniquely which connects all vertices with the
minimum total edge weight.
(B) Both Prim's and Kruskal's algorithms are greedy algorithms.
(C) After optimization, Prim's and Kruskal's algorithms have the same (worst case)
time complexity.
(D) Disjoint-set data structure can be used to improve the time complexity of the
Prim's algorithm.
(E) Fibonacci heap can be used to improve the time complexity of the Kruskal's
algorithm.

Which of the following statements about the Maximum Flow problem are incorrect?
(A) In a flow network, source node has no incoming flow and terminal (sink) node has
no outgoing flow.
(B) Each edge has forward flow and backflow, and the two flows must always be inverses
of each other.
(C) Ford-Fulkerson algorithm finds the maximum flow from source to terminal with
time complexity $O(Ef)$, where E represents the number of edges and f is the
maximum flow of the final graph.
(D) If we look at all the possible cuts in the graph, and find the largest capacity of those
cuts, then that value is the value of the maximum flow for that network.
(E) If a network has antiparallel edges (i.e., the edges connecting two nodes back and
forth), we can convert it to an equivalent one with no antiparallel edges.

Which of the following statements about Single-Source Shortest Paths problem are incorrect?

(A) If a graph $G$ contains a negative-weight cycle, then all shortest paths do not exist.
(B) A subpath of a shortest path is a shortest path.
(C) Dijkstra’s algorithm finds single-source shortest paths in graphs with nonnegative-weight cycles.
(D) If binary heap is used, the worst-case time complexity of Dijkstra’s algorithm is $O(E+V\log V)$, where $E$ represents the number of edges and $V$ the number of vertices.
(E) If the weight of all edges is the same, there is a faster algorithm than Dijkstra’s algorithm to compute single-source shortest paths.

Choose necessary step(s) to prove that a decision problem $D$ is NP-complete:

(A) Show that the problem $D$ can polynomially reduce to an NP-complete problem.
(B) Design a non-deterministic algorithm to solve the problem $D$ in exponential time complexity.
(C) Design a non-deterministic algorithm to solve the problem $D$ in polynomial time complexity.
(D) Design a deterministic algorithm to solve the problem $D$ in polynomial time complexity.
(E) Show that an NP-hard problem can polynomially reduce to the problem $D$.

Choose correct statement(s):

(A) If a problem $X$ can polynomially reduce to an NP-hard problem, then $X$ is NP-hard.
(B) If we can prove that an existing NP-complete problem can polynomially reduce to a problem $X$, then $X$ is NP-hard.
(C) An NP-hard problem can polynomially reduce to any NP-hard problem.
(D) All NP problems can polynomially reduce to any NP-complete problem.
(E) All NP problems can polynomially reduce to any NP-hard problem.

Choose correct statement(s):

(A) If $f(n)=3n^4+8n-1666$, then we can say $f(n)=O(n^5)$.
(B) If $f(n)=3n^4+8n-1666$, then we can say $f(n)=\Omega(n^3)$.
(C) If $f(n)=3n^4+8n-1666$, then we can say $f(n)=O(2^n)$.
(D) If $f(n)=3n^4+8n-1666$, then we can say $f(n)=O(n^4)$.
(E) If $f(n)=3n^4+8n-1666$, then we can say $f(n)=\Omega(n^4)$.

Choose correct statement(s):

(A) Dynamic programming is used to solve problems that can be broken down into overlapping subproblems.
(B) The Longest Common Subsequence (LCS) problem can be solved by dynamic programming with a time complexity of $O(m+n)$, where $m$ and $n$ are the lengths of the two sequences.
(C) Dynamic programming always uses a 2D table for storing intermediate results.
(D) In dynamic programming, memoization stores solutions to subproblems to avoid redundant computations.
(E) Dynamic programming can only be applied to problems with a greedy choice property.

Choose correct statement(s):

(A) Breadth-First Search (BFS) and Depth-First Search (DFS) are non-uninformed search strategies.
(B) A* algorithm combines the actual cost from the start node ($g(n)$) and the heuristic estimate to the goal ($h(n)$). If the heuristic is admissible (never overestimates the true cost) and consistent (satisfies the triangle inequality), A* always guarantees finding the optimal solution.
(C) Hill Climbing can escape from a local optimum due to its greedy nature.
(D) Branch and Bound uses both upper and lower bounds to prune the search space for saving computation.
(E) Dijkstra’s algorithm guarantees the shortest path even if the graph contains cycles.