阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
109年 - 109 關務特考_三等_資訊處理:資料結構#86484
> 申論題
四、給予一串資料:45, 30, 40, 65, 68, 60, 70, 50,將此串資料依序建成一 max-heap樹,並說明如何從此 max-heap 樹進行由小至大的排序(Sorting)。(20 分)
詳解 (共 3 筆)
丁丁
詳解 #4084912
2020/06/22
(共 1 字,隱藏中)
前往觀看
111年警特高普中鋼調查皆上榜
詳解 #5467583
2022/05/19
由於是max-heap,而max-hea...
(共 127 字,隱藏中)
前往觀看
刷題中
詳解 #5856843
2023/06/24
自己解的有錯請噴我
(共 11 字,隱藏中)
前往觀看
相關申論題
五、給予兩線性鏈結串列,其節點 C 語言的宣告如下:(20 分) 此兩線性鏈結串列,分別由指標 plist1 與 plist2 指在串列首,請完成下列 程式片段,將 plist2 所指串列接在 plist1 所指串列後面。
#349667
一、假設 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
(一)說明A[1:n]是一個 max-heap 之定義。(5 分)
#349672
(二)設計一個副程式 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
(a) X 和 Y 之值? (2 分)
#349675
(b)又知此錯離子為一種八面體構造,試畫出此錯離子之立體異構物結構(2 分)
#349676
相關試卷
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