加載中. ..
PDF
104
年公務人員特種考試警察人員、一般警察人員考試及
104
年
特種考試交通事業鐵路人員、退除役軍人轉任公務人員考試試題
代號：71070 全一張
（正面）
等 別：
高員三級鐵路人員考試
類 科 別：
資訊處理
科 目：
資料結構
考試時間： 2 小時 座號：
※注意： 禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、對於很多項係數為 0的多項式加法，譬如 A(x) = 12x1000 + 6x15 + 5 與
B(x) = 8x500 - 56x125 + 10x15 + 1 相加。
請問你會使用陣列（array）或鏈結串列（linked list）來表示此種多項式？為什麼？
該資料結構會包含那幾部分？（10 分）
以A(x)與B(x)為例，畫出 AB 兩多項式的資料結構、說明加法演算法運作的過
程、與最終的資料結構結果。（15 分）
二、
有一陣列 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分）
三、
令 “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 全一張
（背面）
等 別：
高員三級鐵路人員考試
類 科 別：
資訊處理
科 目：
資料結構
四、
分別說明在什麼情況下會用鄰接矩陣（adjacency matrix）或鄰接串列（adjacency list）
表示一個圖形（graph）？為什麼?（10 分）
分別說明在圖形的廣度優先搜尋（breadth first search）與深度優先搜尋（depth first
search）時會使用何種資料結構?為什麼?（10 分）
一個無向圖（undirected graph）所有點（vertex）的分支度（degree）總和與邊
（edge）的個數有何關係？為什麼?（5分）