阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
97年 - 097年地方3等資料結構#48965
>
題組內容
一、heap sort 是一個有名的排序演算法。請回答下列問題：
⑸ heap sort 在排序 n 個資料時，其時間複雜度（time complexity）為何？（5 分）
其他申論題
⑴下圖是 heap 的一個例子，請你說明何謂 heap？（5 分）
#171308
⑵ heap sort 通常使用 heap 的樹狀示意圖（如上圖）來表示其執行的過程。但在實 作 heap sort 的程式時，我們通常並不使用二元樹（binary tree）的資料結構來存 放其資料，而改採用另一種資料結構，請問是那一種資料結構？它是如何存資料 的？（5 分）
#171309
⑶和 merge sort 比起來，heap sort 有何優點？（5 分）
#171310
⑷和 quick sort 比起來，heap sort 有何優點？（5 分）
#171311
⑹如果輸入之資料中所有 n 個元素的值均相等，那麼請問 heap sort 的執行時間會不 會變得比較快（和亂數輸入的資料比起來）？還是變得比較慢？請說明理由。 （5 分）
#171313
⑺ heap sort 算是一個不錯的排序演算法，可惜它不是一個“stable”的 sort 方法。請 你用較簡單的方法，將 heap sort 改良一下，將它變成一個“stable”的 sort 方法。 （5 分）
#171314
二、典型的跳棋棋盤如下圖： 其中每個圓圈上可放上一顆棋子（紅、黃或綠色）或者不放棋子。現在我們不管跳 棋的規則為何或棋子的擺放是否合理，請你設計一個資料結構來表示任何一種可能 的盤面。你必須說明需占用多少空間及如何記錄棋子所在的位置。（20 分）
#171315
⑴試寫一段遞迴的（recursive）副程式，以計算一個二元樹（binary tree）的節點總 數。（10 分）
#171316
⑵如果這個二元樹中共有 n 個節點，請問你在⑴所設計的副程式執行的時間複雜度 （time complexity）為何？（5 分）
#171317
⑴請說明此兩種資料結構在處理佇列（queue）元素的 insertion 及 deletion 時，有何差 異。（5 分）
#171318
阿摩線上測驗
登入
阿摩線上測驗
登入