111 年 國立政治大學數位內容碩士學位學程資訊技術組《計算機概論與程式設計》

本題主要考驗對計算機記憶體層級（Memory Hierarchy）的理解，包含各層級的存取速度、與 CPU 的關聯性，以及揮發性（Volatile）與非揮發性（Non-Volatile）的定義。

核心觀念：
計算機系統為了平衡速度、容量和成本，採用了多層次的記憶體結構。速度越快的記憶體，通常容量越小、成本越高，且越靠近 CPU；速度越慢的記憶體，則容量越大、成本越低。

解題步驟：

1. 記憶體層級排序（由快到慢）：
   我們需要根據各儲存裝置的平均存取時間（Response Time）來排序。一般而言，存取時間越短，代表速度越快。

   • Register (暫存器): 速度最快，直接在 CPU 內部，存取時間約為 1 個 CPU 時脈週期。
   • Cache (快取記憶體): 速度非常快，位於 CPU 和主記憶體之間，分為 L1, L2, L3 等級，存取時間約為幾個到數十個 CPU 時脈週期。
   • RAM (Random Access Memory, 隨機存取記憶體): 主記憶體，速度比快取慢，但比輔助儲存快，存取時間約為數十到數百個 CPU 時脈週期（約 10-100 奈秒）。
   • SSD (Solid State Drive, 固態硬碟): 速度比傳統 HDD 快，使用快閃記憶體，存取時間約為數十到數百微秒。
   • HDD (Hard Disk Drive, 硬碟機): 傳統機械式硬碟，存取時間較長，包含尋道時間（Seek Time）和旋轉延遲（Rotational Latency），存取時間約為數毫秒。
   • CD (Compact Disc, 光碟): 屬於光學儲存，存取速度非常慢，通常用於資料備份或軟體發行，存取時間可能在數十到數百毫秒。
   • Magnetic tape (磁帶): 順序存取裝置，速度最慢，用於大量資料的長期備份或歸檔，存取時間可能在數秒到數分鐘。

   因此，由短到長（快到慢）的排序為：
   Register, Cache, RAM, SSD, HDD, CD, Magnetic tape

2. 判斷哪些在 CPU 上，哪些是揮發性／非揮發性：

   • Register (暫存器):

     • 在 CPU 上：是
     • 揮發性/非揮發性：揮發性 (Volatile)

   • Cache (快取記憶體):

     • 在 CPU 上：是 (通常是 L1, L2 內建於 CPU 晶片，L3 可能在 CPU 封裝內或靠近 CPU)
     • 揮發性/非揮發性：揮發性 (Volatile)

   • RAM (隨機存取記憶體):

     • 在 CPU 上：否 (是主機板上的獨立記憶體模組，CPU 透過記憶體控制器存取)

本題考驗對物件導向程式設計（Object-Oriented Programming, OOP）基本概念的理解，包括其四大特性以及成員的可見性（Access Specifiers）。

核心觀念：
物件導向程式設計是一種程式設計範式，它以「物件」為中心，將資料（屬性）和操作（方法）封裝在一起。其四大特性（或稱四大支柱）是其核心思想，而成員的可見性則是為了實現封裝和資訊隱藏的關鍵機制。

解題步驟：

第一部分：OOP 的四大特性（10%）

物件導向程式設計通常被認為有以下四大基本特性：

1. 封裝 (Encapsulation):

   • 描述： 將資料（屬性）和操作（方法）捆綁在一個單一的單元（即物件）中。同時，它也意味著隱藏物件的內部實現細節，只暴露必要的介面給外部存取。
   • 目的： 提高程式的模組化程度，減少耦合，方便維護和修改。外部使用者只需要知道如何使用物件的公開介面，而不需要了解其內部複雜的運作方式。

2. 抽象 (Abstraction):

   • 描述： 關注物件的「是什麼」（What）而不是「如何做」（How）。它透過定義類別（Class）來表示現實世界的概念或物件，類別只暴露必要的行為和屬性，隱藏不必要的複雜性。
   • 目的： 簡化複雜系統，讓開發者專注於高層次的邏輯，降低理解和使用的門檻。例如，開車時，我們只需要知道如何操作方向盤、油門、煞車，而不需要了解引擎內部的運作原理。

3. 繼承 (Inheritance):

   • 描述： 允許一個類別（子類別或衍生類別）繼承另一個類別（父類別或基底類別）的屬性和方法。子類別可以重用父類別的程式碼，並在其基礎上添加新的功能或修改現有功能。
   • 目的： 實現程式碼的重用，減少重複編寫，建立類別之間的層次關係，符合「is-a」的關係（例如，狗「is a」動物）。

4. 多型 (Polymorphism):

   • 描述： 字面意思是「多種形態」。它允許不同類別的物件對相同的訊息做出不同的反應。最常見的多型形式是方法重載（Overloading）和方法覆寫（Overriding）。
   • 目的： 提高程式的靈活性和擴展性。開發者可以編寫通用的程式碼，處理不同類別的物件，而無需知道物件的具體型別。

核心觀念

本題考查作業系統中的「行程生命週期」（Process Life Cycle），重點是：

• 行程從建立到結束會經歷哪些狀態。
• 行程在不同狀態間如何轉移。
• 造成狀態轉移的事件，例如排程、輸入／輸出請求、I/O 完成與行程結束。

標準五狀態模型包含：

1. New：新建立
2. Ready：就緒
3. Running：執行中
4. Waiting／Blocked：等待中／阻塞
5. Terminated／Exit：結束

---

解題方法

繪製流程圖時，先按照行程執行的時間順序排列：

$$\text{New} \rightarrow \text{Ready} \rightarrow \text{Running}$$

行程進入執行狀態後，有三種主要結果：

• 需要等待 I/O 或其他事件：進入 Waiting。
• 被作業系統搶占：回到 Ready。
• 執行完成：進入 Terminated。

Waiting 狀態中的行程，在 I/O 完成或等待事件發生後，回到 Ready，等待 CPU 再次配置。

---

Process Life Cycle Diagram

                         dispatch
                 ┌────────────────────┐
                 │                    ▼
          ┌──────────┐           ┌──────────┐
          │  Ready   │           │ Running  │
          └──────────┘           └──────────┘
             ▲   │                 │   │   │
             │   │                 │   │   │
 I/O complete│   │ dispatch       │   │   │ exit
             │   │                 │   │   ▼
             │   └─────────────────┘   ┌─────────────┐
             │                         │ Terminated  │
             │                         └─────────────┘
             │
      ┌─────────────┐
      │   Waiting   │
      └─────────────┘
             ▲
             │ I/O request /
             │ event wait
             └────────────── from Running

Running ──interrupt / preemption──► Ready

更清楚地列出六個狀態轉移如下：

$$\text{New} \xrightarrow{\text{admit}} \text{Ready}$$ $$\text{Ready} \xrightarrow{\text{dispatch}} \text{Running}$$ $$\text{Running} \xrightarrow{\text{interrupt / preemption}} \text{Ready}$$ $$\text{Running} \xrightarrow{\text{I/O request / event wait}} \text{Waiting}$$ $$\text{Waiting} \xrightarrow{\text{I/O completion / event occurs}} \text{Ready}$$ $$\text{Running} \xrightarrow{\text{exit}} \text{Terminated}$$

---

五種狀態說明

1. New：新建立

行程已被建立，但尚未進入可競爭 CPU 的狀態。作業系統會為它建立 Process Control Block（PCB），並配置必要的資源與管理資訊。

當作業系統允許此行程進入記憶體及就緒佇列後，行程由 New 轉為 Ready。

---

2. Ready：就緒

行程已經具備執行條件，只缺少 CPU。

處於 Ready 的行程通常位於 ready queue 中，由 CPU scheduler 選擇下一個要執行的行程。Ready 不代表正在執行，而是「可以執行但目前尚未取得 CPU」。

---

3. Running：執行中

行程目前獲得 CPU，處理器正在執行其指令。

Running 狀態的行程可能發生三種轉移：

• 時間片用完或遭到更高優先權行程搶占：回到 Ready。
• 發出 I/O 請求或等待某個事件：進入 Waiting。
• 所有指令執行完成：進入 Terminated。

---

核心觀念

本題考查：

1. Fibonacci 數列的遞迴定義。
2. 迭代法與遞迴法的程式設計。
3. 時間複雜度與空間複雜度分析。
4. 遞迴函式呼叫次數的計算。

題目給定：

$$\operatorname{fib}(1)=1,\qquad \operatorname{fib}(2)=1$$

對於 $n\geq 3$：

$$\operatorname{fib}(n)=\operatorname{fib}(n-1)+\operatorname{fib}(n-2)$$

因此：

$$1,1,2,3,5,8,\ldots$$

---

解題方法一：迭代法

迭代法由前兩項逐步計算後續項目，不會重複計算已經求出的 Fibonacci 數。

Pseudocode

Fibonacci_Iterative(n):
    if n <= 0:
        return error

    if n == 1 or n == 2:
        return 1

    previous = 1       // fib(1)
    current = 1        // fib(2)

    for i = 3 to n:
        next = previous + current
        previous = current
        current = next

    return current

以 $n=6$ 為例：

$i$	計算結果
$1$	$1$
$2$	$1$
$3$	$1+1=2$
$4$	$1+2=3$
$5$	$2+3=5$
$6$	$3+5=8$

所以：

$$\operatorname{fib}(6)=8$$

時間複雜度

迴圈從 $3$ 執行到 $n$，共執行 $n-2$ 次。每次迴圈只進行固定次數的加法與指定操作，因此：

$$T(n)=O(n)$$

空間複雜度

程式只使用 previous、current、next 等固定數量的變數，所需額外空間不隨 $n$ 增加：

$$S(n)=O(1)$$

---

解題方法二：遞迴法

遞迴法直接依照 Fibonacci 的數學定義撰寫。

Pseudocode

Fibonacci_Recursive(n):
    if n <= 0:
        return error

    if n == 1 or n == 2:
        return 1

    return Fibonacci_Recursive(n - 1)
           + Fibonacci_Recursive(n - 2)

例如：

$$\operatorname{fib}(6) = \operatorname{fib}(5)+\operatorname{fib}(4)$$

每一個非基底情況都會再產生兩次遞迴呼叫，因此會形成二元遞迴樹。

時間複雜度

令 $T(n)$ 表示計算 $\operatorname{fib}(n)$ 所需的時間。對於 $n\geq 3$：

$$T(n)=T(n-1)+T(n-2)+O(1)$$

若只用上界估計，由於：

$$T(n-1)+T(n-2)\leq 2T(n-1)$$

可得：

$$T(n)=O(2^n)$$

更精確地說，遞迴呼叫數量與 Fibonacci 數列成長率有關：

$$T(n)=\Theta(\varphi^n)$$

其中：

$$\varphi=\frac{1+\sqrt{5}}{2}$$

考試中通常寫成：

$$\boxed{O(2^n)}$$

表示其時間複雜度為指數級。

原因是相同的子問題會被重複計算。例如 $\operatorname{fib}(4)$ 同時會出現在計算 $\operatorname{fib}(5)$ 與其他分支之中。

空間複雜度

遞迴函式的最大呼叫深度為 $n$。例如一路展開：

本題考驗對區塊鏈技術相關新興概念的理解，特別是非同質化代幣（NFT）和元宇宙（Metaverse），以及它們對現代與未來生活的潛在影響。

核心觀念：
NFT 是一種獨一無二的數位資產，其所有權記錄在區塊鏈上，不可分割且不可替代。元宇宙是一個虛擬的、持續存在的、共享的空間，人們可以在其中進行社交、工作、娛樂等活動，通常與虛擬實境（VR）和擴增實境（AR）技術結合。

解題步驟：

第一部分：NFT 的定義與元宇宙的定義

1. 非同質化代幣 (Non-Fungible Token, NFT):

   • 定義： NFT 是一種基於區塊鏈技術的數位資產，每個代幣都具有獨特的識別碼和元數據，使其無法被互換或分割。與比特幣或以太幣等「同質化代幣」（Fungible Token）不同，後者是可以互換的（例如，一個比特幣與另一個比特幣價值相同且可以互換）。
   • 特性：
     • 獨一無二 (Unique): 每個 NFT 都是獨特的，無法複製或替換。
     • 不可分割 (Indivisible): 通常情況下，NFT 不能被分割成更小的單位。
     • 可驗證 (Verifiable): 區塊鏈技術確保了 NFT 的所有權和真實性是公開且可驗證的。
     • 可程式化 (Programmable): 可以透過智能合約（Smart Contract）嵌入各種功能，例如版稅分配。
   • 應用： 主要用於代表數位藝術品、收藏品、遊戲道具、虛擬土地、音樂、影片片段等數位資產的所有權。

2. 元宇宙 (Metaverse):

   • 定義： 元宇宙是一個虛擬的、持久的、共享的數位空間，結合了虛擬實境（VR）、擴增實境（AR）、網際網路和社交媒體等多種技術。它旨在創造一個沉浸式的、互聯互通的虛擬世界，用戶可以透過虛擬化身（Avatar）在其中進行互動、社交、工作、娛樂、交易等活動，就像在現實世界一樣。
   • 特性：
     • 沉浸感 (Immersive): 透過 VR/AR 等技術提供高度的臨場感。
     • 持久性 (Persistent): 元宇宙是持續存在的，不會因為用戶離開而消失。
     • 互通性 (Interoperable): 理想狀態下，用戶的虛擬資產和身份可以在不同的元宇宙平台之間轉移。
     • 經濟系統 (Economy): 擁有獨立的經濟體系，用戶可以創造、擁有、交易商品和服務（常與加密貨幣和 NFT 結合）。
     • 社交性 (Social): 提供豐富的社交互動體驗。

第二部分：NFT 和元宇宙對當前或未來日常生活的影響

NFT 和元宇宙的影響是深遠且多方面的，它們正在或將會重塑我們的生活方式：

1. 數位所有權與價值認可：
   • 影響： NFT 使得數位內容（如藝術、音樂、影片）能夠像實體物品一樣被擁有、交易和收藏，為數位創作者提供了新的收入來源和變現途徑。過去難以確定所有權的數位資產，現在有了明確的證明。

本題考驗對氣泡排序法（Bubble Sort）的理解，包括其演算法原理、如何進行排序，以及其時間與空間複雜度分析。

核心觀念：
氣泡排序是一種簡單的排序演算法。它重複地遍歷待排序的列表，一次比較兩個相鄰的元素，如果它們的順序錯誤就交換它們。這個過程會不斷重複，直到沒有更多的交換發生，表示列表已經排序完成。每輪遍歷都會將當前未排序部分的最大（或最小）元素「冒泡」到其最終位置。

解題步驟：

1. 氣泡排序法 Pseudocode:

   function bubble_sort(array):
       n = length(array)
       // 外層迴圈控制遍歷的輪數
       // 每一輪都會將最大的元素放到最後面
       for i from 0 to n - 2:  // 總共需要 n-1 輪
           // 內層迴圈進行相鄰元素的比較與交換
           // 每一輪比較到 n-1-i 為止，因為後面的元素已經排好序
           for j from 0 to n - 2 - i:
               if array[j] > array[j + 1]:
                   // 兩元素順序錯誤，交換它們
                   swap(array[j], array[j + 1])
       return array
   

   • 優化版本 (Optional Optimization): 可以加入一個旗標（flag）來記錄在某一輪遍歷中是否發生了交換。如果一輪遍歷下來沒有發生任何交換，則表示列表已經完全排序，可以提前結束演算法。

   function bubble_sort_optimized(array):
       n = length(array)
       swapped = true
       // 外層迴圈，直到沒有交換發生
       for i from 0 to n - 2 and swapped:
           swapped = false // 假設本輪沒有交換
           for j from 0 to n - 2 - i:
               if array[j] > array[j + 1]:
                   swap(array[j], array[j + 1])
                   swapped = true // 發生了交換
       return array
   

2. 對陣列 {29, 14, 17, 4, 53, 31} 的排序過程：
   我們使用原始的氣泡排序（未優化版本）來演示。陣列長度 $n=6$。
   原始陣列：{29, 14, 17, 4, 53, 31}

   第一輪 (i=0): 比較並交換 (j 從 0 到 4)

   • {29, 14, 17, 4, 53, 31} -> 比較 29 和 14, 29 > 14, 交換
   • {14, 29, 17, 4, 53, 31} -> 比較 29 和 17, 29 > 17, 交換
   • {14, 17, 29, 4, 53, 31} -> 比較 29 和 4, 29 > 4, 交換
   • {14, 17, 4, 29, 53, 31} -> 比較 29 和 53, 29 < 53, 不交換
   • {14, 17, 4, 29, 53, 31} -> 比較 53 和 31, 53 > 31, 交換
   • {14, 17, 4, 29, 31, 53} -> 第一輪結束，最大元素 53 已在最後。

   第二輪 (i=1): 比較並交換 (j 從 0 到 3)

   • {14, 17, 4, 29, 31, 53} -> 比較 14 和 17, 14 < 17, 不交換
   • {14, 17, 4, 29, 31, 53} -> 比較 17 和 4, 17 > 4, 交換
   • {14, 4, 17, 29, 31, 53} -> 比較 17 和 29, 17 < 29, 不交換
   • {14, 4, 17, 29, 31, 53} -> 比較 29 和 31, 29 < 31, 不交換
   • {14, 4, 17, 29, 31, 53} -> 第二輪結束，第二大元素 31 已在倒數第二位置。

   第三輪 (i=2): 比較並交換 (j 從 0 到 2)

   • {14, 4, 17, 29, 31, 53} -> 比較 14 和 4, 14 > 4, 交換
   • {4, 14, 17, 29, 31, 53} -> 比較 14 和 17, 14 < 17, 不交換
   • {4, 14, 17, 29, 31, 53} -> 比較 17 和 29, 17 < 29, 不交換
   • {4, 14, 17, 29, 31, 53} -> 第三輪結束，第三大元素 29 已在倒數第三位置。

   第四輪 (i=3): 比較並交換 (j 從 0 到 1)

   • {4, 14, 17, 29, 31, 53} -> 比較 4 和 14, 4 < 14, 不交換
   • {4, 14, 17, 29, 31, 53} -> 比較 14 和 17, 14 < 17, 不交換
   • {4, 14, 17, 29, 31, 53} -> 第四輪結束，第四大元素 17 已在倒數第四位置。

   第五輪 (i=4): 比較並交換 (j 從 0 到 0)

   • {4, 14, 17, 29, 31, 53} -> 比較 4 和 14, 4 < 14, 不交換
   • {4, 14, 17, 29, 31, 53} -> 第五輪結束。

   排序完成。最終陣列：{4, 14, 17, 29, 31, 53}

   繪製過程圖示 (Conceptual Drawing):
   可以透過表格或箭頭來表示每一步的交換。

   輪數	比較與交換過程	陣列狀態