阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
97年 - 097年地方3等資料結構#48965
>
題組內容
五、下圖是一個假想的遊戲樹(game tree),其中終端節點(terminal nodes)的分數表 示先下的電腦(以矩形表示)的得分,分數為正數表示電腦贏了對手(opponent, 以圓形表示),為負數則表示電腦輸了。
⑴試用 Minimax procedure 求 root 的分數。(5 分)
其他申論題
⑴試寫一段遞迴的(recursive)副程式,以計算一個二元樹(binary tree)的節點總 數。(10 分)
#171316
⑵如果這個二元樹中共有 n 個節點,請問你在⑴所設計的副程式執行的時間複雜度 (time complexity)為何?(5 分)
#171317
⑴請說明此兩種資料結構在處理佇列(queue)元素的 insertion 及 deletion 時,有何差 異。(5 分)
#171318
⑵請說明此兩種資料結構各自的優缺點。(5 分)
#171319
⑵請問電腦一開始應該走那一步才會贏?(5 分)
#171321
⑶這種遊戲我們通常稱為 zero-sum game,請解釋 zero-sum 的意義。(5 分)
#171322
⑷如果我們寫一個程式,能很快地將某種遊戲的遊戲樹完全展開,並很快地用 Minimax procedure 求 root 的分數,那麼在這個情形下,是否電腦就能下出最好的 走法?請說明之。(5 分)
#171323
⑴試求出該式子所釋放出的總能量?(5 分)
#171324
⑵若已知該蛻變之半衰期為 10 min,試繪出其蛻變圖。(5 分)
#171325
⑶當蛻變後,該正電子會產生何種作用?其最終之變化如何?(5 分)
#171326