108 年 國立成功大學資訊管理研究所乙組《資料結構》

Show that $\sum_{i=1}^{n} i^3 = (\sum_{i=1}^{n} i)^2$.

For any given positive integers x and n, write a program that uses the minimum number of multiplications to calculate $x^n$ (5%), and justify your answer. (5%)

Let an integer $m$ be expressed as a binary number $b_k b_{k-1} \dots b_1 b_0$ for some integer $k$, and let the remainder of $a$ divided by $n$ be denoted as $a \pmod n$. For example, integer 10 can be expressed as binary number 1010 for $k=3$, and $10 \pmod 8 = 2$.

(1) Explain why the following algorithm can be used to calculate $a^m \pmod n$. (10%)

f ← 1
For i ← k down to 0
  f ← (f × f) mod n
  If bᵢ = 1 Then f ← (f × a) mod n
Next i
Return f

(2) Use the above algorithm to calculate $7^{560} \pmod{561}$. (5%)

(1) Distinguish open hashing from closed hashing. (5%)
(2) Given input {25, 33, 64, 75, 24, 41} and a hash function $h(x) = x \pmod 8$, show the resulting open hash table, closed hash table using linear probing, and closed hash table using quadratic probing after each insertion. (10%)

Circle T or F for each of the following statements to indicate whether the statement is true or false, respectively. If the statement is correct, briefly state why. If the statement is wrong, explain why or give a counter example. Answers WITHOUT reasons will get at most 1 point.

(a) [4%] (T, F) Given $n$ integers uniformly distributed in the range $[-n^3, n^2]$. If we use Bucket Sort to sort these $n$ integers, it takes $O(n^3)$ time, because the range is $O(n^3)$.

(b) [4%] (T, F) Given $n < 10^{20}$ integers whose values are uniformly distributed in the range $[-n^3, n^2]$. If we use Counting Sort to sort these $n$ integers, it takes $O(1)$ time.

(c) [4%] (T, F) The tree in Fig. 1 is a min-heap of a completed binary tree of 5 elements.
🖼️【此處有附圖，請對照原卷】

(d) [4%] (T, F) In a complete undirected graph $K_n$ with $n$ nodes $\{1,2,...,n\}$, let $c_{ij} > 0$ represent the length of any edge $(i,j)$. We can use Dijkstra's algorithm to find a shortest simple path from node 3 to node 4 that CANNOT pass through nodes 1 and 2, but MUST pass through all other nodes.

(e) [4%] (T, F) In a complete undirected graph $K_n = (N,A)$ of $|N|=n$ nodes and $|A|=m$ arcs, let $c_{ij} > 0$ represent the length of any edge $(i, j) \in A$, and $W_i = \sum_{(i,j)\in A} c_{ij}$ represent the sum of lengths for all arcs $(i, j)$ adjacent to node $i$. To calculate $\min_{i \in N} \{W_i\}$, it takes $O(n^2)$ time.

(f) [4%] (T, F) $T(n)=T(n-1)+n, T(1)=1$, then $T(n)=O(n^3)$.

(g) [4%] (T, F) Given a min-heap of $n$ values, to find the maximum of these $n$ values takes $O(\log n)$ time.

(h) [4%] (T, F) A binary search tree of $n \ge 5$ numbers can NEVER be a min-heap.

Given a social simple network G=(N,A) for n=|N| persons. Let node i be person i and $d_{ij}$ be the number of "likes" given to j from i (so, $d_{ij}$ may not equal to $d_{ji}$). D is a given positive integer as a threshold. We construct a directed arc (i,j) if $d_{ij} \ge D$, and $\text{deg}_{i}^{\text{out}}$ and $\text{deg}_{i}^{\text{in}}$ are the outdegree and indegree of node i. Note that it is not necessarily both (i,j) and (j,i) exist at the same time. Suppose there are m=|A| arcs in G, where m<n(n-1). Person i and j are direct friends if both (i,j) and (j,i) exist, and are potential friends if they are NOT friends but still connect to each other by directed paths in G.

(a) [6%] To identify all the direct and potential friends for a person k, can you do this in O(m) time? Why or why not?

(b) [6%] Let $G_i = \sum_{(i,j)\in A} d_{ij} / \text{deg}_{i}^{\text{out}}$ and $R_i = \sum_{(j,i)\in A} d_{ji} / \text{deg}_{i}^{\text{in}}$ represent the average Giver and Receiver index of person i. Can you calculate $G_i$ and $R_i$ for all $i \in N$ within $O(m)$ or better time? Why or why not?

(c) [6%] Suppose we have already calculated the $G_i$ and $R_i$ for all $i \in N$. Let $F_i = R_i - G_i$ represent an average Fortune index. Suppose $\text{deg}_{i}^{\text{out}}$ and $\text{deg}_{i}^{\text{in}}$ for all $i \in N$ are also given. For a person k, we want to find the most fortunate person among his (direct and potential) friends and friends of his friends (i.e., within 2 arcs to or from node k). Can you identify this person in O(1) time, why or why not?