阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
109年 - 109 身心特考_三等_資訊處理:資料結構#86485
> 申論題
題組內容
四、假設有個矩陣 A[1:n]儲存 n 個整數。本題將設計 heap 排序演算法(heap sort)之重要部分,將矩陣 A[1:n]變成一個 max-heap。
(一)說明A[1:n]是一個 max-heap 之定義。(5 分)
相關申論題
一、假設 A[1:n]是一個矩陣,存有n個不同的整數,且已依序從小到大排列。給定一個整數s,設計一個線性時間(linear time)的演算法,找出在A[1:n]中是否存在兩個相異之 A[i]和 A[ j ],使得A[i]+A[ j ]=s。若存在,則印出任一組符合條件之i和 j ;若不存在,則印出 0。(須詳述或證明所設計程式之正確性及其計算複雜度,否則不計分)(25 分)
#349668
(一)若 e 是所有邊中權重最大者,則。(也就是 e 不會在任一個 G的最小權重擴張樹中)(10 分)
#349669
(二)假設 G 是 2-連通(2-connected)。(也就是去掉任一條邊 G 仍是連通的)此時,若 e 是所有邊中權重最大者,則。(15 分)
#349670
三、斐波那契數(Fibonacci number)Fn的定義為:F0 = 0, F1 = 1, Fn= Fn-1 + Fn-2 ,n > 1。下面是一個計算斐波那契數 Fn 的演算法,以類似 C 語言的函數(C function)表示,其中資料型態 integer 表示整數。 假設輸入的整數 n≧0。證明此程式的計算複雜度 T(n) > Fn。在分析計算複雜度時,可將“==”, “=”, “+”和“return”當作只需要一個單位時間的運算。(25 分)
#349671
(二)設計一個副程式 sift(A, r, n)其輸入參數 A 是一個矩陣,n 是矩陣 A 的大小,1≦r≦n 是一個指標。副程式 sift(A, r, n)的功能是將 A[r]為樹根的子樹變成 heap。(在呼叫 sift(A, r, n)之前, A[i]的所有子樹必須已經是 heap)並分析其計算時間確實是 O(h(r)),其中 h(r)是以A[r]為樹根的子樹的高度。(10 分)
#349673
(三)利用 sift(A, r, n)設計一個線性時間的演算法,將矩陣 A[1:n]變成 heap,並證明所設計的演算法的時間複雜度為線性。(10 分)
#349674
(三)請分別說明 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