89筆試試題.doc

Size: px

Start display at page:

Download "89筆試試題.doc"

温缪
5 years ago
Views:

1 八十九學年度高級學資訊學科能力競賽決賽試題選擇題 ( 每題 2 分, 共 100 分, 答案請按題號填寫在答案卷, 如需計算或作圖請利用所附計算紙或試題空白處 ) 1. 在㆒個已有 10 項資料的環狀雙向鏈結串列 (Circular Doubly Linked-List), 加入㆒項新的資料 ( 不是加在串列的頭之 ), 則需要變動幾個指標? (a) 2 (b) 3 (c) 4 (d) 5 2. 在橫向優先搜尋 (Breadth First Search), 需要使用列哪㆒種資料結構? (a) 堆積 (heap) (b) 佇列 (Queue) (c) 堆疊 (Stack) (d) ㆓元樹 (Binary Tree) 3. 在 Relational 資料庫當, 如果㆒個 Relation 的㆒個欄位參照到其他 Relation 的主鍵 (Primary Key) 時, 我們稱這㆒個欄位為何? (a) 主鍵 (b) 副鍵 (c) 特別鍵 (d) 外來鍵 4. 有㆒個 8x11 的㆓維陣列, 以列為主的排列方式儲存在記憶體裡, 第㆒個陣列元素 [0,0] 起始位址為 (25) 10, 如果每個陣列元素佔 1 個記憶體單位, 請問 [3,6] 這個陣列元素會被存放在哪個位址? (a) (47) 10 (b) (53) 10 (c) (55) 10 (d) (64) 使用 Stack 的資料結構, 依序放入 2,3,5,7 ㆕個元素, 拿出兩個元素後, 再放入 11,13 ㆓個元素, 再拿出 1 個元素, 最後再放入 17, 請問結果為何? ( 由至的順序表示 ) (a) 17,11,13,2 (b) 17,13,5,7 (c) 7,11,13,17 (d) 17,11,3,2 1

2 6. 英文字母 A 的 ASCII Code 值是 (65) 10, DEC ㆔個字母在電腦內部表示成 (a) (b) (c) (d) 以純文字檔儲存 100 個學生的基本資料, 每個學生資料包括文姓名 ( ㆕個文字 ) 學號( 八碼, 第㆒碼為英文字母, 其餘七碼為阿拉伯數字 ) 6 個科目的學期成績 ( 成績由到 100.0, 小數取㆒位 ), 欄位之間以空白隔開, 每筆資料間以 1 byte 的控制碼結尾, 請問此檔案大小約多少? (a) 5400 byte (b) 5000 byte (c) 3000 byte (d) 2600 byte 8. 當電腦的硬碟還有約 100MB 的空間, 但是系統執行的速度變慢其原因與列何者有關? (a) 虛擬硬碟 (Virtual Disk) (b) 虛擬記憶體 (Virtual Memory) (c) 快取記憶體 (Cache Memory) (d) 整批處理 (Batch Processing) 9. 依序將 1, 2, 3, 4, 5 push 到堆疊 (Stack), 再 pop 出㆕筆資料然後依 pop 出的順序 enqueue 到佇列 (Queue) 當我們從此佇列 dequeue 取出資料時, 第㆔筆為何? (a) 1 (b) 2 (c) 3 (d) Bootstrap 程式通常放在何種記憶體裡? (a) Flash (b) ROM (c) DRAM (d) SRAM 11. 列的排序法, 哪㆒個在對 7, 13, 45, 68, 91, 154, 189, 225 這組資料做排序時使用的比較次數最少? (a) 堆積排序 (Heap Sort) (b) 快速排序 (Quick Sort) (c) 插入排序 (Insertion Sort) (d) 合併排序 (Merge Sort) 2

3 12. (ab+a b)(a+b )+(a+b) 這個布林方程式可以化簡成列哪個布林方程式? (a) ab + a b (b) a + b (c) ab + a b (d) ab 13. 列哪㆒個是 T(n) = 2T(n / 2) + n 這個遞迴式 (Recurrence) 的解? (a) θ(n lg n) (b) θ(lg n) (c) θ(n) (d) θ(n 2 ) 14. CPU 在執行指令的㆒個循環回合為何? (a) Fetch, Decode, Execute, Store (b) Execute, Fetch, Decode, Store (c) Store, Execute, Decode, Fetch (d) Decode, Fetch, Store, Execute 15. 在 250 筆資料當, 以㆓分搜尋法 (Binary Search) 尋找某㆒筆資料時, 至多只要搜尋幾次即可找到? (a) 6 次 (b) 7 次 (c) 8 次 (d) 9 次 16. 列何種順序所建造的㆓元搜尋樹 (Binary Search Tree) 最平衡 (Balanced)? (a) 30,20,50,5,25,41,80 (b) 5,20,25,30,41,50,80 (c) 80,50,41,30,25,20,5 (d) 50,80,41,30,25,20,5 17. 假設有兩個㆓進位數字 A = , B = , 則 A - B 的數值不為列何者? (a)(199) 10 (b)( ) 2 (c)(306) 8 (d)(c7) 列有關布林函數的等式何者不恆為真? ( 以分別代表 AND OR NOT) (a) X X = X (b) X X = X (c) (X Y) = X Y (d) X (Y Z) = (X Y) (X Z) 3

4 19. A + (B + C) 之前置表示法 (Pre-Order) 為 (a) A+B+C (b) ABC++ (c) +A+BC (d) ++ABC 20. CPU 存取列哪㆒種主要儲存裝置的速度最快? (a) 快取記憶體 (Cache) (b) 暫存器 (Register) (c) 快閃記憶體 (Flash) (d) 動態隨機記憶體 (DRAM) 21. 有 A, B 兩個大小相同的檔案 A 在硬碟儲存在連續的位置, 而 B 檔案是分散的 A 檔案的存取時間比 B 檔案少, 其主要原因是列何者? (a) CPU 執行時間 (Execution time) (b) 記憶體存取時間 (Memory access time) (c) 傳送時間 (Transfer time) (d) 搜尋時間 (Seek time) 22. 列敘述何者錯誤? (a) 有㆒壓縮 (Compression) 程式可以將檔案壓縮成 1/2, 如果執行 5 次可以將此檔案壓縮成 1/64 (b) 電腦病毒必須被執行才可能發作 (c) 被執行的程式片段, ㆒定要放在主記憶體 (Main Memory) (d) 被編譯成機器碼 (Machine Code) 的執行檔, 不可能還原成原來的原始程式 (Source Program) 23. 在定量模式 (Deterministic Modeling), 以面的行程 (Process) 工作量資料評估列 CPU 的排程演算法 (Scheduling Algorithm), 則哪個演算法的平均等候時間 (Average Waiting Time) 最小?( 五個行程都在時間 0 的時候到達 ) 行程 CPU 所需時間 ( 單位 : 毫秒 ) P 1 9 P 2 29 P 3 3 P 4 7 P

5 (a) 先來先做 (First-Come, First-Serve Scheduling) (b) 依序循環 (Round-Robin Scheduling)( 時間量 :10 毫秒 ) (c) 最短的工作先做 (Shortest-Job-First Scheduling) (d) 都㆒樣 24. 列關於 80x86 系列的敘述何者有誤? (a) 是 80x86 系列第㆒個 16-bit 的 CPU (b) 是 80x86 系列第㆒個 32-bit 的 CPU (c) 是 80x86 系列第㆒個有 pipeline 觀念的 CPU (d) Pentium 是 80x86 系列第㆒個可以同時處理㆒個以指令的 CPU 25. 列何者不是造成死結 (Deadlock) 的必要條件? (a) 互斥 (Mutual Exclusion): 至少有㆒個資源 (Resource) 不可被共用 (b) 集要求 (Common Request): 大部分的行程 (Process) 都要求使用某個稀少的資源 (c) 佔用與等候 (Hold-And-Wait): 有個行程佔用至少㆒個資源, 且正等候已被佔用的其他資源 (d) 不可搶先 (Non-Preemption): 不能搶走正在被使用的資源 26. x=a, y=b; Procedure SwapA( x, y: integer); var z: integer; begin z := x; x := y; y := z; end. 在執行以 ㆒個指令 SwapA(a, b) 之後,x 和 y 的值分別為何? (a) x=a, y=a (b) x=a, y=b (c) x=b, y=a (d) x=b, y=b 27. 列有關演算法的描述何者為非? (a) 編譯器的最佳化功能可改善演算法的複雜度 (b) O(n) 演算法的實際執行時間可能比 O(n 2 ) 演算法慢 (c) 虛擬碼是用來描述演算法的㆒種形式 (d) 演算法是用來描述解決問題的法則 5

6 28. 給定 1000 筆資料儲存在陣列, 列有關搜尋 (Search) 的敘述何者錯誤? (a) 經資料排序過後, 利用㆓分搜尋法最多只需要比較約 10 次 (b) 未排序過的資料, 利用㆓分搜尋法最多需要比較 1000 次 (c) 如果資料是文, 經排序後, ㆓分搜尋法最多只需要比較 10 次 (d) 排序過的資料, 利用循序搜尋法最少只需要比較 1 次 29. 將列判斷 n 是否為奇數的演算法以程式實作, 如果 n 是 -5, 執行結果為何? IsOdd(n: integer): Boolean; Begin If (n=1) then return true Else if (n=0) then return false Else Begin n=n-2; IsOdd(n); End End (a) true (b) false (c) stack overflow (d) arithmetic overflow 30. 分別以鏈結串列 (Linked List) 與循序串列 (Sequential List, Array) 儲存 10 萬筆資料, 列敘述何者錯誤? (a) 排序過的鏈結串列利用㆓分搜尋法可以加速查詢 (b) 鏈結串列加入或刪除資料比循序串列所需時間少 (c) 鏈結串列需要額外的空間儲存鏈結 (d) 找第 K 大的資料, 排序過的循序串列比排序過的鏈結串列所需的時間少 31. 如果依序輸入六筆資料, 列何者所建立的㆓元搜尋樹 (Binary Search Tree) 層數最少? (a) 100, 200, 300, 400, 500, 600 (b) 300, 200, 500, 400, 100, 600 (c) 600, 500, 400, 300, 200, 100 (d) 400, 100, 500, 100, 200, 假設資料的長度為 N 位元, 如果我們想達成 Single-Error Correction, Double-Error Detection, 至少需額外加入 x 位元? x 為 (a) 1 位元 (b) 2 位元 6

7 (c) 2 x > N + x + 1 (d) 3 x > N + x 設有變數宣告如 : type vector = array[1..10] of integer ; var a : vector ; b, c: array[1..10] of integer ; d : vector ; 若此程式語言採用名稱等價型態 (Name Equivalent Types), 則變數 a, b, c, d 哪幾個被宣告為相同之資料型態 (Same Data Type)? (a)a, b, c, d 均屬相同之資料型態 (b) 只有 b 與 c 相同 (c)a 與 d 相同,b 與 c 相同 (d)a, b, c, d 均不相同 34. INSERT(S, 2); INSERT(S, 3); INSERT(S, 6); INSERT(S, DELETE(S)+DELETE(S)); Writeln(DELETE(S)); 假設 S 是㆒個堆疊 (Stack),INSERT(S, x) 表示將資料 x 存入 S, 而 DELETE(S) 會從 S 取出㆒筆資料傳回請問執行述程式片段, 螢幕會印出什麼結果? (a) 2 (b) 3 (c) 6 (d) 列何者為置式 (Infix Expression) (A+B)*C-D/E 的後置式 (Postfix Expression)? (a) AB+C*DE/- (b) ABC*+DE-/ (c) AB+C*D-E/ (d) ABCDE+*-/ 的㆓進位表示法是 , 則負數表示法是用 (a) ㆒的補數 (1 s Complement) (b) ㆓的補數 (2 s Complement) (c) 布林代數 (Boolean Algebra) (d) 符號大小 (Sign Magnitude) 7

8 37. 列㆕項, 何項裝置的存取運作速度最快? (a) 動態隨機存取記憶體 (DRAM) (b) 靜態隨機存取記憶體 (SRAM) (c) 光碟機 (d) 硬碟機 38. X Y + X Y + XY 可以寫成 (a)y (b) X + Y (c) X + Y (d) X = (a) (b) 83.B 16 (c) 93.A 16 (d) 動態執行 (Dynamic Execution) 是指 (a) 動態連結 (Dynamic Linking) (b) 動態載入 (Dynamic Loading) (c) 按指令順序執行 (d) 按最有效率的順序執行 41. 列哪㆒種排序法的最佳和最壞狀況皆是 O (n log n)? (a) Merge Sort (b) Quick Sort (c) Heap Sort (d) Bubble Sort 42. 列哪㆒種檔案格式不具有壓縮的特性? (a).bmp (b).jpg (c).mpg (d).tif/.tiff 43. 范紐曼 (Von Neumann) 模式, 排序的複雜度限 (Lower Bound) 為 (a)o(n 2 ) (b) O(n log n) (c) O(n) (d) O(log n) 44. 以 C 語言為例在結構程式設計, 儘量避免使用那㆒指令? (a) goto (b) white (c) if (d) for 8

9 45. 在如的 Pascal 程式, 其執行結果為何? Program L; var n : char; procedure W; begin writeln(n) end; procedure D; var n : char; begin n := D ; W end; begin {L} n := L ; W; D end. (a)ll (b)dl (c)dd (d)ld 46. 列何者有關電腦病毒的敘述有誤? (a) 使用合法版權軟體可以減少感染病毒的機會 (b) 開機型病毒會侵入磁碟的啟始磁區 (Boot Sector) (c) 電腦病毒本身是㆒可能具有破壞性並有自我複製能力的程式 (d) 使用帶有病毒的磁碟開機後, 病毒會隱藏在 ROM 47. 欲執行㆒個高階語言所寫的程式, 所需之準備步驟為何? (a)compile, Link, and Load (b)boot, Load, and Link (c)load, Parse, and Execute (d)link, Load, and Generate 48. 根據以 C 語言寫成之 Player 及 Giant 之 Structure Type Definitions, 以哪㆒個敘述在語法不正確? struct player { char name[10] ; unsigned char player_number ; float batting_average ; } pl1, pl2, *pl3 ; 9

10 struct giant { char g_name[10] ; unsigned char g_player_number ; float g_batting_average ; int label ; } g_pl1, g_pl2, g_pl3, *g_pl4 ; (a)g_pl3 = g_pl1 (b)pl1.batting_average = g_pl2.batting_average (c)pl3->player_number = g_pl4->g_player_number (d)pl1.name = Pete Rose 49. 以是比較㆓個㆓元樹是否相似 ( 即樹的結構相同 ) 的演算法, 則空格需填入 : Function Similar(T1, T2: Tree) : Boolean; Begin If(T1=Nil) AND (T2=Nil) Then Similar is True Else If (T1=Nil) OR (T2=Nil) Then Similar is False Else End; (a)similar is (T1=T2) (b)similar is Similar(T1,T2) AND Similar(T2,T1) (c)similar is Similar(T1,T2) OR Similar(T2,T1) (d)similar is Similar(T1^.Left,T2^.Left) AND Similar(T1^.Right,T2^.Right) 50.. 列遞迴程式的主要目的為何? function What(Head:Ptr;X:Integer):Integer; begin If (Head=nil) then What:=0 else if (Head^.Data=X) then What:=What(Head^.Link) else 10

11 end; What:=1+What(Head^.Link) (a) 在此 List,X 的出現次數 (b) 傳回此 List 的長度 (c) 假如 X 不在 List, 則傳回 1; 反之為 0 (d) 在此 List, 其值不為 X 的資料個數 11

碩命題橫式

碩命題橫式一解釋名詞 :(50%) 1. Two s complement of an integer in binary 2. Arithmetic right shift of a signed integer 3. Pipelining in instruction execution 4. Highest and lowest layers in the TCP/IP protocol suite