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

科目：中山◆電機◆資料結構 | 年份：107年 | 選擇題數：20 | 申論題數：0

試卷資訊

所屬科目：中山◆電機◆資料結構

選擇題 (20)

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.

11. Start with an empty max-hcap of integers, and enter the ten numbers 1 through 10. Let the max-heap be stored in an array. What index is 8 stored at in the array? (A) 2；(B) 3； (C)4；(D)5.

12. Start with an empty max-heap of integers, and enter the ten numbers 1 through 10. Let the max-heap be stored in an array. Remove one entry from the heap. What index is 3 stored at in the array? (A) 5；(B) 4； (C)3；(D) 2.

13. Suppose you are given an array containing six integers 5, 36, 4, 20, 19, and 9 initially. Starting with 5, use insertionsort to sort the array in increasing order. What is the content of the array after 4 is processed? (A) 4, 5, 20, 36, 19, 9；(B) 5, 36, 4, 9, 19, 20； (C)4, 5, 19, 36, 20,9；(D)4, 5, 36, 20, 19,9.

14. Suppose you are given an array containing six integers 1, 2, 3, 4, 5, and 6 initially. You want to sort the array in increasing order. Which sorting method is the most efficient to use? (A) selectionsort；(B) insertionsort； (C)mergesort；(D) quicksort.

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.

16. Consider the graph in Figure 1(b). Starting with node S, what is the order of the nodes processed by the depth-first search? If two or more nodes can be chosen, choose the node with the smallest label first. (A) S-C-A-P-B-M-H-D-R；(B) S-M-H-C-A-P-B-D-R； (C)S-C- A-M-H-P-B-D-R；(D) S-C-R-A-M-H-P-B-D.

17. Consider the graph in Figure 1(b). Starting with node S, what is the order of the nodes processed by the breadth-first search? If two or more nodes can be chosen, choose the node with the smallest label first. (A) S-C-A-M-R-H-P-B-D；(B) S-C-M-A-H-B-P-R-D； (C) S-C-M-A-R-P-B-H-D；(D) S-C-M-A-R-H-P-B-D.

18. Suppose you are doing a breadth-first search of a graph with n nodes. How large can the queue get during the search? (A) n；(B) n - 1； (C)n - 2；(D) 1.

19. An empty hash table has a capacity of 13, and you insert six entries with keys 20, 15, 7, 9, 21, 33, and 48. Using linear probing and the hash function x%(13), what index 21 is stored at in the table? Note that % is the remainder operator, e.g., (100)%(13)=9. (A) 7；(B) 8； (C) 9；(D) 10.

20. An empty hash table has a capacity of 13, and you insert six entries with keys 20, 15, 7, 9, 21, 33, and 48. Using linear probing and the hash function x%(13), what index 48 is stored at in the table? Note that % is the remainder operator, e.g., (100)%(13)=9.
(A) 10；(B) 11； (C) 12；(D) 9.

申論題 (0)