108年 - 國立新竹女子高級中學108學年度第1學期第1次教師甄選資訊概論科試題#75551

選擇題 (12)

6. 在公開金鑰的密碼系統中，既要讓資料在傳送的過程中是以亂碼的方式呈現，除接收者外任何第三方皆無法窺看到資料內容；且要讓傳送者無法否認曾經傳送過此訊息，則需以哪兩個金鑰同時加密才能達成此目的？ (A) 接收者的公鑰及傳送者的私鑰 (B) 接收者的公鑰及傳送者的公鑰 (C) 接收者的私鑰及傳送者的私鑰 (D) 接收者的私鑰及傳送者的公鑰

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

8. 由於堆疊(stack)的資料結構特性，下列哪一種常見程式問題較不可能使用 stack 實作？ (A) 判斷括號合理性 e.g.,"(( )( ))" → True (B) 集合合併(Union-find) (C) 尋找 01 矩陣中的最大連通塊 (D) 文字運算式計算 e.g.,"1+2×3-4" → 3

9. A Windows 內建的遠端桌面連線、B TeamViewer、C FileZilla Server、D Chrome 遠端桌面，對於以上四種內建或額外安裝的軟體，請問哪些能夠達到遠端桌面控制(如：啟動遠端電腦內之程式、使用該遠端電腦登入內網系統等)，其中除了控制端操控者外，亦允許被控制端使用者同時看到操作過程？ (A) ABCD (B) ABD (C) AB (D) BD (E) B

10. 由於 Linux 作業系統中軟體控管指令 yum 與 apt-get 的系統依賴性，在其上升級哪一種程式語言的預設版本時需特別注意與處理？ (A) C (B) Python (C) Java (D) PHP

11. 在 Linux 伺服器端架設自由開源軟體 Moodle 課程平台與 WordPress 網誌平台前，需先啟用一些服務，對於這幾個架設網站平台常使用到的服務，被俗稱為「LAMP」。下列哪一項並非架設 Moodle 與 WordPress 所需先啟用的服務？ (A) Apache (B) MariaDB (C) Python (D) PHP

12. A 想要刪除某一資料夾與其下所有內容(包含子資料夾和檔案)，需下達「rm –r」指令。 B 想要跳回上一個工作階段所在目錄，需下達「cd ~」指令。 C 因檔案過大導致檔案內容檢視加載過慢，可考慮改為使用「less」指令進行檔案檢視。 D 想對程式導入輸入檔與導出輸出檔，需下達「輸入檔＞程式名稱＞輸出檔」指令。 E 啟用網頁伺服器服務後，預設的網頁資料夾通常位於「/usr/www/html/」資料夾下。對於 Linux 作業系統，以上哪些敘述是正確的？ (A) ABD (B) AC (C) DE (D) BCE

申論題 (31)

1.1

1.2

1.3

1.4

1.5

1.6

2. 有一個二元樹(binary tree)中序(In-Order)為 DFBAEGC，後序(Post-Order)為 FDBGECA，請畫出所對應的二元樹結構。(此題 3 分)

3.1

3.2

4. 請依下列鍵值插入順序建立一棵 AVL Tree。鍵值依序為 Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov 及 Dec，鍵值大小請以字典序做比對。(此題 3 分)

5. 請畫出下圖的最小成本生成樹(minimum cost spanning tree)。

6. 有一個 AOE(Activity-on-Edge) 網路如下，請找出其臨界路徑(Critical Path)。

7. 對於遞迴關係式 T(n) = 2*T(n/2) + n, T(A) = 1，求時間複雜度 =_____ 。

8. 對於遞迴關係式 T(n) = T(n-1) + T(n-2), T(0) = 0, T(A) = 1，求時間複雜度 =______ 。

9.1

9.2

9.3

10. 若 Huffman 編碼：A = 10、B = 101、C = 110，則 1011010101101110 解碼後訊息為何？

11. 瀏覽器上的網址是「https://」開頭時，代表資料傳送或網頁瀏覽將經過加密傳送，請問這是使用何種安全協定？

12. 下列程式碼執行後的輸出結果為何？

13. 下列程式碼執行後的輸出結果為何？(此題 3 分)

14. 下列程式碼執行後的輸出結果為何？

15.1

15.2

16. 「無限背包問題」又被稱為「完全背包問題」，即有 n 種物品和一個耐重上限為 W 的背包，對於每種物品有其重量大小 weight 和所屬價值 cost。假設每種物品都有「無限多個」可以索取，在不超過背包耐重上限之下，求出可放入背包的最大物品價值總和。下列為無限背包問題的程式碼，假設背包耐重上限為 9 個單位，四種物品的重量大小與所屬價值如下表，呼叫 find(weight, cost, 4, 9)後輸出結果為何？(此題 3 分)

17. 對於下列程式碼，使用下圖的樹狀結構呼叫 find(root)後輸出結果為何？(此題 3 分)

18. 當遇到電腦無法瀏覽網頁時，會先進行簡易的障礙排除：第一步，檢查電腦 IP、子網路遮罩、預設閘道等設定是否正確。第二步，若電腦設定皆正確，則先嘗試與內網主機 ip 相連、再嘗試與外網主機 ip 相連。第三步，若有主機無法相連，則嘗試偵測為路徑中哪一個節點造成斷線。第四步，若皆無異常則檢查DNS Server運作狀態，即輸入主機名稱是否能解析出對應ip。按照上述四個步驟排序，所對應的 Windows 指令 A ping、B nslookup、C ipconfig、D tracert 依序為 _________。(此題 3 分)

1. 簡要描述什麼是區塊鏈(blockchain)？它的應用和趨勢為何？它的缺點為何？

2. 請對下列兩門 1 學期 2 學分，共 18 週的課程「擇一」進行簡要課程設計：其中一門為多元選修，對象為30位未曾接觸高中資訊課程，但對資訊有興趣的高一學生。另一門為加深加廣選修，對象為 30 位已有半年程式基礎，並對資訊有興趣的高二學生。課程設計中需包含課程名稱、教學目標、課程內容與時間安排、教學平台與工具、所需軟體與硬體、評量方式，若設計與其他科別協作或需其他資源配合亦請描述。

3. 由於學習歷程檔案的上路，除了課堂成績與課堂學習成果，多元表現(如：課外活動、競賽、檢定等)亦越趨重要。對於對資訊領域有興趣的學生，請分為未有任何程式基礎、已有部分程式基礎、初涉資料結構與演算法，此三種不同能力程度的學生，簡要描述所給予的課堂外規劃建議和推薦的資源。

4. 「Two Sum」是一個既經典又充滿巧思的題目，題目敘述如下：

108年 - 國立新竹女子高級中學108學年度第1學期第1次教師甄選資訊概論科試題#75551

試卷資訊

選擇題 (12)

申論題 (31)