【站僕】摩檸Morning>試卷(2018/11/22)

資料結構與資料庫及資料探勘題庫  下載題庫

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

【非選題】
1.一、某個以列為主（row-major）儲存的二維陣列 A[0..7][0..5]，若 A[2,3]的位址為 1084₁₀，A[5,1]的位址為 1148₁₀，則 A[3,4]的位址為多少？若改以行為主（column-major），則 A[3,4]的位址又為多少？請寫出計算式並說明。（10 分）

【非選題】
2.

二、下列為一棵高度平衡二元樹（AVL tree），若依序加入資料：65、55，該如何調整此 AVL 樹？（10 分）

【非選題】
3.三、給予一中序追蹤（inorder traversal）ABCDEGHF 和前序追蹤（preorder traversal）DBACEFGH，請畫出其對應的二元樹，並詳繪左右節點。（10 分）

【非選題】
4.

四、請對下列無方向圖形進行廣向優先走訪（breadth first search），從頂點 1 開始。

【題組】 ⑴請寫出演算法及其走訪過程所需資料結構之使用方式，搜尋時請依照頂點編號由小而大放入該結構，如：若需放入 1、4、6 三個頂點則先放入 1 再放入 4 再放入 6。（5 分）

【非選題】
5.【題組】⑵請由左而右依序寫出對該圖形進行搜尋的拜訪順序，例如：1, 2, 3,…… 表示先拜訪 1 再拜訪 2 再拜訪 3……。（5 分）

【非選題】
6.

五、下列兩題為有關資料庫關聯代數的運算：

【題組】

⑴下面為兩個關聯資料表 T1 和 T2 的內容，若對 T1 和 T2 進行除法運算（DIVIDE）後得到一個關聯資料表 T3，請寫出 T3 的內容。（5 分）

【非選題】
7.【題組】

⑵下面為兩個關聯資料表 R1 和 R2 的內容，其中 X 為其共同屬性（common attribute），若對 R1 和 R2 進行 LEFT OUTER JOIN 後得到一個關聯資料表 R3，請寫出 R3 的內容。（5 分）

【非選題】
8.

六、有一關聯資料表 S 之關聯綱要（relation schema）如下，其中除了主鍵之相依性外，若以 Æ 表示相依性（functional dependency），該表還存在著右列的相依性，請將該關聯資料表修改成符合第二正規化之（second normal form）格式，並寫出其關聯綱要。（15 分）