110年 - 110 身心障礙特種考試_三等_資訊處理：資料結構#98257

科目：公職◆資料結構 | 年份：110年 | 選擇題數：0 | 申論題數：11

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (11)

(一)設計一有效的二維稀疏矩陣資料結構，避免儲存不存在（或其值為 0）的資料，有效利用空間。

(二)使用所設計的資料結構，完成矩陣的轉置（Transpose）運算函式。

(三)使用所設計的資料結構，完成維度分別為 m×n 的 A 矩陣與 n×l 的 B 矩陣之矩陣相乘（Multiply）運算函式。

(一)請以相鄰矩陣（adjacency matrix）表達有向圖形 G。

(二)設計一演算法找尋圖形中所有端點（node）對端點的最短路徑（all-pairsshortest path），並以有向圖形 G 的相鄰矩陣為例說明所使用演算法的計算過程。

(三)請說明在上述(二)中所使用演算法的時間複雜度（time complexity）為何？

(一)請問具有 K 層以上 m = 5 結構的 B-tree 至少可以存放多少筆資料？

(二)請畫出完成運算 insert(7)與 insert(28)後的 B-tree 結構。

(三)完成上述(二)之後接續畫出先後完成運算 insert(15)與 insert(6)的 B-tree結構。

(一)請以該訊息詳述構建霍夫曼碼演算法的過程與結果。

(二)依步驟說明所使用演算法的時間複雜度（time complexity）。