阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
110年 - 110 高等考試_三級_資訊處理:資料結構#102802
> 申論題
題組內容
一、A 為(8×4)矩陣、B 為(4×10)矩陣、C 為(10×3)矩陣、D 為(3×20) 矩陣、E 為(20×4)矩陣,
(一)請列出此 5 個矩陣相乘 A✖B✖C✖D✖E 所有 可能的乘法順序(請用括號表示乘法順序) 。(5 分)
相關申論題
(二)請使用 Dynamic Programming(動態規劃)的技巧計算出此五個矩陣相乘 A✖B✖C✖D✖E 的 最佳乘法順序(請用括號表示乘法順序) ,使得五個矩陣相乘所需要花費 的乘法數量最少。(15 分)
#433775
(三)請列出此五個矩陣相乘所需要花費的最少 乘法數量。 (5 分)(注意:未說明 Dynamic Programming 的計算過程, 不予計分。)
#433776
(一)請設計一個 Greedy(貪婪)的演算 法,來解決找錢給顧客的問題,使得找給顧客金額 W 所使用的銅板數量 最少,並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。 (15 分)
#433777
(二)此 Greedy 演算法適合使用何種資料結構來完成。(5 分)
#433778
(三)此 Greedy 演算法的解法是否能保證為最佳解?請舉例說明。(5 分)
#433779
(一)請使用 C++或 Python 語言,修改此二元 搜尋法,使其能對未排序的(unsorted)且長度為 n 的陣列 A[0:n1],進 行三元化搜尋,即以 divide-and-conquer 技巧將此陣列切成三個子陣列, 並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜 尋,如果找到則回傳 1,如果找不到則回傳 0。(17 分) (注意:請寫一 個 searching 類別,內含一個 search 功能)
#433780
(二)請分析修改後的三元化搜尋 法其最差時間複雜度(worst case time complexity)以 order 的方式表示。 (8 分) (注意:不可將此陣列數值進行排序,請加註解說明程式碼作法。)
#433781
(一)請使用 C 語言寫一副程式 void FindMeanAverage(int A [], int n, int * mean, int * average),對一個未排序的(unsorted)且長度為 n 的陣列 A[0:n1],尋找陣列中的中位數與平均數,並分別存入 mean 及 average 運算複雜度。(17 分)
#433782
(二)請舉例說明此副程式最差情況(worst case)所 花費的運算複雜度。 (8 分)(注意:請加註解說明程式碼作法。)
#433783
(五)若 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