一、Data Structures (50%)
1. (20%)
Given a red-black tree in the following figure.
After one node with value 778 is inserted, the resulting red-black tree is shown as follows.
(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.
參考解答:
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 pi−1×pi, fully parenthesize the product A1A2…An 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 n≤2. Make your bounds as tight as possible.
參考解答:Θ(√nlgn)
4. (15%) Consider the problem of finding the 5-vector x=(xi) that satisfies
(1−10001000−10100−1−10100−1001000−11000−101000−11)(x1x2x3x4x5)≤(0−115−4−1−3−3)
Determine whether there exists a solution or there is no solution.
參考解答:有負cycle, there is no solution.
試題(pdf):連結
有任何問題,或想要完整解釋的,歡迎在下方留言唷!
發佈留言