這份試題是筆試部分的，上機部分之前已經有PO過了喔~ 課程名稱︰資料結構與演算法 課程性質︰資工系大一必修 課程教師︰張智星 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰2016/04/24 考試時限（分鐘）：80mins，14:00~15:20，不加時 試題 : 1. (5 pts) Steps in selection sort: Please show each step of selection sort on the vector [3 5 1 4 2 7 9 6 8]. 2. (4 pts) Shallow copy: A program is used to record each student's quiz scores. a. Class definition: class student { public: student(int n){count=n; score=new int[count];}; ~student(){delete [] score;}; void print(); // Print score int *score, count; string name; }; b. Main program: int main(){ student a(3); a.name="John"; a.score[0]=70; a.score[1]=80; student b=a; b.name="Mary"; b.score[2]=90; } Answer the following sub- questions: a. What are the contents of variables a and b? b. What are the two potential problems of this program? 3. (3 pts) STL vectors: Given an STL vector x, answer the following sub-questions. a. What does "x.reserve(25)" mean? b. What is the difference between x[i] and x.at(i)? c. What is the difference between x.size() and x.capacity()? 4. (2 pts) Efficiency of 2D matrix computation: Given the following code snippet: #define N (100) #define M (200) int twodim[N][M]; int get( int arr [][M] , int n, int m) { return arr [n][m];} Why do you need to give M when calling the function get()? 5. (4 pts) Efficiency of 2D matrix computation: Given the following code snippet: #define M 10000 #define N 20000 int array[M][N]; int rowSum(){ int total=0; for (int i=0; i<M; i++) for (int j=0; j<N; j++) total+=array[i][j]; return total; } int colSum(){ int total=0; for (int j=0; j<N; j++) for (int i=0; i<M; i++) total+=array[i][j]; return total; } a. Which function runs faster? b. Why? 6. (8 pts) Search minimum element in a sorted rotated array: Design a O(log n) algorithm which finds the minimum element in a sorted rotated array. If an array is rotated once, then a[0] is moved to a[1], a[1] is moved to a[2], etc., and a[end] is moved to a[0]. This is repeated for k times if the array is rotatd by k positions. For instance, given a sorted array of [1 2 4 5 7 9], we can rotate it 4 times to have [4 5 7 9 1 2]. 7. (4 pts) Infix vs. postfix: What are the major two advantages of postfix notation over infix notaton? 8. (5 pts) About BT: Given a binary tree with the root located at depth 0, and the height of the tree is defined as the maximum depth. a. What is the maximum number of nodes at depth d of a binary tree? b. What is the maximum number of nodes in a binary tree of height h? c. If a binary tree has 25 nodes, what is its maximum height? d. If a binary tree has 25 nodes, what is its minimum height? e. If a proper binary tree has 35 nodes, what are the numbers of external nodes? 9. (2 pts) Vector representation for BT: In order to access the tree nodes quickly, the binary tree shown at bottom is stored level-by-level in a one-dimensional array A. What are the indices of nodes L, M are? (A=1, B=2, D=3) A / \ B D \ / \ F C J / \ \ G H N / / L K \ P \ M 10. (5 pts) Preorder traversal using a stack: Please use the tree shown at bottom to explain how to do iterative implementation of preorder traversal using an explicit stack. (Please show the contents of the stack in order to describe your approach clearly.) a / | \ b c d / / \ e f g / | \ h i j 11. (5 pts) Level- order traversal using a queue: Please uee the tree shown at Question 10 to explain how to do iterative implementation of level-order traversal using a queue. (Please show the contents of the queue in order to describe your approach clearly.) 12. (6 pts) Euler Tour Traversal: Please use a simple binary tree to explain the concept of Euler Tour Traversal. 13. (3 pts) BT from inorder and preorder sequences: Draw a binary tree with inorder sequence [a b c d e f g h i] and preorder sequence [f b a e d c h g i]. 14. (3 pts) BT from inorder and postorder sequences: Draw a binary tree with inorder sequence [a b c d e f g h i] and postorder sequence [b a e d g i h f c]. 15. (8 pts) Leaders in a list: Design a O(n) algorithm that uses a stack to find leaders in a singly linked list. A leader is a key in a node of a linked list which is bigger than all the keys on its right. For instance: If the linked list stores the keys 2 6 1 5 4, then the leaders are 6, 5, 4.If the linked list stores the keys 8, 7, 9, 6, 2, 3, 1, then the leaders are 9, 6, 3, 1. 16. (3 pts) Complexity of operations on heaps: Give the time complexity of the following operations on a heap of nodes: (a) min (b) insert (c) removeMin. 17. (5 pts) Insertion and deletion in heaps: Draw the max- heap tree after the following operations are performed beginning with an empty heap: insert 43, insert 31, insert 68, insert 24, delete- max, insert 51, insert 44, insert 53, insert 69, insert 71, deletemax. 18. (10 pts) In-place heap sort: Given a vector of [8 5 1 3 7], how do you perform inplace heap sort? Please plot the 5 heaps (both vector and tree representations) during heap construction, and the other 5 during output. 19. (5 pts) Evaluation of expressions in postfix: Use a stack to show how to evaluate the postfix expression 9 8 7 2 3 * - / - 5 2 - * 3 / step by step. (You should draw thestack status after each step.) 20. (5 pts) Infix to postfix conversion using a stack: Use a stack to show how to convert the expression (a/(b- c*d))/(e- a)*c into a postfix form. (You should draw the stack after each step). 21. (5 pts) Catalan number: Let bn be the number of different permutations obtainable by passing the numbers 1, 2, 3, ..., n through a stack and deleting in all possible ways. Give the recursive formula for bn. (Be sure to specify the initial condition for your formula.) (Total score = 100) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.172 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1463624376.A.44C.html