課程名稱︰資料結構與演算法 課程性質︰資訊系必修 課程教師︰蔡欣穆 開課學院：電資學院 開課系所︰資訊系 考試日期（年月日）︰2012/4/17 考試時限（分鐘）：180分鐘 是否需發放獎勵金：是 試題 : Problem 1. In each of the following question, please specify if the statement is true or false. If the statement is true, explain why it is true. If it is false, explain what the correct answer is and why. (12 points. 1 point for true/false and 2 points for the explanation for each question) 1.0001 1. n = O(nlogn) 10 10 10 n 2. n = Ω(2 ) 3. Given an expression tree to represent an arthimetic expression, if we want to evaluate the expression we need to perform a preorder traversal of the tree. Here "to evaluate" means to calculate the result of the expression. 4. A queue follows a Frist-In-Last-Out (FILO) rule. Problem 2. "Short answer" questions (34 points) 1.(a) Why do we need to use a version control system to manage our source codes? (b) When would be a good time for the programmer to commit the current working copy to the repository? (4 points) 2. Using O-notation, please write down the time complexity of the binary search algorithm (a) in the best case and (b) in the worst case in terms of n, the number of elements in the list to be searched. (4 points) 3. Please give the running time of the following program using O-notation in terms if n. (4 points) sum=0; for(i=0;i<n;++i) for(j=1;j<i*i;++j) for(k=0;k<j;++k) ++sum; 4. Suppose we use an array to represent a degree-5 tree. Given the array index i of a certain tree node, please write down the functions to calculate (a) the array index of its parent node and (b) the array index of its second-to-the-left node. (4 points) 5. What is (a) the minimum and (b) the maximum number of nodes in a complete binary tree with a height of H (there are H levels in the tree)? (4 points) 6. Please complete Table 1 to show the progress of converting the infix expression "(3-9+(7+1*4))/6" to its postfix expression using a stack. (6 points) 7. Draw the expression tree of "(3-9+(7+1*4))/6". (4 points) 8. Convert "(3-9+(7+1*4))/6" to a prefix expression. (4 points) Problem 3. Give the definition of Θ-notation. Then prove that log(n!) = Θ(nlogn). (8 points, 2 points for the definition anf 6 points for the proof.) Problem 4. Please answer the following problems about linked lists. You can assume that the linked lists use the following structure. (14 points) struct ListNode{ int data; struct ListNode *next; }; 1. Please give a C function to insert a node in a descending sorted singly linked list, in which the head of the list has the largest data, and the node next to the head node, if exists, has the second large data, etc. The function should use the following declaration (prototype). struct ListNode* InsertSorted(struct ListNode* head, struct ListNode* newNode); In the declaration, head points to the head node of the list and newNode points to the node to be inserted. Your function should return a pointer to the head node of the list after you finish the insertion operation. (6 points) 2. Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both lists are known, but the intersecting node is not known, Also the number of nodes in each of the list before they intersect are unknown and both lists may have it different. List1 and List2 have n and m nodes, respectively. You are given two stacks to hold pointers to the nodes on the lists, Please give an algorithm (either pseudo code or C code) to find the merging node. Your algorithm should have a running time of O(n+m). (8 points) Problem 5. A d-ary heap is a generalized version of heap, compared to a banary heap. Each non-leaf node would have d children instead of 2 (of course, just like binary heap, there could be one node which has less than d children). The d-ary maximum heap still follows the max tree property, i.e., the parent node would always be larger than its child nodes. Like a maximum binary heap, a d-ary maximum heap supports two operations: DeleteMax and Insert. Assume that the number of elements in the heap is n. (24 points) 1. Assume that {10,12,7,18,3,11,20,19} are inserted into an initially empty 3-ary max heap in the given order. Show how the 3-ary max heap would look like after each insertion. (6 points) 2. After all numbers in the given list are inserted, we perform two DeleteMax operations. Show how the 3-ary max heap would look like after each deletion. (4 points) 3. Show how you would represent a d-ary heap with an array. Show how each element in the heap is associated with an array entry - how to map each element to an array index. (2 points) 4. With your representation in P5.3, give an efficient implementation of DeleteMax for a d-ary max heap (pseudo code or C code). The DeleteMax operation should delete and return the maximum value in the heap, and then adjust the heap accordingly so that the remaining items in the heap still maintain the max tree property. Analyze its running time in terms of d and n. (6 points) 5. With your representation in P5.3, give an efficient implentation of Insert for a d-ary max heap (psuedo code or C code). The Insert operation should the given number into the heap. Analyze its running time interms of d and n. (6 points) ┌─┐ │25│ └─┘ / \ / \ ┌─┐ ┌─┐ │7 │ │30│ └─┘ └─┘ \ / \ / ┌─┐ ┌─┐ │23│ │29│ └─┘ └─┘ / / / / ┌─┐ ┌─┐ │8 │ │27│ └─┘ └─┘ \ \ ┌─┐ │12│ └─┘ / \ / \ ┌─┐┌─┐ │10││14│ └─┘└─┘ Figure 1: A Binary Search Tree Problem 6. Please answer the following questions about the binary search tree and the threaded binary search tree: (22 points) 1. Please draw how the binary search tree in Figure 1 would look like after deleting the number 7. (4 points) 2. Since a binary search tree is also a type of binary tree, we can also modify it to become an inorder threaded binary tree. Assume that the following code is used fore representing a threaded binary tree. struct TreeNode* root; //the pointer to the root node struct TreeNode { int data; int LTag, RTag; // show twhether the left/right pointer is a thread, // 0== thread, 1==redular tree edge struct TreeNode *left, *right; //pointers to the left/right child/thread } Please convert the binary tree in Figure 1 (before the node with the number 7 is deleted) to become an inorder threaded binary tree and draw how it would look like. Note that you have to show the value of each field in the structure in each tree node. Remember to draw the dummy node as well. (6 points) 3. Please complete the following C function to return the inorder predecessor of a given node in a threaded binary tree. struct TreeNode* inorderPredecessor(struct TreenNode* given){ //put your C code here } (6 points) 4. Using the inorderPredecessor function inthe previous question, please complete the following function to print out all numbers which are in the threaded binary search tree and are larger than a and smaller than b in descending order. void printAllBetween(int a, int b, struct TreeNode* root){ //put your C code here } (6 points) Problem 7. (Bonus) Please write down two things you like/dislike about this course so far, and how you would change the theings you do not like if you were the professor. :) (4 points) --

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