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

Please choose the best possible answer in each of the following questions. In questions that ask for time complexities, please choose the tightest bound.
1. Consider the following five recursive functions: (A)(B) (C)(D)(E) Which recursion yields the highest asymptotic complexity for T(n)?

2. For an AVL tree with 2021 nodes, let x be the minimum possible height, y be the maximum height, then (y-x) mod 5 is (A)0 (B) 1 (C)2 (D)3 (E) 4

3.For a 2-3-4 tree of height 5, let x be the minimum possible size, y be the maximum possible size, then (xy) mod 5 is (A)0 (B)1 (C)2 (D)3 (E) 4

4. For a binary heap of height 2021, let x be the minimun m possible size, y be the maximum possible size, then (3x+y) mod 5 is (A)0 (B)1 (C)2 (D)3 (E) 4

5. Consider a binary heap that results from suc successively inserting keys 6, 3, 7, 8, 5, 1,2, 4, 9 into an initially empty heap. Then the depth of key 5 is (A)0 (B) 1 (C)2 (D)3 (E) None of above

6. A binomial heap contains 2021 items. . How many among them have depth 7? (A)165 (B) 170 (C) 175 (D) 180 (E) 185 .

7. If Dijkstra algorithm is implemented with Binomial heap as priority qucue, then the complexity is mplexity is (A)O(IVI²+E log IVI) (B)O(IVI²) (C)O(IEl log IVI) (D)O(|E|+|V| log|V|) (E) O(|E|)

8. If Djjkstra algorithm is implem ented with Fibonacci heap as priority queue, then the con (A)O(IV|²+|E|log|V|)(B)O(|V|²) (C)O(|E|log|V|) (D)O(|E|+|VILog|VI) (E)O(|E|)

9. If Dijkstra algorithm is implemented with binary heap as priority queue, then the complexity is (A)O(|V|²+|E|log|V|) (B)O(|V|²) (C)O(|E| log |V|) (D)O(|E|+|V|Iog|V|) (E)O(|E|)

10. If Dijkstra algorithm is implemented with doubly-linked list as priority qucue, then the complexity is (A)O(|V|²+|E|log|V|)(B)O(|V|²) (C) O|E| log|V|)(D)O(|E|+|V|(log|V|) (E) O(|E|)

複選題

二、複選題:
11. Which of the following statements are true? (A) (B) (C)log(n!)= 0(nlogn) (D)log" n = 0(log" logn) (E)

複選題

12. Suppose f(n) is a positive function, which of the following statements are true? (A) (B)(C) (D)(E)

複選題
13. Which of the following stater (A) All binary heaps are leftist heaps. ements are true? (B) All leftist heaps are of height O(logn). (C) The InsertO operation in a leftist heap takes O(logn) time. (D) The DeleteO operation in a leftist heap takes O(logn) time. (E) The Merge0 operation between lefist heaps takes O(logn) time.

複選題
14. Which of the following statements are true? (A)Stack implements a FIFO (first-in-first-out) policy. (B) Queue implements a LIFO (last-in-first-out) policy. (C) Stack can be realized by deque (double-ended queue). (D) The FindO operation in a doubly linked list takes O(n) time. (E) The Enqueue0 operation in a queue takes O(1) time.

複選題
15. Consider a binary search tree that results from successively inserting keys 2,8, 9, 1, 5, 7, 6, 3, 4 into an initially empty tree. Which of the following statements are true? (A) The tree height is 4. (B) Key 8 is prior to key 3 in terms of pre-order traversal. (C) Key 2 is prior to key 7 in terms of post-order traversal. (D) Key 4 is prior to key 5 in terms of in-order traversal. (E) Key 3 and key 9 are siblings.

複選題
16. Which of the following are balanced search trees? (A) Binary search tree (B) Red-black tree (C) AVL tree (D)2-3-4 tree (E) Splay tree

複選題

17. Which of the following statements are true? (A) An insertion in AVL tree requires Ω(logn) single- and double-rotations in the worst case. (B) An insertion in AVL tree requires O(1) single- and double-rotations in the worst case. (C) A deletion in AVL tree requires Ω(logn) single- and double-rotations in the worst case. (D) A deletion in AVL tree requires O(1) single- and double-rotations in the worst case. (E) There is no red left child in AA tree.

複選題
18. Consider an AVL tree that results from successively inserting keys 2, 4, 5, 3, 8, 7, 1, 6, 9 into an initially empty tree. Which of the following statements are true? (A) The tree height is 4. (B) Key 3 and key 5 have the same depth. (C) Key 2 and key 8 have the same height. (D) Key 6 is a icaf. (E) Key 7 is the parent of key 9.

複選題
19. Consider the splay tree in Figure 1. Which of the following statements are true?
(Assume bottom-up splay, also assume the Join0 operation splays on the maxim mum element in the left tree, which then attaches the right tree.)

(A)In Figure 1, after deleting key 26, then key 33 is a child of key 48. (B) In Figure 1, after deleting key 26, then key 17 is the root. (C) In Figure 1, after inserting key 75, then key 64 is an ancestor of key 99. (D)In Figure 1, after inserting key 75, then key 33 is a descendant of key 5S. (E) In Figure 1, after inserting key 75, then key 75 is the root.

複選題
20. Consider the red-black tree in Figure 2, which of the following statements are true? (Assume bottom-up insertion/deletion) (A) In Figure 2, after inserting key 14, then there are 6 red nodes. (B) In Figure 2, after inserting key 54, then key 49 and key 54 are siblings. (C) In Figure 2, after deleting key 22, then key 25 and key 73 are siblings. (D) In Figure 2, after deleting key 66, then key 35 is red. (F) In Fignre 2, after deleting key 83, then key 89 is red.

複選題
21. Consider an AA tree that results from successively inserting keys 96, 49, 79, 14, 41, 87, 75, 90 61 into an initially empty tree. Which of the following statements are true? (A) The root is key 61. (B) There is less than 3 horizontal links. (C) Key 41 and key 49 are in the same level. (D) Key 87 and key 96 are siblings. (E) Key 14 is the parent of key 41.

複選題
22. Consider a min-heap. Which of the following statements are true? (A) For any subtree of a min-heap, the root ol the subtree contains the smallest key occurring anywhere in that subtree. (B) An array that is in ascending order is a binary min-heap. (C) The sequence [1,5,6,7.14, 17,10,23, 13,12] is a binary min-heap. (D) The largest key muust in a leaf (E) The smallest key must reside in a leaf I reside in

複選題
23. Consider a Fibonacci heap that results from successively inserting 929 (distinct) keys into an initially empty heap, followed by deleting the minimum key. Which of the following statements are true?(A) The Fibonacci heap is of degree 9.(B) The Fibonacci heap is of height 12.(C) There are 5 trees in the Fibonacci heap.(D) With one additional decrease key operation, the Fibonacci heap can have 6 trees.(E) With two additional decrease key operations, the Fibonacci heap can have 7 trees.

複選題

24. Which of the following are desirable properties of a hash function h(x)? (A) If x₁ ,.., x_n are the items to be hashed, then the numbers h(x₁),.... h(x_n) should be uniformly distributed over the integers. (B) The range of h(x) should include a wide range of integers. (C) The range of h(x) should stay within the desired hash-table size. (D) It should be computable in O(1) time. (E) It should take distinct values over all possible items to be hashed.

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

試卷資訊

選擇題 (24)

申論題 (0)