108 年 國立政治大學資訊管理學系碩士班資管組《計算機概論》

此題考察客戶端-伺服器（Client-Server）架構與檔案伺服器（File-Server）架構的比較。

客戶端-伺服器架構通常能提供更好的安全性，因為伺服器端可以集中管理權限和資源。同樣地，其擴展性（scalability）也較佳，可以透過增加伺服器或升級伺服器來應對成長的需求。然而，客戶端-伺服器架構通常會產生較高的網路流量，因為所有請求和回應都需要經過網路傳輸。

此題考察 Cookie 的種類及其生命週期。

Cookie 是網站儲存在使用者瀏覽器中的小型資料檔案，用於記錄使用者的資訊或偏好。

• Session Cookie (階段性 Cookie)：這種 Cookie 僅在使用者瀏覽網站期間有效，當使用者關閉瀏覽器時，Session Cookie 就會被刪除。
• Persistent Cookie (永久性 Cookie)：這種 Cookie 會儲存在使用者的電腦上，直到預設的到期日期為止，即使關閉瀏覽器後仍然存在。

核心觀念

• 陣列 (Array) 為一種連續記憶體區塊，元素的存取必須透過索引 (index) 直接定位到記憶體位址。
• 索引必須是離散且可比較大小的類型，以便在編譯期或執行期計算位移量。
• 在主流程式語言（C、C++、Java、C#、Python 等）中，整數型別 (integer) 是唯一符合此需求的基本型別。
• 雜湊式或關聯式結構（如 PHP 的 associative array、JavaScript 的 object）雖允許以字串為鍵，但這些結構不屬於傳統陣列的概念，且在課程教材中通常以「陣列」限定為「整數索引」的資料結構。

解題方法

1. 先確認題目所指的「Arrays」為線性陣列，即每個元素在記憶體中以固定間距排列。
2. 依照陣列的位址計算公式
   $\text{address}(A[i]) = \text{base\_address} + i \times \text{element\_size}$
   其中 $i$ 必須是可直接做算術運算的整數，才能產生合法位址。
3. 判斷四個選項中，哪些類型可以作為 $i$。
   • integer：符合；
   • string、float、double、boolean：無法直接作為位移量，需額外轉換或不支援。
4. 依此排除不符合的選項，找出唯一包含 integer 的答案。

此題考察檔案結構（File Structure）與叢集（Clustering）問題的關聯。

叢集（Clustering）在檔案系統中通常指的是將相關的資料塊（blocks）在物理上盡可能地儲存在磁碟上相鄰的位置。這樣做的好處是可以減少磁頭尋道時間，提高讀取效率，特別是當需要讀取一系列相關的資料時。

• Sequential File (順序檔)：資料按順序儲存，讀取下一筆資料時通常就是磁碟上的下一筆，這與叢集的目標一致。
• Indexed File (索引檔)：使用索引塊來指向實際資料塊。

此題考察關聯式資料庫（Relational Database）的結構。

在關聯式資料庫模型中：

• 表格 (Table)：由列（rows）和欄（columns）組成，用來表示一個實體集合。
• 欄 (Column)：代表實體（例如「學生」）的某個特徵或屬性（例如「學號」、「姓名」、「系所」）。每一個欄都有一個名稱和一個資料型態。
• 列 (Row)：代表實體集合中的一個具體實例（例如「學號為 10701 的張三，就讀資訊管理學系」）。每一列中的值對應於該實體的各個屬性。

核心觀念

SQL 的 LIKE 用來比對字串模式：

• % 代表任意長度的字元序列，也可以是空字串。
• _ 代表恰好一個任意字元。
• 引號內未使用萬用字元的字元都按字面比對，空格也算字元。

所以 LIKE ' a%' 的模式依序是：一個空格、字母 a，接著任意字元序列。

解題方法

拆解模式 ' a%'：

1. 第一個位置必須是空格。
2. 第二個位置必須是 a。
3. % 可比對零個或多個後續字元，所以符合模式的字串至少有「空格＋a」兩個字元。

SELECT * 表示回傳 Products 表中符合條件資料列的所有欄位。

選項分析

此題考察網頁設計中，針對不同裝置螢幕尺寸自動調整內容的技術。

• Responsive Web Design (響應式網頁設計)：指的是網頁能夠自動偵測使用者的螢幕尺寸、平台和方向，並據此自動調整佈局、圖片大小、字體等，以提供最佳的瀏覽體驗。這就是題目所描述的「automatically adjust the content (resize, hide, shrink, or enlarge) to display appropriately relative to the size of the device screen」。

此題考察 XML (Extensible Markup Language) 的特性。

XML 是一種標記語言，設計用於儲存和傳輸資料。它的主要特點包括：

• 人機可讀性 (Human-readable and Machine-readable)：XML 的語法清晰，人類可以輕鬆閱讀和理解，同時也能被機器（程式）輕鬆解析。
• 可擴展性 (Extensible)：XML 允許使用者自定義標記（markup），因此可以為任何類型的資料創建客製化的標記結構。
• 結構化資料 (Structured Data)：XML 強調資料的結構和層次，可以表示複雜的資料關係。
• 資料交換 (Data Exchange)：XML 廣泛用於不同系統之間的資料交換。

選項分析：
a) It generates both machine and human readable data formats：這是 XML 的一個主要優點，所以為真。

此題考察使用者介面（User Interface, UI）的類型。

題目描述的介面允許使用者透過「觸摸（touch）、手勢（gesture）和語音（voice）」等「普通、直觀的行為」來與軟體互動。這種介面旨在模仿人類在現實世界中的互動方式，讓人們能夠以最自然、最直觀的方式使用科技產品。

• Natural User Interface (NUI) (自然使用者介面)：這類介面強調使用人們天生就會的行為（如觸摸、手勢、語音）來與設備互動，而不需要學習複雜的指令或按鈕。例如，觸控螢幕手機上的滑動、捏合手勢，或語音助理的指令。

此題考察「跨平台應用程式」（Cross-platform Application）的定義。

跨平台應用程式是指一個軟體能夠在多種不同的作業系統（如 Windows, macOS, Linux, Android, iOS）上運行，並且通常在不同平台上的行為表現一致。

選項分析：
a) a program that coordinates data sharing among various devices：這描述的是分散式系統或協同作業的應用，不一定是跨平台的。

核心觀念
本題測驗對「網路通訊」層面的概念，尤其是無線區域網路（WAPs）與 TCP/IP 協定族的功能。需要掌握以下定義：

• WAP（Wireless Access Point）：提供無線裝置連接至有線局域網路的橋接裝置，主要作用是將無線訊號轉換為有線訊號，讓 PC 與行動裝置能無線存取網路。
• TCP/IP 協定：由多層協定組成，其中 IP（Internet Protocol） 負責封包的路由與位址尋找，TCP（Transmission Control Protocol） 則負責將資料切割成多個段（segments）並在目的端重新組合，確保可靠傳輸。
• 封包（packet）：在 OSI 模型第 3 層（網路層）或 TCP/IP 的網路層中，資料會被切割成若干個封包，每個封包包含標頭與資料負載。

解題方法
針對選項逐一驗證其敘述是否符合上述概念：

1. 判斷敘述是否描述 WAP 的功能與結構。
2. 判斷敘述是否描述 TCP/IP 的路由或封包處理機制。
   只要找出與事實相違背的描述，即為「NOT true」的選項。

選項分析

• a) WAPs enables PCs and devices to transfer data wirelessly among themselves
  WAP 的本質是 橋接（bridge）或 接取點（access point），它把 無線裝置 連接到 有線網路，但無法直接讓兩台無線裝置之間彼此傳輸資料——資料仍須先經過有線背後的交換機或路由器。若兩台裝置同屬同一個 WAP，實際上是 透過 WAP 轉發，而非「彼此直接傳輸」。

此題考察 XML 文件結構的組成元素。

XML (Extensible Markup Language) 文件有其特定的結構要求：

• Root Element (根元素)：每個有效的 XML 文件必須有一個單一的根元素，它包含了文件中所有的其他元素。
• Elements (元素)：由開始標籤、結束標籤和內容組成，是 XML 的基本構成單元。內容可以是文字、其他元素或兩者皆有。
• Attributes (屬性)：提供關於元素的額外資訊，附加在開始標籤內。
• Data (資料)：XML 文件中的內容通常就是資料，可以是文字、數字或其他標記。

此題考察作業系統中的分頁（Paging）技術。

分頁（Paging）是虛擬記憶體管理的一種技術，其核心思想是將主記憶體（RAM）和輔助儲存（如硬碟）劃分成固定大小的區塊，然後將主記憶體中的程式和資料分頁儲存在硬碟上。當程式需要存取儲存在硬碟上的頁面時，作業系統會將該頁面從硬碟載入到主記憶體中，如果主記憶體已滿，則會將主記憶體中一個不再使用的頁面換出（swap out）到硬碟上，以騰出空間。這個過程就是「交換」（swapping）或「頁面置換」（page replacement）。

選項分析：
a) The technique of dividing data into disk sectors：這是磁碟管理的範疇，將資料劃分成磁區（sector），與分頁無關。

此題考察作業系統中，當分頁（Paging）操作過於頻繁時所產生的現象。

當作業系統花費大量時間在分頁（將資料從硬碟讀入記憶體，或將記憶體資料寫回硬碟）操作上時，這表示系統的虛擬記憶體管理效率低下，CPU 幾乎都在等待 I/O 操作完成，而不是執行實際的程式指令。這種現象稱為「分頁交換風暴」（Paging Thrashing）或簡稱「Thrashing」。

此題考察硬碟分割（Partitioning）的概念。

硬碟分割是指將一個實體硬碟劃分成一個或多個邏輯上的區域，每個區域可以被作業系統視為一個獨立的磁碟機。這樣做的好處包括：

• 安裝多個作業系統：可以在同一台電腦上安裝 Windows、Linux 等不同的作業系統，每個系統安裝在一個獨立的分割區。
• 組織和管理資料：將系統檔案和使用者資料分開儲存，便於備份和管理。
• 提高安全性：將敏感資料放在獨立的分割區，可以更容易地設定權限或進行加密。

選項分析：
a) the hard drive will be divided into distinct drives：這正是硬碟分割的核心目的，將一個物理硬碟劃分為多個邏輯上的「獨立磁碟機」。

核心觀念

• 遞迴函式的時間複雜度可透過遞迴關係式 (recurrence relation) 求得。
• 觀察每一次遞迴呼叫的參數變化量，判斷遞迴深度。
• 常用的遞迴深度判斷法則：若參數每次縮減為原來的常數因子 $c\;(0<c<1)$，則遞迴層數為 $\Theta(\log_{1/c}(\text{初始值})$。

解題方法

1. 分支情形

   int exam (int n, int m, int num) {
       if (n < 30)               // A
           return num = n * m;   // 終止，僅 O(1)
       else if (n < 90)          // B
           return exam (n, m/2);
       else                       // C
           return exam (n/2, m);
   }
   

   • 情形 A：$n<30$ 為基礎情況，執行常數時間 $O(1)$。
   • 情形 B：$30\le n<90$，僅把 $m$ 除以 $2$，遞迴深度取決於 $m$。
   • 情形 C：$n\ge 90$，把 $n$ 除以 $2$，遞迴深度取決於 $n$。

2. 建立遞迴關係式

   • 記 $T(n,m)$ 為 exam 的最壞執行時間。
   • 基礎情況
     $T(n,m)=\Theta(1),\quad n<30.$
   • 若 $30\le n<90$
     $T(n,m)=T\!\left(n,\frac{m}{2}\right)+\Theta(1).$
   • 若 $n\ge90$
     $T(n,m)=T\!\left(\frac{n}{2},m\right)+\Theta(1).$

此題考察嵌套循環的時間複雜度分析。

函數 exam(n, m, cnt) 包含兩個嵌套的 for 循環，以及一個內層的 cnt++ 操作。
外部循環是 for (int i = 0; i < n * m; i++)。這個循環會執行 $n \times m$ 次。
內部有兩個循環：

1. for (int j = n; j > 0; j--) cnt++;
   這個循環對於每一次外部循環（i 的每一次迭代）都會執行 $n$ 次。
   因此，這個循環總共會執行 $(n \times m) \times n = n^2 m$ 次。

2. for (int k = 0; k < i; k++) cnt++;
   這個循環的執行次數取決於外部循環變數 i 的值。
   當 i = 0 時，執行 0 次。
   當 i = 1 時，執行 1 次。
   當 i = 2 時，執行 2 次。
   ...
   當 i = n*m - 1 時，執行 $n*m - 1$ 次。

   這個循環總共執行的次數是：
   $0 + 1 + 2 + \dots + (n \times m - 1)$

此題考察嵌套循環的時間複雜度分析。

函數 exam(n, m, cnt) 包含一個外層循環 for (int i = n * n; i > 0; i--)，以及兩個內層循環。
外層循環從 $n^2$ 開始，遞減到 1。這個循環的總迭代次數是 $n^2$ 次。

內層循環：

1. for (int j = 0; j < n; j++) cnt++;
   這個循環對於外層循環的每一次迭代，都會執行 $n$ 次。
   由於外層循環執行 $n^2$ 次，所以這個循環總共執行 $n^2 \times n = n^3$ 次。

2. for (int k = 0; k < i; k++) cnt++;
   這個循環的執行次數取決於外層循環變數 i 的值。
   外層循環的 i 值從 $n^2$ 開始，遞減到 1。
   當 i = n^2 時，執行 $n^2$ 次。
   當 i = n^2 - 1 時，執行 $n^2 - 1$ 次。
   ...

核心觀念

• AVL 樹是一種自平衡二元搜尋樹，對於每一個節點 $x$，其左子樹與右子樹的高度差（Balance Factor）必須滿足 $|h_{\text{left}}(x)-h_{\text{right}}(x)|\le 1$。
• 給定高度 $h$，最小節點數 $N_{\min}(h)$ 會出現在「高度差恰好為 1」的極端情形。此時樹的結構是「左子樹高度為 $h-1$，右子樹高度為 $h-2$」或相反。
• 依此遞迴關係可得
  $N_{\min}(0)=1,\qquad N_{\min}(1)=2,$
  $N_{\min}(h)=1+N_{\min}(h-1)+N_{\min}(h-2),\; h\ge 2.$
  此遞迴與 Fibonacci 數列相同，只是起始值不同。

解題方法

1. 使用上述遞迴公式從低高度逐層計算至 $h=5$。
2. 計算過程：

此題考察在 AVL 樹（或任何二元搜尋樹）中，以遞減順序遍歷並列印所有奇數值的時間複雜度。

要以遞減順序遍歷一個二元搜尋樹，我們需要執行「反向中序遍歷」（Reverse In-order Traversal）。標準的中序遍歷（左-根-右）會以遞增順序訪問節點。反向中序遍歷（右-根-左）則會以遞減順序訪問節點。

遍歷過程如下：

1. 遞迴地遍歷右子樹。
2. 訪問根節點。
3. 遞迴地遍歷左子樹。

在遍歷過程中，當訪問到一個節點時，我們需要檢查其值是否為奇數。如果是奇數，則將其列印出來。

時間複雜度分析：

• 遍歷整個 AVL 樹需要訪問每一個節點一次。
• 假設樹中有 $N$ 個節點。
• 對於每個節點，我們執行以下操作：
  • 檢查節點值是否為奇數（常數時間 $O(1)$）。

核心觀念

本題考察閾值式人工神經元（perceptron）：

其中 $w_i$ 為連線權重、$x_i$ 為輸入值。將加權總和 $s$ 與神經元內的閾值 $\theta$ 比較：

圖中連線上的數字是權重，神經元圓圈內的數字是閾值。

解題方法

上方輸入已知：上方輸入為 $1$，下方輸入為 $0$，因此：

下方網路的兩個輸入皆為 $1$。

第一個隱藏神經元的閾值為 $0.5$：

此題考察 Java 中物件宣告與初始化。

程式碼定義了一個 Stacks 類別，它實現了 StackTypes 介面（雖然介面內容未提供，但我們可以從類別成員推斷其功能）。
Stacks 類別有三個成員變數：

• int Counter = 0;：一個整數計數器，初始值為 0。
• int CntStopper = 10;：一個整數，表示計數器的上限，初始值為 10。
• int[] StackNew = new int[10];：一個整數陣列，大小為 10。

push 方法用於向堆疊（stack）中添加元素，它會檢查 Counter 是否小於 CntStopper，如果條件滿足，則將新元素放入 StackNew 陣列，並遞增 Counter。

題目要求分析執行 StackTypes Stack; 這一語句後，Counter 的值。
這一語句是宣告一個名為 Stack 的變數，其型別是 StackTypes。
然而，這只是一個「宣告」，並沒有實際創建一個 Stacks 物件，也沒有將其初始化。
在 Java 中，宣告一個物件變數（reference variable）並不會立即創建物件。物件的創建需要使用 new 關鍵字。
例如，Stacks myStack = new Stacks(); 才會創建一個 Stacks 物件。

如果 Stack 是一個介面變數，那麼它必須指向一個實現了 StackTypes 介面的物件。
StackTypes Stack; 這行程式碼僅僅是宣告了一個指向 StackTypes 型別物件的參考變數 Stack。此時，Stack 的值為 null。

由於沒有創建 Stacks 的實例物件，所以其中的成員變數（如 Counter）並沒有被初始化或訪問。
因此，在執行完這一語句後，Counter 的值是未定義的，或者說，根本沒有與 Stack 這個宣告的參考變數相關聯的 Counter。
如果這是一個物件宣告，那麼 Stack 變數的值是 null。
如果我們嘗試訪問 Stack.Counter，將會拋出 NullPointerException。

題目問的是「value of Counter associated with Stack」。
由於 Stack 是一個未初始化的參考變數（值為 null），它並沒有關聯任何 Counter 變數。
Counter 是 Stacks 類別的成員變數，只有在創建 Stacks 物件後才會存在。

所以，在執行 StackTypes Stack; 後，Stack 變數的值是 null。它沒有關聯任何 Stacks 物件，因此也沒有關聯其中的 Counter 成員變數。
此時，Counter 的值是無法獲取的，或者說，不存在一個與 Stack 關聯的 Counter。

嚴格來說，執行 StackTypes Stack; 這條語句本身，並不會直接影響或初始化任何 Counter 的值。
Counter 是 Stacks 類別的成員，只有在創建 Stacks 物件時才被初始化。
StackTypes Stack; 僅僅是宣告了一個指向 StackTypes 的引用變數，其初始值為 null。

如果這是一個宣告，那麼 Stack 的值是 null。
如果題目問的是 Stack 這個參考變數本身的值，那就是 null。
但題目問的是 Counter 的值，並且是「associated with Stack」。

此題考察 Java 中物件方法調用與成員變數的變化。

在前一小題中，我們假設 Stack 被初始化為一個 Stacks 物件的實例，並且 Counter 的初始值是 0。
現在執行 Stack.push(5);。

我們來分析 push 方法的邏輯：

public void push(int NewInputs)
{
    if (Counter < CntStopper)
        StackNew [Counter++] = NewInputs;
}

1. if (Counter < CntStopper)：檢查 Counter 是否小於 CntStopper。

   • 在 Stacks 類別中，Counter 的初始值是 0，CntStopper 的初始值是 10。
   • 所以，第一次執行 push 時，0 < 10 為真。

2. StackNew [Counter++] = NewInputs;：

   • Counter++ 是一個後置遞增操作。這意味著：
     • 首先，使用當前 Counter 的值作為陣列索引。

此題考察 Java 中物件方法調用和陣列索引。

首先，我們需要理解 StackTypes Stackl; 這條語句。
與小題 (a) 類似，這僅僅是宣告了一個 StackTypes 型別的參考變數 Stackl。
如果沒有後續的物件創建（例如 Stackl = new Stacks();），那麼 Stackl 的值是 null。
嘗試在 null 參考上調用方法（如 Stackl.push(100);）會導致 NullPointerException。

但是，在研究所考試中，通常會假設代碼是可執行的，或者存在隱含的物件創建。
讓我們假設 Stackl 被初始化為一個 Stacks 物件的實例。
例如，假設執行了 StackTypes Stackl = new Stacks();。

現在分析 push 方法的調用：
Stacks 類別定義：

• int Counter = 0;
• int CntStopper = 10;
• int[] StackNew = new int[10];

此題考察 Java 中物件方法調用和成員變數的變化，與小題 (c) 類似。

同樣，我們假設 Stack2 被初始化為一個 Stacks 物件的實例。
Stacks 類別定義：

• int Counter = 0;
• int CntStopper = 10;
• int[] StackNew = new int[10];

調用 push 方法的順序和值：

1. Stack2.push(6);
   • Counter 是 0。0 < 10 為真。
   • StackNew[0] = 6;
   • Counter 變為 1。

核心觀念

作業系統的死結（deadlock）是指一組行程彼此等待對方持有的資源，導致所有行程都無法繼續執行。死結成立的必要條件有四項，必須同時具備。

解題方法

依序列出死結的四個必要條件，並說明每項條件描述的資源分配或等待狀態。

1. 互斥（Mutual exclusion）：至少有一種資源一次只能由一個行程使用。其他需要該資源的行程必須等待。
2. 持有並等待（Hold and wait）：行程已持有至少一項資源，同時等待取得其他資源。等待期間不釋放已持有的資源。