左下圖為一6× 6迷宮,其中灰色區域表示不可通行,其餘可通行區域則
有編號,入口與出口分別位於左上角(編號0)與右下角(編號35)。
假定每個區域有八個可能的行動方向,找尋出口路徑時,會依序嘗試此
八個方向(次序請參考右下圖之箭頭編號)。利用深度優先搜尋(depth-first
search),在迷宮中探索所有可行路徑(路徑中不可包含重複的區域)。
(1) 利用區域編號,寫出找到的第一條路徑(編號間用逗號隔開)。
(2) 利用區域編號,寫出找到的倒數第二條路徑(編號間用逗號隔開)。
(3) 找到第一條路徑前,曾經拜訪過但最後未出現在該路徑上之區域有那
些?(利用區域編號作答)
(4) 若迷宮大小改為2 × 2,且所有區域均可通行,仍以左上角與右下角區
域做為入口與出口,則共存在多少種不同路徑?
線性探測(linear probing)、平方探測(quadratic probing)與雙雜湊(double
hashing)可用來解決雜湊(hashing)時發生的碰撞(collision)問題,它
們使用不同的g(key, i)函數來決定發生第i 次(i ≥ 0)碰撞時,鍵值key 在
雜湊表中的探測位置。
(1) 線性探測為何會產生群集(clustering)問題?假設雜湊函數與表格容
量分別為h(key)與T,先寫出其g(key, i)函數後,再說明之。
(2) 問題同(1),但將線性探測改為平方探測。
(3) 設計雙雜湊函數時,有何基本原則?先寫出其g(key, i)函數,再說明
之。
(4) 在何種狀況下,使用雙雜湊才能探測到雜湊表中所有可用的位置?
(5) 某空雜湊表共有7 個位置,使用線性探測來排解碰撞問題。假設鍵值
k1, k2, k3 均對應至相同的雜湊值4,先依序將k1, k2 與k3 加入雜湊表
後,再刪除k2。請問此時查詢表中是否含有k3,其結果為成功或失敗?
請配合圖形說明之。
二元搜尋樹(binary search tree):
(1) 二元搜尋樹與堆積(heap)有何主要相異點?寫出二項。
(2) 將一含有n 個節點(n >1)之二元搜尋樹以堆積來表示,並以一陣列來
儲存此堆積,請問此陣列容量可能之最小值與最大值分別為何?請說
明原因。
(3) 已知二元樹節點含有二個指標欄位以指向其左子與右子,請問一棵具
有n個節點(n >=1)的二元樹,存在多少個空的指標欄位(也就是其值
為NULL)?請說明原因。
(4) 依序將整數鍵值45, 33, 17, 65, 54, 70, 88, 25 加入一棵空的二元搜尋
樹,再繪製此二元樹對應之引線樹(threaded tree)。
排序(Sorting):參考下表之程式一與程式二回答問題。
(1) 程式一是那一種排序演算法的實作?又其中的s 變數有何功用?
(2) 當程式一結束執行後,第9 行的swap()函數共被呼叫幾次?又此時變
數i 的值為何?
(3) 程式二是那一種排序演算法的實作?當其中的while 迴圈第一輪執行
完畢後,陣列a 的內容為何?
(4) 參考程式二,假設陣列a的元素個數為N(N >1),若要成功完成排序,
整數變數p 的值需有那些限制?請說明原因。
參考下右圖形(graph)回答問題,頂點(vertices)中的數字為頂點編號,
邊(edge)上的數值代表成本(cost)。
(1) 分別使用相鄰矩陣(adjacency matrix)與相鄰串列(adjacency list)來
儲存此圖時,何者所需之記憶體空間較小?假設節點編號與邊值均不
大於255,且指標欄位需占用4 個位元組(byte)。
(2) 利用Sollin 演算法(Sollin’sAlgorithm)找出此圖的最小
成本生成樹(minimum costspanning tree),須按步驟寫出此樹的
成長過程。
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)