Loading [MathJax]/jax/output/CommonHTML/jax.js

考試

104成大資聯程設[參考解答]

一、Data Structures (50%)

1. (20%)

Given a red-black tree in the following figure.

mt01

After one node with value 778 is inserted, the resulting red-black tree is shown as follows.

mt02

(a) Please describe the operation procedures for this insertion.
(b) Please indicate the color and value of node A and node B, respectively.

參考解答:
(a) 略
(b) node A: black, 614. node B: red, 419.


2. (10%) Given the expression, (x+y)*w+u/(v+x*w)+z, Please show the content in the stack after the operand v is read in postfix transformation.

參考解答:

mt03

3. (20%)

(a) Please finish the lost code for the choose function in the following Dijkstra shortest path implementation for a graph without negative-weight edges.

(b) In a directed graph without a cycle of negative length but with a negative-length edge, we can implement Bellman-Ford algorithm as follows to compute shortest paths. Please fill in the lost code.

參考解答:
(a)

for (i = 0; i < n; i++)
{
    if (distance[i] < min && !found[i])
    {
        min = distance[i];
        minpos = i;
    }
}

(b)

for (int i = 0; i < n; i++)
    for (int u = 0; u < n; u++)

二、Algorithms (50%)

1. (10%) Prove or disprove: The single-source shortest paths problem can be solved in linear time in directed acyclic graphs.

參考解答:
(1) 找Topological sort.
(2) 從sort的順序由前到後作Bellman-Ford algorithm的Relax function.


2. (15%) The matrix-chain multiplication problem can be stated as follows: Given a chain (A1,A2,,An) of n matrices, where for i=1,2,,n, matrix Ai has dimension pi1×pi, fully parenthesize the product A1A2An in a way that minimizes the number of scalar multiplications. Suppose that you have 6 matrices: A1 has dimension 30×35,A2 has dimension 35×15,A3 has dimension 15×5,A4 has dimension 5×10,A5 has dimension 10×20,A6 has dimension 20×30. Please calculate the minimum number of scalar multiplications.

參考解答:16375


3. (10%) Give asymptotic upper and lower bounds for T(n)=2T(n4)+n. Assume that T(n) is constant for n2. Make your bounds as tight as possible.

參考解答:Θ(nlgn)


4. (15%) Consider the problem of finding the 5-vector x=(xi) that satisfies

(1100010001010011010010010001100010100011)(x1x2x3x4x5)(01154133)

Determine whether there exists a solution or there is no solution.

參考解答:有負cycle, there is no solution.


試題(pdf):連結

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

發佈留言