课程名称︰ 资料结构 课程性质︰ 必修 课程教师︰ 陈郁方 开课学院 ：管理学院 开课系所︰ 资管系 考试日期（年月日）︰ 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