15. Feature A: The worst-case running time is O(n log n)； Feature B: No additional memory is required. Which of the following sorting methods has both features A and B?
(A) heapsort；
(B) quicksort；
(C)insertionsort；
(D) mergesort.

Note: There are 20 questions in total. Each one is 5 points. Please choose one answer for each question. No extra points will be deducted for wrong answers. 1. Suppose a node in a linked list A contains two fields, data and link, where link is the pointer to the following node. Let head-ptr be a pointer to the first node of A. Suppose we would like to traverse all the nodes of A by the loop "while (Ihead.ptr){B；}". What is B?(A) head. ptr == NULL； (B) head-pr = x(head-ptr) → link； (C) head-ptr = head-ptr -＞ link； (D) thead ptr = x(head_ptr) → link.

2. Suppose we have a tree where the left subtree of its root contains 2500 nodes and the right subtree contains 200 nodes. How many nodes are processed before the root node for the post-order traversal? (A) cannot be determined；(B) 2500； (C)200；(D) 2700.

3. For any general tree, which of the following statements is false? (A) Pre-order traversal makes sense；(B) Post-order traversal makes sense； (C)In-order traversal makes sense；(D) No traversals make sense.

4. Suppose a binary scarch tree is built with the following words (inserted in this order): blue- berry, peach, orange, banana, pear, cherry, mango. How many comparisons are needed to search for the word mango? (A) 5；(B) 4； (C)3；(D) 2.

5. What is the prefix expression of (((3 + 7) x (3/5) - (4 x 2)? Note that each operand is a one-digit number. (A) -x +/ x 373542；(B) - x +37/35 x 42； (C)373542 x / +.x-；(D) - x / + 3735 x 42.

6. What is the value of the postix expression 293/ x 4 -9+? Note that each operand is a one-digit number. (A) 11;(B) 13; (C)15;(D) 17.

7. Consider a complete binary tree with exactly 10000 nodes, implemented with an array. Sup- pose that a node has its value stored at index 4999 in the array. What index is the value stored at for this node's parent? (A) 1499；(B) 1450； (C)2499；(D) 2450.

8. Consider a complete binary tree with exactly 10000 nodes, implemented with an array. Sup- pose that a node has its value stored at index 4999 in the array. What index is the value stored at for this node's right child? (A) 9998(B) 9999； (C)10000；(D) The node has no right child.

9. Consider the tree in Figure 1(a). What is the order of the nodes processed in the in-order traversal? (A) D-F-B-E-G-A-C；(B) D-B-F-E-G-A-C； (C)D-B-F-G-E-A-C；(D) D-B-F-E-A G-C .

10. Consider the tree in Figure 1(a). What is the order of the nodes processed in the pre-order traversal? (A) A-B-E-D-F-G-C；(B) A-B-F-E-D-G-C； (C)A-B-D-G-F-E-C；(D) A-B-D-B-F- G-C.

110年 - 110 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#104251

109年 - 109 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#106105

107年 - 107 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#110049

106年 - 106 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#110221

102年 - 102 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#110205