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

Suppose that the following list is the result of the first partition step of quick sort.

$12,\ 9,\ 1,\ 13,\ 19,\ 24,\ 22,\ 20$

Which of the following statements is correct about the partition step?

(A) The pivot could have been either $13$ or $19$.
(B) The pivot must be $13$.
(C) Both $13$ and $19$ are pivots in the first partition.
(D) Neither $13$ nor $19$ could have been the pivot.
(E) None of the above.

Build a binary search tree for the input sequence $9,4,8,7,20,15,14,3,10$. It is assumed that the tree root is on level $1$.

(A) There are five levels in the tree.
(B) $20$ is on level $3$.
(C) $7$ and $10$ have the same father.
(D) The left subtree of $20$ has $1$ node.
(E) None of the above.

Which of the following tree is a legal max-heap?

(A) A tree with level-order traversal sequence $\{67,45,19,22,43,16\}$.
(B) A tree with level-order traversal sequence $\{67,43,19,22,45,16\}$.
(C) A tree with level-order traversal sequence $\{14,18,27,19,63,48\}$.
(D) A tree with level-order traversal sequence $\{45,22,67,8,34,52\}$.
(E) None of the above.

Blank (B1) in the algorithm above should be ____.

(A) swap($list[i+1]$, $list[j]$, $temp$)
(B) swap($list[i]$, $list[j]$, $temp$)
(C) swap($list[i]$, $list[j+1]$, $temp$)
(D) swap($list[i+1]$, $list[j+1]$, $temp$)
(E) None of the above.

Blank (B2) in the algorithm above should be ____.

(A) perm($list$, $i+1$, $n$)
(B) perm($list$, $i$, $n$)
(C) perm($list$, $j$, $n$)
(D) perm($list$, $j+1$, $n$)
(E) None of the above.

Consider an empty hash table with $10$ buckets and each bucket has $2$ slots. Suppose that the hash function is $h(n)=n\bmod 10$, and the following numbers are sequentially inserted into the hash table:

$6,\ 16,\ 22,\ 45,\ 54,\ 25,\ 7,\ 75,\ 5,\ 108$

Which of the following statements are true?

(A) If linear probing is adopted to handle overflow, the summation of the numbers in the full buckets of the hash table is $287$.
(B) If linear probing is adopted to handle overflow, the summation of the numbers in the full buckets of the hash table is $172$.
(C) If quadratic probing is adopted to handle overflow, the summation of the numbers in the full buckets of the hash table is $221$.
(D) Compared with quadratic probing, linear probing requires fewer bucket accesses (in average).
(E) None of the above.

A hash function maps a key into a bucket in the hash table. Which of the following statements is true?

(A) A division hash function with divisor $D=7^r$, where $r$ is an integer, may result in serious collision.
(B) Compared with hash chaining, open addressing requires fewer bucket accesses (in average).
(C) When hash chaining is used to resolve overflows, the search for a key involves comparison with keys that have different hash values.
(D) In dynamic hashing, data buckets grow or shrink (added or removed dynamically) as the records increase or decrease.
(E) None of the above.

For the following items, choose the correct one(s):

(A) $d^{(2)}[5,1]=2$
(B) $d^{(2)}[5,4]=-3$
(C) $d^{(3)}[4,1]=4$
(D) $d^{(3)}[4,2]=11$
(E) $d^{(3)}[4,5]=6$

Follow the previous question. Choose the correct item(s):

(A) $d^{(4)}[1,2]=7$
(B) $d^{(4)}[1,3]=-1$
(C) $d^{(5)}[1,2]=-2$
(D) $d^{(5)}[3,2]=-2$
(E) $d^{(5)}[4,2]=3$

According to this graph, choose the correct item(s):

(A) $\delta[a,h]=13$
(B) $\delta[b,h]=12$
(C) $\delta[d,h]=6$
(D) $\delta[e,h]=5$
(E) $\delta[f,h]=7$

Follow the previous question. Choose the correct item(s):

(A) $[b,c,d,g,h]$ is a progress path.
(B) $[b,e,d,g,h]$ is a progress path.
(C) $[b,e,f,h]$ is a progress path.
(D) $[a,b,f,h]$ is a progress path.
(E) $[a,b,e,g,h]$ is a progress path.

Follow the previous question. Choose the correct item(s):

(A) There is totally $1$ progress path from $e$ to $h$.
(B) There are totally $9$ progress paths from $a$ to $h$.
(C) There is totally $1$ progress path from $f$ to $h$.
(D) There are totally $3$ progress paths from $b$ to $h$.
(E) There are totally $5$ progress paths from $c$ to $h$.

A divide-and-conquer algorithm solves a problem directly if the problem is small. If the problem is large, it is first divided into two or more parts called subproblems. Each subproblem is then recursively solved (conquered) in the same manner. Afterwards, the solutions to the subproblems are combined (merged) into a solution to the original problem.

The merge sort algorithm is a well-known example following the divide-and-conquer paradigm. The key operation of the merge sort algorithm is the merging of two sorted sequences.

To perform the merging, we use an auxiliary procedure $\operatorname{MERGE}(A,p,q,r)$, where $A$ is an array and $p$, $q$, and $r$ are indices numbering elements of the array such that $p\le q<r$. The procedure assumes that the subarrays $A[p\ldots q]$ and $A[q+1\ldots r]$ are in sorted order. It merges them to form a single sorted subarray that replaces the current subarray $A[p\ldots r]$.

The pseudo code of the MERGE operation is shown below. Based on the operation, we can design the merge sort algorithm easily.

(a) Write a detailed divide-and-conquer merge sort algorithm using the MERGE operation. Note that the algorithm MUST include well-described input and output. ($9\%$)

(b) Analyze the time complexity of the merge sort algorithm with the big-O notation. ($8\%$)

$\operatorname{MERGE}(A,p,q,r)$

Input:
$A$: an array of elements;
$p,q,r$: indices of $A$, where $p\le q<r$, and the subarrays $A[p\ldots q]$ and $A[q+1\ldots r]$ are in sorted order (from small to large).

Output:
$A$: an array of elements, where the subarray $A[p\ldots r]$ is in sorted order (from small to large).

1. $n_1\leftarrow q-p+1$
2. $n_2\leftarrow r-q$
3. create arrays $L[1\ldots n_1+1]$ and $R[1\ldots n_2+1]$
4. for $i\leftarrow 1$ to $n_1$

5. do $L[i]\leftarrow A[p+i-1]$
   

6. for $j\leftarrow 1$ to $n_2$

7. do $R[j]\leftarrow A[q+j]$
   

8. $L[n_1+1]\leftarrow\infty$
9. $R[n_2+1]\leftarrow\infty$
10. $i\leftarrow 1$
11. $j\leftarrow 1$
12. for $k\leftarrow p$ to $r$

13. do if $L[i]\le R[j]$
    

14.     then $A[k]\leftarrow L[i]$
    

15.          $i\leftarrow i+1$
    

16.     else $A[k]\leftarrow R[j]$
    

17.          $j\leftarrow j+1$
    

Given a chain $\langle A_1,\ldots,A_n\rangle$ of $n$ matrices, where matrix $A_i$, $i=1,\ldots,n$, has dimension $p_{i-1}\times p_i$, the matrix-chain multiplication problem is to fully parenthesize the product $A_1\ldots A_n$ in a way that minimizes the number of scalar multiplications.

We can use the dynamic programming strategy to solve the matrix-chain multiplication problem as follows. Define $m[i,j]$ to be the minimum number of scalar multiplications needed to compute the matrix product $A_i\ldots A_j$, $i\le j$.

Since we know the value of $m[i,j]$ for $i=j$, we can then calculate $m[1,n]$ in a bottom-up manner as the minimum number of scalar multiplications for the product $A_1\ldots A_n$ by a recursive form of $m[i,j]$.

Write down the recursive form of $m[i,j]$. ($8\%$)

Below is the algorithm AllPairCost which computes the shortest distances between all pairs of vertices $i,j$, where $i\ne j$.

Formally, given distances of edges in graph $G$, determine the shortest distances between all pairs of vertices in $G$. Note that the distance of an arbitrary edge in $G$ is non-negative.

(a) Blanks (B3) and (B4) in the algorithm below should be ____ and ____. ($4\%$)

(b) Blank (B5) in the algorithm below should be ____. ($3\%$)

Algorithm AllPairCost

Input: a two dimensional array $C$, where $C[i][j]$ denotes the distance of directed edge $(i,j)$ (i.e. the edge from vertex $i$ to vertex $j$).

Output: a two dimensional array $D$, where $D[i][j]$ denotes the shortest distance from vertex $i$ to vertex $j$.

1: int $i$, $j$, $k$;
2: for ($i=0$; $i<n$; $i$++)
3: for ($j=0$; $j<n$; $j$++)
4: (B5) ____;
5: for ($k=0$; $k<n$; $k$++)
6: for ($i=0$; $i<n$; $i$++)
7: for ($j=0$; $j<n$; $j$++)
8: if ((B3) ____)
9: (B4) ____;

Suppose that array $A[1:n]$ maintains a binary tree. For a binary tree node stored in $A[i]$, its two children (if exist) are stored in $A[2i]$ and $A[2i+1]$, respectively.

The program below aims to complete the following two tasks:

i. adjust array $A$ to establish a max heap, and
ii. apply heap sort on the max heap built in (i) in nondecreasing order.

(a) Blank (B6) in the program below should be ____. ($4\%$)

(b) Blank (B7) in the program below should be ____. ($4\%$)

void adjust(int $A$[], int $root$, int $n$)
{
int $child$, $rootkey$;
int $temp$;
$temp=A[root]$;
$rootkey=A[root]$;
$child=2*root$;
while ($child\le n$) {
if (($child\le n$) && ($A[child]<A[child+1]$))
$child$++;
if ($rootkey>A[child]$)
break;
else {
(B6) ____;
$child\mathrel{*{=}}2$;
}
}
(B7) ____;
}

void heapsort(int $A$[], int $n$)
{ /* perform a heap sort on $A[1:n]$ /
int $i$, $j$;
int $temp$;
for ($i=n/2$; $i>0$; $i$++) / adjust the binary tree to establish the max heap /
adjust($A$, $i$, $n$);
for ($i=n-1$; $i>0$; $i$--) { / heap sort /
swap($A[1]$, $A[i+1]$, $temp$); / exchange $A[i]$ and $A[i+1]$ */
adjust($A$, $1$, $i$);
}
}