课程名称︰ 资料结构与程式设计 课程性质︰ 选修 课程教师︰ 郑振牟 开课学院： 电机资讯学院 开课系所︰ 电机工程学系 考试日期（年月日）︰ 2008/12/03 考试时限（分钟）： 约60分钟 是否需发放奖励金： 是，谢谢 （如未明确表示，则不予发放） 试题 : 1. Show that Gaussian Elimination has a complexity of O(n^2) by counting the number of field operations involved in eliminating an n-by-n matrix to its row echelon form. 2. Write an algorithm to construct a biary tree given preorder and inorder traversal sequences. Is the tree unique? Prove or disprove by giving a counter example. 3. Complete the max heap implementation below. template <typename T> class max_heap { public: max_heap () : size (0), capacity (8) { heap = new T[capacity + 1]; } ~max_heap () { delete heap; } void push (T const& e) { if (size==capacity) { //double heap's capacity or die } int foo = ++size; while ( foo != 1 && heap[foo/2] < e) { heap[foo] = heap[foo/2]; foo /= 2; } heap[foo] = e; } void pop (); //delete max element T const& top () const; //return max element bool is_empty () const; //is heap empty private: T* heap; int size; int capacity; }; 4. A source node of a directed graph is a node that does not have any incoming edges, whereas a sink node is a node that does not have any outgoing edges. Using Bellman-Ford, compute the all-destination shortest paths from the source node of the graph given below by its weighted adjacency matrix. What is the shortest path from that source to the sink node? Show the process of Bellman-Ford by recording the d and p arrays as done in class. [0 6 5 5 0 0 0] [0 0 0 0 -1 0 0] [0 -2 0 0 1 0 0] [0 0 -2 0 0 -1 0] [0 0 0 0 0 0 3] [0 0 0 0 0 0 3] [0 0 0 0 0 0 0] --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.243.6