資訊處理 91 年資料結構考古題

請回答下列問題： 兩個變數X 與Y 欲做內容之交換，往往需要藉由第三個變數temp，例如： temp←X; X←Y；Y←temp 今假設變數X=63，Y=28 規定不能使用第三個變數temp 來做交換，問有什麼其他 方法使得X=28，Y=63？（10 分） 一個數字的inversion 是在其左邊大於它的數字的數目，一組數字的inversion 的集 合稱為inversion table。請寫出一組數字=(4, 1, 5, 3, 2)的inversion table。（10 分）

給予下列美國五個城市的交通圖： 提出一種方式表示這個圖。（5 分） 提出一種方法計算城市間的最短距離。（10 分） 找出這個圖的遞移性閉包(Transitive closure)。（5 分）

把一筆鍵值(key value)加入一棵order 為m 的B-樹(B-tree)，在什麼情況下，這棵樹 的高度會增加1 層。請說明新資料所加入的節點(node)在加入之前，節點內所含鍵 值的個數，以及高度如何變化？（10 分） 把一筆特定的鍵值(key value)由一棵order 為m 的B-樹(B-tree)中去除，請說明那個 節點的資料被去除，以及在什麼情況下，這棵樹的高度會減少1 層。答案必須包 括在資料被除去之前，節點內的鍵值個數，和高度如何變化。（10 分）

多相式合併排序法(Polyphase meging)是一種磁帶的外部排序方法。其做法是將已排 序好的資料組(sorted blocks 或runs)依某一種方式分配到不同的磁帶機上，再加以合 併。問： 今若有四個磁帶機可用，而最初有57 個資料組，請說明使用多相式合併排序法的 過程。（你必須先寫出最初分配的過程，再寫出實際合併排序的過程）（15 分） 使用多相式合併排序法有什麼限制？應如何處理？例如：當 中只有53 個已排 序好的資料段落時。（5 分）

若一個「雜湊表格」(hash table)有m 個儲存格，且已存放了n 個「關鍵值」(keys)，我 們會說此雜湊表格的「載重因子」(load factor)為α= n/m。當α>1 時，到此雜湊表格所 進行的每一次查詢運算，是否一定要使用O(1+α)的時間？請詳細說明為什麼？（20 分）