阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 98年 - 098年地方3等資料結構#48278
98年 - 098年地方3等資料結構#48278
科目:
公職◆資料結構 |
年份:
98年 |
選擇題數:
0 |
申論題數:
19
試卷資訊
所屬科目:
公職◆資料結構
選擇題 (0)
申論題 (19)
⑴利用區域編號,寫出找到的第一條路徑(編號間用逗號隔開)。(4 分)
⑵利用區域編號,寫出找到的倒數第二條路徑(編號間用逗號隔開)。(4 分)
⑶找到第一條路徑前,曾經拜訪過但最後未出現在該路徑上之區域有那些?(利用 區域編號作答)(5 分)
⑷若迷宮大小改為 2 × 2,且所有區域均可通行,仍以左上角與右下角區域做為入口 與出口,則共存在多少種不同路徑?(5 分)
⑴線性探測為何會產生群集(clustering)問題?假設雜湊函數與表格容量分別為 h(key)與 T,先寫出其 g(key, i)函數後,再說明之。(4 分)
⑵問題同⑴,但將線性探測改為平方探測。(4 分)
⑶設計雙雜湊函數時,有何基本原則?先寫出其 g(key, i)函數,再說明之。(4 分)
⑷在何種狀況下,使用雙雜湊才能探測到雜湊表中所有可用的位置?(3 分)
⑸某空雜湊表共有 7 個位置,使用線性探測來排解碰撞問題。假設鍵值 k1, k2, k3 均 對應至相同的雜湊值 4,先依序將 k1, k2 與 k3 加入雜湊表後,再刪除 k2。請問此 時查詢表中是否含有 k3,其結果為成功或失敗?請配合圖形說明之。(5 分)
⑴二元搜尋樹與堆積(heap)有何主要相異點?寫出二項。(6 分)
⑵將一含有 n 個節點(n>1)之二元搜尋樹以堆積來表示,並以一陣列來儲存此堆 積,請問此陣列容量可能之最小值與最大值分別為何?請說明原因。(6 分)
⑶已知二元樹節點含有二個指標欄位以指向其左子與右子,請問一棵具有 n 個節點 (n>=1)的二元樹,存在多少個空的指標欄位(也就是其值為 NULL)?請說明 原因。(5 分)
⑷依序將整數鍵值 45, 33, 17, 65, 54, 70, 88, 25 加入一棵空的二元搜尋樹,再繪製此 二元樹對應之引線樹(threaded tree)。(8 分)
⑴程式一是那一種排序演算法的實作?又其中的 s 變數有何功用?(6 分)
⑵當程式一結束執行後,第 9 行的 swap()函數共被呼叫幾次?又此時變數 i 的值為 何?(6 分)
⑶程式二是那一種排序演算法的實作?當其中的 while 迴圈第一輪執行完畢後,陣 列 a 的內容為何?(6 分)
⑷參考程式二,假設陣列 a 的元素個數為 N(N>1),若要成功完成排序,整數變 數 p 的值需有那些限制?請說明原因。(7 分)
⑴分別使用相鄰矩陣(adjacency matrix)與相鄰串列 (adjacency list)來儲存此圖時,何者所需之記憶 0 1 8 17 28 12 體空間較小?假設節點編號與邊值均不大於 255, 14 2 14 3 30 4 且指標欄位需占用 4 個位元組(byte)。(5 分) 20 25 22
⑵利用 Sollin 演算法(Sollin’s Algorithm)找出此圖 5 6 10 14 的最小成本生成樹(minimum cost spanning tree), 6 7 12 須按步驟寫出此樹的成長過程。(7 分)