94年 - 94-1 高等考試_三級_資訊處理：程式語言#24744

1 在儲存佇列（queue）元素時，以環狀陣列（circular array）來取代線性陣列（array），最主要可得到下列那一項優點？ (A)較節省儲存空間 (B)易於修正佇列之前端索引（front） (C)避免大量資料搬移 (D)可儲存較多資料項

2 下列有關堆積（heap）的敘述，何者是正確的？ (A)可視為一棵二元搜尋樹（binary search tree） (B)可視為一棵完整二元樹（complete binary tree） (C)可視為一棵完全二元樹（full binary tree） (D)可視為一棵紅黑樹（red-black tree）

3 陣列（array）A 共有6 列8 行資料，以列為主（row major order）儲存在記憶體中，A 的起始位址為20。假設陣列中的每份資料占2 個記憶單位，則第3 列第6 行的位址為何？ (A)62(B)64(C)66(D)68

4 下列何種資料結構最適合用來處理遞迴呼叫（recursive call）？ (A)佇列（queue） (B)堆疊（stack） (C)二元樹（binary tree） (D)鏈結串列（linked list）

5 利用循序搜尋法（sequential search）自下列名字中 [Alice, Byron, Carol, Duane, Elaine, Floyd, Gene, Henry, Iris] 搜尋Elaine，需比較幾次名字？ (A)1(B)3(C)4(D)5

6 利用二元搜尋法（binary search）自下列名字中 [Alice, Byron, Carol, Duane, Elaine, Floyd, Gene, Henry, Iris] 搜尋Elaine，需比較幾次名字？ (A)1(B)3(C)4(D)5

7 利用二元搜尋法（binary search）自200 個名字中搜尋某個特定名字，若為成功搜尋（successful search），最多需比較多少個名字？ (A)6(B)7(C)8(D)9

8 n 個整數以陣列（array）儲存，將存放於最前面及最後面之元素印出，所需之時間複雜度，以下列何者表示最為適當？ (A) O（1） (B)O（log（n）） (C) O（n） (D)O（n²）

9 對一堆疊依序加入（push）1, 2, 3 其間可輸出（pop）元素，請問下列何者為不可能之輸出？ (A) 1, 2, 3 (B)1, 3, 2 (C) 2, 1, 3 (D)3, 1, 2

10 n 個整數以堆疊（stack）儲存，將其中之最小元素印出，所需之時間複雜度，以下列何者表示最為適當？ (A) O（1） (B)O（log（n）） (C) O（n） (D)O（n²）

11 假設陣列（array）資料以行為主（column major order）儲存在記憶體中，且每份資料占1 個記憶單位，若陣列A 的第一個元素A［0, 0］位址為2152，A［4, 5］位址為2196，則A［5, 4］的位址為何？ (A)2159(B)2169(C)2173(D)2189

12 利用氣泡排序法（bubble sort）將以下10 個資料依由小至大順序排列：37, 41, 19, 81, 43, 25, 56, 61, 49, 41 ，下列何者可表示經第2 階段（pass）處理後的資料順序？ (A) 19, 37, 41, 25, 43, 56, 49, 41, 61, 81 (B)37, 19, 41, 43, 25, 56, 61, 49, 41, 81 (C) 41, 37, 81, 43, 25, 56, 61, 49, 41, 19 (D)41, 81, 43, 37, 56, 61, 49, 41, 25, 19

13 利用不同的走訪方式（traversal）追蹤二元樹（binary tree）的節點（node），下列敘述何者是正確的？ (A)由二元樹的中序走訪（inorder traversal），可決定該二元樹之根節點（root node） (B)由二元樹的中序走訪，可決定該二元樹之葉節點（leaf node）個數 (C)由二元樹的中序走訪及後序走訪（postorder traversal），可決定該二元樹 (D)由二元樹的前序走訪（preorder traversal）及後序走訪，可決定該二元樹

14 以10 為基數，採低位數優先（least significant digit first）的方式，進行基數排序法（radix sort）將以下8 個資料由小至大順序排列：224, 454, 321, 735, 496, 524, 98, 456，下列何者可表示經第1 階段（pass）處理後的資料順序？ (A) 98, 224, 321, 454, 456, 496, 524, 735 (B)321, 224, 524, 454, 735, 456, 496, 98 (C) 321, 224, 454, 524, 735, 456, 496, 98 (D)321, 224, 454, 524, 735, 496, 456, 98

15 假設指標First 指向單鏈結串列（singly linked list）的首項資料，為使First→next→next→data 敘述有意義，此一串列至少需含有幾個節點？ (A) 1 個節點 (B)2 個節點 (C) 3 個節點 (D)4 個節點

16 某二元樹（binary tree）之前序走訪（preorder traversal）為ABCDEFGHJIK，中序走訪（inorder traversal）為DCEBAFHGJIK。此二元樹的根節點（root node）為何？ (A)A(B)D(C)F(D)K

17 撰寫老鼠走迷宮程式時，需記錄走過路徑，以作為無路可走時後退的依據。下列何種資料結構最適合用來記錄走過路徑？ (A)佇列（queue） (B)堆疊（stack） (C)二元樹（binary tree） (D)鏈結串列（linked list）

18 某二元樹（binary tree）之中序走訪（inorder traversal）為DBGEHAFC，而後序走訪（postorder traversal）為DGHEBFCA，對於該二元樹之性質，下列敘述何者是正確的？ (A)根節點（root node）為A (B)葉節點（leaf node）共5 個 (C)G 節點之親代節點（parent node）為H (D)前序走訪（preorder traversal）為ABDECFGH

19 將41 新增至下圖所示之二元搜尋樹（binary search tree），請問那一個節點（node）將成為新增節點的親代節點（parent node）？

(A) 35 (B)37 (C) 39 (D)42

20 輸入參數：A：含N 個整數之陣列，下標（index）值由1 至N, Low：整數， High：整數

若以Funny（A, 1, N）敘述呼叫Funny 函式，下列那個選項最能說明其功能？ (A)將 A 的前N 個資料排成由小至大順序 (B)將 A 的前N 個資料排成由大至小順序 (C)將 A 的前N 個資料依相反順序排列 (D)將 A 的第一個資料與第N 個資料內容互換

21 將中序（infix）運算式A / B –（C＋D）*E + A*C 轉換成後序（postfix）運算式為： (A)A B / C D＋E * - A C *＋ (B)A B / C＋D E * - A C *＋ (C)A B / C D＋E *- * A C＋ (D)A B / C D E＋* - A C *＋

22 含3 個節點（node）的二元樹（binary tree），共有幾種不同的形狀？ (A)3(B)5(C)6(D)8

23 遞迴式：若n＞1 時，T（n）= 2T（n/2）＋2n，且T（1）＝20，其解為： (A)T（n）＝ O（n） (B)T（n）＝ O（n²） (C)T（n）＝ O（n log n） (D)T（n）＝ O（log（log n））

24 下列有關雜湊表（hash table）的敘述，何者最為適當？ (A)在最壞情況下，刪除資料要O（n）的時間 (B)在最壞情況下，新增資料要O（log n）的時間 (C)在最壞情況下，搜尋資料要O（n2）的時間 (D)在最好情況下，搜尋資料要O（log n）的時間

25 針對下面之圖形（graph），以拓撲排序法（topological ordering）列出所有節點（node），下列之排列順序何者是不正確的？

(A) ABCD (B)ABDC (C) ADBC (D)ADCB

26 利用堆積排序法（heap sort）將以下10 個資料依由小至大順序排列：26, 5, 77, 1, 61, 11, 59, 15, 48, 19 ，下列何者可表示經第2 階段（pass）處理後的資料順序？ (A) 61, 48, 59, 15, 19, 11, 26, 5, 1, 77 (B)1, 5, 11, 15, 19, 77, 59, 26, 48, 61 (C) 59, 48, 26, 15, 19, 11, 1, 5, 61, 77 (D)11, 15, 48, 26, 19, 77, 59, 61, 5, 1

27 利用插入排序法（insertion sort），將資料38, 8, 64, 15, 23, 21 由小至大排序，請問在排序過程中，下列那個資料順序是可能發生的？ (A) 8, 38, 64, 15, 23, 21 (B)8, 21, 23, 38, 64, 15 (C) 8, 38, 64, 23, 15, 21 (D)8, 15, 38, 64, 21, 23

28 若將含20 個節點（node）的完整二元樹（complete binary tree）儲存於一維陣列（array）A 中，假設陣列之下標值由1 開始至20 依序儲存各節點資料。下列敘述何者是正確的？ (A)A [4] 的親代節點（parent node）為A [3] (B)A [5] 的親代節點為A [3] (C)A [4] 的左邊子節點（left child）為A [8] (D)A [10] 的右邊子節點（right child）為A [20]

29 下表為某演算法資料量n 與計算時間T（n）對照表，有關時間複雜度（time complexity）的推測，下列何者最為適當？

(A) O（1） (B)O（log n） (C) O（n log n） (D)O（ √n）

30 某二元樹（binary tree）的前序走訪（preorder traversal）表示法為：ABCD，那麼下列何者不可能為該二元樹的後序走訪（postorder traversal）表示法？ (A)DCBA(B)CDBA(C)CBDA(D)DBCA

31 下列何種資料結構最適合作為印表機的緩衝器（buffer）？ (A)佇列（queue） (B)堆疊（stack） (C)二元樹（binary tree） (D)鏈結串列（linked list）

32 圖（graph）這種資料結構主要用來表示資料間的何種關係？ (A)循序（sequential） (B)階層（hierarchical） (C)連結（connected） (D)相對（relative）

33 輸入參數： N：整數

若以Strange（13）敘述呼叫函式，其執行結果為何？ (A)4(B)7(C)10(D)11

34 將資料80, 72, 66, 44, 21, 33，依由小至大順序進行排序。在第2 階段（pass）後之資料順序為66, 72,80, 44, 21, 33，請問所使用的排序方法最可能為下列那種方法？ (A)氣泡排序法（bubble sort） (B)挑選排序法（selection sort） (C)插入排序法（insertion sort） (D)堆積排序法（heap sort）

35 下列之描述何者最為適當？ (A)自鏈結串列（linked list）搜尋某特定資料，在最壞情況下所需時間複雜度為O（log n） (B)利用線性搜尋法（linear search）自有序陣列找尋最小值，在最壞情況下所需時間複雜度為O（log n） (C)自二元搜尋樹（binary search tree）找尋最小值，在最壞情況下所需時間複雜度為O（log n） (D)自 AVL 樹（tree）找尋最小值，在最壞情況下其時間複雜度為O（log n）

36 一圖形有n 個節點（node）及e 個邊（edge），若以相鄰矩陣（adjacent matrix）表示，則利用深度優先搜尋法（depth first search）所得出之擴張樹（spanning tree）的時間複雜度（time complexity）為： (A)O（n²） (B)O（ne） (C)O（n） (D)O（e）

37 下列有關霍夫曼樹（Huffman tree）的敘述，何者是正確的？ (A)可視為二元搜尋樹（binary search tree） (B)可視為AVL 樹（AVL tree）的特例 (C)可用來作資料排序 (D)可用來作資料壓縮

38 下列有關AVL 樹（AVL tree）的敘述，何者最為適當？ (A)在最壞情況（worst case）下，刪除一個節點（node）所需時間為O（n） (B)在最壞情況下，新增一個節點所需時間為O（n） (C)在最壞情況下，新增一個節點所需時間為O（log n） (D)搜尋一個節點所需時間最少為O（log n）

39 下列何種資料結構最適合用來挑選最小（或最大）的資料？ (A)佇列（queue） (B)堆疊（stack） (C)樹狀結構（tree） (D)堆積（heap）

40 用鏈結串列（Linked List）儲存無次序之資料時，下列敘述何者最為適當？ (A)找尋最大資料時要O（n）的時間 (B)做插入（Insertion）要 O（n）的時間 (C)做刪除（Deletion）要O（log n）的時間 (D)找尋某特定資料時要O（log n）的時間

41 下列那一種程式語言最符合以下敘述：「在過去40 年間，這種語言被廣泛使用於開發商業應用軟體。」？ (A)ADA(B)C(C)COBOL(D)FORTRAN

42 結構化程式設計應避免使用以下何種敘述？ (A)for(B)goto(C)if(D)switch

43 設I＝3，J＝10，K＝8，以下之邏輯運算式何者之運算結果為真（true）？ (A)I＋K＜＝J (B)（I＜J）and not（J＞K） (C)（（I＜K）or（J＜K））and（K＞＝0） (D)not（（I＞J）or（K＞I））

44 以下那一種程式語言沒有提供布林（Boolean）資料型態？ (A)C89(B)C++(C)Java(D)Pascal

45 以下何者不是C++程式語言的變數儲存類別（storage class）？ (A)extern(B)global(C)register(D)static

46 以下有一BASIC 程式：

若此程式之執行結果如右：

則程式中的空格內應填入以下何者？ (A)I＜J(B)I＜＝J(C)I＞J(D)I＞＝J

47 以下有C 程式語言的4 個變數宣告，其中那一個是錯誤的？ (A)float x; (B)short j; (C)double float k; (D)unsigned char n;

48 下列關於「多載化函式」（overloaded functions）的描述何者正確？ (A)一組「多載化函式」中，每一個函式都有著相同的名稱 (B)一組「多載化函式」中，每一個函式的參數個數都必須一樣 (C)Ada 語言不支援「多載化函式」 (D)「多載化函式」的程式碼通常很短，每一個函式通常都只有一、兩行敘述

49 以下有一以C 語言撰寫之遞迴函式（recursive function）。假設N≧0，而此函式是用來計算0 至N 之間的所有整數之和：

則空格中應填入以下何者？ (A)while（N＜＞0）return N＋Sum（N＋1） (B)return（N－1）＋Sum（N－1） (C)return N＋Sum（N－1） (D)return（N－1）＋Sum（N）

50 有一類似Pascal 語法之程式如下：

若上述程式採用靜態領域（static scoping）的方式決定變數的領域（scope），則其執行結果為何？ (A) 0 1 2 2 (B)0 1 2 2 2 (C) 上述程式在編譯時會有錯誤，因為程式中使用了一個未經宣告的變數 (D)程式將產生無窮盡（infinite）的結果，因為這個程式包含了一個無窮遞迴（infinite recursion）

51 在編譯式的程式設計環境中，編寫完成一個程式之後的執行步驟為以下何者？ (A)編譯（compiling）→連結（linking）→載入（loading）→執行（executing） (B)編譯（compiling）→載入（loading）→連結（linking）→執行（executing） (C)連結（linking）→編譯（compiling）→載入（loading）→執行（executing） (D)載入（loading）→連結（linking）→編譯（compiling）→執行（executing）

52 有一文法如下：

S → aS | bA

A → d | ccA

此文法可產生以下那一個字串？ (A)bccddd(B)abbbd(C)ababccd(D)aabccd

53 在程式語言中，同一個運算符號常被用於多種目的，例如「＋」號除了用於加法運算之外，諸如Java 、Visual Basic 等語言也將「＋」號用於連接兩個字串。以下那一個名詞表示著這種「同一符號、多種用途」的概念？ (A)operator coercion (B)operator conversion (C)operator overloading (D)operator side effect

54 某些程式語言允許使用者在副程式（subprograms）中宣告history sensitive 的變數，使這些區域變數（local variables）不會隨著副程式執行結束而消失，其資料可以保留至下一次的副程式呼叫時使用。在C、C++和Java 語言中，使用者若欲使用history sensitive 的區域變數，則應在變數宣告時，在變數資料型態前加上以下那一個字？ (A)auto(B)cast(C)retain(D)static

55 以下是一個用C 的語法所寫成的程式：

設若參數傳遞是採用傳址法（pass-by-reference），則程式執行結束時，變數value 之值為以下何者？ (A)3(B)5(C)7(D)9

56 有一個二維陣列A [1..row, 1..col] 儲存於記憶體中，其起始位址為。若此陣列之每一個元素的大小為1 byte，且陣列元素是採「以列為主」（row major order）的方式儲存，則以下那一個運算式正確地表示陣列元素A [i, j] 在記憶體的位址？ (A)＋（i－1）* row＋j－1 (B)＋（i－1）* col＋j－1 (C)＋（j－1）* row＋i－1 (D)＋（j－1）* col＋i－1

57 有一C 程式中定義了以下巨集（macro）：

#define sum（a, b） a＋b

#define prod（a, b） a * b

則當以下兩行敘述執行結束時，ans1 和ans2 之值分別為何？

58 若欲於C++程式中加入例外處理（exception handling）的功能，則程式中可能會造成例外（exceptions）的敘述應寫在那一個區段（block）內？ (A)catch(B)check(C)throw(D)try

59 下列何種程式語言與其他語言差異最大? (A)C++(B)Fortran(C)Java(D)JavaScript

60 有一C++ 程式片段如下：

若此程式執行時將以捷徑運算（short circuit evaluation）的方式處理邏輯運算式，則以下那一個敘述最適切地說明了此一程式片段的執行結果？ (A)此程式片段將會有編譯錯誤，因為布林變數y 和整數變數x 不可同時出現在if 敘述的條件中 (B)此程式片段將會產生「除數為零」的執行錯誤 (C)此程式片段的編譯和執行都不會有錯，執行後將印出 success (D)此程式片段的編譯和執行都不會有錯，執行後將印出 failure

61 C++允許使用者在class（物件類別）的定義中加入使用者自訂之建構函式（constructor）。下列何者是關於建構函式的正確描述？ (A)建構函式的名稱一定要與其所屬之class 的名稱相同 (B)一個 class 只能有一個建構函式 (C)建構函式可以回傳任何型態的資料給呼叫者 (D)建構函式一定要宣告在private 區域中

62 以下為一以C 語言寫成之compute ( ) 遞迴函式（recursive function），此函式將回傳一整數值：

以下的三個函式呼叫中，那一個（或那幾個）會造成無窮遞迴（infinite recursion）？

(A)只有（乙）會造成無窮遞迴 (B)（甲）和（丙）都會造成無窮遞迴 (C)（乙）和（丙）都會造成無窮遞迴 (D)（甲）、（乙）、（丙）都會造成無窮遞迴

63 某些程式語言對於程式識別字的大小寫有所區分，例如 “Total” 和 “total” 會被這些語言視為兩個不同的識別字。設有一程式片段如下：

假設這個程式語言區分大小寫，則此程式片段執行後，將印出以下那一個結果？ (A)0(B)100(C)200(D)300

64 以下那一個程式片段會使變數sum 被設定為1 至99 之間所有偶數的和？

65 以下4 個Pascal 程式片段中，那一個可以正確地判斷整數n 是否為質數？

66 在C++中，一個class 的成員函式（member functions）之中若至少有一個是pure virtual function，則此種class 稱為以下何者？ (A)abstract class(B) dynamic class (C)polymorphic class (D)static class

67 有一C 語言之switch 敘述如下：

此敘述等同於下列那一個程式片段？

68 編譯過程包含3 個主要步驟，依序為語句分析（lexical analysis）、語法分析（syntax analysis 或parsing）、以及以下何者？ (A)程式碼產生（code generation） (B)除錯（debugging） (C)整合測試（integration testing） (D)連結（linking）

69 有一Pascal 之函式定義如下，其參數n 是採用傳址（pass-by-reference）的方式傳遞：

下列程式片段中呼叫了func( ) 函式：

k :＝10;

n1 :＝k/2 + func（k）;

n2 :＝func（k）＋k/2;

在「左結合律」（left associativity）的特性下，此程式片段執行後，n2 之值為何？ (A)35(B)40(C)60(D)70

70 假設某一程式語言所能接受之識別字必須符合以下語法圖（syntax diagram）之規範，則以下那一個識別字是錯誤的？

(A)ant (B)boy (C)aaa (D)a1b2c3

71 以下是一個C++的template function：

假設我們已在程式中宣告了以下變數，且各變數均已有適當的初始值：

int a, b, c;

char d, e, f;

則以下那一個max( ) 函式呼叫會造成編譯時的錯誤（compile-time error）？ (A)c＝max（a, b）; (B)c＝max＜int＞（a, b）; (C)c＝max（int a, int b）; (D)c＝max（d, e）;

72 假設一個C++程式中有著以下的變數宣告：

int x ;

bool result ;

試考慮以下3 個程式片段：

以上那一個（或那幾個）程式片段具有下述功能：當x 是偶數時，result 會被設定為true；反之，當 x 是奇數時，result 會被設定為false？ (A)（甲）和（乙）(B)（甲）和（丙）(C)（乙）和（丙）(D)只有（乙）

73 以下是使用Extended Backus-Naur Form（EBNF）所描述的設定敘述的語法，其中＜letter＞是英文的大小寫字母，而＜digit＞則是阿拉伯數字0..9。根據此語法，以下那一個設定敘述是正確的？

(A)tax:＝A*B1(B)F:＋D(C)G1:＝G2＋G3＋G4(D)X:＝X＋100

74 假設x 為一整數變數，且x 已有初始值。若有一Ｃ程式片段如下：

if（x＞5）x *＝2 ;

if（x＞10）x＝0 ;

以上程式片段之執行效果等同於下列那一個程式片段？ (A)if（x＞5）x＝0 ; (B)if（x＞5）x *＝2 ; (C)if（x＞5）x＝0 ;

else x * = 2; (D)if（x＞5）x *＝2 ;

else if（x＞10）x＝0 ;

75 如果我們打算使用Pascal 語言寫一個雙層for 迴圈，以便將以下內容填入一個名為Matrix 的5 ×5 陣列中：

則以下之雙層for 迴圈的空格內應填入什麼？

(A)i＝j (B)i＜＞j (C)（i＋j）mod 2＝0 (D)（i＋j）mod 2＜＞0

76 有一文法（grammar）G＝{{S}, {0, 1}, P, S }，其中P＝{S→SS, S→0S1, S→1S0, S→empty}。根據此文法所產生之語言為以下何者？

(A){W | where W has an equal number of 0’s and 1’s}

(B){0n1n | where n ≥ 0}

(C){0n1n | where n ≥ 0} U {1ⁿ0ⁿ where n ≥ 0}

(D){0m1k | where m, k ≥ 0} U {1^m0^k where m, k ≥ 0}

77 有一Prolog 程式如下：

如果我們針對此程式鍵入以下問句（query）：

?- a（X, Y）, not（c（X））, d（X,Y）.

則Prolog 系統所產生的第一組答案將會是以下何者？ (A)X = 2 Y = 1 (B)X = 3 Y = 2 (C)X = 3 Y = 4 (D)X = 4 Y = 2

78 以下有一名為Mystery( ) 之函式，此函式回傳一個布林（Boolean）值：

以下那一個句子最適切地描述了Mystery( ) 函式之回傳值？ (A)Mystery( ) 函式所回傳的一定是 false 值 (B)Mystery( ) 函式所回傳的一定是 true 值 (C)如果使用者所輸入之k 個整數中，有任何一個是正數時，Mystery( ) 函式將回傳true 值 (D)如果使用者所輸入之k 個整數全部是正數時，Mystery( ) 函式將回傳true 值

79 下列C++程式中，那一行程式敘述會產生編譯時的錯誤（compile-time error）？

(A)a1.x = 7; (B)b1.y = 8; (C)b1.z = 9; (D)b2 = b1;

80 假設f 函式是用來將傳入之字串反轉後傳出（例如當所傳入之字串是 “abc” 時，則f 函式將傳回 “cba”），而g 函式則是用來將傳入的兩個字串連接後傳出（例如當所傳入的兩個字串分別是 “abc” 與 “def” 時，則g 函式將傳回“abcdef”）。設若字串變數x 目前之內容為 “abcd”，則f（g（x, f（x）））之函式呼叫將傳回以下那一個字串？ (A)abcddcba(B)dcbaabcd(C)abcdabcd(D)dcbadcba

94年 - 94-1 高等考試_三級_資訊處理：程式語言#24744

試卷資訊

選擇題 (80)

申論題 (0)