阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
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
(a) X 和 Y 之值? (2 分)
#349675
(b)又知此錯離子為一種八面體構造,試畫出此錯離子之立體異構物結構(2 分)
#349676
(a)當反應剛開始時,所測量到的活化能是多少? (3 分)
#349677
(b)當反應快要結束時,所測量到的活化能是多少? (3 分)
#349678