課程名稱︰ 資料結構 課程性質︰ 必修 課程教師︰ 陳郁方 開課學院 ：管理學院 開課系所︰ 資管系 考試日期（年月日）︰ 101 / 11 /12 考試時限（分鐘）： 兩節課 是否需發放獎勵金： yes （如未明確表示，則不予發放） 試題 : --- 1. Which of the following statements about recursion are correct (複選)? a. A recursive implementation usually runs faster than an iterative implementation. b. Each recursive program has exactly one base case. c. If each recursive call diminishes the problem size, the program will eventually termininate. d. All recursive programs can be translate to iterative programs doing the same job. 2. What kind of memory problem does the following program fragment have? (a)(四分) | (b)(四分) | (c)(四分) int *a , *b; | int *a , *b; | int *a , *b; a = new int; | b = NULL; | a = new int; a = b; | a = new int; | b = a; delete a; | *a = *b; | delete b; delete b; | | a. Memory leak b. Double delete c. Point to an illegal memory location d. Null pointer dereference 3. Please translate the following infix expression to equivalent postfix expression a. (a+b)-c*a/(b-a) (三分) b. (a*b)/c+a-(b/a) (三分) c. a+b-c/d (三分) 4. Which of the following statements about stack and queue are correct(複選)? a. Array-based implementation of stack pop operation does not need shift data. b. Array-based implenentation of stack push operation does not need shift data. c. Array-based (circular) implementation of queue enqueue operation does not need shift data. d. Array-based (circular) implementation of queue dequeue operation dois not need shift data. 5. The following picture illustrates the current status of memory and pointers a. Please draw a picture of the memory and pointer status after the following code has been execurated (五分) newPtr -> next = cur =>next; prev->next = newPtr; delete curl; b. Please write a program fragment that insert the item pointed by newPtr to the lacation in between the items pointed by prev and cur (五分) [item | → [item |→ [item | → X [item] ↑ ↑ ↑ prev cur newPtr 6. Given the following definition of C++ class stack for a linked-list based implementation , please try to implementation its copy constructor(九分) tyepdef int StackItemType; class Stack { public : Stack(); Stack(const Stack &Q); ~Stack() ... privite: Struct StackNode { StackItemType item; StackNode *next; } StackNode *topPtr; // point to the head of the linked-list }; 7. The following is a biniary tree. a. Is it a balanced tree?(一分) b. Is it a complete tree?(一分) c. Show the string obtained by preorder traversal(兩分) d. Show the string obtained by inorder traversal(兩分) e. Show the string obtained by postorder traversal(兩分) f. what is the level of node G?(一分) g. What are the siblings of node F(兩分) A B C D E F G 8. The folowing is a biniary search tree a. Draw the result after you insert node 9 to the tree(五分) b. Draw the two possible result after you deleted node 20 in the tree (五分) 10 8 20 5 15 22 12 18 9. For implementation of ADT table , which implemontation method we learned in the lecture is the best for the following cases? a. Will frequently do insertion , and occasionally do retrieval and deletion.(三分 b. Do insertion only once at the beginning and frequently do retrieval. Never do deletion.(三分) c. Frequently do all the operations and want to have a good average perpormance(三分) Insert Delete Retrive unsorted array based O(1) O(n) O(n) unsorted pointer based O(1) O(n) O(n) sorted array based O(n) O(n) O(logn) sorted pointer based O(n) O(n) O(n) binary search tree O(logn) O(logn) O(logn) 10. The following is an array representing a heap _________________________ | 10 | 8 | 5 | 3 | 2 | 4| ﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉ a. Show each intermediate steps of inserting node 11 to the heap(五分) b. Shwo each intermediate steps of deleting node 10 from the heap(五分) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.245.226