[試題] 96上 張瑞益 資料結構 期末考

[miracle0722 (miracle)]

課程名稱︰資料結構
課程性質︰工科海洋系資組必修
課程教師︰張瑞益
開課學院：工學院
開課系所︰工程科學及海洋工程學系
考試日期（年月日）︰2008.01.16
考試時限（分鐘）：9:10~12:00
是否需發放獎勵金：是
（如未明確表示，則不予發放）

試題 :
1.[10 points] Use "Circular Linked List with Dummy Head Node"to show the
                            4        4   3
              addition of 3x -5 and x - x.(圖示即可)

2.[5+5 points] 何謂 Bound Folding Hashing? 何謂 Balanced Binary Tree?

3.[10 points] 何謂 Double Hashing? (請詳列公式與其建議值)

4.[5+5 points] 如何用 array 與 pointer 表示一個 Full Binary Tree? (圖示即可)

5.[5+5 points] 舉列說明 a general tree 與 a forest 的二元表示法.(圖示即可)

6.Given a sequence of numbers 3467, 7864, 451, 6783, 2432, 56547, 2316.
  [10 points] Show the steps to do "Quick Sort" on this sequence.(圖示即可)

  [10 points] Show the steps to do "Heap Sort" on this sequence.(圖示即可)

7.[10 points] Run Prim's algoritem on the graph with the starting node A.(如圖)

  [5+5 points] Show the DFS and BFS results of the graph with the starting
               node A.

                            E
                      10 ／
                       ╱   ∕
                  2   A  8 ∕9
                   ／  ╲ ∕
                 B       D
                  ﹨  ／5
                 3  C

8.[10 points] 證明：一個含有 n 個節點的二元樹的高度h滿足[log (n+1)]<= h <= n.
                                                            2
[100分] 請把求解的步驟寫出來(可用圖示說明)，勘酌字體大小在正反面作答。
   勿用考卷以外紙張。

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