课程名称︰资料结构与演算法 课程性质︰系必修 课程教师︰蔡欣穆 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2012/06/19 考试时限（分钟）：180 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Data Structure and Algorithm, Spring 2012 Final Examination 124 points Problem 1. In each of the following question, please specify if the statement is true or false. If the statement is true explain why it is true. If the statement is true, explain why it is true. If it is false, explain what the correct answer is and why. (24 points, 1 point for true/false and 3 points for the explanation for each question) 1. In a strongly-connected component of a graph, there is at least one articulation point. 2. After performing a depth-first search(DFS) in an undirected graph, there is no cross edge in the generated depth-first forest. 3.If the costs of all edges in a graph are distinct and the graph is connected, then the minimum spanning tree of this graph is unique. 4. When sorting on multiple keys, least-significant-key-first sorting is easier to implement then most-significant-ket-first sorting. 5. When the load factor is high(close to 1), the performance of a hash table is much worse when using chaining than when using open addressing. 6. When using the directory-less dynamic hash table as shown in the lecture, the overflow problem caused by an insertion is always resolved after expanding the hash table. Problem 2. "Short answer" questions: (32 points) 1. Describe the worst-case for the heap sort algorithm. When dose it happen and what is the worst case running time? (4 points) 2. Please explain why when a new element is added to a red-black tree it is initially set to have red color. (4 points) 3. Please calculate the value of the prefix function pi[i], 1<=i<=18 for the pattern string "abacabadabacabacaa" and fill out Table 3. Please use the definition of the prefix function from the lecture(not the homework). In other words, the minimal output value is 0, not -1. (6 points. Each incorrecet entry deduct 2 points. More the 2 incorrect entries result in 0 point) 4. Continuing with the previous question. Please specify which characters(and their indices) in the pattern string did you compare to when you calculate the prefix function for the following input: "d" at index 8 and "c" at index 16 using the KMP algorithm. (4 points) 5. What is a stable sorting algorithm? What is an adaptive sorting algorithm? Please explain (4 points) 6. Describe the reason that in the implementation of quick sort sometimes we prefer to choose the pivot randomly instead of always choosing the left most or the right most elements in the array as the pivot (4 points) 7. Fill out the blank in following C code segment so that the function performs counting sort: (6 points) void CountingSort(int A[], int n, int B[], int k) { //A contains the input array with length n //B contains the sorted array (to be output)_ int C[K], i, j; for (i=0;i<K;++i) C[i]=0; for (j=0;j<n;++j) C[A[j]]=C[A[j]]+1; for (i=1;i<K;++i) C[i]=C[i]+C[j-1]; /* Fill out the blank here!! */ } Problem 3. Please answer the following questions about graph. (12 points) 1. Please use the Bellman-Ford algorithm to determine the costs of the shortest paths (the number next to the edges in the graph are the costs for traveling through them) from vertex 1 to all other vertices in the graph in Figure 1. Use Table 1 to show how the algorithm is executed in each iteration. (6 points) 2. Please use the Dijkstra's algorithm to determine the costs of the shortest paths (the number next to the edges in the graph are the costs for traveling through them) from vertex 1 to all other vertices in the graph in Figure 1. Use Table 2 to show how the algorithm is executed in each iteration. (6 points) Problem 4. A depth-first forest classifies the edges of a graph into tree, back forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories. Prove that in a breadth-first search(BFS) of an undirected graph, the following properties hold. (recall that v.d of the vertex v stores the distance from the source s to vertex v calculated by the BFS algorithm) (12 points) 1. There are no back edges and no forward edges. (6 points) 2. For each cross edge (u,v), we have v.d=u.d or v.d=u.d+1 (or v.d=u.d-1 since u and v can be exchanged). (6 points) Problem 5. Hashing: (18 points) Suppose we will build a hash table using open addressing with quadratic probing. The hash function is h(k,i) = (h'(k) + c1 i + c2 i^2) mod m. And the auxiliary hash function is h'(k) = k mod m. 1. Suppose we select m=7, c1=0.5, c2=0.5. Show the content of the hash table after inserting all of the following keys into the initially empty hash table in the given order: {57,38,52,16,73,8}. (4 points) 2. Explain why when using quadratic probing, we have a milder form of clustering called secondary clustering, as opposed to primary clustering, which occurs when using linear probing. (3 points) 3. How do we make sure when an item is deleted from the hash table, we can still find other item? For example, if 57 is deleted in 1., can we still find 8? (3 points) 4. Based on your answer to the previous question and using open addressing with quadratic probing, complete the C function below so that it can correctly find the item to be searched. (4 points) int search(int key, int H[], int m, int c1, int c2) { //key is the key of the item to be searched //H[] is the hash table //m, c1, c2, are the parameters used in the hash function int index=key % m; while( /* fill in the blank here */) { /* fill in the blank here */ } return index; //if the item is not found, you should set the index to be -1 } Problem 6. Multi-pattern string matching problem: (16 points) In the worst case, Rabin-Karp algorithm still has a matching time of O((n-m+1)m) = O(nm), although on average the matching time is only O(n+m), where n is the length of the string and m is the length of the pattern. Therefore, for the regular "single-pattern" string matching problem it is considered inferior to algorithm such as KMP, which has a matching time of only O(n). However, Rabin-Karp has great performance in the "multi-pattern" string matching problem. In this problem, there are k patterns of the same length m, {P1, P2, ..., Pk} and the string T of length n. A shift is valid if we can find at least a pattern Pi such that T[s+1..s+m]==Pi[1..m], 1<=i<=k. To solve the problem, you need to find all valid shifts. The pseudo-code of the original Rabin-Karp algorithm is shown at the end of the problem description. 1. Please show how you would modify the original Rabin-Karp algorithm to solve the multi-pattern string matching problem. Fill in the blank of the Rabin-Karp- Multi-Matcher function. (8 points) 2. Show that your algorithm has a matching time of O(n+km) (to simplify the analysis, as shown in the lecture notes you can assume the number of valid shifts is a constant and the probability for spurious hits is 1/q, where q is the modulus used in the algorithm and is much larger than m). (8 points) Rabin-Karp-Matcher(T, P, d, q) n=T.length m=P.length h=d^(m-1) mod q p=0 t=0 for i=1 to m p=(dp+P[i]) mod q q=(dt+T[i]) mod q for s=0 to n-m if p==t if P[1..m]==T[s+1..s+m] print "Pattern occurs with shift" s if s < n-m t=(d(t-T[s+1]h)+T[s+m+1]) mod q Rabin-Karp-Multi-Matcher(T, P[], k, d, q) /* fill in your code here */ Problem 7. Out of all topics we covered in the lectures this semester, which one do you like the most? Which one do you dislike the most? Why? Please give some constructive suggestions. Any other course-related comments are also welcomed. (I am sorry that I did not find the time to write down my comments to your feedbacks in the midterm. But I did read all of them and take them seriously. Your feedbacks are very important for me to improve the courses, so I hope that most of you can kindly write a few sentences at least. Thanks a lot!) (10 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.98 ※ 编辑: poao 来自: 140.112.30.98 (06/21 19:52)