⑷依序將整數鍵值 45, 33, 17, 65, 54, 70, 88, 25 加入一棵空的二元搜尋樹，再繪製此 二元樹對應之引線樹（threaded tree）。（8 分）

⑸某空雜湊表共有 7 個位置，使用線性探測來排解碰撞問題。假設鍵值 k1, k2, k3 均 對應至相同的雜湊值 4，先依序將 k1, k2 與 k3 加入雜湊表後，再刪除 k2。請問此 時查詢表中是否含有 k3，其結果為成功或失敗？請配合圖形說明之。（5 分）

⑴二元搜尋樹與堆積（heap）有何主要相異點？寫出二項。（6 分）

⑵將一含有 n 個節點（n＞1）之二元搜尋樹以堆積來表示，並以一陣列來儲存此堆 積，請問此陣列容量可能之最小值與最大值分別為何？請說明原因。（6 分）

⑶已知二元樹節點含有二個指標欄位以指向其左子與右子，請問一棵具有 n 個節點 （n＞=1）的二元樹，存在多少個空的指標欄位（也就是其值為 NULL）？請說明 原因。（5 分）

⑴程式一是那一種排序演算法的實作？又其中的 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 分）