<4D F736F F D20B8EAB054B0F2A5BBAFE0A44F>

Size: px

Start display at page:

Download "<4D F736F F D20B8EAB054B0F2A5BBAFE0A44F>"

寂掌谈
5 years ago
Views:

1 2002 年國際資訊奧林匹亞研習營甄試資訊基本能力測驗本測驗共 50 題, 測驗時間為 50 分鐘 1 下列那一個元件不屬於 CPU? (1) 算數邏輯單元 (ALU) (2) 控制單元 (control unit) (3) 暫存器 (register) (4) 記憶體 (memory) 2 某電腦具有 16MB 記憶體, 其中 16MB 所指為何? (1) bits (2) bytes (3) bytes (4) bits 3 快閃記憶體 (flash memory) (1) 是揮發性記憶體 (volatile memory) (2) 是動態隨機存取記憶體 (DRAM) (3) 可以當成可程式唯讀記憶體 (programmed ROM) (4) 主要用做快取記憶體 (cache memory) 4 JPEG (joint photographic experts group) 壓縮檔主要用來壓縮下列何種檔案? (1) 靜態影像檔 (2) 音樂檔 (3) 視訊檔 (4) 動畫檔 5 下列那一個網路系統不屬於臺灣所有? (1) DAPAR (2) TANet (3) SeedNet (4) HiNet 1

2 6 會重覆複製自己而把整個硬碟填滿自己檔案拷貝的為下列何種病毒? (1) 開機病毒 (boot sector virus) (2) 特洛城木馬 (Trojan horse) (3) 炸彈 (bomb) (4) 蟲 (worm) 7 CPU 的超純量架構 (superscalar architecture) 指的是 : (1) 大量平行運算 (massively parallel computation) (2) 一個時脈週期可以執行超過一個指令 (3) 超強的整數運算 (4) 超強的浮點數運算 8 下列何種作業系統的處理方式和即時處理(real-time processing) 類似? (1) 交談式 (interactive) 作業系統 (2) 批次 (batch) 作業系統 (3) 多工 (multi-tasking) 作業系統 (4) 分時 (time-sharing) 作業系統 9 Microsoft Foundation Class (MFC) 是 : (1) Word 的外掛 (plug-in) 程式 (2) Internet Explorer 的外掛程式 (3) 物件導向的程式庫 (4) 給 Visual Basic 呼叫的 10 在物件導向的概念中, 類別 (class) 與物件 (object) 的關係是 : (1) 物件是類別的子集合 (2) 物件與類別是對等關係 (3) 物件是類別所產生的案例 (4) 物件是繼承類別而來的 11 下列哪一個敘述必為真實的? (1) 使用資料庫的系統絕對不是決策支援系統 (2) 專家系統中對於知識的表達必須是敘述性的 (3) 推理機中的向前推理是一種目標主導的推理法 (4) 人工智慧的程式不能夠用傳統語言 ( 如 PASCAL 等 ) 寫成 2

3 12 下列對於某程式功能的描述中, 從下列那一個敘述可判斷該程式可能為一個專家系統? (1) 根據法則給予適當建議 (2) 動態地配置與回收記憶體空間 (3) 可自動從資料庫中讀取相關資料 (4) 利用財務狀況資料判斷未來的企業風險 13 計算機的記憶體有時在每個位元組上加入一個同位 (parity) 位元, 此位元的作用為何? (1) 可以發現記憶體內容一個位元的錯誤 (2) 可以發現記憶體內容一個位元的錯誤, 並加以更正 (3) 可以發現記憶體內容多個位元的錯誤 (4) 可以發現記憶體內容多個位元的錯誤, 並加以更正 14 下列那一種關係是錯誤的? (1) 10n 2 + 4n = O(n 2 ) (2) 6 2 n + n 2 = Θ(2 n ) (3) loge(n 4 ) = Ω(log2(n)) (4) 6 2 n + n 2 = O( n 2 ) 15 堆疊資料結構通常不適合用來做 (1) 走迷宮 (2) 副程式返回 (3) 遞迴 (4) 緩衝區 16 一般下棋程式所用的方法通常為: (1) 排序 (2) 最小最大搜尋 (min-max search) (3) 最佳化 (4) 二元樹搜尋 17 在一個樹中, 如果有 N 個節點 (node), 則有多少個邊 (edge)? (1) N+1 (2) N (3) 2N (4) N-1 3

4 18 在一個 N 個節點的二元樹中, 任意兩個節點可以找到多少條路徑? (1) N (2) 1 (3) 2 (4) 3 19 如欲使用二元搜尋法, 則資料必須具備以下何種特性? (1) 資料必先經過排序 (2) 資料必須不重複 (3) 資料必須全為正數或全為負數 (4) 資料必須為整數 20 如欲檢驗在給定兩節點之間是否存在一路徑, 則可以使用何種演算法? (a) 深度優先搜尋 (b) 廣度優先搜尋 (c) 二分搜尋 (d) 費式搜尋 (1)ac (2)ab (3)abc (4)abcd 21 如欲尋找在給定兩節點之間之最短路徑, 則可以使用何種演算法? (1) 深度優先搜尋 (2) 廣度優先搜尋 (3) 二分搜尋 (4) 費式搜尋 22 如欲檢驗一算式中所有之小括號 (), 中括號 [], 及大括號 {} 是否對稱, 則下列何種資料結構最適合? (1) stack (2) queue (3) heap (4) hash table 4

5 23. 如將 1,n,2,n-1,3,n-2,,n/2 依序加入一原本為空的二元搜尋樹, 則此樹之高度為 (1) O(log n) (2) O(n) (3) O(n log n) (4) O(n 0.5 ) 24 在執行一個無法結束的遞迴函式(recursive procedure) 時, 會發生什麼樣的問題? (1) 堆疊超出範圍 (stack out of bound ) (2) 陣列超出範圍 (array out of bound) (3) 堆疊溢位 (stack overflow) (4) 停止條件 (stopping case) 25 有一個數列按照二元樹 (binary tree) 的資料結構儲存, 假設欲搜尋的數字為 9, 那麼在搜尋完成前, 至少需要幾次的比較? (1) 1 (2) 2 (3) 3 (4) 4 26 把一個問題切割成若干個小問題, 然後分別去解決個別的小問題, 最後再把小問題的答案結合成大問題的解答, 這樣的方法稱之為 : (1) divide and conquer (2) dynamic programming (3) greedy (4) search 27 有 25 位同學彼此不認識, 每天在圓桌聚餐一次, 每次聚餐後每個人便會與相鄰的二人認識, 則最少需要多少天後才會使得每個人皆彼此認識? (1) 5 (2) 12 (3) 13 (4) 25 5

6 28 設 T 為一個 m 元樹, 也就是 T 中的每一個節點之分支度小於或等於 m 若 T 中共有 n 個節點, 其中內部節點數為 i, 葉節點數為 j, 且共有 k 個分枝則以下何者不恆為真? (1) k = i + j - 1 (2) j (m-1) i (3) n m i + 1 (4) i k/m 29 有六個檔案其中分別包含 9, 7, 6, 5, 4, 10 筆資料, 將此六個檔案兩兩合併, 經五次合併之後成為單一的檔案假設合併兩個檔案所需成本等於這兩個檔案資料筆數之和, 則合併此六個檔案所需之最小成本為何? (1) 41 (2) 82 (3) 104 (4) 有一個初始為空的堆疊, 執行以下動作 : Push A ; Push B ; Pop ; Push C ; Push D ; Push E ; Pop; Pop, 則最後一個 Pop, 會取出何值? (1)A (2)C (3)D (4)E 31 已知下列敘述為真: (a) 張三不喜歡吃西瓜或李四不喜歡吃西瓜 (b) 若王五不喜歡吃西瓜, 則李四喜歡吃西瓜 (c) 若張三喜歡吃西瓜, 則李四喜歡吃西瓜則下列何者為真? (1) 張三不喜歡吃西瓜 (2) 李四不喜歡吃西瓜 (3) 王五不喜歡吃西瓜 (4) 以上皆非 6

7 32 在串列(linked list) 的資料結構中, 假設 head 是指向一個串列的頭的指標, next 是用來指向下一個串列元件的指標現在有一個新增的元件為 p, 要加到此串列的最前頭, 則下列何者為正確的步驟? (1)head next=p; (2)p next=head; head=p; (3)head=p; p next=head next; (4)p next=head next; head=p; 33 已知在一棵二元樹 T 中包含 7 個節點,7 個節點分別存放 A, B, C, D, E, F, G, 且資料不重複今由根節點開始, 以前序 (preorder traversal) 來追蹤此二元樹, 且每走到一個節點便印出節點中的資料, 得到 BDFAGEC 的結果, 以後序 (postorder traversal) 來追蹤這棵二元樹, 得到 AFECGDB 的結果, 則下列何者不可能為由根節點開始以中序 (inorder traversal) 來追蹤這棵二元樹的節點順序? (1) BAFDEGC (2) FADEGCB (3) BDFGAEC (4) AFDEGCB 有一空的堆疊, 以下子程式 (subroutine) 對此堆疊從事資料存取及運算 : PUSH X : 把 X 這個整數存入推疊最上方 POP : 把推疊最上方資料取出, 並列印在螢幕上 SWAP : 把推疊最上方兩個資料交換位置 ADD : 取出推疊最上方兩個資料, 相加後再 PUSH 到推疊 34 假設堆疊剛開始不存放任何資料, 執行 PUSH 5 PUSH 6 SWAP POP 後, 則此堆疊的內容由上而下為 (1)5 6 (2)6 5 (3)5 (4)6 7

8 35. 假設堆疊剛開始不存放任何資料, 執行 PUSH 3 PUSH 4 ADD PUSH 5 後, 則此堆疊的內容的由上而下為 (1)7 5 (2)5 3 4 (3)5 7 (4) 假設堆疊剛開始不存放任何資料, 執行 PUSH 101 PUSH 33 POP PUSH 29 ADD POP 後, 則最後一個 POP 會列印 (1)33 (2)101 (3)130 (4)134 有一佇列 (Queue), 以下子程式 (subroutine) 對其從事資料存取及運算 : ADDQ X: 把 X 這個整數加到貯列最後方 DELQ : 把貯列最前方資料取出, 並列印在營幕上 REVQ : 把貯列中所有資料的先後循序相反, 也就是原先最前方的資料變成最後, 第二個變成例數第二, 以此類推 37 假設佇列剛開始不存放任何資料, 執行 ADDQ 1 ADDQ 2 ADDQ 3 DELQ ADDQ 4 後, 則此佇列的內容由前到後為 : 8

9 (1) (2)4 3 2 (3)2 3 4 (4) 假設佇列剛開始不存放任何資料, 執行 ADDQ 7 ADDQ 8 ADDQ 9 DELQ ADDQ 10 REVQ 後, 則佇列的內容由前到後為 (1) (2) (3)7 8 9 (4) 在下列宣告後, Sat 之值為何? typedef enum weekdays { Sun, Mon, Tue, Wed, Th, Fri, Sat }; (1) 5 (2) 6 (3) 7 (4) 8 40 如果要設計一個計算 n 總和的遞迴程式, 下列的程式碼應填入何項? function sum(n) begin if n=1 then sum:=1 else sum:= end. (1)sum(n-1)+1 (2)sum+1 (3)sum(n)+1 (4)sum(n)+sum(n-1) 9

10 41 執行下列程式片段後,A[8] 元素內的值為何? A[1]:=1; A[2]:=1; For i = 3 to 10 do A[i]:= A[i-1] + A[i-2] Endfor (1)1 (2)3 (3)13 (4)21 42 執行下列程式片段後, 螢幕的顯示為何? int a[3][3]={{11,12,13},{14,15,16},{17,18,19}}; int *b,*c; b=*(a+1); c=*a+1; printf("\n%d %d",*b,*c); (1) (2) (3) (4) 在下列宣告與指令運算後, 執行 string1 之列印 (printf), 下列何種字串會出現? char string1[] = { dog }; char string2[] = { house }; string1[1] = 2 ; *(string1 + 3) = a ; *(string1+8) = b ; (1) d2gahousb (2) d2g (3) 2oghaousb (4) dog 10

11 44 執行下列的程式片段後, 螢幕的顯示為何? void test(int m, int* n){ m=10; *n=m+(*n); } void main(){ int i=5,j=2; test(i,&j); printf("\n%d",i+j); } (1) 7 (2) 12 (3) 17 (4) 下列程式片段的執行結果為何? PROGRAM test1; VAR a,b,c:integer; PROCEDURE count(x:integer; var y:integer; z:integer); BEGIN y := x+z; END; BEGIN a:= 1; b:= 2; c:= 3; count(a,b,c); count(b,c,a); writeln(a,b,c); END. (1) (2) (3) (4)

12 46 下列程式片段的執行結果為何? PROGRAM test2; VAR a:integer; PROCEDURE trans; VAR a:integer; BEGIN a:= 5; END; BEGIN a:= 1; trans; a:= 3; writeln(a); END. (1) 1 (2) 3 (3) 5 (4) 無法執行以下題目所用到的程式碼片段是以類似 Pascal 語法的虛擬碼所撰寫 47 在下列虛擬碼的程式中, 假設 F 和 G 是兩個檔案, 檔案內容是若干筆的整數資料, 而 R 和 S 是兩個整數變數已知 F 檔案內的數字已按照非遞減的方式排列 (non-decreasing order) 則下列的程式虛擬碼片段會做什麼動作? Open_for_read (F); Open_for_write (G); Read (F, R); S := R; Write (G, S); While (not EOF(F)) do Begin Read (F, R); If (R <> S) then Begin S := R; Write (G, R); End; End; (1) 將 F 檔案中, 不連續重複出現的資料複製到 G (2) 將 F 檔案中, 出現兩次或兩次以上的資料複製到 G (3) 將 F 檔案中, 不出現於 G 檔案中的資料寫到 G (4) 將 F 檔案中, 每筆資料寫兩次到 G 12

13 48 假設 ArrayType 是一個大小為 Max 的整數陣列資料型態 (array [1..Max] of Integer ), 而 N 介於 1 和 Max 之間, 則執行下列的程式虛擬碼片段會有什麼結果? Function What ( A : ArrayType;N, T : Integer) : Boolean; Begin If (N = 1) then What := (A[1] = T) Else if (A[N] = T) then What := True Else What := What (A, N-1, T); End; (1) 如果 A 陣列的第一個或最後一個元素值等於 T 值, 傳出 true (2) 傳出 A 陣列元素中, 等於 T 值的元素個數 (3) 傳出 A 陣列元素中, 等於 T 值的最後一個元素索引值 (index) (4) 如果 A 陣列中有元素的值和 T 值相等, 傳出 true 49 假設 X 陣列的內容如右 : [1, 25, 74, 13, 82, 53, 29, 31, 90, 2, 66, 60, 41, 11, 73], 且 N = 5, 則 Mystery (X, N) 傳出的值為何? function Mystery (X : IntArray;N : Integer) : integer; Var Temp := integer; Begin If (N = 1) then Mystery := X[1] Else Begin Temp := Mystery (X, N-1); If (X[N] > Temp) then Mystery := X[N] Else Mystery := Temp; End; End; (1) 1 (2) 11 (3) 82 (4) 在下列什麼條件下, 函式 Mystery 會遞迴呼叫? (1) If (X[N] > Temp) (2) If (X[N] < Temp) (3) If (N = 1) (4) If (N <> 1) 13

資料結構與演算法複習試題(出自：全國資訊競賽89, 91、IOI 2002, 2003)

資料結構與演算法複習試題(出自：全國資訊競賽89, 91、IOI 2002, 2003) 資料結構與演算法複習試題 ( 出自 : 全國資訊競賽 89, 91 IOI 2002, 2003) Stack and Queue 1. 假設指令 ENQ X 的動作是將暫存器 X 的值存入佇列, 指令 DEQ X 的動作是自佇列取出一個數目存入暫存器 X 中若暫存器 A B C D 的內含值分別為 6 7 8 9 時, 依序執行 ENQ A ENQ B DEQ C DEQ D ENQ C ENQ