Yiting Lin>试卷(2015/06/28)

公職◆資料結構題庫 下載題庫

104 年 - 104年高員三級鐵路人員_資訊處理 資料結構#22433 

选择:0题,非选:10题
立即測驗 
我要補題 回報試卷錯誤 試卷下載

【非選題】

一、對於很多項係數為 0 的多項式加法,譬如 A(x) = 12x 1000 + 6x 15 + 5 與 B(x) = 8x 500 - 56x 125 + 10x 15 + 1 相加。

【題組】請問你會使用陣列(array)或鏈結串列(linked list)來表示此種多項式?為什麼? 該資料結構會包含那幾部分?(10 分)

#23662
編輯私有筆記

【非選題】【題組】以 A(x)與 B(x)為例,畫出 AB 兩多項式的資料結構、說明加法演算法運作的過 程、與最終的資料結構結果。(15 分)

#23663
編輯私有筆記

【非選題】二、有一陣列 A=(179, 208, 306, 93, 859, 984, 55, 9, 271, 33)要由小排到大。使用堆積 排序法(heap sort)需要先將 A 陣列整理成 max heap,然後再經過 9 個回合(pass) 的 reheap 才能將資料由小排到大,請寫出整理成 max heap 後與第一個回合 reheap 結束時 A 陣列的內容。(10 分)

#23664
編輯私有筆記

【非選題】有 6 個已排序過的檔案,長度分別為 7,9,2,3,6,13。這 6 個檔案經過 5 次的 兩兩合併,成為一個完整排序過的檔案。已知合併時間複雜度與兩個合併檔案的 長度和成正比,請用 merge tree 寫出他們的合併順序與結果,且 merge tree 的 left subtree 長度小於 right subtree。(10 分)

#23665
編輯私有筆記

【非選題】有 n 筆資料,請說明如果任意選最左邊的資料當成比較基準資料(pivot),則快 速排序法(quick sort)在最糟的情況下時間複雜度為多少?(5 分)

#23666
編輯私有筆記

【非選題】三、令 “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 分)

#23667
編輯私有筆記

【非選題】請填入下列 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
}

#23668
編輯私有筆記

【非選題】四、分別說明在什麼情況下會用鄰接矩陣(adjacency matrix)或鄰接串列(adjacency list) 表示一個圖形(graph)?為什麼?(10 分)

#23669
編輯私有筆記

【非選題】分別說明在圖形的廣度優先搜尋(breadth first search)與深度優先搜尋(depth first search)時會使用何種資料結構?為什麼?(10 分)

#23670
編輯私有筆記

【非選題】一個無向圖(undirected graph)所有點(vertex)的分支度(degree)總和與邊 (edge)的個數有何關係?為什麼?(5 分)

#23671
編輯私有筆記