台北市106年度高级中等学校学生电脑软体设计竞赛初赛.PDF

台北市106 年度高級中等學校學生電腦軟體設計競賽初賽 壹、選擇題 1. 有一個彈珠台軌道安排成 10層的二元樹，彈珠由第 1層的根節點滾下，一直滾到第 10層 才會停下，第 10層有 512個葉節點，編號為 0 到 511 ，每一個內部節點是有記憶的分流 裝置，如果前一顆經過此節點的彈珠往左(右 )邊子節點滾過去，下一顆經過此節點的彈珠 就會往右 (左)邊子節點滾過去，一開始的時候每一個分流裝置都開向左，順序滾下第 1顆 球、第 2顆球、 … ，一直到第361顆球時，請問第 361顆球會停在編號多少的頁節點上 ? (A) 126 (B) 60 (C) 84 (D) 45 2. 在 DVD 光碟中存放資料時，如果沒有適當地運用錯誤更正碼保護資料，光碟片萬一被輕微 刮傷時就會損失很多資料，因此光碟存放資料的標準會運用到下列哪一種編碼來處理資料 ? (A) 統一碼(Unicode) (B) 二維條碼(QR-Code) (C) 霍夫曼 (Huffman) (D)里德 所羅門- (Reed-Solomon, RS) 3. 有一個演算法執行時平均需要做 log (n!)次的關鍵運算，請問其時間複雜度為? (A) O(nn) (B) O(n log n) (C) O(n) (D) O(n!) 4.計算兩個布林運算 ： A = ((x==3 || x==4) y==0) B = (x==3 || (x==4 y==0)) 請問 以下敘述何者正確？ (A)若 A 值 為 真時， B 值 必為真。 (B)若 B 值 為真時，A 值 必為真。 (C)若 A 值 為假時，B 值 必為假。 (D) A 和 B從 不同時為真。 5.已 知某種程式語言計算整數除法 a/b 與 a%b 有二規則： (1)計算結果無條件捨去小數位，例如 10/3 = 3 ，-29/10 = -2 。 (2)對任兩個整數值 a 和 b ，滿足 a = (a/b)*b + a%b 。 請問 128 % (-9)的 結果為何？ (A) -7 (B) -2 (C) 2 (D) 7 6. 有 一棵二元搜尋樹 (binary search tree) ，存放數 值 1, 2, …, 7 ，共七個數值。請問 以下敘述何者正確？ (A) 對這棵二元搜尋樹 施行中序 (in-order) 走訪來列印節點中的數值 ，則 必定依序印 出 1, 2, 3, …, 7 。 (B) 對這棵二元搜尋樹施行前序 (pre-order) 走訪 來列印節點中的數值 ，有可能依序 印 出 1, 2, 3, …, 7 。 (C) 對這棵二元搜尋樹施行後 序 (post-order) 走訪 來列印節點中的數值 ，有可能依序 印 出 1, 2, 3, …, 7 。 (D) 以上皆是。 7. 一個無向圖 (undirected graph) 是由點 (verext)的 集合和無向邊 (edge)的 集合所 組成。以下何者敘述正確？ (A) 若有 N 個點 、(N – 1)個邊，則此圖稱為一個樹 (tree) 。 (B) 若此圖中任兩 個點可 透過一個 以上的邊相連，則此圖稱為一個樹。 (C) 若此圖原本 不存在循環 (cycle) 而增加任意一個邊後便造成循環，則此圖稱為一 個樹。 (D) 以上皆是。 8.若電腦中表示資料的字元只有 26個小寫英文字母與 0,1,2, …, 9 等阿拉伯數字，則每個 字元最少用幾個bits 來表示？ (A)36 (B) 26 (C) 16 (D) 6 ̅ 9. A 、B各代表一個 bit ，則布林代數式 AB+AB= ？ (A) A (B)B (C)0 (D) 1 10.有關 NOR閘之敘述，下列何者錯誤？ (A) 先執行 NOT運算再做 OR 運算 (B)所有輸入皆為 0時，輸出才為 1 (C)可將數個 NOR閘連接起來設計成一個 AND閘 (D)任何邏輯布林電路都可以只用 NOR閘就設計出來 11.一般說來 RSA加密系統與 DE