複選題
8. Let T(n) denote the time taken to sort a list of n records. Which of the following statements are false for QuickSort?
(A) T(n) = 2T(n/2) + cn for some constant c in the worst-case scenario.
(B) T(n) = 4T(n/4) + cn for some constant c in the worst-case scenario.
(C) T(n) = T(n-1) + cn for some constant c in the worst-case scenario.
(D) T(n) = 2T(n-2) + cn for some constant c in the best-case scenario. 

1. Which of the following statements are true? (A) When converting the infix expression a*(bte/d)*(e-l)+g to its postfix form, there are at most 4 tokens in the stack at any moment. (B) The postfix form of infix expression (a+b-c)*(d-e) is abc-+de-* (C) The infix expression of postfix expression 3k-2m4+*+pab-*/ is((3-k)+2(m+4)/(p*(a-b)) (D) When converting the infix expression a*(b+c/d)*(c-) to its postfix form, there are at most 3 tokens in the stack at any moment.

2. Which of the following statemnents about n-element AVL trees are false? (A) The time complexity of deleting element with key k is O(1). (B) The time complexity of insertion is O(log n). (C) If the AVL tree has height = h, then n >=, where Fittl is the Fibonacci numbet, i e.，(D)hL - bR should be O, where hi, and hr denote the height of the left subtree and the right subtree, respectively.

複選題3. Consider a weight-biased leftist tree (WBLT). Let w(x) be the number of internal nodes in the subtrec with root x. Which of the following statemnents are false?(A) The length of the rightmost path from intemal node x to an extemal node must be no greater than log2(w(x)+1). (B) The height of the subtree with root x must be no greater than 1og2(w(x)+1). (C) Combining two weight-based lettist trees with a total of n elements is done in time O(log n). (D)A max WBLT is a max tree that for every interal node y, w(LefiChild(y) is greater than or equal to w(RightChild(y)).

複選題4. Which of the following statements are true? (A) In general, a recursive version is less efficient in terms of time and space than a non-recursive version. (B) The function F1 below is executable (i.e., terminable) for all positive integer x. (C) When input data are 21 and 12, the output of function F2 is 4, i.e., F2(21, 12)-4. Int F2(int x, int y) (D)When input data is 5, the output of function F3 is 5, ie, F3(S) -5.

複選題5. In a 2-dimension integer array arr[5][5], which of the followings are equal to arr[3][2]? (A)*(*arr+17) (B) (*(arr+3)[2](C) *((*(arr+3))+2)(D) (*arr+3)[2] retum ptq;

複選題6. Given PUSH sequence and POP sequence. Which of the following statements are false? (A) PUSH 1 2 3 4; POP 1 2 3 4; It must be a Queue (B) PUSH 1 2 3 4; POP 2 1 3 4; It must be a Stack (C) PUSH 1 2; POP 1 2; It could be a Stack (D) PUSH 1 2 3 4; POP 2 3 1 4, It is neither Stack nor Queue

複選題7. Insert the set (23, 12, 34, 46, 28, 11, 6, 7, 0, 33, 30, 45) into an empty hash Table T of size 17. Suppose that the hash function h(k, i) = (k + i) mod 17, where i = 0 to 16. If we remove 46 after inserting the set, which keys should modify their positions? (A) 11 (B) 0 (C) 33 (D) 45 (E) 30

複選題9. The pseudo code below aims to reverse a linked list.  Which of the following statements are true? (A) Blank (1) should be C != NULL. (B) Statement C->next = P; reverses node's pointer. (C) Blank (2) should be*Href= C; (D) Statement P = C; moves the pointer to the next.

複選題10. The adjacency list below is for an AOE network. The end field points to a list of adjacent vertices, dur field is the duration of the activity, link field points to another adjacent vertex, vertex field is the id of the adjacent vertex, count filed is the number of immediate predecessors. Which of the following statements are true? (A) The total duration of the critical path is 18. (B) Path 0, 1, 4, 6, 8 is not a critical path. (C) Path 0, 2, 4, 7, 8 is a critical path. (D) The latest time that event 4 (i.e., vertex 4) can occur is 8.

40. Determine the expected search cost of an optimal binary search tree for a set of n = 5 keys with the following probabilities. We assume that all searches are successful. (A) 2.15 (B)1.15 (C)2.10 (D) 1.10 (E) 2.0

110年 - 110 國立臺灣大學_碩士班招生考試_電信工程研究所丙組:資料結構與演算法(B)#113108

110年 - 110 國立中央大學_碩士班招生考試_資工類：資料結構與演算法#105890

109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850

104年 - 104 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113199