阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 104年 - 104年高員三級鐵路人員_資訊處理 資料結構#22433
104年 - 104年高員三級鐵路人員_資訊處理 資料結構#22433
科目：
公職◆資料結構 |
年份：
104年 |
選擇題數：
0 |
申論題數：
10
試卷資訊
所屬科目：
公職◆資料結構
選擇題 (0)
申論題 (10)
請問你會使用陣列（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
}
四、分別說明在什麼情況下會用鄰接矩陣（adjacency matrix）或鄰接串列（adjacency list） 表示一個圖形（graph）？為什麼?（10 分）
分別說明在圖形的廣度優先搜尋（breadth first search）與深度優先搜尋（depth first search）時會使用何種資料結構?為什麼?（10 分）
一個無向圖（undirected graph）所有點（vertex）的分支度（degree）總和與邊 （edge）的個數有何關係？為什麼?（5 分）
阿摩線上測驗
登入
阿摩線上測驗
登入