阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
104年 - 104年高員三級鐵路人員_資訊處理 資料結構#22433
> 申論題
四、分別說明在什麼情況下會用鄰接矩陣(adjacency matrix)或鄰接串列(adjacency list) 表示一個圖形(graph)?為什麼?(10 分)
相關申論題
請問你會使用陣列(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
分別說明在圖形的廣度優先搜尋(breadth first search)與深度優先搜尋(depth first search)時會使用何種資料結構?為什麼?(10 分)
#23670
一個無向圖(undirected graph)所有點(vertex)的分支度(degree)總和與邊 (edge)的個數有何關係?為什麼?(5 分)
#23671
(五)若 n = 10,且每一組球生產後放上裝箱輸送帶的 球的大小順序非固定順序 。假設輸送帶上原本配置 n 個機器人,若改成配置 2n 個機器人, 整組球順序排好的速度可以加快多少?請說明。
#560494
相關試卷
114年 - 114 地方政府公務特種考試_三等_資訊處理:資料結構#134706
114年 · #134706
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
114年 · #133251
114年 - 114 高等考試_三級_資訊處理:資料結構#128753
114年 · #128753
114年 - 114 關務特種考試_三等_資訊處理(選試英文):資料結構#126563
114年 · #126563
114年 - 114 身心障礙特種考試_三等_資訊處理:資料結構#126562
114年 · #126562
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理:資料結構#124511
113年 · #124511
113年 - 113 高等考試_三級_資訊處理:資料結構#121217
113年 · #121217
113年 - 113 關務特種考試_三等_資訊處理(選試英文):資料結構#119489
113年 · #119489
112年 - 112 地方政府特種考試_三等_資訊處理:資料結構#118368
112年 · #118368
112年 - 112 公務升官等考試_薦任_資訊處理:資料結構#117327
112年 · #117327