[試題] 97上 鄭振牟 資料結構與程式設計 第二次小考

[llewxam (鋼琴中的大賦格)]

課程名稱︰      資料結構與程式設計
課程性質︰      選修
課程教師︰      鄭振牟
開課學院：      電機資訊學院
開課系所︰      電機工程學系
考試日期（年月日）︰    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
推 ketsu1109   :已收入精華區
→ llewxam     :打錯了，這一堂課是複選必修，請精華區改成一下