107 鐵路特考高員三級 資訊處理 程式語言 考古題詳解
第 一 題20 分
Java 程式語言採用 dynamic dispatching。請問下面的 Java 程式輸出為何?並請略加解釋 dynamic dispatching。
import java.lang.*;
class A1 { public void accept(B1 V, C1 W) { System.out.println("1.\n"); V.visit(W, this); }
public void accept(B2 V, C2 W) {
System.out.println("2.\n");
V.visit(W, this);
}
public void accept(B3 V, C3 W) {
System.out.println("3.\n");
V.visit(W, this);
}
}
class A2 extends A1 { public void accept(B1 V, C1 W) { System.out.println("4.\n"); V.visit(W, this); }
public void accept(B2 V, C2 W) {
System.out.println("5.\n");
V.visit(W, this);
}
public void accept(B3 V, C3 W) {
System.out.println("6.\n");
V.visit(W, this);
}
}
class A3 extends A2 { public void accept(B1 V, C1 W) { System.out.println("7.\n"); V.visit(W, this); }
public void accept(B2 V, C2 W) {
System.out.println("8.\n");
V.visit(W, this);
}
public void accept(B3 V, C3 W) {
System.out.println("9.\n");
V.visit(W, this);
}
}
class B1 { public void visit(C1 W, A1 U) { System.out.println("11.\n"); W.inspect(U, this); }
public void visit(C2 W, A2 U) {
System.out.println("12.\n");
W.inspect(U, this);
}
public void visit(C2 W, A3 U) {
System.out.println("13.\n");
W.inspect(U, this);
}
public void visit(C3 W, A3 U) {
System.out.println("14.\n");
W.inspect(U, this);
}
}
class B2 extends B1 { public void visit(C1 W, A1 U) { System.out.println("15.\n"); W.inspect(U, this); }
public void visit(C2 W, A2 U) {
System.out.println("16.\n");
W.inspect(U, this);
}
public void visit(C2 W, A3 U) {
System.out.println("17.\n");
W.inspect(U, this);
}
public void visit(C3 W, A3 U) {
System.out.println("18.\n");
W.inspect(U, this);
}
}
class B3 extends B2 { public void visit(C1 W, A1 U) { System.out.println("31.\n"); W.inspect(U, this); }
public void visit(C2 W, A2 U) {
System.out.println("32.\n");
W.inspect(U, this);
}
public void visit(C2 W, A3 U) {
System.out.println("33.\n");
W.inspect(U, this);
}
public void visit(C3 W, A3 U) {
System.out.println("34.\n");
W.inspect(U, this);
}
}
class C1 { public void inspect(A1 U, B1 V) { System.out.println("41.\n"); }
public void inspect(A2 U, B2 V) {
System.out.println("42.\n");
}
public void inspect(A3 U, B3 V) {
System.out.println("43.\n");
}
}
class C2 extends C1 { public void inspect(A1 U, B1 V) { System.out.println("51.\n"); }
public void inspect(A2 U, B2 V) {
System.out.println("52.\n");
}
public void inspect(A3 U, B3 V) {
System.out.println("53.\n");
}
}
class C3 extends C2 { public void inspect(A1 U, B1 V) { System.out.println("61.\n"); }
public void inspect(A2 U, B2 V) {
System.out.println("62.\n");
}
public void inspect(A3 U, B3 V) {
System.out.println("63.\n");
}
}
class Demo { public static void main(String[] arg) { A2 a; B2 b; C2 c;
a = new A3();
b = new B3();
c = new C3();
a.accept(b, c);
}
}
登入後即可作答並保存紀錄。
核心觀念
本題主要測驗物件導向程式語言中多型(Polymorphism)與分派機制(Dispatching Mechanism)的核心原理:
- 靜態分派(Static Dispatch)與編譯期多載解析(Overload Resolution): 在 Java 中,方法多載(Overloading)屬於靜態綁定(Static Binding)。編譯器在編譯時期,依據呼叫目標與傳入參數的宣告型態(Declared Type / Static Type),決定要綁定哪一個特定簽章(Signature)的方法。
- 動態分派(Dynamic Dispatching)與執行期覆寫解析(Override Resolution): 方法覆寫(Overriding)屬於動態綁定(Dynamic Binding)。在執行時期,JVM 依據呼叫目標(Receiver Object)的實際物件實體型態(Actual / Dynamic Type),動態決定調用該實體類別所實作的方法版本。
- 單一動態分派(Single Dynamic Dispatch): Java 僅支援單一動態分派,亦即只有接收者(Receiver Object,即方法所屬的呼叫端物件)會在執行時期依動態型態分派;傳入方法的參數(Arguments)則完全依編譯時期的宣告型態決定,不具備多重分派(Multiple Dispatch)的能力。本題程式碼結構即為模擬雙重分派(Double Dispatch)的訪客模式(Visitor Pattern)架構。
解題方法
分析此類「多載+覆寫+多層繼承」的程式追蹤題,必須嚴格拆解為「編譯期定簽章(靜態)」與「執行期定實作(動態)」兩步驟,分段推導各層呼叫:
Step 0:釐清變數的型態設定
在 Demo.main 中:
A2 a = new A3;a的靜態型態為A2,動態型態為A3。B2 b = new B3;b的靜態型態為B2,動態型態為B3。C2 c = new C3;c的靜態型態為C2,動態型態為C3。
Step 1:分析 a.accept(b, c);
- 編譯時期(靜態綁定簽章):
- 接收者
a的宣告型態為A2。 - 參數
b的宣告型態為B2,參數c的宣告型態為C2。 - 編譯器在
A2類別中尋找最相符的方法簽章:A2中宣告了accept(B2 V, C2 W)。 - 因此,編譯器將此呼叫鎖定為
accept(B2, C2)簽章。
- 執行時期(動態分派實作):
- 接收者
a的實際物件型態為A3。 - JVM 尋找
A3是否覆寫了accept(B2, C2):
public void accept(B2 V, C2 W) {
System.out.println("8.\n");
V.visit(W, this);
}
- 執行該方法,輸出
8.。
Step 2:分析 V.visit(W, this);(在 A3.accept 內執行)
此時在 A3 的 accept(B2 V, C2 W) 內:
- 接收者
V的宣告型態為B2(執行期傳入的是b,動態型態為B3)。 - 參數
W的宣告型態為C2(執行期傳入的是c,動態型態為C3)。 - 關鍵參數
this:因當前代碼位於類別A3中,關鍵字this的宣告型態即為A3。
- 編譯時期(靜態綁定簽章):
- 接收者
V的宣告型態為B2。 - 傳入參數型態為
(C2, A3)。 - 編譯器在類別
B2中尋找吻合(C2, A3)的方法簽章:B2中定義了visit(C2 W, A3 U)。 - 因此,編譯器鎖定簽章為
visit(C2, A3)。
- 執行時期(動態分派實作):
- 接收者
V的實際物件型態為B3。 - JVM 尋找
B3是否覆寫了visit(C2, A3):
第 二 題20 分
(一) 請問下面的 Scheme 程式執行結果為何?
(define x 0)
(+ 5 (call/cc (lambda (cc) (set! x cc) 6)))
(* 8 (* 9 (+ 10 (x 35))))
(二) 執行完上列程式之後,接著再執行下面的程式,結果又為何?
(+ 8 (- 9 (* 12 (x 31))))
登入後即可作答並保存紀錄。
核心觀念
本題的核心考點為函數式程式語言(Functional Programming)中的延續(Continuation)與一級延續(First-class Continuation)機制,具體落實在 Scheme 語言的 call-with-current-continuation(常縮寫為 call/cc)。
- 延續(Continuation)的本質: 在程式求值過程中,「延續」代表「當前運算完成後,剩餘未完成的計算步驟與計算環境」。若將當前求值的運算式抽換為一個佔位符(或稱「洞」,Hole),剩下的運算脈絡就是延續上下文(Evaluation Context),記作 。
call/cc的運作方式: 語法為(call/cc (lambda (cc) ...))。
call/cc會將「包裹住它自身的外層剩餘計算脈絡」捕捉為一個一級程序物件(First-class Procedure),並作為引數傳給其接收的匿名函數(即參數cc)。- 若匿名函數內部正常求值結束(未調用
cc),則回傳該值給外層接續執行。 - 關鍵特性(非區域跳躍):若在任何地方調用該延續物件
(cc val),程式會立即捨棄調用當下的所有外部計算脈絡,直接跳回當初捕捉延續的位置,並將引數val填入當時的上下文 中繼續求值。在 Scheme 中,延續是一級公民(First-class object),可賦值給全域變數並重複調用。
解題方法
(一) 第一部分程式執行過程推導
- 定義變數:
(define x 0)
在全域環境中宣告變數 x 並初始化為 0。
- 捕捉延續並求值:
(+ 5 (call/cc (lambda (cc)
(set! x cc)
6)))
- 此處求值
(+ 5 (call/cc ...)),其當前的延續上下文為: call/cc捕捉此上下文 並繫結到參數cc。- 執行
(set! x cc):將全域變數x指向這個延續程序 。 - 匿名函數主體最後求值為
6,正常返回給call/cc。 - 填入原延續上下文:
- 因此,此運算式的求值結果為
11,且全域變數x已被設定為「接收一個數值並加 5」的延續物件。
第 三 題20 分
在 Unix/Linux 的系統裡,libfoo.a 與 libfoo.so 之類的程式庫(libraries)有何不同?並依生成方式、使用方式、使用時機、對系統的影響等面向說明。
登入後即可作答並保存紀錄。
核心觀念
本題測驗 Unix/Linux 作業系統環境下程式庫(Library)的本質、編譯連結機制(Linking)與執行期記憶體管理。核心觀念包含:
- 靜態程式庫(Static Library,
.a):本質為目的檔封存檔(Archive),於連結期(Link time)由靜態連結器(Linker, 如ld)將被引用的機器碼直接複製並整合至最終的可執行檔(Executable)內部。 - 動態共用程式庫(Shared Library / Shared Object,
.so):本質為位置無關程式碼(PIC),編譯連結期僅在執行檔中記錄符號參照(Symbol References)與相依資訊,直到程式載入期或執行期(Load time / Runtime)才由動態載入器(Dynamic Linker/Loader, 如ld.so)載入記憶體供一個或多個行程共用。
解題方法
本題為標準的申論比較題,評分標準著重在「觀念區分是否透徹」與「題目所列之四項面向是否完整作答」。作答架構直接切入題目要求的四大構面(生成方式、使用方式、使用時機、對系統的影響),並在生成與使用面向列出具體的 Unix/Linux 指令(如 gcc 參數、ar 工具),展現對底層運作的精確掌握。
一、本質與定義對比
libfoo.a(靜態程式庫):副檔名.a代表「Archive」,是一組目的檔(.o)的集合包裝。執行檔產生後即自給自足,不再依賴原.a檔案。libfoo.so(動態共用程式庫):副檔名.so代表「Shared Object」,是包含符號表與可重定位代碼的獨立二進位模組。執行檔本身不含函式本體,執行時需仰賴系統中的.so檔案。
二、依題目要求面向深入剖析
1. 生成方式(Creation / Generation)
libfoo.a:
- 將原始碼編譯為一般目的檔:
gcc -c foo.c -o foo.o - 使用封裝工具
ar(Archiver)將多個.o檔打包並建立索引:ar rcs libfoo.a foo.o
libfoo.so:
- 編譯原始碼時必須加上
-fPIC(Position Independent Code)參數,生成與記憶體位置無關的程式碼:gcc -fPIC -c foo.c -o foo.o - 透過編譯器/連結器加上
-shared參數,組裝為共用物件:gcc -shared -o libfoo.so foo.o(亦可單一步驟完成:gcc -fPIC -shared foo.c -o libfoo.so)
2. 使用方式(Usage / Linking & Loading)
libfoo.a:- 編譯連結階段:使用編譯器指令連結靜態庫,例如:
gcc main.c -L. -lfoo -o main(或直接指定路徑gcc main.c libfoo.a -o main)。 - 執行階段:執行檔
main內部已包含foo模組的實體機器碼。執行時直接載入記憶體執行,環境中無需存在libfoo.a。 libfoo.so:- 編譯連結階段:指令語法外觀相同(
gcc main.c -L. -lfoo -o main),但連結器僅在main內部寫入「需要libfoo.so及未解析符號」的動態相依清單。 - 執行階段:
- 隱式動態連結(Implicit Linking / Load-time):作業系統執行程式時,由動態載入器(如
/lib/ld-linux.so)依指定路徑(如環境變數LD_LIBRARY_PATH、系統快取/etc/ld.so.cache、/lib、/usr/lib、RPATH)尋找libfoo.so並載入記憶體。 - 顯式動態載入(Explicit Loading / Run-time):程式亦可在原始碼中透過系統呼叫 API(如
dlopen、dlsym、dlclose)在執行期間隨時動態掛載與卸載。
3. 使用時機(Use Cases)
libfoo.a之適用時機:- 系統極限環境或單一執行檔發行:如嵌入式系統(Embedded Systems)、極簡容器映像檔(如 Scratch container)、救援開機環境(Rescue Mode / Single-user mode),避免因系統遺失共享庫而無法啟動。
- 追求高度可攜性(Portability):軟體需在各類不同版本之 Linux 發行版上部署,避免目標機器函式庫版本不相容問題。
- 極致效能與即時系統(Real-time Systems):消除執行期動態符號解析與間接定址(PLT/GOT)的開銷。
第 四 題20 分
考慮下列與前後文無關的文法(context-free grammar)。請問它是 LL(1) 文法嗎?如果是,請寫出它的 LL(1) 文法分析表(LL(1) parse table)。如果不是,請說明理由。
登入後即可作答並保存紀錄。
核心觀念
- LL(1) 文法之定義與充要條件: 一個前後文無關文法(Context-Free Grammar, CFG) 為 LL(1) 文法,若且唯若對於任何非終端符號 的任意兩條相異產生規則 與 ,均滿足以下條件:
- 若 ,則
- 與 不可同時推導出空字串
若文法中不存在任何可推導出 的非終端符號(-free grammar),則判定條件簡化為:同一個非終端符號的所有相異候選分支,其 集合兩兩互斥。
- 與 集合定義:
- :由符號串 所能推導出的所有字串中,第一個終端符號所組成的集合。
- :在所有合法的文法衍生句型中,緊接在非終端符號 正後方的終端符號集合(若 可在最末端,則包含輸入結束符號 )。
- LL(1) 文法分析表(Parse Table)建構規則: 對於文法中的每一條產生規則 :
- 對所有終端符號 ,將 填入分析表表格 。
- 若 ,則對所有 (含 ),將 填入 。
- 若分析表中每一個儲存格至多只容納一條產生規則(無多重定義衝突),則該文法即為 LL(1) 文法。
解題方法
步驟一:分析文法符號
- 非終端符號集合:,起始符號為
- 終端符號集合:
- 輸入結束標記:
- 本文法中完全沒有 產生規則,因此所有符號皆無法推導出 (Nullable 符號集合為空集)。
步驟二:計算各非終端符號的 集合
依據文法規則由底層向上推導:
- 由規則 6:
- 由規則 2、3:
- 因此,
- 由規則 4、5:
- 因此,
- 由規則 1:
- ,因 無法推導出 ,故
各產生規則右側之 彙整如下:
步驟三:計算各非終端符號的 集合
- 起始符號 :
- 由規則 1():
- 後方為 ,因 不衍生 ,故
- 後方為 ,因 不衍生 ,故
- 位於產生式末端,故
- 由規則 4():
- 後方緊接終端符號 ,故
- 由規則 2():
第 五 題20 分
(一) 請問下列 C 程式執行的結果是什麼?
#include <stdio.h>
int a, b;
void main() { a = 4; b = 30;
printf("Before the switch statement, a= %d.\n", a);
switch (a) {
case 1:
a = a * 10;
break;
case 2:
a = a * 10;
break;
case 3:
a = a * 10;
while (a < b)
case 4: {
a = a + 5;
}
break;
case 5:
a = a * 10;
break;
default:
b = a * 10;
break;
}
printf("after the switch statement, a= %d.\n", a);
}
(二) 請檢視下面的 C++ 程式,請問執行該程式後的輸出為何?
#include <stdio.h>
class A { public: int X;
A() {
X = 1;
printf("X = %d\n", X);
}
};
class B : public A { public: B() { X = 2; printf("X = %d\n", X); } };
main() { B *pB = new B; }
登入後即可作答並保存紀錄。
核心觀念
switch敘述與case標籤的本質: 在 C 語言規格中,case標籤的本質是「跳躍目標標籤」(Jump Target Label),其底層運作方式等同於goto標籤。- 控制結構交錯(Duff's Device 原理):
ANSI/ISO C 語法允許
case標籤置於switch複合陳述內部的任何子區塊、迴圈或條件式結構內部。這種寫法最著名的實例為最佳化技術「達夫設備」(Duff's Device)。 while迴圈的控制流程: 當程式流程透過switch外部跳躍直接進入while迴圈體內部時,會直接執行該標籤所在的陳述句;當迴圈體執行到結尾時,控制權會回到while的條件判斷式(Controlling Expression),只要條件為真,迴圈就會繼續正常迭代。
解題方法(程式執行追蹤與數值推導)
- 初始狀態:
- 全域變數 ,。
- 執行
printf("Before the switch statement, a= %d.\n", a); - 印出:
Before the switch statement, a= 4.
- 進入
switch (a):
- 此時 ,控制權依據標籤匹配,直接跳越至
case 4:所在位置。 case 4:位於while (a < b)迴圈管轄的陳述句內部,因此程式直接切入並執行複合陳述區塊{ a = a + 5; }。
while迴圈迭代推導:
- 第 1 次執行(跳入執行):
。
執行完迴圈體後,流程抵達迴圈結尾,轉移至
while (a < b)進行條件判斷: (條件成立,繼續執行迴圈體)。 - 第 2 次迭代: 。 條件判斷:(成立)。
- 第 3 次迭代: 。 條件判斷:(成立)。
- 第 4 次迭代: 。 條件判斷:(成立)。
- 第 5 次迭代: 。 條件判斷:(成立)。
- 第 6 次迭代:
。
條件判斷:(條件不成立,跳出
while迴圈)。
- 離開
switch結構:
while迴圈終止後,緊接著執行迴圈外的break;敘述。- 該
break;屬於外層switch敘述,因此跳離整個switch區塊。
- 最終輸出:
- 執行
printf("after the switch statement, a= %d.\n", a); - 此時 ,印出:
after the switch statement, a= 34.