政大 114 年資管所（資管組） 計算機概論 參考答案

Normalization：依函數相依把資料表拆分成符合 1NF、2NF、3NF、BCNF 的結構。目的是消除資料重複，避免 insertion／update／deletion anomaly，維持一致性。

Denormalization：刻意把拆開的資料表合併，容許可控的資料重複。目的是減少 JOIN，提升讀取效能。

Star Schema：一張 Fact Table 直接連接多張未正規化的 Dimension Table。

Snowflake Schema：把 Dimension Table 再正規化拆成多層子表。

關鍵差異：維度表是否正規化。Star 的 JOIN 少、查詢快但資料重複多；Snowflake 的 JOIN 多、查詢較慢但較省空間、一致性較易維護。

2.1 ADT 只定義資料可做的操作與其語意，不規定實作；資料結構是實現 ADT 的具體方式，同一 ADT 可有多種實作（如 Stack 可用 array 或 linked list）。

2.2 Inheritance：子類別取得父類別的屬性與方法，並可擴充或覆寫。目的是程式碼重用，並建立 is-a 型別階層。

2.3 Polymorphism：同一個方法呼叫在不同物件上表現不同行為（Overloading、Overriding）。目的是讓呼叫端以統一介面操作不同型別的物件，提升彈性與可擴展性。

• Encoding：把資料轉成另一種表示格式（Base64、UTF-8），可逆、不需金鑰，用於傳輸與儲存的相容性，沒有保密作用。
• Encryption：把資料轉成只有持金鑰者能還原的密文（AES、RSA），可逆、需金鑰，提供機密性。
• Hashing：把任意長度輸入轉成固定長度輸出（SHA-256），單向不可逆，用於完整性驗證與密碼儲存。

差異：Encoding 與 Encryption 可逆，Hashing 不可逆；只有 Encryption 需要金鑰。

4.1 Linear Regression 預測連續數值，輸出不受限，用 MSE；Logistic Regression 做二元分類，以 Sigmoid 把輸出壓到 $(0,1)$ 表示機率，用 Cross-Entropy。主要差異在輸出是否為機率。

4.2 做得出分類器，但不是好方法：

1. $f(\overline{x})$ 可能小於 0 或大於 1，沒有機率意義。
2. MSE 為擬合數值設計，不是為最小化分類錯誤設計。
3. 位在正確側但離邊界很遠的樣本仍被 MSE 當成大誤差，會把迴歸線拉偏，使邊界附近的樣本被錯分。

5.1 Git workflow 是本機的版本控制流程（add、commit、branch、merge）；GitHub workflow 建立在 Git 之上，加入遠端協作（push／pull、Fork、Pull Request、Code Review）。差異在單機版本管理與多人遠端協作審查。

5.2

1. git merge 失敗後，git status 列出衝突檔案。
2. 開啟衝突檔，找到 <<<<<<<、=======、>>>>>>> 標記。
3. 人工決定保留內容，刪除標記。
4. git add <file> 標記為已解決。
5. git commit 完成 merge。

5.3

1. 在 GitHub 對目標 repository 按 Fork。
2. git clone 自己的 fork 到本機。
3. git checkout -b feature 開新分支開發。
4. git commit 後 git push origin feature。
5. 在 GitHub 對原專案發起 Pull Request。
6. 通過 Code Review 與 CI 後，由維護者 Merge 進 main。

6.1 Router。

6.2 Network Layer（第 3 層）。

6.3 TTL 每經過一個 router 減 1，歸零即丟棄並回傳 ICMP Time Exceeded，防止封包在路由迴圈中無限循環。

6.4 不一定。只有 IP 封包才有 IP header；ARP 等非 IP 協定的 frame 沒有。

6.5 把兩台 host 的 IP 各與子網路遮罩做 bitwise AND，網路位址相同即同一子網路。

6.6 Private IP 是 RFC 1918 保留的 10.0.0.0/8、172.16.0.0/12、192.168.0.0/16，只在內部網路有效，用於企業與家用內網；Public IP 全球唯一、可在 Internet 上路由，用於對外服務的主機。不能直接送，Private IP 在公網上無法路由，須經 NAT（由內網主動連出，或設定 port forwarding）。

f(a,b,n) 計算 $a\times b^n$（快速冪）。

def canFinish(n, p):
    indeg = [len(p[i]) for i in range(n)]   # p[i] 為課程 i 的先修課
    out = [[] for _ in range(n)]
    for i in range(n):
        for c in p[i]:
            out[c].append(i)                # 邊的方向：先修課 c -> 課程 i
    q = [i for i in range(n) if indeg[i] == 0]
    done = 0
    while q:
        u = q.pop()
        done += 1
        for v in out[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == n