阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
97年 - 097年地方3等資料結構#48965
> 申論題
題組內容
五、下圖是一個假想的遊戲樹(game tree),其中終端節點(terminal nodes)的分數表 示先下的電腦(以矩形表示)的得分,分數為正數表示電腦贏了對手(opponent, 以圓形表示),為負數則表示電腦輸了。
⑵請問電腦一開始應該走那一步才會贏?(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
⑸ heap sort 在排序 n 個資料時,其時間複雜度(time complexity)為何?(5 分)
#171312
⑹如果輸入之資料中所有 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
相關試卷
114年 - 114 地方政府公務特種考試_三等_資訊處理:資料結構#134706
114年 · #134706
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
114年 · #133251
114年 - 114 高等考試_三級_資訊處理:資料結構#128753
114年 · #128753
114年 - 114 關務特種考試_三等_資訊處理(選試英文):資料結構#126563
114年 · #126563
114年 - 114 身心障礙特種考試_三等_資訊處理:資料結構#126562
114年 · #126562
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理:資料結構#124511
113年 · #124511
113年 - 113 高等考試_三級_資訊處理:資料結構#121217
113年 · #121217
113年 - 113 關務特種考試_三等_資訊處理(選試英文):資料結構#119489
113年 · #119489
112年 - 112 地方政府特種考試_三等_資訊處理:資料結構#118368
112年 · #118368
112年 - 112 公務升官等考試_薦任_資訊處理:資料結構#117327
112年 · #117327