[試題] 100下 蔡欣穆 資料結構與演算法 期末考
課程名稱︰資料結構與演算法
課程性質︰系必修
課程教師︰蔡欣穆
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰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)
推
06/21 20:13, , 1F
06/21 20:13, 1F
推
06/21 20:54, , 2F
06/21 20:54, 2F
推
06/21 23:05, , 3F
06/21 23:05, 3F
推
06/21 23:21, , 4F
06/21 23:21, 4F