115年 - 115 經濟部所屬事業機構_新進職員甄試試題_統計資訊：1 .資料庫及資料探勘 2 .程式設計#146958

科目：國營事業◆1.資料庫及資料探勘 2.程式設計 | 年份：115年 | 選擇題數：0 | 申論題數：17

試卷資訊

所屬科目：國營事業◆1.資料庫及資料探勘 2.程式設計

選擇題 (0)

申論題 (17)

一、【表 1】列出某關聯式資料庫 3 個資料表【Students】、【Takes】及【Courses】，各自有 3 個欄位，資料表與欄位都以英文命名，標示底線的欄位為主鍵，例如：【Takes】的主鍵是{Sid, Cno}。假設所有欄位都不存在空值(NULL)，請以此資料庫為目標，依序撰寫滿足下列問題需求的 SQL 查詢。(5 題，每題 4 分，共 20 分)

(一)假設任 2 位教師或導師的姓名皆不相同，請使用 INTERSECT 集合運算撰寫 SQL 查詢，找出所有同時擔任導師的教師姓名。
(二)同上題，請改用 IN 子查詢撰寫 SQL 查詢，找出所有同時擔任導師的教師姓名。
(三)延續子題(一)假設，請使用 GROUP BY 分組運算撰寫 SQL 查詢，找出修習 Jessica 老師所教授之所有課程的學生學號及姓名。
(四)延續子題(一)假設，假設不同學號的學生可能有相同姓名，請使用 JOIN 連接運算撰寫 SQL 查詢，找出與姓名為 Julie 的學生具有相同導師之學生學號及姓名，姓名為 Julie 的學生亦包含在查詢結果中。
(五)同上題，請改用 IN 子查詢撰寫 SQL 查詢，找出與姓名為 Julie 的學生具有相同導師之學生學號及姓名，姓名為 Julie 的學生亦包含在查詢結果中。
二、【表 2】列出交易資料集【Set A】及【Set B】出現項目 X 和項目 Y 的共現頻率表 (contingency table)，計算項目集 XY 的支持度(support)、提升度(lift)與 Phi 相關係數 ($\phi$coefficient)等評估指標的公式如下：

$$\text{Support}(X, Y) = P(X \cap Y)$$

$$\text{Lift}(X, Y) = P(X \cap Y) / P(X)P(Y)$$

$$\phi\text{coefficient}(X, Y) = (P(X \cap Y)P(\neg X \cap \neg Y) P(X \cap \neg Y)P(\neg X \cap Y)) / \sqrt{P(X)P(\neg X)P(Y)P(\neg Y)}$$

請回答下列問題：(3 題，每題 5 分，共 15 分)

(一)針對交易資料集【Set A】計算 XY 的提升度與 Phi 相關係數，比較 2 個指標所反映項目 X 與項目 Y 的關係，並明確說明各數值大小代表的意義。
(二)針對交易資料集【Set B】計算 XY 的支持度與提升度，並根據 2 個指標說明項目 X 與項目 Y 所呈現的關係。
(三)比較交易資料集【Set A】及【Set B】所算出的指標，分別說明 3 個指標數值的異同及其意義，並據此判斷項目 X 與項目 Y 的關聯程度，回答時必須引用各指標的數值。
三、給定一維座標表示的 8 個資料點：8、12、2、1、3、4、6、16，任 2 點距離定義為座標相減的絕對值。請回答下列問題：(3 題，每題 5 分，共 15 分)

(一)給定 2 個初始群中心(initial centroids)為座標 1 與 16，請採用 Kmeans 分群法將這些資料點分成 2 群，反覆進行分群與群中心更新，直到沒有任何資料點改變所屬分群為止。
(二)依據上題的分群結果，分別計算座標 1 與 16 之資料點的輪廓係數(Silhouette coefficient)，並說明其數值所代表的分群意義。
$$\text{Silhouette coefficient } S(x) = (b(x) a(x)) / \max \{a(x), b(x)\}$$

$a(x)$ = 資料點 $x$ 與同一群中其他資料點的平均距離，

$b(x)$ = 資料點 $x$ 與其他各群資料點之平均距離中的最小值。

(三)計算每個資料點的輪廓係數(Silhouette coefficient)，再計算各分群的平均輪廓係數，並根據資料分布解釋所得結果。
四、以下為 C 語言撰寫之程式碼片段，請回答下列問題：(2 題，共 15 分)

| | 【程式碼片段一】 | | 【程式碼片段二】 |
| | | | |
| 01 | #include | 01 | int score = 2; |
| 02 | void calculate() { | 02 | int result = 10; |
| 03 | static int a = 5; | 03 | switch (score) { |
| 04 | int b = 5; | 04 | case 1: |
| 05 | a += 10; | 05 | result += 5; |
| 06 | b += 10; | 06 | case 2: |
| 07 | printf("(%d,%d) ", a, b); | 07 | result += 10; |
| 08 | } | 08 | case 3: |
| 09 | int main() { | 09 | result += 20; |
| 10 | calculate(); | 10 | break; |
| 11 | calculate(); | 11 | default: |
| 12 | calculate(); | 13 | result += 30; |
| 13 | printf("\n"); | 13 | } |
| 14 | return 0; | 14 | printf("%d\n", result); |
| 15 | } | 15 | |

(一)請寫出【程式碼片段一】執行完畢後的螢幕輸出結果。(7 分)
(二)請寫出【程式碼片段二】執行完畢後的螢幕輸出結果。(8 分)
五、初始為空的最小堆積樹(MinHeap)，給定以下 6 個整數的資料數列：45, 32, 28, 15, 8, 25。請回答下列問題：(3 題，共 15 分)

(一)依序將這 6 個數字插入該 MinHeap 中，請畫出插入這 6 個數字後，最終完成的 MinHeap 樹狀結構。(6 分)
(二)承上題，將 MinHeap 樹根的最小數字(Root)移除。在移除該數字後，依據 MinHeap 的重整規則(Heapify)進行調整，請畫出重整完成後，最終的 MinHeap 樹狀結構。(6 分)
(三)透過不斷重複「移除 MinHeap 根節點的最小數字並進行重整」的動作，依序取出的數字即可排列成一個由小到大的數列，這種排序演算法稱為堆積排序(Heap Sort)。請問在資料筆數為 N 的情況下，Heap Sort 的最佳(Best Case)、最壞(Worst Case)與平均(Average Case)時間複雜度分別為何？(3 分)
六、某半導體代工廠希望分析每日產能是否能穩定達到生產目標。請撰寫一函式，計算每日產能達到或超過目標值的最長連續天數，並註明所使用的程式語言。(20 分)

函式介面如下：

int maxDays(int Production[], int N, int Target)

輸入參數：

1. Production：整數陣列，記錄連續 N 天的每日產能
2. N：整數，表示陣列 Production 的長度
3. Target：整數，表示每日目標產能

回傳值：

回傳一個整數，表示 Production 中連續「產能大於或等於 Target」的最大天數

範例：

Production = [1200, 800, 1500, 1300, 900, 1100, 1400, 1600]

N = 8

Target = 1000

輸出：3

說明：

產能大於或等於 1000 的連續區段為：

➤ [1200]：連續 1 天
➤ [1500, 1300]：連續 2 天
➤ [1100, 1400, 1600]：連續 3 天

因此，最大連續天數為 3