102年 - 102 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113274

科目：交大◆資工◆資料結構與演算法 | 年份：102年 | 選擇題數：0 | 申論題數：31

試卷資訊

選擇題 (0)

申論題 (31)

1. (5%) In the Knuth-Morris-Pratt string-pattern matching algorithm, we need a failure function. Compute the failure function for the following pattern.

2. (5%) In a binary tree, there may be many null pointers. We may use these pointers to point to in-order predecessors and successors. These pointers are called thread pointers. Draw all the thread pointers in the following binary tree.

3. (5%) Assume there are only variables such as a, b, c, and binary operators, such as t, -, *, and /in an arithmetic expression. The expression is fully parenthesized, that is, there is a pair of parentheses for each operator. Examples are (a+b)-c)/d), ((a+(c-(b-a))/d)+1), (((a+b)+c)+d)+e), etc.

Write a program that translated a fully-parenthesized expression into its prefix form. The input is a correct, fully-parenthesized arithmetic expression, stored in a read-only array. This program can use 3queues together with the usual stack pointers. You cannot use additional storage, such as arrays, except a fixed number of simple temporary variables. In the program, you can only push, pop, examine the contents of a cell, and compare two contents of two cells for equality. The program can scan the input from left to right only once. It cannot store the input expression somewhere else for repeated examinations. You can use C or Java or Pascal or other similar programming languages to write this program. Your program should clearly show the underlying algorithm. Minor details and errors in the program will be tolerated. In particular you need to explain your data structures with examples.

4. (5%) Assume each node contains a data, Ithread, rthread, Icbild, and rchild fields. Ithread and rthread are Boolean fields. Icbild and rchild are pointers. If Ithread is true, the Ichild field will be considered as a left thread； otherwise, Ichild will point to the left child. Similarly for the rthread and rchild fields. Consider the following algorithm for pre-order traversal of a binary tree using thread pointers:

Please fill in the missing line 6 with an assignment statement.

(a)n²ⁿ+5．3²ⁿ=θ(n²ⁿ).

(b) 3n^1.0001+ 99n log n =0(n^1.1).

(c)n log(2n)=O(n ln n).

(d)n²log(5n)=θ(n²).

(e) n^0.999 log n=θ(n²).

(1). If your application requires frequent random access (i.e. retrieving the value for a given key), using the data structure _____ to store the data will give the longest average access time.

(2). Assume there is a total ordering of data, and your application requires frequent range queries to the data (i.e. retrieving data with keys in the range [lower _bound, upper _bound]). Range query to your data can be efficiently implemented with the data structure _____.

(3). If we want to emulate a priority queue, which of the three data structures will be the best choice (i.e. both element addition and extract-max have to be efficient) _____.

(1). After the tree rotations, the parent of node 4 will be node _____

(2). After the tree rotations, the parent of node 7 will be node _____

Let's apply the following additional tree rotations in sequence left_rorate(1)→ right_rorate(4)→ left_rorate(6)→ right_rorate(3).

(3). After the seven tree rotations are applied to T, an in-order traversal of T will output a sequence of the tree nodes as _____

(1). Draw the hash table after the insertions _____

(2). What is the worst-case time complexity for searching in a hash table of size N _____

(3). What is the best-case time complexity for searching in a hash table of size N _____

(1). After the call to xsort returns, the content of the data [ ] array will be _____
(You have to list all 10 elements of the data I ] array sequentially, starting from data [0],data [1],,.,etc.)

(2). How many times will the function part it ion be invoked? _____ times.

(3). The worst-case time complexity of the xsort function for an input array data [ ] with size elements is _____

10. (5%) Figure 7 presents the code for computing the number of connected components in an undirected graph. In the code, the undirected graph is stored in the form of adjacency lists. The graph has N vertices, which correspond to vert ices [N] at Line 25. Each vertex is a tVertex structure as given at Line 9~20. The function ConnectUndirected (v1, v2) is used for creating an undirected edge between vertex v1 and vertex V2. The function NumberOfComponents ( ) at Line 36 will return the number of connected components in the graph.
Please complete the code by filling the blanks in Figure 7. There are a total of three blanks at Line 30,32, and 43 to be filled.
In the following problem 1 1-15, til in the blanks. Please try to keep all t u answers on the same sheet of the answer book. Each problem is worth 5 points. No partial credit will be given for only one correct blank. However you do not have to provide any justification.

11. (5%)Suppose that the amount of flow in the maximum flow from source to sink in the network G=(V,E) is f, and that all capacities are integral. Suppose n = |V| and m = |E|. How long would it take at this maximum flow using the Ford-Fulkerson algorithm?_____. Suppose the minimum s-t cut in the network G has x arcs. Suppose that one adds y units of capacity to each arc of G, creating a transformed network G'. The capacity of the minimum cut of G' is at most _____.

12. The running time of Kruskal's algorithm for a connected undirected weighted graph G=(V,E) is _____. Suppose that all edge weights in a graph G are integers in the range from 1 to |V|. How fast can you make Kruskal's algorithm run?_____

13.(5%) If some of the edge weights in a graph are negative, the shortest path can be obtained using's algorithm by first adding a large constant C to each edge weight, where C is large every resulting edge weight will be nonnegative (True or False). _____The Bellman-Ford algorithm is not suitable if the input graph has negative-weight edges (True or False)._____

14. (5%) Given a graph as below. Show the weight on the edge between Node x and Node y after reweighting using Johnson's algorithm. _____ Show the fifth row of an adjacent matrix (with order of u, v, x, y,z) after using the Floyd-Warshall Shortest Paths algorithm with the intermediate Node u._____

15. (5%) You are the program chair of a conference! Part of your job is to assign papers to 6 papers P1,P2,P3, P4,P5, P6 and 3 reviewers R1, R2, R3. Initially, each reviewer constructs a list of papers he is willing to review as followings: R1 ={P1,P3, P5, P6},R2 ={P1, P2,P4},R3={P1,P2,P3,P4, P5, P6}. An assignment of papers to reviewers is valid if each paper is assigned to at least 2distinct reviewers that are willing to review that paper. The maximum number of papers assigned to anyer should not be greater than 4. You would like to maximize the total number of pap are validly assigned. Please model this problem using a s-t flow network G = (V, E) (Draw a flow network with capacity labeling)._____ What is the maximum number of papers that can be validly assigned?_____

16. (5%) Consider the multiplication of four matrices with dimensions in the following order: 10x11,11x25,25x40,40x2. Find the optimal parenthesization of the above product and the minimum number of scalar multiplications needed.

17. (5%) Consider the problem of finding a vector (X₁, X₂, X₃, X₄, X₅ ) satisfying the following constraints such that X₁ + X₂ + X₃ + X₄ + X₅ is maximized, where x_i - 0 for i=1,...,5. What are the maximum value and the corresponding vector?

18. Consider a set of 6 nodes 1, 2, 3, 4, 5, 6 and their corresponding weights: 2, 3, 4, 4, 5, 6.

(a) (5%) Build a binary tree with these nodes appearing in the leaves such that the maximum of w[il x (1/2)^d[i] is minimized, where w[i] is the weight and d[i] is the depth of node i in the tree. Note that the root has depth 0. What is the optimal value?

(b) (10%) Give a greedy algorithm for N nodes and explain your idea.