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

18. Which of the following statements are true? (A) The search operation in a binary search tree of size n is O(logn). (B) The height of a binary search tree of size n is Ω(logn). (C) The search operation in an AVL tree of size n is O(logn). (D) The height of an AVL tree of size n is O(logn). (E) The delete operation in an AVL tree of size n is O(logn).

19. Consider the AVL tree in Fig.1.
(A) In Fig. I, after inserting the key 66, then the parent of key 66 is key 61. (B) In Fig. I, after inserting the key 99, then the key 95 has two children. (C) In Fig. I, after inserting the key 30, then the parent of key 30 is key 35. (D) In Fig.I, after deleting the key 75, then the key 87 has two children. (E) In Fig.1, after deleting the key 1, then the parent of key 23 is key 13.

21. Consider the red-black trec in Fig.2
  (A)In Fig.2, after top-down inserting the key 86, then the color of key 86 is red. (B) In Fig.2, after top-down inserting the key 9, then the parent of key 9 is key 13. (C) In Fig.2, after top-down deleting the key 87, then the color of key 85 is red. (D) In Fig.2, after top-down deleting the key 10, then the parent of key 13 is key 15. E) The 2-3-4 tree representation of Fig.2 has height 2.

22. Consider the AA tree in Fig.3
(A) Key 4 and key 63 have the same level. (B) Key 62 and key 69 have the same level. (C) In Fig.3, after inserting the key 1, the key 4 is in the same level of key 42. (D)In Fig.3, after inserting the key 61, the parent of key 61 is key 62. (E) In Fig.3, after inserting the key 88, the parent of key 86 is key 77.

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ⁿ).