複選題

25. Let f(n) ~ g(n) denote f(n) (8(n), and f(n) g(n) denote f(n) E D(g(n) but f(n) O(g(n)). Which of the following statements are correct?
(A) [log₂n]! ~ nlogn ＞ logn ~ log_en ＞  
(B)nⁿ ＞ n!~ (logn)ⁿ ＞ 4ⁿ ＞ n³2ⁿ.
(C)n!(logn)ⁿ＞log(n!)~  n logn ＞
(D)If f(n) is O(),then f(n)²is 0(n).
(E) If f(n) is O(n),then is 0(2ⁿ).

1. Consider a hash table with 13 slots. Suppose we use linear probing as the collision resolution strategy, where the i'th probe position (wherc i = 0, 1, 2, ..) for a key k is given by the function h(k,i) = (k+i) (mod 13) Suppose we insert the following 9 keys into the hash table in the exact sequence: 66, 4, 84, 91, 100, 72, 70, 37, 61. What is the index of the slot storing the key 61? (A)2 (B)8 (C)9 (D)10 (E) None of above

2. The worst case time complexity of constructing a binary heap from an unordered array of n items (A)O(n) (B)O(n log*n) (C)O(n logn) (D)O(n2) (E)O(n2 log n)

3. In a binary heap of size n, the worst case time complexity of one delete-min operation is (E) O(n log n) (A)O(1) (B)O(log*n) (C)O(log n) (D)O(n)

4.The worst casc time complexity of one union operation upon two binary heaps of total size n is (B)O(log*n) (A)O(1) (C)O(logn) (D)O(n) (E)O(n log n)

5. In a binomial heap of size n, the worst case time complexity of n consec ive insert operations is (A)O(n) (B)O(n log*n) (C)O(n logn) (D)O(n2) (E)O(n2 log n)

6.In a binomial heap of size n, the worst case time complexity of one insert operation is (A)O(1) (B)O(log*n) (C)O(logn) (D)O(n) (E) O(n log n)

7. In a binomial heap of size n, the worst case time complexity of one find-min operation is (A)O(1) (B)O(log*n) (C)O(log n) (D)O(n) (E) O(n log n)

8. In a Fibonac cci heap of size n, the worst case time complexity of one insert operations is (A)O(1) (B)O(log*n) (C)O(log n) (D)O(n) (E)O(n log n)

9. In a Fibon nacci heap of size n, the worst case time complexity of one decr (C)O(log n) e-key operations is (A)O(1) (B)O(log*n) (D)O(n) (E) O(n log n)

10. In a Fibonacci heap of size n, the worst case time complexity of n delete-min operations is (A)O(n) (B)O(n log*n) (C)O(n logn) (D)O(n2) (E)O(n2 10g n)

110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:資料結構(B)#102892

109年 - 109 國立臺灣大學_碩士班招生考試_電機工程研究所丙組:資料結構(B)#105932