全國86筆試題目

教育部全國高級中學八十六學年度

資訊學科能力競賽決賽 筆試題目

說明:

1. 答案必須寫在答案卷上

2. 作答時間80分鐘。本試題共有75題選擇題。

3. 若需計算或作圖,請利用本試題的空白處或反面。

4. A部份每題答錯倒扣0.25分。B部份每題答錯倒扣0.5分(不答不倒扣)。

5. 試題不必交回。僅繳交答案卷即可。

 

A. 選擇(5選1) 每題1分,共50題。

1. 以下那種裝置可同時擔任輸入及輸出功能?

(A) 印表機 (B) 鍵盤 (C) 觸摸式螢幕 (D) 光筆 (E) 滑鼠

2. 下列那一種資料儲存裝置其資料讀取時間與資料儲存位置最相關?

(A) RAM (B) DAT磁帶機 (C) CD-ROM (D) Disk (E) ROM

3. 下列對RAM的敘述那個是錯誤的?

(A) 儲存的資料能被讀出 (B) 電源關掉內容都消失 (C) 能寫入資料

(D) 與ROM的主要差別在於記憶大小 (E) 通常以Mega Bytes為單位

4. 下列何者為命令處理程式,它可以辨識使用者鍵入的命令?

(A) MSDOS.SYS (B) AUTOEXEC.BAT (C) FORMAT.COM

(D) COMMAND.COM (E) CONFIG.SYS

5. 英文字母「A」的10進位ASCII值為65,則字母「Q」的16進位ASCII值為

(A) 73 (B) 81 (C) 51 (D) 94 (E) 98

6. 一般而言,下面那一種記憶體速度最快?

(A) ROM (B) RAM (C) 暫存器(Register) (D) 快取記憶體(Cache Memory)

(E) 硬碟

7. 一般PC所使用的內碼為:

(A) EBCDIC (B) BLSI (C) NTSC (D) ASCII (E) 以上皆非

8. 十進位數52520的九補數 (9s complement) 為何?

(A) 47479 (B) 47480 (C) 47478 (D) 52520 (E) 以上皆非

9. 下列那一個八進位數值為八進位數23.4 和八進位數56.4之和?

(A) 66.0 (B) 102.0 (C) 79.8 (D) 515.10 (E) 以上皆非

10. 程式計數器(Program Counter)的作用是:

(A) 存放錯誤指令的個數 (B) 存放指令的長度 (C) 存放程式指令

(D) 存放下一個要被執行之指令的位址 (E) 存放資料處理結果

11. 專門對資料進行運算及比對的是那一個單元的工作?

(A) Control Unit (B) Register(暫存器) (C) ALU (D) DOS

(E) 以上皆非

12. 在1946年完成之計算機ENIAC的主要元件是:

(A) 電晶體 (B) 真空管 (C) 積體電路 (D) 繼電器

(E) 以上皆非

13. 半導體 PROM 所儲存之資料在電源中斷後,就:

自然消失 (B) 自動顯示 (C) 只能寫入 (D) 維持不變 (E) 以上皆非

14. 當實數絕對值太小時, 計算機內部無法表示而以零取代, 此種狀況稱為

(A) overflow (B) underflow (C) truncation error (D) rounding error (E) NULL

15. 下列有關微程式(Micro Program)的描述,何者是對的?

(A) 微程式是一組程式,用來有效管理電腦資源,及系統的整體操作。

(B) 微程式可以幫助使用者更方便操作電腦。

(C) 微程式目的是要讓CPU的閒置時間(Idle time) 降至最低。

(D) 微程式就是指微算機用的程式。

(E) 微程式是在 CPU 內的軔體(Firm Ware)。

16. 下列何者為二進位數10011001的一補數(1s complement)?

(A) 11001101 (B)01010011 (C) 11001110 (D) 01100110 (E) 以上皆非

17. 溜覽網頁時, Java 的 Applet 程式在何處執行 ?

(A) 在 server端 (B) 在用戶端 (C) 都可能 (D) 在網路上 (E) 以上皆非

18. 考慮8 bit 的有號數, 負數用2補數; 下列那一對二進位數的和會溢位(overflow)?

(A) 11001101, 01110111 (B) 01010011, 10101111 (C) 11001110 , 10001110

(D) 01001110, 10110001 (E) 以上都不會overflow

19. 在 QBASIC 下,執行下列程式之結果為:

(A) 0 (B) 3 (C) 4 (D) 12 (E) 語法錯誤

100 I = 7

200 J = 11

300 FOR I = 1 TO J

400 J = J - 1

500 NEXT I

600 PRINT I

 

20. 假設一資料檔案含有 N 個項目的資料,N 相當的大且這些資料是依某關鍵值key

 由大排到小。現在若用Sequential search在這些資料找尋某key的元素,則平均而言所

需時間用N 表示最接近:

(A) (N+1)/2 (B) N*(N-1)/2 (C) Log2(N) (D) N*Log2(N) (E) 以上皆非

21. 目前SRAM記憶體的存取時間(access time)大約為

(A) 10 ms (B) 10 nano sec. (C) 60 nano sec. (D) 10 μs (E) 60 μs

22. 下列何者為 (A+B)*C/D-E 的前置式(prefix expression)?

(A) *A B+ / C - D E (B) - * A + B C / D E (C) - /*+A B C D E

(D) A B + C * D / E - (E) 以上皆非

23. 要為新開發的印表機寫驅動程式, 若考慮程式要又小又有效率, 則下列那一種程式語言最適合?

(A) C (B) Fortran (C) C++ (D) Pascal (E) 組合語言 (Assembly)

 

24. 請問Telnet和FTP是屬於TCP/IP通訊協定中那一層的服務?

(A) Transport (B) Application (C) Internet layer (D) Network (E) Link

 

25. 網際網路資料傳遞都是利用IP位址(IP Address)作目的地的定位, 請問目前廣泛使用IP位址是多少位元組 (byte) ?

(A) 2 (B) 4 (C) 6 (D) 8 (E) 12

26. 以太網路(Ethernet)的連結拓蹼(Topology)為何?

(A) 環狀(Ring) (B) 匯流排(Bus) (C) 星狀(Star) (D) 樹狀(Tree) (E)盒狀

 

27. 下面那些網路服務包含有影像與圖形的顯示功能

1.BBS 2.FTP 3.WWW

(A) 1 only (B) 3 only (C) 1,2 (D) 1,3 (E) 1,2,3

 

28. 下列那種語言是屬於個體導向 (object-oriented, 物件導向)?

(A) C (B) Pascal (C) HTML (D) Java (E) Basic

 

29. 中央處理器(CPU)除了算數運算功能之外, 另一主要功能為:

(A) 邏輯運算 (B) 輸出入功能 (C) 記憶體管理 (D) 螢幕顯示控制

(E) 檔案系統管理

 

30. 以下所列之電腦周邊裝置中, 那一項之屬性與其它項不同?

(A) 滑鼠 (B) 鍵盤 (C) 麥克風 (D) 掃瞄器 (E) 列表機

 

31. 在電腦處理中, 每個中文字需要利用兩個位元組來儲存, 而英文字母則只需要一個位 元組, 其差異主要是因為:

(A) 英文字母結構較簡單 (B) 中文字數較多 (C) 中文辭彙較多 (D) 以上皆是

32. 程式執行時,對不同輸入資料有時候對有時候錯, 最可能的原因是

 (A)程式語法(Syntax) 錯誤 (B) 程式語意(Semantics)錯誤 (C) 邏輯設計錯誤  

    (D) 對輸入資料處理不周延 (E) 作業系統出錯

33. 請問下列那個單元與控制單元(CU)合稱中央處理單元(CPU):

(A) IU (B) OU (C) ALU (D) MU (E) 以上皆非

34. 下列那一個有關 JPEG的敘述是正確的?

(A)是一種資料傳輸的標準 (B) 是一種中文內碼的格式 (C) 是一種影像檔的格式

(D) 是一種影像壓縮的標準 (E) 以上皆非

35. 下面個人電腦上的作業系統那一個有內含支援網路程式?

1.DOS 2. WINDOWS 3.1 3. WINDOWS 95 4. WINNDOWS NT

(A) 1,2,3,4 (B) 2,3,4 only (C) 3,4 only (D) 3 only (E) 4 only

 

36. 下面那些是 WWW 上的導覽系統 ?

1.Microsoft IE 2.BBS 3.Netscape Navigator 4.NEWS 5.Java

(A) 1,3 only (B) 1,3,4 (C) 1,3,5 (D) 1,3,4,5 (E) 3 only

 

37. 在程式執行時,通常會有以下情形:前後距離相距不遠的兩個指令(instruction)若其中

之一被執行,另外一個也會馬上被執行到。這樣的情形叫做

(A) Temporal Locality (B) Functional Locality (C) Instruction Locality

(D) Spatial Locality (E) Program Locality

 

38. 實數存入電腦時, 有些電腦有使用隱藏位元(hidden bit), 其目的是:

(A) 提高可表示之數值的範圍 (B) 使運算更快 (C) 提高準確度(precision)

(D) 使電腦較穩定 (E) 以上皆非

 

39. 為了維持快取記憶體和記憶體間資料的一致性,通常會有一些解決的方法,其中之一就是當改變快取記憶體中的資料時,連主記憶體中對應的部份一併更改。這樣的方法叫做:

(A) Write-Back (B) Write-On (C) Write-Through (D) Write-All (E) Write-Once

 

40. 請問TCP是屬於TCP/IP通訊協定中那一層的服務?

(A) Application (B) Transport (C) Internet layer (D) Network (E) none of the above

 

41. 利用快速排序法 (quick sort)對 n 筆資料排序,在平均情況下(average-case)所需的執行

時間(time complexity)為何? 選最恰當的:

(A) O(n) (B) O(n log n) (C) O(n2) (D) O(n2 log n) (E) O(n3)

 

42. 利用快速排序法(quick sort)對n筆資料排序,在最壞情況下(worst-case)所需的執行時

間(time complexity)為何? 選最恰當的:

(A) O(n) (B) O(n log n) (C) O(n2) (D) O(n2 log n) (E) O(n3)

 

43. 有一部電腦, 其CPU為133 MHz, 則其一個clock之時間為:

(A) 1/133 * 10 -9 (B) 133 * 10 6 (C) 1/133 * 10 -6 (D) 133 * 10 -9 sec (E) 133

 

44. 假設有一部個人電腦,它的記憶體(RAM)容量是W, 硬碟容量是X, 快取記憶體(cache)的容量是Y, CPU內的暫存器(register)容量是Z,一般而言下列何者正確?

(A) Z>Y>X>W (B) X>W>Z>Y (C) X>W>Y>Z (D)X>Y>W>Z (E)以上皆非

 

45. 微處理機中除了主記憶體外尚有快取記憶體 ( cache memory ), 其主要的功能為:

(A) 可以減少磁碟空間 (B) 可以有效地增進程式的整體執行速度 (C) 可以降低主記憶體的成本 (D) 可以減少程式偵錯的時間.

 

46. FIFO 是哪一種資料結構的特性?

(A) stack (B) heap (C) linked list (D) queue (E) none of the above

47.在計算時間複雜度時, 常用Big O來表示, 如f(n)=n+2時, 其複雜度為O(n).

試問f(n)=3n2log n + 100n2 + 10 之Big O函數為何?

O(n) (B) O(n2) (C) O(n (log n+1)) (D) O(n2log n) (E) O(n + log n)

 

48.下列那一個排序演算法(sorting algorithm)是屬於各個擊破(divide-and-conquer)演算法?

(A) 氣泡排序法 (bubble sort) (B) 插入排序法 (insertion sort)

(C) 合併排序法(merge sort) (D) 選擇排序法 (selection sort) (E) 以上皆非

 

49. 利用二元搜尋法 (binary search) 在序列 (1, 3, 4, 7, 9, 10, 16, 17, 18, 20, 21, 23, 29) 中 找尋16 的所在位置,共需作幾次比較 (comparison)?

(A) 1 (B) 2 (C) 4 (D) 7 (E) 13

 

50. Intel 之Pentium-100 CPU其名稱中的 100 表示什麼意義 ?

(A)電腦開機後只要經過 1/100 秒便能完成開機

(B) CPU之同步計時器(CLOCK)的頻率為 100,000,000Hz

(C) CPU之同步計時器(CLOCK)的頻率為 100,000Hz

(D)CPU 每秒可執行 100 個指令(instruction)

(E) CPU 每秒可執行 100萬個指令(instruction)

 

B. 選擇(5選1) 每題2分

 

1. 假設有n個整數,它們的值域的範圍是065535,則下列何者為是:

(A) the worst-case of quick sort is θ(nlogn)

(B) the worst-case of heap sort is θ(n)

(C) the best-case of merge sort is θ(n)

(D) quick sort is one of the optimal comparison sorts

(E) the worst-case of counting sort is θ(n)

2. 欲將一首三分鐘的音樂存成數位檔案,若取樣率是44kHz,每一樣點的解析度是16

bit,在沒有壓縮的情況下,此檔案的大小約為:

(A) 150 MB (B) 15 MB (C) 1.5 MB (D) 0.15 MB (E) 0.015 MB

3. 下列那種網路服務提供超連結 (hyperlink) 功能?

(A) BBS Email (B) Email Gopher (C) Gopher WWW

(D) BBS Gopher (E) BBS WWW

4. 下列四種排序法中, 其排序效能整體來看平均表現最好的是

(A) quick sort (B) bubble sort (C) merge sort (D) insertion sort (E) 一樣好

5. 下列那種特性不屬於個體導向 (object-oriented, 物件導向) 語言?

(A) Polymorphism (B) Inheritance (C) Hashing (D) Data abstraction

(E) Encapsulation

下列那一敘述是正確的?

(A) 十進位6.75的二進位是110.011 (B) 十進位6.75的二進位是110.11

(C) 十進位6.75的八進位是6.3 (D) 十進位6.75的八進位是6.03

(E) 十進位6.75的十六進位是6.6

有一電腦使用64位元(bit)來存實數, 指數部份用10位元; 則理論上共可表示幾個

不同的實數?

(A) 210 (B) 264 (C) 254 (D) 255 (E) 無法決定

一樣物品之價錢介於11000元之間(整數價錢), 利用二元搜尋法 (Binary Search),

保證可在幾次之內猜到正確價錢 (假設每次猜價都會得到正確,較大,或較小之回覆).

10 (B) 12 (C) 16 (D) 8 (E) 5

 

 

9. 有一C語言程式如下:

int a(int x) {return (x+1);}

int b(int y) {return y+a(y+1);}

int c(int z) {if (z>0) {return a(z)+b(z+1)+c(z-1);} return 0;}

void main() { printf("%d\n",c(4)); }

 

請問最後的運算結果是:

(A) 17 (B) 24 (C) 38 (D) 50 (E) 57

以下程式是用Pascal-like 語言寫的:

program test9;

var cnt,ans:integer;

function fib(n: integer):integer;

begin

cnt:=cnt+1;

if(n<=1)then fib:=1 else fib:=fib(n-1)+ 2*fib(n-2);

end;

begin

cnt:=0; ans:= fib(5);

writeln(cnt, ‘ ’,ans);

end.

則此程式輸出:

(A) 36 54 (B) 43 54 (C) 36 43 (D) 15 21 (E) 以上皆非

11. 在二補數表示方式中, 下列那一個8位元的整數最小?

00001010 (B) 10010100 (C) 10000001 (D) 11111111 (E) 00000000

 

關於電腦檔案處理, 以下敘述那一項是錯誤的

一個資料檔案可以有多個索引檔 (B) 索引檔的目的是為了加快資料搜尋

索引檔內容一定按大小排序以利搜尋 (D) 資料檔案中每一筆資料(record)不必固定大小就可以建立索引檔 (E) 索引檔的每一筆(record)資料應固定大小

 

簡單選取排序法(Simple Selection Sort)主要過程(假設由大到小排列):

在未排好序的資料中,找出最大者,然後將該資料與第一個資料對調位置,

重複此程序至未排好序的資料個數等於零為止

請問此排序法將個N資料按大小排序, 所需之時間(或資料比較次數)與何者成正比 ?

(A) N (B) N*(N-1) (C) Log2N (D) N Log2N

設有一二元樹 ( binary tree ), preorder traversal1 2 3 5 8 9 6 10 4 7 11,

inorder traversal2 1 8 5 9 3 10 6 7 4 11. 試問其postorder traversal

11 7 4 10 6 9 8 5 3 2 1 (B) 2 8 9 6 10 7 4 11 5 3 1

(C) 2 8 9 5 10 7 11 4 6 3 1 (D) 2 8 9 5 10 6 3 11 7 4 1 (E) 以上皆非

 

Hanoi Tower的解可以寫成如下的recurrence relation

 

 

 

試問n=16 , T(n) 為多少

217 (B) 216+1 (C) 216-1 (D) 216+16

 

16. 以下為一個C function

int F( int n ) {

if ( n == 0 ) return 0;

if ( n == 1 ) return 1;

return F( n-1 ) + F( n-2 );

}

試問F(12) 為多少?

(A) 89 (B) 128 (C) 233 (D) 144

17. 如圖之network, 以下何者不是其topological order

(A) ABCDEF (B) ABECDF (C) ABCEDF (D) ABDCEF (E)都不是

 

18. T(n) 為處理某問題之時間複雜度T(n)=n+2*T(n/2), T(1)=1, n=2k, T(n)=

log n (B) n log n (C) n + n log n (D) n2 (E) 2n

 

19. 下列四種方法哪一個可用於 Deadlock prevention?

(A) rollback (B) spooling (C) ostrich algorithm (D) two-level scheduling (E) none

20. 假設T是一個具有n個節點(node) m個邊(edge)的無向圖形(undirected graph)。在下面

那些情況下,T絕不可能是一棵樹 (tree)

1. (n, m)=(15, 15) 2. (n, m)=(20, 19) 3. (n, m)=(21, 22)

(A) 1 only (B) 2 only (C) 1, 2 (D) 2, 3 (E) 1, 3

21. 假設S是一個堆疊(stack)INSERT(S, x)表示將資料x存入S中, DELETE(S)會從

S中取出一筆資料傳回。請問執行下列程式段,螢幕上會印出什麼結果?

INSERT(S, 2);

INSERT(S, 3);

INSERT(S, 6);

INSERT(S, DELETE(S)+DELETE(S));

Writeln(DELETE(S));

(A) 2 (B) 3 (C) 5 (D) 6 (E) 9

 

22. 二維陣列array[1][1]位於記憶體中的1000位址, 若為colum major(行為主)的儲存方式,

陣列大小為array[1..20][1..20], 各元素為短整數型態(short int), 請問array[4][3]的位址為:

(A) 1043 (B) 1062 (C) 1086 (D) 1088 (E) 1124

 

23. 下列幾個著名的問題中,哪一個與 IPC 有關?

(A)the travelling salesman problem (B)the sleeping barber problem

(C) the 0/1 knapsack problem (D) the middle-man attack problem (E) none

 

24. 一般電腦內的數字系統是以二進位 ( binary code ) 為基礎, 現在有另外一種數碼系統

叫作格雷碼 ( Gray Code ), 其特點為當數字增加1, 其數碼只會有一個位元有變化

( 01, 10 ). 格雷碼與十進位制之間的轉換須透過二進位之幫助. 45為例, 其二進位為101101, 轉換方式如下

現有一Gray Code 11011010111, 試問其為何數字?

1137 (B) 975 (C) 1354 (D) 1124 (E) 1178

25. 下列何者非國內生產掃瞄器 (scanner) 的廠商?

(A) 力捷 (B) 全友 (C) 鴻友 (D) 台積電 (E) none of the above

教育部全國高級中學八十六學年度

資訊學科能力競賽決賽 筆試答案卷

編號:___________

 

A. 每題一分,共50題。每題答錯倒扣0.25分。

1. ____ 2. ____ 3. ____ 4. ____ 5. ____

6. ____ 7. ____ 8. ____ 9. ____ 10. ____

11. ____ 12. ____ 13. ____ 14. ____ 15. ____

16. ____ 17. ____ 18. ____ 19. ____ 20. ____

21. ____ 22. ____ 23. ____ 24. ____ 25. ____

26. ____ 27. ____ 28. ____ 29. ____ 30. ____

31. ____ 32. ____ 33. ____ 34. ____ 35. ____

36. ____ 37. ____ 38. ____ 39. ____ 40. ____

41. ____ 42. ____ 43. ____ 44. ____ 45. ____

46. ____ 47. ____ 48. ____ 49. ____ 50. ____ A項總分________

B. 每題二分,共25題。每題答錯倒扣0.5分。

1. ____ 2. ____ 3. ____ 4. ____ 5. ____

6. ____ 7. ____ 8. ____ 9. ____ 10. ____

11. ____ 12. ____ 13. ____ 14. ____ 15. ____

16. ____ 17. ____ 18. ____ 19. ____ 20. ____

21. ____ 22. ____ 23. ____ 24. ____ 25. ____ B項總分________

 

總分:_____________

back(3).gif (3040 個位元組)