109年 - 109國立臺灣大學_碩士班招生考試_資訊工程學研究所:資料結構與演算法(A)#106053

Please select all the correct answer(s) to question 1 to 10. Note that there could be O to 5 correct answ wers. If non answer is correct, answer "none". If you do not wish to answer a question, leave it blank. All 10 answer rs m must be written on the first page of your answer book, and the answer to question 1 must be in the first line, the answer to question 2 must be in the second line, and so on. If you fail to follow these rules then your answers will be ignored. ne of the a
1. (3 points) Let f(n) be the number of additions in the following algorithm.  1.f(n)=
2. f(n)=O(n²logn)
 3. f(n)=O(n³)
4. f(n)=O(n³logn)
 5. f(n)=

2. (3 points) Given two sorted list A and B (in increasing key order), the following recursive algorithn merges A and B into a sorted list C (also in increasing key order).
 ㆍ If either A or B is empty then the result is the other list.
ㆍ If both A or B are not empty, we compare the keys of the first nodes of A and B, and select the smaller one (denoted as s), and remove it from the list. Then we recursively merge the remaining parts of A and B into a new sorted list C', then we concatenate s with C' into the iral sorted list
 Let f(n, m) be the minimum number of comparisons of this algorithm, where n and m are the numbers of nodes in A and B respectively. f(n,m) is?
1.Ω(n)
2. Ω(m)
 3. Ω(n +m)
4. Ω(mn)
5.Ω(mar.(logm +logn))

3. (3 points) We now use the merge algorithm in the previous question to sort a set of keys. We irst make each key a list of a single node. Then we merge the first and the second lists into a sorted list of length two, the third and the fourth lists into a sorted list of length two, and so on. If we start with n keys now we have roughly n/2 sorted list of length two now. We then merge these lists of length two into roughly n/4 sorted list of length four, and so on. Finally we will have a sorted list of length n. Let f(n) denote the mazimum possible total number of comparisons of this algorithm, then f(n) is? Note that all the answers are in little-o notation. 1.o(n)
2.
 3.o(nlogn)
 4.o(n(logr)²) 5.o(n²)

4. (3 points) A binary minimun heap is a binary tree in which every level is completely full, except the last level, which is filled from the left to right. Here the level of a node is its distance to the root, so the root has leve! O and the children of the root will have level 1, and so on. Also the key of a parent is less than those of its children. For ease of discussion we assume that all keys in the heap are distinct. Now which of the following descriptions about a binary minimum heap of 10 nodes (see the igure below) are correct?
1. The second smallest key is always in level 1.
2. The largest key is always in a leaf, ie., a node without any children.
3. The second largest key is always in a leaf.
 4. Let n be the number of nodes and we consider the case of arbitrary n, then the height of the tree is θ(logn).
5. Let n be the number of nodes and we consider the case of arbitrary n, then we can find the thind stnallest key of the beap by O(1) key comparisons.

6. (3 points) A randomized quick sort works as follows. For ease of discussion we assur me that the sequence we want to sort, K = (k₁,... .,k_n), is a pernutution of 1 to n. We randomly and uniformly pick a key & from K. Then we partition K into two subsets - Ki that has keys less than k and K₁ that has keys greater than k. Then we recursively sort K₁and K₂, and combine the results with k to get the sorted sequence.
 1. The number of key comparisons will always be max aunized when the keys in K are already sorted.
 2. Let |K₁| and|K₂|be the number of keys in K₁ and K₂ respectively. The expected value of max(|K₁|,|K₂|) is n.
3. The algorithm will compare two keys &: and ky at most ouce, so the numnber of key comparisons is O(n²). 4. The probability that the algorithm will compare ky and ly (n2i＞ jZ 1) is 
5. Let P= {(i,j)|1≤i，,j ≤ni≠j}. The expected total number of key comparisons is

8. (3 points) A randomized linked list sorting algorithm works as follows. We want to build a linked list
in which the keys are in increasing order. That is, every node has a smaller key than its successor in
the list. For ease of discussion we assume that the keys are distinct in integers from 1 to n. The algorithn
randomly picks a key from the rem maining keys, and inserts it into the list. This pro
keys are inserted. The inserted key k will skip those at the beginning of the list that are smaller than
ocess repeats until all
it, and will stop at the first key p that are greater than it. We then insert the key k  before p. To ensure
that all keys will stop we assumne that initially the list has only one key, n + 1. After we insert all keys
we will have a sorted linked list from 1 to n + 1.
1. Every inserted key will stop exactly once.
 2. The smallest key 1 will not skip any keys.
3. The largest key n will always skip n–1 keys.
 4. The expected number of keys that the key i will skip is Ω(i).

(b) (6 points) Consider the special case that the distance difference between two cousecutive stations is I, ie,-li= 1 (1 ≤i ≤n -1). Give an O(n) solution by defining a recurrence formula for f(n). Clearly explain the meaning of your formula and why it can be computed in O(n) time.

(a) (9 points) Given an undirected graph G = (V,E), where V = {u₁,...u_m} (m ＞ 0) and E = {e₁,...，en) (n ＞ 0), devise an algorithm to check if the graph G is a tree or not by using UNION(ui,uj) with union-by-height and FIND(uk) with no path com pression, where Ui,Us and U_k V. Clearly describe your solution and analyze the tinre cumplexity of your algorithm in the worst case. No code is required (code will not be graded).