105年高等考試技師資料結構線上測驗

1.: (一) 請用C 或Java 程式語言以1.遞迴(recursive)和2.迴圈(iterative)方法寫出求Fn 的
函式(function) Fib(n)。（10 分）
(二) 請各別分析你所寫出1.遞迴(recursive)和2.迴圈(iterative)演算法的時間複雜度，
並以Big-O 方式表示。（5 分）

2.: 圖形(graph)的實際表達方法通常可以使用1.相鄰矩陣(adjacency matrix)、2.相鄰串列
(adjacency list)等資料結構。以下為一有向圖(directed graph) G = (V, E)：

(一) 請以C 或Java 程式語言寫出1.相鄰矩陣(adjacency matrix)和2.相鄰串列(adjacency
list)的宣告以有效表達有向圖G 的資料結構；並繪出相對使用以上資料結構表達有
向圖G 的矩陣與串列結果示意圖。（10 分）
(二) Floyd-Warshall's algorithm 是找尋圖形中所有端點(node)對端點最短路徑(all-pairs
shortest path)的方法，請選擇一種資料結構，以有向圖G 為例，繪圖說明用此一演算
法求解過程中每一回合(run)的計算結果。（10 分）

3.: 對資料庫系統的永久儲存結構而言，通常必須能夠隨著檔案紀錄的增多，進而動態
的新增儲存區塊(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
說明你所設計的動態雜湊結構方法。（10 分）

4.: 一個跨國量販公司資料庫系統的部分相關關聯式表格名稱、欄位屬性名稱和資料如
下：（每小題5 分，共15 分）

(一) 請指出每一個表格最合理的主鍵(primary key)欄位集合與外鍵(foreign key)。
(二) YU01 分公司在今天售出產品編號A13011 的4 件貨品，請以SQL 語法寫出新增此
筆售貨紀錄到SALE 表格中的功能。
(三) 以SQL 語法寫出查詢(query)：亞洲'Asia'商店所賣出產品名稱為'k-phoneS'的總數量。

5.: 承續第四題，量販公司的高層決策者希望能夠從系統的每日交易運作資料庫(operational
transaction database)中，建立線上分析處理(on-line analytical processing, OLAP)系
統。因此，首先必須由PRODUCT、SALE、COMPANY、STATE 等資料表中轉換
構建資料倉儲(data warehouse)。假設所要分析的主要目標資料項包括：‘售貨的金
額’(NUM*VALUE)和‘數量’(NUM)；分析的維度(dimension)包括有：‘售出日期’、‘地
區’和‘產品’等3 個維度，並且各個分析維度又可進一步分成以下概念階層(concept
hierarchy)所組成的分析層次：
售出日期：年(year) > 季(quarter) > 月(month) > 日(day)
地區：洲別(area) > 國別(country) > 城市(city)
產品：產品類別(class) > 產品編號(product)
請應用資料倉儲模型(data warehouse model)為此OLAP 系統設計資料倉儲綱要
(schema)，並回答下列問題：

(一) 採用的綱要模型為何？請說明原因。（5 分）
(二) 請繪出所設計的綱要，包含事實表格(fact table)、維度表格(dimension table)，以
及相對的參考屬性(referential attribute)。（15 分）

6.: 某營運單位的資料庫系統經系統分析、進一步設計後，得到實體-關係模型(E-Rmodel)
圖結果如下。其中屬性(attribute)名稱下有底線者為各實體(entity)的主鍵，實體C 中
的屬性彼此另有以下的功能相依(functional dependency)存在：C3→C4，C3→C2。

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

購買題庫後，可使用那些功能？