阿摩線上測驗 登入

97年 - 097年地方3等資料結構#48965

科目：公職◆資料結構 | 年份：97年 | 選擇題數：0 | 申論題數：16

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (16)

⑴下圖是 heap 的一個例子，請你說明何謂 heap？（5 分）
⑵ heap sort 通常使用 heap 的樹狀示意圖（如上圖）來表示其執行的過程。但在實 作 heap sort 的程式時，我們通常並不使用二元樹（binary tree）的資料結構來存 放其資料，而改採用另一種資料結構，請問是那一種資料結構？它是如何存資料 的？（5 分）
⑶和 merge sort 比起來，heap sort 有何優點？（5 分）
⑷和 quick sort 比起來，heap sort 有何優點？（5 分）
⑸ heap sort 在排序 n 個資料時，其時間複雜度（time complexity）為何？（5 分）
⑹如果輸入之資料中所有 n 個元素的值均相等，那麼請問 heap sort 的執行時間會不 會變得比較快（和亂數輸入的資料比起來）？還是變得比較慢？請說明理由。 （5 分）
⑺ heap sort 算是一個不錯的排序演算法，可惜它不是一個“stable”的 sort 方法。請 你用較簡單的方法，將 heap sort 改良一下，將它變成一個“stable”的 sort 方法。 （5 分）
二、典型的跳棋棋盤如下圖：  其中每個圓圈上可放上一顆棋子（紅、黃或綠色）或者不放棋子。現在我們不管跳 棋的規則為何或棋子的擺放是否合理，請你設計一個資料結構來表示任何一種可能 的盤面。你必須說明需占用多少空間及如何記錄棋子所在的位置。（20 分）
⑴試寫一段遞迴的（recursive）副程式，以計算一個二元樹（binary tree）的節點總 數。（10 分）
⑵如果這個二元樹中共有 n 個節點，請問你在⑴所設計的副程式執行的時間複雜度 （time complexity）為何？（5 分）
⑴請說明此兩種資料結構在處理佇列（queue）元素的 insertion 及 deletion 時，有何差 異。（5 分）
⑵請說明此兩種資料結構各自的優缺點。（5 分）
⑴試用 Minimax procedure 求 root 的分數。（5 分）
⑵請問電腦一開始應該走那一步才會贏？（5 分）
⑶這種遊戲我們通常稱為 zero-sum game，請解釋 zero-sum 的意義。（5 分）
⑷如果我們寫一個程式，能很快地將某種遊戲的遊戲樹完全展開，並很快地用 Minimax procedure 求 root 的分數，那麼在這個情形下，是否電腦就能下出最好的 走法？請說明之。（5 分）