106年 - 國立台南第二高級中學106學年度第1次教師甄選筆試-資訊科技概論科#61536

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

試卷資訊

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

選擇題 (5)

1. ( ) 下列何者為運算式「9-8/4+1」所對應的「前置」(prefix)表示式？ (A) +-9/841 (B) 9-8/4+1 (C) 984/-1+ (D) -9/84+1

2. ( ) 用 8 位元 1 的補數來表示「－45」，應得到： (A) 00101101 (B) 01000101 (C) 11010010 (D) 11000101

3. ( ) 以下哪一種排序演算法是使用 divide and conquer 原理進行排序？ (A) 氣泡排序 Bubble Sort (B) 堆積排序 Heap Sort (C) 合併排序 Merge Sort (D) 插入排序 Insertion Sort

4. ( ) 以下關於資料結構與演算法的敘述哪些正確？(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) 1、3 (C) 3、4 (D) 3、5 (E) 3、4、5

5. ( ) 以下關於網路的 IP 位址、MAC 與 port 的敘述哪些正確？(1) MAC 為網路卡上的位址，MAC 的長度為 4 位元組。(2) IP 位址可以設定於作業系統上，可以更改。(3) IPv6 的長度為 16 位元組。(4) 2001::2121::cd32 是合法的 IPv6 位址。(5) port 號碼為 443，主要用於 HTTPS 的服務。 (A) 2、3、4 (B) 2、3、5 (C) 1、3、5 (D) 3、5 (E) 3、4、5

申論題 (13)

1. 假設某個二元樹的中序（inorder）走訪順序是 BEDFGAC，而後序（postorder）走訪順序是 EGFDBCA，則其前序（preorder）走訪順序為？。（3%）

2. 有 100 個士兵想要過河，只能透過附近岸邊的一個小船過河，船上面剛好有兩個小男孩在上面玩。這艘船只能一次乘載兩個小男孩或一個士兵的重量，划船時只需要一個士兵或小男孩就可以。請問在這兩個小男孩的協助下，讓所有士兵都可利用這條小船渡過河，渡船最少要來回兩岸幾次？。（4%）

3. 四個人打算過一座吊橋，開始時他們都位於該橋的一側，天很黑，四個人手裏只有一個手電筒。該橋一次最多只能同時過兩個人，無論是一個人或兩個人過橋都需要使用手電筒來照明看路，而且手電筒只能讓人攜帶過橋的方式傳遞。四個人過橋速度都不一樣，第一個人過橋需要 1 分鐘，第二個人需要 2 分鐘，第三個人需要 5 分鐘，第四個人需要10 分鐘。由於速度不同，兩人過橋的時間以最慢的人為標準。請問 4 個人過橋的至少需要幾分鐘？。（4%）

【已刪除】

4. 下圖代表一個城市的地圖，圖中灰色的部分是不可通行的區域。所有道路都是直線，請找出從 A 到 B 所有最短路徑的總數 (所有的最短路徑長度必須都是相同的，但是所選擇的路線都不能相同) 。（4%） phpEiz9dv

【已刪除】

5. 下列程式執行後 main 函數內的變數 i 的值為何？如果程式無法執行，或編譯錯誤，則請針對錯誤原因簡短說明。（4%） phpYutRFD

【已刪除】

6. 下列程式執行後 x 函數被呼叫幾次？如果程式無法執行，或編譯錯誤，則寫出錯誤類型，並針對錯誤原因簡短說明。（4%） phpCfUEq3

7. 使用二進位來對”abcdabaa”進行編碼，而且需要能夠根據編碼迅速解碼回復到原來字串，詴問最少需要多少位元來進行編碼？。（4%）

【已刪除】

8. 根據下列 C 語言程式碼，螢幕的輸出結果為何？如果出現錯誤，則針對錯誤原因進行簡短說明。。（4%） phpa13WUl

9. 請只用一行的 C 語言表示式，來判斷一個整數變數 t 是否為 2 n 次方，t 變數中的值＞0，如果 t=2n，則傳回 1，反之則傳回 0。該表示式中不能使用【if、while】等條件判斷，也不能使用【while、for】等迴圈敘述。（4%）第三大題：簡答題（共 4 題）

1. 請寫出在作業系統（Operating System）中產生死結（Deadlock）的四個必要條件，並簡要說明其條件內容。（10%）

2. 河內塔(Tower of Hanoi)傳說它源自古印度神廟中的一段故事。而這間神廟有三根柱子，其中一根上面串滿了64個金盤。天神指示寺院裡的僧侶將64個金盤移動到另一個柱子，規定在每次的移動中，只能搬移一片金盤，並且在過程中必須保持金盤由上至下是直徑由小至大的次序移動；人們相信依據天神的指示當這些盤子被移動完畢，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。請簡要的解釋什麼叫做「遞迴 Recursion」並且以虛擬碼 pseudo code 的形式寫下利用遞迴的概念如何解決河內塔問題？（10%）

3. 給定 4 個 node，共可組成幾種不同的二元樹？請全部詳列出來。（10%）

(1)請使用「錢幣面額為 1、5、7、13，目標金額為 17」為範例，寫出此題解題過程，動態規劃演算法(Dynamic Programming)使用陣列暫存結果，解答須包含陣列元素所代表的意義，陣列初始值如何設定，一次考慮一種硬幣面額對陣列的影響，最後顯示目標金額為 17 的最少硬幣數，請使用文字說明與陣列(表格)呈現計算的過程。 (2)將題(1)的想法轉換成 C 語言或虛擬碼(pseudo code)。