課程名稱︰資料結構與演算法 課程性質︰必修 課程教師：林軒田 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2013.04.18 考試時限（分鐘）：120分鐘 試題 : Midterm Examination Problem Sheet TIME: 04/18/2013, 10:20-12:20 This is an open-book exam. You can use any printed materials as your reference during the exam. Any electronic devices are not allowed. Any form of cheating, lying or plagiarism will not be tolerated. Students can get zero scores and/or get negative scores and/or fail the class and/or be kicked out of school and/or receive other punishments for those kinds of misconducts. Both English and Chinese (if suited) are allowed for answering the questions. We do not accept any other languages. ┌─────────────────────────────────────┐ │There are 8 problems in the exam, each worth 25 points ─ the full credit │ │is 200 points. Some problems come with a few sub-problems to help you get │ │partial credits. For the 8 problems, 3 of them are marked with * and are │ │supposedly simple; 3 of them are marked with ** and are supposedly │ │regular; 2 of them are marked with *** and are supposedly difficult. There│ │is one bonus problem, numbered 1126, with 10 points. The problems are │ │roughly ordered by difficulty. │ └─────────────────────────────────────┘ (1) (25%, *) To count the number of boys/girls in some department, student C wrote the following program: 1 #include <iostream> 2 using namespace std; 3 void increase(int count){ 4 count++; 5 } 6 7 int main(){ 8 char ID[1126][11]; 9 int num_student; 10 int countBoy = 0; 11 int countGirl = 0; 12 13 //some code that initializes the ID array 14 //with something like "A123456789" per row 15 //also, num_student will be initialized 16 17 for(int i = 0; i < num_student; i++){ 18 if (ID[i][1] == '1') 19 increase(countBoy); 20 else 21 increase(countGirl); 22 } 23 cout << countBoy << ' ' << countGirl << endl; 24 return 0 ; 25 } (a) (10%) Assume that num_student is 1126 with 460 boys and 666 girls, what is the output of the program above? (b) (15%) If your answer above is not 460 666, explain how you can modify the program above with only one line to output 460 666. If your answer above is 460 666, explain to the TAs how the memory slots of the local variable countBoy in main and the local variable count in increase are changed during the first call to increase(countBoy). (2) (25%, *) Consider a complete binary tree with 11 nodes where each nodes are numbered from 1, 2, …, 11 that corresponds to its position in the array representation, with root being node number 1. That is, node i has a left child (if any) at 2i and a right child (if any) at 2i + 1. (a) (10%) Draw the binary tree with clear illustrations on the node numbers. (b) (5%) Do a post-order traversal in the binary tree above and print out the node numbers visited. (c) (5%) Do a in-order traversal in the binary tree above and print out the node numbers visited. (d) (5%) Do a pre-order traversal in the binary tree above and print out the node numbers visited. (3) (25%, *) You have been using a singly-linked list for your application, where each node is of the form struct Node{ int value; Node* next; }; But now there is a new need in your application that requires you to find the previous nodes quickly. Therefore, you need to write a program to convert your singly-linked list to a doubly-linked one. Therefore, you define the following DNode structure to represent a node in your doubly-linked list: struct DNode{ int value; DNode* next; DNode* prev; }; (a) (15%) Use any pseudo-code to describe an algorithm that takes a singly-linked list (i.e. a Node* head entry) and returns the new doubly-linked list (i.e. some DNode* entry) while deleting the memory allocated by the original singly-linked list. Your algorithm needs to be "on the fly". That is, it visits each node of the singly-linked list once and creates the corresponding node in the doubly-linked list immediately. (b) (10%) Modify your pseudo-code above to describe an algorithm that takes the same input but returns the new doubly-linked list in reverse order. Your algorithm still needs to be "on the fly". (Hint: You only need to change very few lines.) (4) (25%, **) Suppose you have two nonempty stacks S and T and a deque D. Use any pseudo-code to describe an algorithm that passes through the elements within S and T once, and uses D so that S contains all the elements of T below all of its original elements, with both sets of elements still in their original order. (5) (25%, **) The financial team in your company finds an old calculator implemented with the LISP language, which is based on prefix expressions of binary operators of the form ( - ( * 7 ( + 3 5 ) ) 1 ) But the team wants to evaluate the expression quickly, and therefore they want to transform the expression to its post-fix form. For simplicity of this problem, let's assume that there are parentheses in the expressions (which is true for LISP but not necessary in general). Use any pseudo-code to describe an algorithm transforms a valid prefix expression to a corresponding post-fix one (without parentheses). For instance, the post-fix expression that corresponds to the one above is 7 3 5 + * 1 - Your algorithm is only allowed to use one stack with size larger than the length of the prefix expression, and at most O(1) of additional memory. (Hint: Think about parentheses matching.) ┌─────────────────────────────────────┐ │For the following two problems, you can only use this definition: │ │Let f, g be functions from non-negative real numbers to non-negative real │ │numbers. We say f(n) = O(g(n)) iff there is a real constant c > 0 and an │ │real constant n_0 ≧ 1 such that f(n) ≦ cg(n) for n ≧ n_0. │ │Note that we use real numbers here for the simplicity of your proof below │ │(so you don't need to have floors and ceilings running in your proof). │ └─────────────────────────────────────┘ (6) (25%, **) Using the fact that log_e(n) ≦ n - 1 for all n ≧ 1, prove the following statement: "For any k > 0, log_2(m) = O(m^k)." (7) (25%, ***) Generalize your proof above to prove the following statement (or if you think the statement is wrong, disprove it): "Assume that f(n) = O(g(n)) and h(n) is a function from non-negative real numbers to non-negative real numbers. In addition, assume that ● h(n) is monotonically increasing: h(n') ≧ h(n) for all n' ≧ n ● The inverse function h^(-1)(m) of h exists for any m > 0 Then, f(h(n)) = O(g(h(n)))." (Hint: If this is true, let f(n) = log_2(n), g(n) = n, and h(n) = n^k and you can "easily" prove the statement in the previous problem with a few more lines.) (8) (25%, ***) For the binary max-heap with integer keys that is represented with an array and satisfies the heap properties: ● The nodes form a complete binary tree ● The node with the largest key in each sub-tree is at the root of the sub-tree (hence, the node with the overall largest key is at the root of the full tree.) (a) (5%) Student C thought that this property is true: "The node with the (2^k)-th largest key of the max-heap is within the first 2^(k+1) - 1 elements of the array." Show a heap without this property and thus prove student C wrong. (b) (10%) For a set of distinct integers, define the rank of an integer i be the total number of integers that are in the set and are not smaller than i. For instance, the largest number within the set is of rank 1, and the 2nd-largest number is of rank 2, and so on. Now, consider a set of all the elements within a binary max-heap that contains distinct integers. When the heap is of size 2^k - 1, prove that for a node at the third position of the array (the right child of the root), it is at least of rank 2 and at most of rank 2^(k-1) + 1. (c) (10%) Now, consider a binary max-heap that contains distinct integers and is of an arbitrary size ≧ 3, use any pseudo code to describe an algorithm that computes the rank of the node at the third position of the array. Your algorithm should run in O(r) time, where r is the rank of the node. (1126) (Bonus 10%, ???) We discussed about the difference between selection sort and heap sort, where it appears that the only change comes from replacing the linear search of the unordered batch (that can be either an array, a linked list, or almost anything) to a heap represented with an array. Given that the time complexity of heap sort, O(N logN) for N elements, is supposedly better than the time complexity of selection sort, O(N^2), why would anyone wants to use selection sort? Make some wild guesses and convince the TAs of some scenarios that is worth considering selection sort instead of heap sort. (Hint: Imagine that your boss, who is not of CS major, asks you this question. The TAs will grade qualitatively on whether you can convince your boss in a reasonable manner.) --

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