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

Cn r= ە ۖ ۔ ۖ ۓ 0, 1, 若r>n 若 n==r 1, 若 r==0 Cr n-1+Cr-1 n-1, 其他 ，兩項式係數的組合遞迴演算法公式如左。 請用你熟悉的程式語言，撰寫此遞迴函式。（5 分） 若n=5, r=3，請用二元樹畫出其遞迴呼叫的情形。（5 分） 最後的傳回值是多少？（5 分） 共遞迴呼叫幾次？（5 分）

給定如下圖所示之環狀雙向鏈結串列（circular doubly linked list），並以A 指向其中 一個節點。請用類C 之虛擬語言（C-like pseudo code）完成下列動作。 在A 所指向節點之右鏈結（rlink）插入由B 所指向的一個新節點。（6 分） 刪除A 所指向的節點，並將A 指向其原節點之右鏈結（rlink）節點。只能使用A 指標。（6 分） 刪除整個串列，完成後A 應指向NULL。只能使用A 指標。（13 分）

對於很多項係數為0 的多項式加法，譬如A(x) = 12x1000 + 6x15 + 5 與 B(x) = 8x500 - 56x125 + 10x15 + 1 相加。 請問你會使用陣列（array）或鏈結串列（linked list）來表示此種多項式？為什麼？ 該資料結構會包含那幾部分？（10 分） 以A(x)與B(x)為例，畫出AB 兩多項式的資料結構、說明加法演算法運作的過 程、與最終的資料結構結果。（15 分）

有位程式設計師在撰寫程式時遇到了一個難解的問題，後來發現有兩個演算法可以 解這個難題：演算法A 的時間複雜度為 )) ! log( (

在計算學生成績的程式中，按成績的高低分為五級，且用IF 指令，其程式如下： if S<60 then G = ‘F’ else if S<70 then G = ‘D’ else if S<80 then G = ‘C’ else if S<90 then G = ‘B’ Else G = ‘A’ 若學生在五個等級中的分布是不平均的，分布機率如下表： 分數（Score） 90-100 80-89 70-79 60-69 0-59 等第（Grade） A B C D F 機率 0.05 0.30 0.50 0.1 0.05 假設學生人數為5000 人，請回答下列問題： 請畫出IF 指令的二元樹分析圖並分析此IF 指令可能的比較次數。（10 分） 若用最佳化二元樹修正IF 指令，請畫出該二元樹，並分析IF 指令可能的比較次 數。（10 分） 可使用什麼資料結構，使程式指令更為精簡，並請說明。（5 分） 104年公務人員特種考試關務人員考試、 104年公務人員特種考試身心障礙人員考試及 104年國軍上校以上軍官轉任公務人員考試試題 全一張 （背面） 考 試 別： 關務人員考試

假設有1000 筆資料將以雜湊法（hashing）放入雜湊表（hash table）。 若該雜湊表有750 桶（buckets）× 4 槽（slots），不管採用何種雜湊函數，1000 筆 資料都放入雜湊表後，該表之載入密度（load factor）為何？（7 分） 若要做到完整雜湊（perfect hashing），雜湊函數應該要有何特性？（8 分） 假設建立雜湊表時若發生碰撞就採取線性探測法（linear probing）來放入資料，且 在1000 筆資料都放入該雜湊表後，搜尋每筆資料的平均所需查看（access）次數 希望約為2，在盡量不浪費空間的前提下，該雜湊表應該如何設計？請以「桶」 （buckets）、「槽」（slots）、「載入密度」（load factor）等之數量加以敘述，並說明 為何該設計符合平均查看次數之限制。（10 分）

有一陣列A＝（179, 208, 306, 93, 859, 984, 55, 9, 271, 33）要由小排到大。使用堆積 排序法（heap sort）需要先將A 陣列整理成max heap，然後再經過9 個回合（pass） 的reheap 才能將資料由小排到大，請寫出整理成max heap 後與第一個回合reheap 結束時A 陣列的內容。（10 分） 有6 個已排序過的檔案，長度分別為7，9，2，3，6，13。這6 個檔案經過5 次的 兩兩合併，成為一個完整排序過的檔案。已知合併時間複雜度與兩個合併檔案的 長度和成正比，請用merge tree 寫出他們的合併順序與結果，且merge tree 的left subtree 長度小於right subtree。（10 分） 有n 筆資料，請說明如果任意選最左邊的資料當成比較基準資料（pivot），則快 速排序法（quick sort）在最糟的情況下時間複雜度為多少？（5 分）

n n O ，演算法B 的時間複雜度為 )) )! ((log ( 2 n n O 。假設輸入資料的個數n通常都很大，他應該選擇那個演算法比較好， 原因何在？（20 分） 二、樹（tree）是一個很常用的資料結構。一個樹是指一個沒有迴圈（cycle）的聯通圖 （connected graph）。（每小題10 分，共20 分） 證明：每個具有n個節點（node）的樹， 1 > n ，至少有2 個分支度（degree）為 1 的節點。（分支度就是指有多少邊以此節點為端點。） 用前項結果證明：每個具有n個節點的樹， 1 > n ，恰好有 1 − n 個邊（edge）。

佇列（Queue）結構的插入（Insert）和刪除（Delete）演算法如下： const int N=10; int Rear=0, Front=0; void Insert(char item, char Queue[]) void Delete(char item, char Queue[]) { if (Rear==N-1) { if (Front==Rear) cout<<“Queue Is Full”; cout<<“Queue Is Empty”; else else { Rear=Rear+1; { Front =Front + 1; Queue[Rear]=item; item = Queue[Front]; } } } } 請問上述演算法的佇列結構，會有什麼問題存在？（5 分） 可用什麼資料結構解決？（5 分） 承上之資料結構，請寫出插入（Insert）和刪除（Delete）演算法。（10 分）

給定下列以陣列所表示之16 筆有序數列。 i 0 1 2 3

令 “i”代表插入（insert）一筆資料，“d” 代表刪除（delete）一筆資料。畫出在空 的binary search tree 做i4, i2, i6, i5, i1, i9, d4, i3, i8, d6, i10, i7, d5 動作之後最終的 binary search tree，而刪除資料時用比刪除資料大的資料取代它並調整成binary search tree。（10 分） 請填入下列C 程式中三個空格以完成ptr 指向樹根的binary search tree 上搜尋key 的程式。（15 分） typedef struct node { struct node *left; int data; struct node *right;} NODE; NODE *search(NODE *ptr, int key) { while(ptr != NULL ) { If (key == ptrÆdata) return (1) ; If (key < ptrÆ data) (2) ; else (3) ; } return NULL } 104年公務人員特種考試警察人員、一般警察人員考試及104年 特種考試交通事業鐵路人員、退除役軍人轉任公務人員考試試題 代號：71070 全一張 （背面） 類 科 別： 資訊處理

給定一個權重圖（weighted graph）， ) , , ( w E V G = ，其中每個邊（edge）e的權重 ) (e w 都是正整數，為了簡單，假設 } ,..., 2,1 { n V = 。任意點v 與起始點s的距離可以用 一個矩陣 ] .. 1[ n d 來表示。（每小題10 分，共20 分） 設計一個只需 ) (n O 空間的方法來記錄從s出發，到達每個點的最短路徑。 說明計算與印出從起始點s到任意點 V t ∈ 的最短路徑的演算法。（解此小題時可參考 Dijkstra 或其他演算法來設計，且不須將Dijkstra 或別的演算法做詳細的描述。）

圖形的理論是起源於西元十八世紀，有一位數學家尤拉（Eular）為了解決「肯尼茲 堡橋樑」問題，而想出的一種圖形結構理論。所謂的「肯尼茲堡橋樑」問題是：某 一個人由某地點出發，最後再回到原點，必須要經過每一座橋，並且只能經過一 次。如下圖所示： 請問肯尼茲堡的人有無可能走過所有的橋樑1 次，到過每個地方，而後又回到肯 尼茲堡？（5 分） 土地代表頂點A,B,C,D，橋樑代表邊1~7，請畫出此圖形結構。（5 分） 數學家尤拉（Eular）對「肯尼茲堡橋樑」問題所找出的規則是什麼？（5 分） 請舉一個具有尤拉循環（Eulerian Cycle）的例子，並寫出其路徑。（5 分）

分別說明在什麼情況下會用鄰接矩陣（adjacency matrix）或鄰接串列（adjacency list） 表示一個圖形（graph）？為什麼?（10 分） 分別說明在圖形的廣度優先搜尋（breadth first search）與深度優先搜尋（depth first search）時會使用何種資料結構?為什麼?（10 分） 一個無向圖（undirected graph）所有點（vertex）的分支度（degree）總和與邊 （edge）的個數有何關係？為什麼?（5 分）

有個矩陣 ] .. 1[ n A ，n的值很大。在矩陣A中存有n個正整數，且從小到大排列。給定 某個整數x ，二分搜尋法（binary search）可以在 ) (log n O 的時間內找出x 在矩陣 ] .. 1[ n A 的位置，或宣告在 ] .. 1[ n A 中沒有x 。在某個應用中，已知絕大部分的x 都會出 現在矩陣 ] .. 1[ n a 的前面m個元素，且m 的值遠小於n，但是無法預知m的範圍。設 計一個演算法，可以在 ) (log m O 的時間內完成搜尋。（20 分）

學生的學號格式是（N1N2N3N4N5N6N7），假設儲存空間為99，請用數字分析法 （Digital Analysis），分別以學號為鍵值（Key）雜湊（Hashing）出其資料儲存的 位址。數字的分布曲度（Skewness）設為sk，則ski= ∑ = 9 ~ 0 1 - j ij | a | ，其aij表示Ni出現的個數。 請依下列五位學生的學號算出其ski值。（10 分） Student 1 ID: 0392018 Student 2 ID: 0392124 Student 3 ID: 0392238 Student 4 ID: 0252714 Student 5 ID: 0392468 請寫出此五位學生儲存的位址。（5 分） 肯尼茲堡

假設有個矩陣 ] .. 1[ n A 儲存n個整數。Quick sort 是一個排序演算法。假設有個副程式 partition ) , , ( r l A 其輸入參數A是一個矩陣， n r l r l < < , , ，是兩個指標。其回傳的值m 也是一個指標。這個副程式可將矩陣中從l 到r 的這一段資料 ] .. [ r l A 區分成兩段： ] .. [ m l A 和 ] .. 1 [ r m A + ，使得在 ] .. [ m l A 中的元素都小於或等於x ，而在 ] .. 1 [ r m A + 中的 元素都大於或等於x，其中x 是從 ] .. [ r l A 中隨機選擇的一個整數。接下來要在此兩段 資料遞迴執行partition。避免這些遞迴計算可以用一個堆疊（stack）來處理。假設 partition ) , , ( r l A 回傳m，則執行： if ) ( m l < push ) , ( m l into stack if ) 1 ( r m < + push ) ,1 ( r m + into stack 一開始，堆疊中只有一組資料， ) ,1( n 表示 ] .. 1[ n A 需要排序。如此反覆將堆疊最上面 的資料 ) , ( r l 移出，執行partition ) , , ( r l A ，直到堆疊沒有資料為止。 （每小題10 分，共20 分） 證明在最糟情況下，堆疊的高度可以達到 2 / n 。 設計一個好的演算法以降低stack 的高度，並證明堆疊的高度最多只需要 1 log + n 。

請寫出圖(2)所示二元樹的前序、中序和後序走訪。（6 分）

資料20、30、10、50、60、40、45、5 請建立成一棵AVL 樹，（6 分）請依序 刪除60 及30，在推導過程需註明旋轉的類別。（6 分）

若採雜湊搜尋法中的移位折疊相加法，且m=1000，請推導鍵值x=123456789 的儲 存位址在那裡？（5 分） 九、請推導圖(3)之拓撲排序。（10 分） 十、有一二維陣列A(-1:5, -4:2)之啟始位址A(-3,-4) = 100，以列為主排列，請問A(1,1)所 在位址？（6 分）若以行為主排列，請問A(1,1)所在位址又如何？（6 分）（假設陣 列內元素長度都為1） 圖(2) 圖(3)

9 10 11 12 13 14 15 A[i] 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 請畫出該陣列以二元搜尋法搜尋資料之二元搜尋樹（binary search tree）。（5 分） 假設陣列內的資料量共有1024 筆資料，則二元搜尋樹共會有幾層（最上層為 第1 層）？請說明。（5 分） 若是陣列中有兩個相鄰的數字對調位置（也就是只有此兩個數字順序錯誤），最多 可能會有多少數字將無法以二元搜尋法成功找到？請說明。（15 分） 104年公務人員升官等考試、104年關務人員升官等考試 104年交通事業公路、港務人員升資考試試題 代號：26260 全一張 （背面） 等 級： 薦任 類科（別）： 資訊處理 科 目： 資料結構 四、給定m 個印表機共用一個印表佇列（printer queue）。印表機A1, …, Ak 每次都從印表 佇列選取優先權最高（優先權數字最大）的列印工作進行列印，印表機Ak+1, …, Am 每次都選取優先權最低（優先權數字最小）的列印工作進行列印。每天需要列印工作 繁多，因此該印表佇列在選取優先權最高、最低及排入新印表需求的效率非常重要。 假設該印表佇列以對稱最小最大堆積（Symmetric min-max heap, SMMH）加以實作。 找到並移除最高優先權印表工作的時間複雜度為何？排入新印表需求的時間複雜 度為何？請以Big-O 方式敘述。（5 分） 若所有印表機都尚未開機，而送進印表佇列的順序如後（數字代表該印表優先權）： 8, 18, 28, 38, 35, 25, 15, 5, 40, 1。請將該印表佇列以SMMH 樹狀結構圖表示之。 （15 分） 承上題，若A1 開機，並處理了優先權最高的印表工作。請將印表佇列變化結果 以SMMH 樹狀結構圖表示之。（5 分）