104年特種考試交通事業鐵路人員考試高員三級_資料結構
首頁
>
線上測驗
>
公職考試>資訊處理(高員三級)
> 104年特種考試交通事業鐵路人員考試高員三級_資料結構
年度
年度
107
106
105
104
1.
對於很多項係數為0的多項式加法,譬如
與
相加。
(一) 請問你會使用陣列(array)或鏈結串列(linked list)來表示此種多項式?為什麼?該資料結構會包含那幾部分?(10分)
(二) 以A(x)與B(x)為例,畫出AB兩多項式的資料結構、說明加法演算法運作的過程、與最終的資料結構結果。(15分)
題型:申論題
難易度:尚未記錄
看詳解
2.
(一) 有一陣列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分)
題型:申論題
難易度:尚未記錄
看詳解
3.
(一) 令“i”代表插入(insert)一筆資料,“d”代表刪除(delete)一筆資料。畫出在空的binary search tree做i4, i2, i6, i5, i1, i9, d4, i3, i8, d6, i10, i7, d5動作之後最終的binary search tree,而刪除資料時用比刪除資料大的資料取代它並調整成binarysearch 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
}
題型:申論題
難易度:尚未記錄
看詳解
4.
(一) 分別說明在什麼情況下會用鄰接矩陣(adjacency matrix)或鄰接串列(adjacency list)表示一個圖形(graph)?為什麼?(10分)
(二) 分別說明在圖形的廣度優先搜尋(breadth first search)與深度優先搜尋(depth first search)時會使用何種資料結構?為什麼?(10分)
(三) 一個無向圖(undirected graph)所有點(vertex)的分支度(degree)總和與邊(edge)的個數有何關係?為什麼?(5分)
題型:申論題
難易度:尚未記錄
看詳解
購買題庫後,可使用那些功能?
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)