105年 - 105 專技高考_資訊技師：資料結構與資料庫及資料探勘#85803

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

試卷資訊

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

選擇題 (0)

申論題 (12)

(一)請用 C 或 Java 程式語言以1.遞迴（recursive）和2.迴圈（iterative）方法寫出求 Fn 的函式（function）Fib(n)。

(二)請各別分析你所寫出1.遞迴（recursive）和2.迴圈（iterative）演算法的時間複雜度，並以 Big-O 方式表示。

(一)請以C或 Java程式語言寫出1.相鄰矩陣（adjacency matrix）和2.相鄰串列（adjacency list）的宣告以有效表達有向圖 G 的資料結構；並繪出相對使用以上資料結構表達有向圖 G 的矩陣與串列結果示意圖。

(二)Floyd-Warshall's algorithm 是找尋圖形中所有端點（node）對端點最短路徑（all-pairs shortest path）的方法，請選擇一種資料結構，以有向圖 G 為例，繪圖說明用此一演算法求解過程中每一回合（run）的計算結果。

三、對資料庫系統的永久儲存結構而言，通常必須能夠隨著檔案紀錄的增多，進而動態的新增儲存區塊（block），例如：B-tree 樹狀檔案資料結構，即可隨著資料量變大而增加葉節點區塊（leaf node block）或增加樹的高度來因應。傳統的雜湊（hashing）方法為靜態雜湊（static hashing）結構，雖然有快速搜尋資料的優點，但是無法有效率的擴充儲存區塊；為改善靜態雜湊的缺點，動態雜湊（dynamic hashing）結構則能夠同時達成快速搜尋資料和動態擴充儲存區塊的功能。假設每一儲存區塊最多可以儲存 3 筆紀錄資料，試設計一動態雜湊資料結構與相對應的新增函數（Insert(key)），用以下的鍵值（key）新增順序為例：
1, 3, 5, 7, 2, 4, 6, 8, 10, 9, 11, 21
說明你所設計的動態雜湊結構方法。

(一)請指出每一個表格最合理的主鍵（primary key）欄位集合與外鍵（foreign key）。

(二)YU01 分公司在今天售出產品編號 A13011 的 4 件貨品，請以 SQL 語法寫出新增此筆售貨紀錄到 SALE 表格中的功能。

(三)以 SQL 語法寫出查詢（query）：亞洲'Asia'商店所賣出產品名稱為'k-phoneS'的總數量。

(一)採用的綱要模型為何？請說明原因。

(二)請繪出所設計的綱要，包含事實表格（fact table）、維度表格（dimension table），以及相對的參考屬性（referential attribute）。

(一)將以上實體-關係模型轉成符合第二正規化格式（second normal form）的關聯式表格綱要（relational schema）。

(二)將本題⑴中的關聯式表格綱要轉成符合第三正規化格式（third normal form）的關聯式表格綱要。