阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
111年 - 111 身心障礙特種考試_三等_資訊處理:資料結構#107534
> 申論題
題組內容
一、請回答下列 Big O 的相關問題:
(二)給定 100 萬個介於 0 到 100(含 0 及 100)的整數,請利用任一種高階 程式語言寫出一個 O(N)的由大至小的排序演算法,並說明此演算法 為何是 O(N)的方法。(15 分)
相關申論題
(一) Big O Notation,根據維基百科又稱為漸進符號,它是用於描述演算法漸 進行為的數學符號。更確切地說,它用更簡單的函式來描述一個演算法在 數量上的漸進趨勢。某個問題可採用 5 個演算法 A~E 求解,各演算法執 行時間的 Big O 分別如下:A 為 O(N2),B 為 O(Nlog(log N)),C 為 O(),D 為 O(N2log(N)),E 為 O(SQRT(N))。當 N 很 大時,請根據演算法的執行時間,由慢至快排序這 5 個演算法。(10 分)
#460611
(一)若處理 Hash Table 衝突的方法為開放定址法(Open Addressing Hashing) 中的線性探測法(Linear Probing):增量函數 F(i)= i(i 為衝突的次 數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在 相同機率的情況下,查找成功及查找失敗的平均查找長度(Average Search Length; ASL)。(15 分)
#460613
(二)若處理 Hash Table 衝突的方法為開放定址法(Open Addressing Hashing) 中的平方探測法(Quadratic Probing):增量函數 F(i)= i2(i 為衝突 的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計 算在相同機率的情況下,查找成功及查找失敗的平均查找長度(Average Search Length; ASL)。(15 分)
#460614
三、請寫出對以下 8 個數字[44, 62, 31, 5, 82, 49, 16, 7],依序建構最小堆積樹 (Min Heap Tree)的過程。為方便最小堆積樹的建構,我們通常會使用一 個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆 積樹的建構。最小堆積樹建構完成後,請寫出如何用此樹依序將數字由小 到大的排序過程。請說明此種排序法的計算複雜度 Big O 為何?(25 分)
#460615
(一)首先將圖的信息建成一個 N*N 的初始距離矩陣,其中 N 是節點的個 數,矩陣的各列(Rows)代表 From Nodes,矩陣的各行(Columns) 代表 To Nodes,矩陣中的值則分別代表上圖中從 From Node 到 To Node 的距離。(5 分)
#460616
(二)其次列舉從 D 到 C 的最短路徑求解過程(需輸出最短路徑的值及路徑) , 並說明此方法的計算複雜度 Big O 為何。(15 分)
#460617
(三)請分別說明 Binary Search Tree 與 Red Black Tree 在插入、刪除與搜尋數 字等三操作的時間複雜度。(12 分)
#570252
(二)從空集合開始,依下列數字串 1, 2, 3, 4, 5, 6, 7, 8 順序插入節點建立並繪 出 Red Black Tree。(紅色節點請以雙線同心圓表示,例如將紅色節點 5 表示成 ;黑色節點請以單線圓表示,例如將黑色節點 8 表示成 ) 。 (13 分)
#570251
(一)從空集合開始,依下列數字串 1, 2, 3, 4, 5, 6, 7, 8 順序插入節點建立並繪 出 Binary Search Tree。(5 分)
#570250
(三)若 Graph 有 n 個節點與 e 個邊,請分別以 Big O 寫出以 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存 Graph 空間複雜度。比較 且說明兩者在空間複雜度的優劣。(14 分)
#570249
相關試卷
115年 - 115 關務特種考試_三等_資訊處理(選試英文):資料結構#138980
115年 · #138980
115年 - 115 身心障礙特種考試_三等_資訊處理:資料結構#138979
115年 · #138979
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