一、Data Structure (50%)
1. (20%) Let Sn be the expected number of comparison in a successful search of a randomly constructed n-node binary tree, and let Un be the expected number of comparisons in an unsuccessful search. We assume that Hn is the n-th harmonic number. Please represent Sn and Un respectively using harmonic number.
參考解答:


2. (30%) For the AOE (Activity on Edge) network described by the table, (a) What is the earliest time the project can finish? (b) Please list all critical paths. Note that state 1 is the starting state and state 10 is the goal state.
Activity | From state | To state | Time |
a1 | 1 | 2 | 5 |
a2 | 1 | 3 | 5 |
a3 | 2 | 4 | 3 |
a4 | 3 | 4 | 6 |
a5 | 3 | 5 | 3 |
a6 | 4 | 6 | 4 |
a7 | 4 | 7 | 4 |
a8 | 4 | 5 | 3 |
a9 | 5 | 7 | 1 |
a10 | 5 | 8 | 4 |
a11 | 6 | 10 | 4 |
a12 | 7 | 9 | 5 |
a13 | 8 | 9 | 2 |
a14 | 9 | 10 | 2 |
參考解答:
(a) 22
(b)
1: a2→a4→a8→a9→a12→a14
2: a2→a4→a8→a10→a13→a14
3: a2→a4→a7→a12→a14
二、Algorithms (50%)
1. (20%) Solving the recurrence T(n)=2T(n/4)+√n using Θ notation.
參考解答:Θ(√nlgn)
2. (20%) The incident matrix of a directed graph G=(V,E) with no self-loops is a |V|×|E| matrix B=(bij) such that
bij={−1if edge j leaves vertex i1if edge j enters vertex i0otherwise
Describe what the entries of the matrix product BBT represent, where BT is the transpose of B.
參考解答:
Let A=BBT=(aij)
aij={vi‘s indeg()+outdeg()i=j−1×edges between vi and vji≠j
3. (10%) The Fibonacci numbers are defined by recurrence
F0=0,
F1=1,
Fi=Fi−1+Fi−2 for i≥2.
Give an O(n)-time dynamic-programming algorithm to compute the nth Fibonacci number.
參考解答:
array f[0...n];
f[0] = 0;
f[1] = 1;
for i = 2 to n:
f[i] = f[i - 1] + f[i - 2];
return f[n];
題目(pdf):連結
有任何問題,或想要完整解釋的,歡迎在下方留言唷!
Jackson
您好,請問一下,Data Structure critical path 只有那兩條嗎 ?
我看 a2 → a4 → a7 → a12 → a14 也是 22 = 5 + 6 + 4 + 5 + 2
mt
這條也是,已經更正,感謝!