Processing math: 100%

考試

101成大資工程設[參考解答]

一、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.

參考解答:

mt01
mt02

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: a2a4a8a9a12a14
2: a2a4a8a10a13a14
3: a2a4a7a12a14


二、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=j1×edges between vi and vjij


3. (10%) The Fibonacci numbers are defined by recurrence

F0=0,
F1=1,
Fi=Fi1+Fi2 for i2.
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):連結

有任何問題,或想要完整解釋的,歡迎在下方留言唷!

2 留言

  1. Jackson

    您好,請問一下,Data Structure critical path 只有那兩條嗎 ?
    我看 a2 → a4 → a7 → a12 → a14 也是 22 = 5 + 6 + 4 + 5 + 2

發佈留言