阿摩線上測驗 登入

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 分）