109年 - 109桃高教甄初試參考答案(資訊科技).pdf#86520

科目：教甄◆資訊科技概論專業(電腦科) | 年份：109年 | 選擇題數：20 | 申論題數：15

試卷資訊

所屬科目：教甄◆資訊科技概論專業(電腦科)

選擇題 (20)

1.對於廣度優先搜尋(Breath-First Search, BFS)和深度優先搜尋(Depth-First Search, DFS)演算法，假設撰寫為找到任一目標節點後即返回與結束程式，請問下列敘述何者是錯誤的？ (A) 假設樹中有多個符合目標的節點，BFS 一定可以找到最淺的目標節點。 (B) 假設樹中有多個符合目標的節點，DFS 一定可以找到最深的目標節點。 (C) 假設樹中有多個符合目標的節點，BFS 和 DFS 所找到的目標節點可能不是同一個。 (D) BFS 和 DFS 的時間複雜度皆為 O(V+E)，其中 V 為圖中節點數量、E 為圖中邊的數量。

2.使用 SNMP 協定若需穿過防火牆來傳送查詢封包時，則防火牆上必須允許下列哪一種封包通過防火牆： (A) TCP 目的 port=22 (B) UDP 目的 port=161 (C) UDP 目的 port=138 (D) ICMP 。

3.若將一個網段 10.10.0.0/23 平均分割為 8 個子網路 ( Subnet)，則可用的 IP 位址共有幾個？(A)240 (B)510 (C)254 (D)496

( )4.區塊鏈在 FinTech 金融科技中扮演重要的角色，下列針對區塊鏈敘述何者有誤？ (A) 區塊鍊是一個「去中心化的分散式資料庫」 (B) 區塊鍊中每一筆資料一旦寫入就不可以再改動 (C) 區塊鏈有個人化帳本的特性 (D) 區塊鏈是比特幣的底層技術

5.完全二元樹(Complete binary tree)節點編號是由最上層往下，每一層由左而右依序編號。例如四層的完全二元樹共有 15 個節點(第一層有節點 1，第二層有節點 2,3，第三層有節點 4，5，6，7，第 4 層有節點 8-15)。請問節點 1348 會在完全二元樹的第幾層? (A)10 (B)11 (C)12 (D)13

6.下列為一副程式的虛擬碼，其中 B 為函數名稱，而 n、m 為變數。請問呼叫 B(5,3)會得到什麼結果？

(A)8 (B)10 (C)13 (D)15。

.

7.堆疊運作包含了 push (輸入)及 pop(輸出)兩個函數，若依序輸入(push) 1、2、3、4、5 等五個數字，輸入過程中亦可輸出(pop)，則以下何者是可能的輸出順序? (A)14235 (B)42531 (C)23154 (D)35412

8.若有一個程式有 40%的運算是必須循序進行無法進行平行運算的，而該程式在單一核心的處理器上執行時間是 100 秒，則理論上該程式在雙核心與四核心的處理器上的最佳處理時間應為：(A)20秒和10 秒 (B) 30 秒和 15 秒 (C) 50 秒和 25 秒 (D) 70 秒和 55 秒

( )9.從技術標準的角度來看，按照 ITU(International Mobile Telecommunication Advanced)的定義，第四代行動通訊技術標準(4G)，在高速移動狀態下需達到 100Mbps，而靜態傳輸時需達到下列那一個速度? (A) 500Mbit/s (B) 1Gbit/s (C) 3Gbit/s (D) 4Gbit/s

( )10.若要將 44、36、18、37、24 五個數放入雜湊表(hash table)中，請問使用以下哪一個公式計算鍵值比較不會造成碰撞(collision)? ( % 為取餘數運算，/為整數除法 ) (A) n%10 (B) n/10 (C) n%10 + n/10 (D) n%10 - n/10。

11.給定下列程式片段，請問若以該程式判斷全年 365 天(變數 month 為月份，day 為該月所屬日期，不考慮閏年)，有幾天會被判斷成耶誕節?( ! 運算子為邏輯運算 NOT，&&運算子為邏輯運算 AND) (A) 354 (B) 1 (C) 11 (D) 364。

12.以下資料結構與演算法的敘述那些正確?(1)廣度優先搜尋(Breadth-first search)通常使用 stack 進行實作。(2) 在最差的情況下，快速排序演算法(quick sort)效率相較於合併排序(merge sort)來得快。(3)動態規劃演算法 (dynamic programming)使用陣列(array)暫存計算結果避免重複計算。(4)優先權佇列(priority queue)可以使用堆積樹(heap tree)進行實作。(5)2-3-4-tree 是 B-tree 的一種 (A) 1、2、3 (B) 3、4、5 (C) 3、4 (D) 3、5

13.在使用對稱式加密的前提下，N 個使用者需要協商幾個秘密金鑰？ (A) ) (B) 3N (C) 2N (D) N ²。

14 在 Linux 環境中，檔案 test.sh 的屬性為「-rwxr-xr--」，下列哪一個指令無法將檔案屬性改為「-rwxrwxrx」？ (A) chmod 775 test.sh (B) chmod g=rwx,o=rx test.sh (C) chmod g+w,o+x test.sh (D) chmod 755 test.sh。 .

15.在 linux 上建置 MRTG 監測網路流量系統時，通常使用下列那一個命令來設定定時執行量測網路流量及繪製圖表的工作? (A) ls (B) ping (C) crontab (D) mv。

16.下列那一種資料結構不為平衡樹? (A) Heap Tree (B) Binary Seach Tree (C) Red-Black Tree (D)AVL Tree

17.請問下列哪些問題主要用動態程式規劃(Dynamic Programming)來解決? 甲、最長共同子序列乙、最小生成樹丙、最佳矩陣連乘計算順序丁、最短路徑問題 (A) 甲、丙、丁 (B) 甲、乙、丙 (C) 乙、丙、丁 (D) 甲、乙、丙、丁

18.以下這段 C 程式的輸出為何？ (A) 2 (B)4 (C) 8 (D) 16。 );>

19. 在某個推理遊戲中，你的任務是要從四個嫌疑犯中找出真正的小偷，這四個嫌疑犯中只會有一個講真話，也就是其他人都說假話，以下是這四個嫌疑犯的自白，請問真正的小偷是那一位？ Mandy：Jack 偷錢。 Jack：Roland 偷錢。 Roland：Jack 說謊。 Kim：我沒有偷錢。 (A) Roland (B) Mandy (C) Jack (D) Kim 。

20. n 位元的二補數，其最大值為 a，最小值為 b，總共可表示 c 個數值，請問下列何者正確？(A) a = 2^n-1 -1 (B) b = -2^n-1 (C)c = 2ⁿ (D)以上皆是。

申論題 (15)

1. 若想要將 140.122.28.158 與 140.122.28.192 設定在同一個子網路之內，並且要最小化此子網路內的 IP 位址個數，請問子網路遮罩應設為多少?________

2. 有一根 8 公尺長的鋼管，可以切成任意數段的鋼管出售(假設鋼管只能切成 1 公尺的整數倍長)，依據下列的價目表，請問此鋼管最佳切法所得到的最高總售價為何? (2)

3. 假設有 3 個硬碟 A B C 容量分別為 20G，20G，30G，試計算規劃成 RAID5 之後容量是 (3)

4. 給定中序表述式(infix expression): A/(B-C)+D*((E-A)*C/F) , 請問其後序表述式為何？ (4)

5. 使用二進位來對”abcdabaa”進行霍夫曼編碼，而且需要能夠根據編碼迅速解碼回復到原來字串，試問最少需要多少位元來進行編碼? (5)

6. 定義一個具遞迴式的函式如下(Ackerman’s function)其中 A(1,1)=3，請問 A(1,4)= (6)

7. 若以電腦程式計算一個業務員要到 n 個城市拜訪客戶的最短距離，共有多少種情況要計算? (7)

8. 在 C 語言中，假設 b 是一個整數陣列，其在記憶體之起始位址為 1000，且一個整數以 4 個位元組(4bytes)儲存，假設 ptr 是指向 b 的指標變數，則 ptr+2 是多少? (8)

9. 下列程式片段執行結果 a 值為多少? (9)

10. 下列是一個 C/C++程式，請問其時間複雜度為?10

11. 以下這段 C 程式的輸出為何？ (11)

12. 以下這段 Python 程式執行時，若輸入資料為"the zen of python"，則輸出為何？ (12)

13. 高度為 h(假設單一節點的高度為 0)的二元樹最多會有 (13) 個節點。

14. 若完美二元樹（perfect binary tree = full and complete binary tree）有 L 個葉節點(leaf node)，則其總節點數為 (14)

15.以下這段 Python 程式的執行結果何？ (15)