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

科目：研究所、轉學考(插大)◆資料結構與演算法 | 年份：110年 | 選擇題數：10 | 申論題數：5

試卷資訊

所屬科目：研究所、轉學考(插大)◆資料結構與演算法

選擇題 (10)

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 >=61e8d55a1917e.jpg, where Fittl is the Fibonacci numbet, i e.，61e8d5a278fdd.jpg(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. 61e8d6262077a.jpg(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) 61e8d65330684.jpg (D)When input data is 5, the output of function F3 is 5, ie, F3(S) -5.61e8d69936ba6.jpg
複選題
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
複選題
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. 
複選題

9. The pseudo code below aims to reverse a linked list.61e8d6e7bb457.jpg61e8d7107d0d6.jpg  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?
61e8d74dac90b.jpg (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.

申論題 (5)

(A) (15%) Assume that 61e8d8728bbea.jpgBy the assumptions and above definition and theorem, prove that D is NP-complete.
(B) (5%) By the above definitions and theorem, show the following statement is true or false. You should also show your reasons. If the reasons are incorrect, then you get no point. Statement: An NPC problem can polynomially reduce to any NPC problem.
(C) (5%) By the above definitions and theorem, show the following staten ement is true or false. You should also show your reasons. If the reasons are incorrect, then you get no point. Statement: If an NPC problem can be solved in polynomial time by a deterministic algorithm, then all NP problems can also be solved in polynomial time by a deterministic algorithm.
(A)(12%) For a weighted graph G-(V, E) and two vertices x, y in Y, give an efficient algorithn to find a shortest path from x to y. Analyses the time complexity of the algorithm.

(B) (13%) Now you a are given a a weighted graph G-(V, E), a specified vertex s in V, an array d ] of size V, and it is claimed that for each v in Y, dty is the length of the shortest path from s to v. The claim may be correct or may be not. Design a linear time algorithm to check whether the claim is correct. Analyses the time complexity of your algorithm and make sure it is linear, that is, the running time of your algorithm must be O(|V|+|E|).