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

所謂三主對角線矩陣(tridiagonal matrix)，定義為在這種稀疏矩陣中，除了主對角線和 其上下的元素非0 外(就是其中間的三條斜線非0)，其它皆為0，如圖一。假如矩陣 A，以列主序(row major order)的方式存到陣列B 中，若A[0][0]存到B[0]處，則A[i][j]， n j i < ≤, 0 ，存至B 中的那一個位置？（20 分） ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ x x x x x x x x x x x x x x x x x x x . . . 圖一 Tridiagonal matrix A

現有兩「串列」（linked list），串列內之元素皆已由大到小依序接續排列。（20 分） 請寫出一簡短程序，將這兩個串列「合併」（merge）為一個單一的串列，串列內 之元素也是由大到小依序接續排列。 你所寫的程序的時間複雜度為何？（以O (⋯)表示）

有一個年輕小伙子，不到二十歲就拿到了電腦博士學位，教了幾年書又覺得學生的 素質和他的認知有一段距離，一氣之下，決定入山出家當和尚去了。經過面談後， 住持方丈覺得他的心意已決，了無牽掛，乃為其剃度，同時覺得他的學識能力甚佳， 於是乎就指定他去管理後山的藏經閣。到了藏經閣，這位年輕的和尚嚇了一跳，整 棟屋子擺滿了各式各樣的經書，寺裡的和尚借書，並無任何法則，想讀就拿，讀累 了，就隨便放回去! 他心想為了保存這些彌足珍貴的經書，該是為這些經書電腦化的 時候了。他希望他的經書管理系統，具有登入借閱者的基本資料以外，同時希望具 有查詢、新增、刪減經書的能力。這個和尚花了整整一年的時間，將這些經書分門 別類擺在架子上，同時他發現了一些現象如下：每一本經書皆為單一個作者編著， 且同一作者不會在不同年編著同一名稱的經書；同一名稱的經書，有不同的和尚在 同一年或不同年為其編著；一個和尚在同一年或不同年會編著不同名稱的經書；編 著者的出生年月日皆不可考。經過思考後，他馬上進行程式寫作，只花了半小時系 統就完成了。假如你是他的話，你將採取何種資料結構來製作此經書管理系統，詳 述其優缺點。（20 分）

對於具「線性序列」（linear order）關係的關鍵值集合，「優先佇列」（priority queue） 此抽象資料型態可用以保存一組關鍵值，並只支援以下四項運算： create()：建立一個空的優先佇列。 insert(x, Q)：將關鍵值x 加入優先佇列Q。 maximum(Q)：傳回優先佇列Q 中的最大值。 extract-maximum(Q)：傳回並除去優先佇列Q 中的最大值。 如何以「二元堆積」（binary heap）的方式，在一個「陣列」（array）裡存放該優先佇 列S 的元素，並支援 到 四項運算？並請說明所製成的優先佇列在處理以上四項 運算時，並列出其時間複雜度。（20 分）

假設有n 筆資料，利用快速排序法依其鍵值(key)排成由小到大，試證明： 快速排序法的最佳計算時間為 ) log ( 2 n n O 。（5 分） 快速排序法的最差計算時間為 ) ( 2 n O 。（5 分） 快速排序法的平均計算時間為 ) log ( 2 n n O 。（10 分） （請接第二頁） 九十二年公務人員升官等考試試題 代號： 科 別： 資訊工程、資訊處理 全四頁 (第二頁) 38250 38450

下圖中的邊都附有權值（weight）。圖中路徑（path）的長度為其中所有邊權值的總 和。列出下圖所有從s 點出發，到t 點的最長路徑。（20 分）

我們可以利用堆疊資料結構來把中置式(infix expression)轉成後置式(postfix expression)。 其轉換的方法如演算法一，而其用到的ISP 和ICP 表為圖二 。其中運算子" + - "為 二元運算子(binary operator)。 procedure POSTFIX(E) //convert the infix expression E to postfix. Assume the last character of E is a "∞" , which will also be the last character of the postfix. Procedure NEXT-TOKEN returns either the next operator, operand or delimiter – whichever comes next. STACK(1:n) is used as a stack and the character " ∞ − " with ISP( " ∞ − " ) = -1 is used at the bottom of the stack. ISP and ICP are functions. // STACK(1) Å " ∞ − " ; top Å 1 // initialize stack, top is the pointer of the stack // loop x Å NEXT-TOKEN(E) case :x = "∞" while top >1 do //empty the stack // print(STACK(top)); top Å top – 1 end print ( "∞" ) return :x is an operand: print(x) :x = ") " :while STACK(top)  " (" do //unstack until ") " // print (STACK(top)); top Å top – 1 end top Å top – 1 //delete " (" // :else: while ISP(STACK(top))ICP(x) do print (STACK(top)); top Å top – 1 end call ADD(x, STACK, n, top) //insert x in STACK // end forever end POSTFIX 演算法一：POSTFIX （請接第三頁） 九十二年公務人員升官等考試試題 代號： 科 別： 資訊工程、資訊處理 全四頁 (第三頁) 38250 38450 Symbol ISP (In-Stack Priority) ICP (In-Coming Priority) Symbol ISP (In-Stack Priority) ICP (In-Coming Priority) Symbol ISP (In-Stack Priority) ICP (In-Coming Priority) ) - - ) - - ) - - ** 3 4 ** 3 4 ** 4

說明紅黑樹（red-black tree）與一般的二元找尋樹有什麼關係？（5 分） 一般的樹都可轉換成紅黑樹嗎？請說明理由。（5 分） 請以下兩圖為例說明紅黑樹的轉換原則，請以虛線代表紅色指標，實線代表黑色 指標。（10 分）

*, / 2 2 *, / 1 1 *, / 2 3 +, - 1 1 +, - 2 2 +, - 1 1 ( 0 4 ( 0 4 ( 0 5 圖二.(a) 圖二.(b) 圖二.(c) Symbol ISP (In-Stack Priority) ICP (In-Coming Priority) Symbol ISP (In-Stack Priority) ICP (In-Coming Priority) ) - - ) - - ** 3 3 ** 5

如果「可能出現的關鍵值集合」（universe of keys）U 是一個存在有「線性序列」（linear order）關係的集合，那麼「雜湊表格」（hash table）與「二元搜尋樹」（binary search tree）都可以用來「製作」（implement）以關鍵值為查詢方式的「字典」（dictionary）。 請就「雜湊表格」與「二元搜尋樹」兩者在「建立初始字典」（creation），「查詢單一 關鍵值」（search），「消除單一關鍵值」（delete），「合併字典」（merge）四項運算方面， 比較兩者在運算時間上的複雜度。我們可假設「二元搜尋樹」中的「葉節點」（leaf nodes）在樹中的深度差別最多唯一，且假設關鍵值隨機出現在雜湊表格中得任何一 個儲存格，且無「碰撞」（collision）情形發生。（20 分） i j

*, / 2 2 *, / 3 4 +, - 1 1 +, - 1 2 ( 0 4 ( 0 6 圖二.(d) 圖二.(e) 圖二 ISP 和ICP 的運算子表 圖二.(a)為一般型態的運算子狀況，其優先權順序為" ( ) " > "**" >" * /" >" + - "；在運 算子的結合性中" **" 運算子為右結合，" * /" 運算子為左結合，" + -" 運算子為左結 合。 若把運算子" * / + -" 的結合性改為右結合（但其他性質不變），則應該用圖二中的 那一個ISP 和ICP 的運算子表？（5 分） 若把運算子" **" 的結合性改為左結合（但其他性質不變），則應該用圖二中的那 一個ISP 和ICP 的運算子表？（5 分） 若把運算子" */" 的結合性改為右結合（但其他性質不變），則應該用圖二中的那一 個ISP 和ICP 的運算子表？（5 分） 若把運算子" */" 的優先權改為比運算子"+ -"的優先權還低（但其他性質不變），則 應該用圖二中的那一個ISP 和ICP 的運算子表？（5 分） （請接第四頁） 九十二年公務人員升官等考試試題 代號： 科 別： 資訊工程、資訊處理 全四頁 (第四頁) 38250 38450 五、在一個二元搜尋樹中有 n a a a ..., , , 2 1 ，n 個識別字，其中 n a a a < < < ... 2 1 。假設搜尋 ia 的 機率為 ip 則搜尋成功的成本為 ) ( 1 i i n i a level p ∑ ⋅ ≤ ≤ 。但因搜尋有可能不成功，我們可 以把不在二元搜尋樹中的識別字分成n+1 個類別 i E ， n i ≤ ≤ 0 ，0 E 包含所有識別字X， X< 1 a ， i E 包含所有識別字X， ia <X< 1 + ia ， n i < ≤ 1 ， n E 包含所有識別字X， X> n a 。假設搜尋失敗的機率為 iq 則搜尋失敗的成本為 )1 ) ( ( 0 − ⋅ ∑ ≤ ≤ i node failure level q n i i 。因此一個二元搜尋樹的總成本為 ) ( 1 i i n i a level p ∑ ⋅ ≤ ≤ + )1 ) ( ( 0 − ⋅ ∑ ≤ ≤ i node failure level q n i i 。 其中∑ ≤ ≤ i n i p 1 + ∑ ≤ ≤ n i iq 0 =1。令ij T 為一個最佳搜尋二元樹，具有 j i a a ..., , 1 + 個識別字，i<j。 ii T 為空樹， n i ≤ ≤ 0 。ij T 無定義，i>j。令ij c 為尋找ij T 的成本， 0 = ii c 。ijr 為ij T 的根， ∑ + = + + = j i k k k i ij p q q w 1 ) ( 為ij T 的重量。 令n=4 且 = ) , , , ( 4 3 2 1 a a a a (do, if, read, while)。 假設 )1,1,3,3 ( ) , , , ( 4 3 2 1 = p p p p 和 )1,1,1,3,2 ( ) , , , , ( 4 3 2 1 0 = q q q q q 。為了方便計算，所有的機 率值已經預先放大16 倍，依搜尋總成本找出其最佳搜尋樹。（20 分）