111 年 國立成功大學資訊管理研究所甲組《計算機概論》

📄 試題原卷 免費註冊後即可對照原始考卷 PDF免費註冊

第 A-1. 題

A-1. Multiple choice questions: (choose only ONE answer for a question; 3% for each question)
(1) What kind of operating system programs will be permanently resident in memory?
(A) Compiler programs.
(B) Supervisory programs.
(C) Timing programs.
(D) Gyroscope sensor programs.
(E) Spooling programs.

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對作業系統核心功能的理解。作業系統中,負責管理硬體資源、處理系統呼叫、並提供基本服務的程式,通常會常駐於記憶體中,以便隨時被 CPU 存取。

(A) 編譯器 (Compiler programs) 是應用程式,用於將原始碼轉換為機器碼,執行時載入記憶體,結束後即可移除。
(B) 監督程式 (Supervisory programs),又稱核心 (Kernel) 或系統核心,是作業系統的核心部分,負責管理 CPU、記憶體、I/O 裝置等,是作業系統最基礎且重要的部分,因此會永久駐

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-1. 題

(2) The feature of an object-oriented programming language that allow the instances of different objects to respond to the same message differently is called
(A) portability.
(B) inheritance.
(C) messaging.
(D) encapsulation
(E) polymorphism

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對物件導向程式設計 (Object-Oriented Programming, OOP) 中多型 (Polymorphism) 概念的理解。

物件導向程式設計的四大特性為:封裝 (Encapsulation)、繼承 (Inheritance)、多型 (Polymorphism) 和抽象 (Abstraction)。

(A) 可攜性 (Portability) 指的是程式能夠在不同環境下執行的能力。
(B) 繼承 (Inheritance) 允許一個類別繼承另一個類別的屬性和方法,實現程式碼重用。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-1. 題

(3) A(n) class is used take the responsibility of instantiating a group of utilities classes (e.g., data access classes).
(A) factory
(B) adapter
(C) domain
(D) entity
(E) controller

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對設計模式 (Design Patterns) 中 Factory Pattern 的理解。

在物件導向設計中,有時需要建立一個物件,而這個物件又需要建立其他一系列的輔助物件(utility classes)。Factory Pattern 的主要目的是將物件的建立邏輯封裝起來,使得客戶端程式不需要知道如何具體地創建這些物件。

(A) Factory (工廠類別):這類別的職責就是負責建立(instantiate)其他物件,特別是當建立過程比較複雜,或者需要根據不同條件創建不同類型的物件時,Factory Pattern 就很有用。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-1. 題

(4) A backup facility (e.g., an office or a warehouse) that has the necessary components (e.g., space, power, cooling equipment, and Internet connection) of a computer facility, but does not have any computer equipment installed is called a
(A) service site
(B) warm site
(C) cold site
(D) reference site
(E) hardware site

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對災難復原 (Disaster Recovery) 中不同備援站點 (Backup Sites) 的分類與理解。

備援站點的類型主要根據其準備程度和恢復速度來區分:

  • Hot Site (熱站點):包含所有必要的硬體、軟體、資料和通訊設施,可以立即接管營運。
  • Warm Site (溫站點):包含硬體設備和網路連接,但軟體和資料需要從備份還原,恢復時間比 Hot Site 長。
  • Cold Site (冷站點):僅提供基礎設施,如空間、電力、空調和網路連接,但沒有安裝任何硬體設備。所有硬體、軟體和資料都需要從頭購買、安裝和配置。恢復時間最長。
🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-1. 題

(5) Using
"data diddling."
is one of the most effective protective measures to counteract the network attack strategy of
(A) digital certificates

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念
本題考查的是「防護措施 ↔ 攻擊策略」的配對概念。要能判斷某一防護手段(data diddling)最能抵禦哪一種網路攻擊手法,必須先了解 data diddling 的原理與目的,再對照常見的攻擊類型,找出最符合的配對。


解題步驟

  1. 什麼是 data diddling?

    • Data diddling(資料擾亂)是指在資料傳輸或儲存過程中,故意對資料內容施以微小、難以偵測且不影響正常使用的變更。常見做法包括在資料中加入隨機噪聲、改變校驗碼或在訊息中插入偽資訊。其目的在於:
      • 降低資料被竊取後的可用性(即使竊取者取得資料,也因被「擾亂」而難以直接利用)。
      • 偵測未授權的資料存取(擾亂的痕跡會在驗證階段顯示異常)。
  2. data diddling 能防哪類攻擊?

    • 防護焦點:保護 資料完整性 與 防止資料被直接利用。
    • 典型對應的攻擊策略:
      • 數位憑證(digital certificates) 被盜或偽造後,攻擊者可利用憑證進行 偽裝(impersonation)或 中間人攻擊。若對傳輸的憑證資料施以 data diddling,竊取的憑證會因被擾亂而失效,從而削弱攻擊者利用憑證的可行性。
      • 其他如 純粹的封包截取(packet sniffing) 或 流量分析 則較少依賴資料內容本身,而是關注元資料;對此類攻擊,data diddling 的效益較低。
  3. 為什麼 data diddling 對 digital certificates 有效?

    • 憑證內容(公鑰、簽章等)若被竊取且未經擾亂,攻擊者可直接在偽造的伺服器上使用,完成 Man‑in‑the‑Middle 或 偽裝。
    • 透過 data diddling,在憑證被儲存或傳送前加入不可預測的雜訊或變更校驗碼,使得竊取者取得的憑證在驗證階段會失敗。
    • 此外,合法使用者在驗證時仍能根據事先共享的密鑰或協議還原正確資料,故不影響正常服務。
  4. 結論

    • 在題目所給的選項中,唯一能與 data diddling 的防護特性相匹配的攻擊策略即 digital certificates(數位憑證)相關的竊取與偽造行為。

【答案】

(A) digital certificates


補充說明

  • 若題目原本提供多個選項(例如:A. digital certificates、B. packet sniffing、C. denial‑of‑service、D. traffic核心觀念
    本題考查的是「防護措施 ↔ 攻擊策略」的配對概念。
🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-1. 題

(6) Among the basic approaches to utilizing the spectrum available to the wireless local area networks,
____ spreads the data over multiple carrier frequencies to transmit the data in parallel, while those multiple carrier frequencies are spaced to ensure that they do not interfere with one another.
(A) frequency-hopping spread spectrum (FHSS)
(B) direct sequence spread spectrum (DSSS)
(C) service se identifier (SSID)
(D) orthogonal frequency division multiplexing (OFDM)
(E) carrier sense multiple access with collision avoidance (CSMA/CD)

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查無線區域網路(WLAN)中的展頻技術與多載波調變技術,關鍵在於辨認題幹描述:

  • 將資料分散到多個載波頻率上。
  • 多個載波可同時平行傳輸資料。
  • 各載波頻率彼此保持正交,因此能有效避免相互干擾。

符合上述描述的是正交分頻多工(Orthogonal Frequency Division Multiplexing, OFDM)。

OFDM 將高速資料流分割成多個低速子資料流,分別調變到許多彼此正交的子載波上。雖然這些子載波的頻譜可能部分重疊,但因為彼此正交,在接收端仍可分離各子載波的訊號。

解題方法

判斷本題可抓住三個關鍵詞:

  1. 「multiple carrier frequencies」:使用多個載波頻率。
  2. 「transmit the data in parallel」:資料以平行方式傳送。
  3. 「spaced to ensure that they do not interfere」:載波彼此正交,以降低相互干擾。

OFDM 的核心概念正是將資料分成多條平行的子通道,並以正交子載波傳送。其子載波間隔通常設計為:

Δf=1Tu\Delta f = \frac{1}{T_u}

其中:

  • Δf\Delta f 為相鄰子載波的頻率間隔。
  • TuT_u 為有效符號時間。

此頻率間隔可使不同子載波在取樣判斷時彼此正交,因此即使頻譜互相重疊,也不會造成理想情況下的載波間干擾。

選項分析

(A) frequency-hopping spread spectrum(FHSS)

FHSS 是跳頻展頻技術。傳送端會依照預定的跳頻序列,在許多不同頻率間快速切換傳輸。

其重點是「隨時間改變傳輸頻率」,而不是同一時間使用多個子載波平行傳輸資料。因此不符合題幹描述。

(B) direct sequence spread spectrum(DSSS)

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-1. 題

(7) ____ is an effective data storage structure when every record in the table has to be retrieved (in any order) every time the table is accessed.
(A) Hasp
(B) Heap
(C) Bitmap
(D) ISAM
(E) B+-Tree.

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對資料庫儲存結構(索引結構)的理解,特別是何種結構適合隨機存取大量資料。

題目要求的是一種儲存結構,它能有效地在「每次存取表格時,以任意順序檢索所有記錄」。這意味著該結構不依賴於特定的排序順序來快速定位記錄,而是能夠直接或透過簡單的查找機制存取所有記錄。

我們來分析各選項:
(A) Hasp:這似乎是一個拼寫錯誤或不常見的術語,可能與 Hasp-key (硬體鎖) 有關,與資料儲存結構無關。
(B) Heap:在資料庫中,Heap 結構的表格(或稱堆積表)沒有預設的排序順序。記錄是按照插入的順序或由系統決定的順序儲存的。存取所有記錄時,需要掃描整個表格。雖然不是最高效的,但它確實允許以「任意順序」存取所有記錄,因為它沒有強制排序。
(C) Bitmap (位圖索引):位圖索引非常適合於具有低基數(distinct values 很少)的欄位,它使用位元陣列來表示欄位值是否存在。雖然查詢時可以快速過濾,但它本身不是一個記錄的儲存結構,而是建立在現有記錄之上的索引。要檢索所有記錄,仍需配合底層的資料儲存結構。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-2. 題

A-2. Programming and modeling questions:
(1) Explain what an "association class" is for and give an example using the format of a class diagram based on the Unified Modeling Language (UML) convention. (8%)

登入後即可作答並保存紀錄。

這一題的完整詳解

關聯類別 (Association Class)

定義與用途:
關聯類別 (Association Class) 是一種在 UML 類別圖中,用來描述兩個類別之間關聯 (Association) 本身所具有的屬性或操作的類別。簡單來說,當兩個類別之間的關聯關係,除了簡單的連接之外,還需要承載額外的資訊時,就可以引入關聯類別。

想像一下,兩個類別 A 和 B 之間存在一個關聯。如果這個關聯本身需要儲存一些資訊,例如一個時間戳記、一個權重、一個狀態,或者需要執行某些與這個關聯相關的操作,那麼我們就可以將這些資訊封裝成一個新的類別,並將其與 A 和 B 的關聯連接起來。這個新的類別就是關聯類別。

關聯類別的出現,通常是因為:

  1. 關聯需要屬性:例如,在「學生」和「課程」之間,有一個「選課」的關聯。這個「選課」本身可以有屬性,比如學生的「成績」(grade)、選課的「日期」(date)。
  2. 關聯需要操作:例如,「訂單」和「商品」之間的「訂購項目」(order item) 關聯,可能需要執行「計算該訂購項的總價」的操作。
  3. 關聯需要參與者 (Participant):有時候,關聯本身可能需要進一步的細化,或者需要表示關聯的某些方面,而這些方面不屬於任何一個單獨的類別。

UML 表示法:
在 UML 類別圖中,關聯類別通常表示為一個類別框,它通過虛線連接到表示關聯的線段上。

範例:
考慮「學生」(Student) 和「課程」(Course) 兩個類別,以及它們之間的「選課」(Enrollment) 關聯。

一個學生可以選修多門課程,一門課程可以被多個學生選修,這是一個多對多 (many-to-many) 的關聯。
如果我們只想表示「學生選修了課程」,那麼一個簡單的多對多關聯就足夠了。
但是,如果我們需要記錄每個學生在特定課程上的「成績」(grade) 和「選課日期」(enrollmentDate),那麼這個「選課」本身就有了額外的資訊。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-2. 題

(2) Please write a method (using pseudo code or any programming language that you want) along with the SQL queries needed that allows us to retrieve the information (including movieID, movieTitle, yearReleased, studio, and producer) of all the videos that are directed by a particular director (e.g. Christopher Nolan) and present all the information retrieved on the screen. You can assume that the database connectivity has been established. Additionally, four tables, including Video (including movieID, movieTitle, yearReleased, directorID, studioID, and producerID), Studio (including studioID and studioName), Producer (including producerID, producerFirstName, and producerLastName), and Director (including directorID, directFirstName, and directorLastName), are used to store all those pieces of information of the videos in the relational database. Create and use the data attributes that are not listed in the questions if you find it necessary. (12%)

登入後即可作答並保存紀錄。

這一題的完整詳解

此題要求編寫一個方法(可使用偽代碼或任一程式語言),並配合 SQL 查詢,從關聯式資料庫中擷取特定導演執導的影片資訊,並顯示在螢幕上。

資料庫結構:

  • Director 表:
    • directorID (Primary Key)
    • directFirstName
    • directLastName
  • Video 表:
    • movieID (Primary Key)
    • movieTitle
    • yearReleased
    • directorID (Foreign Key referencing Director)
    • studioID (Foreign Key referencing Studio)
    • producerID (Foreign Key referencing Producer)
  • Studio 表:
    • studioID (Primary Key)
    • studioName
  • Producer 表:
    • producerID (Primary Key)
    • producerFirstName
    • producerLastName

目標:
擷取特定導演(例如 Christopher Nolan)執導的影片資訊,包括 movieID, movieTitle, yearReleased, studioName (從 Studio 表取得), 和 producerFirstName, producerLastName (從 Producer 表取得)。

解題思路:

  1. 找到導演的 directorID:首先需要根據導演的名字(例如 "Christopher Nolan")在 Director 表中查詢到對應的 directorID。
  2. 查詢影片資訊:使用找到的 directorID,在 Video 表中找出所有符合條件的影片。
  3. 連結其他表格:為了獲取 studioName 和 producer 的名字,我們需要將 Video 表與 Studio 表和 Producer 表進行連接(JOIN)。
  4. 顯示結果:將查詢到的所有影片資訊(movieID, movieTitle, yearReleased, studioName, producerFirstName, producerLastName)輸出到螢幕。

SQL 查詢語句:

我們需要兩個步驟:
首先,找到目標導演的 ID。
然後,基於導演 ID,連接 Video, Studio, Producer 表,並篩選出目標導演的影片。

查詢 1:找到導演 ID

SELECT directorID
FROM Director
WHERE directFirstName = 'Christopher' AND directLastName = 'Nolan';

假設這個查詢返回 directorID = 101。

查詢 2:獲取影片資訊(使用 JOIN)
我們可以將上述兩個步驟合併成一個 SQL 查詢,透過 JOIN 操作直接完成。

SELECT
    V.movieID,
    V.movieTitle,
    V.yearReleased,
    S.studioName,
    P.producerFirstName,
    P.producerLastName
FROM
    Video AS V
JOIN
    Director AS D ON V.directorID = D.directorID
LEFT JOIN -- 使用 LEFT JOIN 以確保即使 Studio 或 Producer 資訊缺失,影片資訊也能顯示
    Studio AS S ON V.studioID = S.studioID
LEFT JOIN
    Producer AS P ON V.producerID = P.producerID
WHERE
    D.directFirstName = 'Christopher' AND D.directLastName = 'Nolan';

偽代碼方法:

這裡我們假設有一個 DatabaseManager 類別,它提供了一個方法來執行 SQL 查詢並返回結果。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 A-2. 題

(3) Please write a method (using pseudo code or any programming language that you want) that performs the task of "binary search" using a "recursive" approach. (9%)

登入後即可作答並保存紀錄。

這一題的完整詳解

此題要求編寫一個使用遞迴 (recursive) 方法實現二分搜尋 (binary search) 的程式。

二分搜尋 (Binary Search)
二分搜尋是一種在有序陣列 (sorted array) 中查找特定元素的搜尋演算法。它的基本思想是:

  1. 檢查中間的元素。
  2. 如果中間元素是目標值,則搜尋成功。
  3. 如果目標值小於中間元素,則在陣列的左半部分繼續搜尋。
  4. 如果目標值大於中間元素,則在陣列的右半部分繼續搜尋。
  5. 重複這個過程,直到找到目標值,或者搜尋範圍為空(表示目標值不存在)。

遞迴方法 (Recursive Approach)
遞迴是指一個函數在其定義中直接或間接呼叫自身。對於二分搜尋,遞迴的實現會涉及:

  • 一個基本情況 (base case),用於終止遞迴(例如,搜尋範圍為空,或找到目標值)。
  • 遞迴步驟 (recursive step),將問題分解為更小的子問題,並呼叫自身來解決這些子問題。

偽代碼實現:

我們需要一個函數,它接收一個有序陣列、目標值,以及當前搜尋的範圍(通常用起始索引 low 和結束索引 high 表示)。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-1. 題

Part B
B-1 Multiple Choice Question: Indicate ONE answer choice that best completes the statement or answers the question. (3% for each question)

  1. In a(n)
    database, query data is collected from one or more shards of a distributed database, then processed by the database management system (DBMS) to create the query response.
    (A) SQL
    (B) NoSQL
    (C) relational
    (D) OLAP
    (E) Cloud

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念
本題測驗的是 分散式資料庫的查詢處理流程。在分散式資料庫中,資料會被切分成多個 shard(分片),每個分片負責儲存整體資料的子集合。當使用者下達查詢時,DBMS 必須先從一個或多個相關分片取得所需資料,然後在 查詢處理 (query processing) 階段進行過濾、投影、連接、聚合等運算,最終組合成完整的查詢回應。此過程是大多數 SQL(關聯式)資料庫 在分散式部署時的典型行為。

解題方法

  1. 先辨識題幹描述的關鍵步驟:

    • 「從一或多個 shard 取得查詢資料」
    • 「由 DBMS 處理並產生回應」
  2. 再比對選項的概念與上述步驟的相容性:

    • SQL:支援完整的查詢語言與複雜查詢處理,且在分散式環境(如分片、平行查詢)仍由 DBMS 完成資料的收集與統合。
    • NoSQL:多採鍵值或文件模型,查詢功能較簡化,往往不會經過全功能的 DBMS 統一處理。
    • relational:描述資料模型(關聯模型),未必涵蓋「由 DBMS 整合多個 shard」的具體實作細節。
    • OLAP:屬於分析型資料庫,重點在多維度聚合與報表,概念上也會從多個資料來源取資料,但題幹的「query processing」指向一般的資料查詢(SQL)而非分析專屬的多維度運算。
    • Cloud:僅指部署環境,與查詢流程無直接關聯。

    由此可排除 B、C、D、E,只剩 A (SQL) 為唯一符合描述的選項。

選項分析

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-1. 題

refers to an industry standard used to support the communication among equipment from several vendors and provide network flexibility.
(A) WAN
(B) LAN
(C) RAN
(D) ORAN
(E) WLAN

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對網路標準和技術的理解。題目要求找出一個「行業標準」,用於支援「多個供應商設備之間的通訊」,並提供「網路彈性」。

我們來分析各個選項:
(A) WAN (Wide Area Network, 廣域網路):WAN 是一種網路連接,覆蓋大範圍區域(如城市、國家或全球)。它本身不是一個特定的行業標準,而是網路的一種分類。
(B) LAN (Local Area Network, 區域網路):LAN 是一種覆蓋小範圍區域(如建築物、辦公室)的網路。同樣,LAN 也是一種網路分類,而不是一個具體的行業標準。
(C) RAN (Radio Access Network, 無線接入網路):RAN 是行動通訊網路的一部分,負責連接終端設備(如手機)到核心網路。它涉及無線通訊的標準,但通常與特定行動通訊技術(如 4G, 5G)相關。
(D) ORAN (Open Radio Access Network, 開放式無線接入網路):ORAN 是一個相對較新的概念,它倡導開放、標準化的介面,允許不同供應商的硬體和軟體組件在 RAN 中協同工作。這使得電信營運商可以混合使用來自不同供應商的設備,從而提高網路彈性,降低成本,並加速創新。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-1. 題

is a compilation of binary data stored in a single DB field.
(A) Memo
(B) Integer
(C) BLOB
(D) Logical
(E) Record

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對資料庫欄位 (field) 資料類型的理解。題目要求找出一個能儲存「二進位資料編譯 (compilation of binary data)」在「單一資料庫欄位」中的資料類型。

我們來分析各個選項:
(A) Memo:Memo 欄位通常用於儲存較長的文字字串,類似於 Text 或 Long Text。它主要用於儲存文字資訊,而不是二進位資料。
(B) Integer:Integer (整數) 用於儲存數值,通常是 32 位元或 64 位元的整數。它儲存的是數字,不是二進位資料。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-1. 題

  1. To deal with huge amounts of data and computation involved in Big Data,
    used software utilities.
    (A) Hadoop
    (B) GIMP
    (C) KeePass
    (D) openSIS
    (E) PuTTY
    is a set of frequently

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對大數據 (Big Data) 相關技術和軟體的認識。題目詢問哪一個軟體工具集合(utility)常用於處理大數據的龐大資料量和計算需求。

我們來分析各個選項:
(A) Hadoop:Apache Hadoop 是一個開源框架,專門為分散式儲存和分散式處理大數據而設計。它包含 Hadoop Distributed File System (HDFS) 用於儲存,以及 MapReduce 或 Spark 等計算框架用於處理。Hadoop 是處理大數據最常用和最基礎的軟體集合之一。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-1. 題

other users.
refers to a virtual space that users can access and immerse via digital devices and interact with
(A) Multiverse
(B) Originverse
(C) Xenoverse
(D) Zenverse
(E) Metaverse

登入後即可作答並保存紀錄。

這一題的完整詳解

此題考驗對新興數位概念的理解,特別是關於虛擬空間的術語。題目描述的「虛擬空間,用戶可以透過數位設備存取、沉浸其中並與其他用戶互動」。

我們來分析各個選項:
(A) Multiverse (多元宇宙):在物理學或科幻作品中,指由無數個宇宙組成的集合。這與虛擬空間的互動性無關。
(B) Originverse:這不是一個廣泛使用的標準術語,可能指某個特定產品或概念。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-2. 題

B-2 Programming and Short answer

  1. Bubble Sort, Selection Sort, and Insertion Sort are basic sorting algorithms to sort numbers. To sort 9, 2, and 4, following table can be used to demonstrate the steps of an ascending bubble sort by only showing swapping steps:
    Tablel Bubble Sort steps
    Bubble sorting
    924 (Original)
    294
    249 (Sorted)
    Considering following numbers: 75, 29, 47, 3, and 12
    Using the table formation above (Table 1) and only showing the steps with swapping (or insertion), please sort the numbers (75, 29, 47, 3, and 12) ascendingly by
  1. Selection Sort (5%)
  2. Insertion Sort (Please only show the insertion steps, 5%)
  3. Bubble Sort (5%)
    note 1: Please draw tables on your answer sheet for each sorting algorithm
    note 2: For each table, please clearly indicate which algorithm is used
    note 3: in-place sorting

登入後即可作答並保存紀錄。

這一題的完整詳解

此題要求對給定的數字序列 75, 29, 47, 3, 12 使用三種基本排序演算法(選擇排序、插入排序、氣泡排序)進行升序排序,並以表格形式展示排序過程中的關鍵步驟(交換或插入)。

給定數字序列: 75, 29, 47, 3, 12


1) Selection Sort (選擇排序)

核心思想:
選擇排序是一種簡單的排序演算法。其餘數列中,找到最小(或最大)的元素,將其與已排序部分的後一個元素交換位置。重複這個過程,直到所有元素都排序完成。

步驟展示:
我們需要找到當前未排序部分的最小元素,並將其與未排序部分的開頭元素交換。

Table: Selection Sort Steps

PassArray State (before swap)Action (Find min & Swap)Array State (after swap)
Initial[75, 29, 47, 3, 12]-[75, 29, 47, 3, 12]
Pass 1[75, 29, 47, 3, 12]Min is 3 at index 3. Swap 75 and 3.[3, 29, 47, 75, 12]
Pass 2[3, 29, 47, 75, 12]Min is 12 at index 4. Swap 29 and 12.[3, 12, 47, 75, 29]
Pass 3[3, 12, 47, 75, 29]Min is 29 at index 4. Swap 47 and 29.[3, 12, 29, 75, 47]
Pass 4[3, 12, 29, 75, 47]Min is 47 at index 4. Swap 75 and 47.[3, 12, 29, 47, 75]
Sorted[3, 12, 29, 47, 75]-[3, 12, 29, 47, 75]

說明:

  • Pass 1: 在 [75, 29, 47, 3, 12] 中,最小的是 3,其索引是 3。將 75 (索引 0) 與 3 (索引 3) 交換。陣列變為 [3, 29, 47, 75, 12]。
  • Pass 2: 在 [29, 47, 75, 12] (從索引 1 開始的未排序部分) 中,最小的是 12,其索引是 4。將 29 (索引 1) 與 12 (索引 4) 交換。陣列變為 [3, 12, 47, 75, 29]。
  • Pass 3: 在 [47, 75, 29] (從索引 2 開始的未排序部分) 中,最小的是 29,其索引是 4。將 47 (索引 2) 與 29 (索引 4) 交換。陣列變為 [3, 12, 29, 75, 47]。
  • Pass 4: 在 [75, 47] (從索引 3 開始的未排序部分) 中,最小的是 47,其索引是 4。將 75 (索引 3) 與 47 (索引 4) 交換。陣列變為 [3, 12, 29, 47, 75]。
  • 此時陣列已排序完成。

【答案】(1) 選擇排序結果表格如上。

2) Insertion Sort (插入排序)

核心思想:
插入排序將陣列分為兩部分:已排序部分和未排序部分。它從未排序部分取一個元素,並將其插入到已排序部分的正確位置。

步驟展示:
題目要求僅展示「插入步驟」。這意味著我們關注的是從未排序部分取出元素後,如何在已排序部分找到位置並進行插入(可能涉及元素的移動)。

Table: Insertion Sort Steps

PassCurrent Element to InsertSorted PartUnsorted PartAction (Insert Element)Array State (after insertion)
Initial-[][75, 29, 47, 3, 12]-[75, 29, 47, 3, 12]
Pass 175 (from index 0)[75][29, 47, 3, 12]Insert 75 into empty sorted part.[75, 29, 47, 3, 12]
Pass 229 (from index 1)[75][47, 3, 12]Insert 29 into [75]. Since 29 < 75, shift 75 right. Insert 29 before 75.[29, 75, 47, 3, 12]
Pass 347 (from index 2)[29, 75][3, 12]Insert 47 into [29, 75]. 47 > 29, 47 < 75. Shift 75 right. Insert 47 before 75.[29, 47, 75, 3, 12]
🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 B-2. 題

B-2 Programming and Short answer
2. Matrix Multiplication (10%)
Following is an example of matrix multiplication between 2 square matrices while row=column=2.
A
B
E
F
X
C
D
G
H
AE+BG AF+BH
CE+DG CF+DH
Considering 2 square matrices A and B while row=column=n, please finish the program in the BOX to store
the results of the matrix multiplication between 2 matrices to a new square matrix, Result_Matrix[n][n].
note 1: Assuming A and B are not empty.
note 2: C or C++ are preferable to finish the program.
note 3: You may still use other languages if you think it is clear.
Please copy all program (Italic) below on your answer sheet to answer:
int A[n][n];
int B[n][n];
int Result_Matrix[n][n]={};
int row=n;
int column=n;
for(int i=0; i< row; i++)
{
for(int j=0; j< column; j++)
{
for(int k=0; k< column; k++)
{
}
}
}

登入後即可作答並保存紀錄。

這一題的完整詳解

此題要求完成一個 C/C++ 程式碼片段,實現兩個 n x n 矩陣 A 和 B 的乘法,並將結果儲存在 Result_Matrix[n][n] 中。

矩陣乘法原理:
兩個 n x n 矩陣 A 和 B 的乘積 C (即 C = A × B) 也是一個 n x n 矩陣。矩陣 C 中的元素 CijC_{ij} (位於第 i 列,第 j 行) 是由矩陣 A 的第 i 列與矩陣 B 的第 j 列對應元素相乘後求和得到的。
Cij=∑k=1nAik⋅BkjC_{ij} = \sum_{k=1}^{n} A_{ik} \cdot B_{kj}

程式碼分析:
題目提供了程式碼框架,其中:

  • int A[n][n]; 和 int B[n][n]; 是輸入的兩個 n x n 矩陣。
  • int Result_Matrix[n][n]={}; 是用於儲存結果的 n x n 矩陣,並初始化為全零。
  • int row=n; 和 int column=n; 設置了矩陣的維度。
  • 外層兩個 for 迴圈分別用於遍歷結果矩陣 Result_Matrix 的每一個元素 CijC_{ij} (對應 i 和 j)。
  • 內層的 for 迴圈(由變數 k 控制)用於執行求和 ∑k=1nAik⋅Bkj\sum_{k=1}^{n} A_{ik} \cdot B_{kj}。

填補程式碼:
我們需要在內層 for 迴圈中,計算 Aik⋅BkjA_{ik} \cdot B_{kj} 的值,並累加到 Result_Matrix[i][j] 中。由於 Result_Matrix 已經初始化為零,我們可以逐步累加。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

第 3. 題

  1. What is the Von Neumann architecture? What is the Von Neumann Bottleneck? (10%)

登入後即可作答並保存紀錄。

這一題的完整詳解

馮紐曼架構 (Von Neumann Architecture)

馮紐曼架構,又稱普林斯頓架構 (Princeton Architecture),是由數學家約翰·馮·紐曼 (John von Neumann) 在 1945 年提出的,是現代電腦最基本的設計模型。其核心思想是:

  1. 儲存程式 (Stored-Program Concept):程式指令和資料都儲存在同一個記憶體中。這與早期的電腦設計(如哈佛架構,其程式指令和資料有獨立的記憶體空間)不同。
  2. 指令和資料共享同一匯流排 (Shared Bus):CPU 透過中央處理器 (CPU) 讀取記憶體中的指令和資料,並將處理結果寫回記憶體。CPU、記憶體和輸入/輸出 (I/O) 設備之間透過一組共用的匯流排(包含位址匯流排、資料匯流排和控制匯流排)進行通訊。
  3. 順序執行指令 (Sequential Instruction Execution):CPU 按照程式在記憶體中的順序,一條一條地取出並執行指令。

主要組成部分:

  • 中央處理器 (CPU):負責執行指令,包括算術邏輯單元 (ALU) 和控制單元 (CU)。
  • 記憶體 (Memory):儲存程式指令和資料。
  • 輸入/輸出設備 (I/O Devices):負責與外部世界進行互動。
  • 匯流排 (Bus):連接 CPU、記憶體和 I/O 設備的通訊通道。

優點:

  • 彈性高:程式和資料儲存在同一記憶體中,可以方便地修改程式或將資料作為程式執行(例如,用於自修改程式)。
  • 結構簡單:相較於哈佛架構,硬體設計更為簡潔。

缺點:

  • 馮紐曼瓶頸 (Von Neumann Bottleneck):這是其主要缺點,將在下方詳細說明。

馮紐曼瓶頸 (Von Neumann Bottleneck)

馮紐曼瓶頸是指在馮紐曼架構中,CPU 和記憶體之間通過一個共用的、有限頻寬的匯流排進行通訊,導致 CPU 的處理速度遠快於記憶體傳輸資料的速度,進而限制了整個系統的執行效率。

🔒

後續完整解題步驟與【答案】

免費註冊,享三天全站完整詳解閱覽。

免費註冊

其他考古題