112年 - 112 桃園市立高級中等學校教師聯合甄選試題:資料處理#113999

選擇題 (13)

1.請選出作用於應用層（applicationlayer）的通訊協定(A)VoIP(B)TCP(C)SMTP(D)UPD (E)IP。

2.下列關於自由軟體（freesoftware）的描述何者不正確(A)可以免費下載(B)可任意複製、散佈、安裝(C)可以使用其完整功能(D)沒有試用期的限制(E)不能任意修改，並重新發行成為可被販賣的軟體。

3.假設系統存取快取記憶體的時間為25奈秒(Nanosecond,ns)，直接存取主記憶體的時間為150ns，若系統採用混合快取記憶體與主記憶體的方式儲存分頁表(pagetable)。在快取記憶體的命中率(hitratio)為99%，且目標資料皆儲存於主記憶體的情況下，此系統每次存取到目標記憶體所需的期望時間為(A)176.25ns(B)26.25ns(C)176.5ns(D)175ns(E)以上皆非。

4.費氏數列(Fibonaccinumbers)定義如下：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)ifn＞1。定義新的數列如下：F(0)=0,F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)+F(n-3)ifn＞2，在定義新的數列中，F(3)=3，F(8)為何？(A)20(B)37(C)67(D)68(E) 125

5.以下排序法為傳統未改良的演算法。以下哪一種排序法，排序n個元素的陣列時，在最佳情況（bestcase）和最壞情況（worstcase）下，其時間複雜度均為O(nlogn)？(A)泡沫排序法(BubbleSort)(B)插入排序法(InsertionSort)(C)合併排序法(MergeSort)(D)快速排序法 (Quick Sort) (E) 選擇排序法 (Selection Sort)

6.在一個完滿二元樹（FullBinaryTree）中，其樹葉節點有128個，則整個二元樹共有多少個節點？(A)255(B)256(C)511(D)512(E)129

7.檢驗算式中所有之小括號()、中括號[]及大括號{}是否對稱，以下哪一種資料結構最適合？(A)queue(B)stack(C)heap(D)hashtable(E)tree

8.執行下列程式片段，輸出結果為何?
(A)3(B)4(C)5(D)6(E)7

9.請選出下列何者為揮發性記憶體(A)暫存器(B)記憶卡(C)硬碟(D)快取記憶體(E)以上皆是。

10.請選出下列何者的值與其他的都不相同(A)111000012(B)215(C)3418(D)E216(E)以上皆不相同。

11.以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為節點，這些邊都有一個數值，代表此邊的成本。我們可以去除圖形中的某些邊，使得剩下的邊能連結所有的節點，何種演算法能使佈線成本最低。 (A)Bellman-FordAlgorithm(B)DijkstraAlgorithm(C)Floyd-Warshall (D)KruskalAlgorithm(E)PrimAlgorithm

12.數字迷宮為一個二維的數字陣列。可以用上、下、左、右方向在迷宮中尋訪。假設每一格的數字代表造訪該格的成本，那麼求出從入口(左上角)走到出口(右下角)所需的最小成本。何種演算法能找出最小成本？
(A)Bellman-FordAlgorithm(B)Dijkstra Algorithm (C) Floyd-Warshall (D) Kruskal Algorithm (E) Prim Algorithm

13.以下哪些問題通常使用動態程式規劃(DynamicProgramming)來解決？ (A)最長共同子序列（LongestCommonSubsequence）：在兩個序列中找到一個最長的子序列，該子序列在兩個序列中以相同的順序出現 (B)最小編輯距離（MinimumEditDistance）：計算將一個字串轉換成另一個字串所需的最小編輯次數。 (C)最長遞增子序列（LongestIncreasingSubsequence）：在一個數列中找到一個最長的遞增子序列。 (D)最小生成樹（MinimumSpanningTree）：在一個連通的帶權無向圖中，找到一棵包含所有節點的樹，且所有邊的權值總和最小。 (E)最短路徑問題（ShortestPathProblem）：在一個帶權有向圖中，找到從一個起點到其他所有節點的最短路徑。

申論題 (12)

1.A的值為00000000，B的值為10000001，則經過（AORB）XOR（NOTB）運算後的結果為何？_______

2.從兩個數字中找出最大的一個而不使用判斷描述，修改下列程式碼空白內容為何？

3.輸入資料為9,4,1,5,12,11,10,15,2,3，建立一個二元搜尋樹(BinarySearchTree)，輸出二元搜尋樹的後序拜訪的結果_______。

4.在Knuth的一本書"TheArtofComputerProgramming-Volume1"有一些產生排列的技巧。其中有一個方法是這樣的：對一個已經存在的排列：A₁A₂A₃,...,A_n-1，如果要插入一個X，所有可能插入的方式為： X_A1A₂A₃,...,A_n-1，A₁XA₂A₃,..., A_n-1，A₁A₂ X A₃, ... , A_n-1，...，A₁A₂A₃, ... , X A_n-1， A₁A₂A₃, ... , A_n-1X 例如：從2314這個排列要插入5在所有可能的位置，可以得到_________

(a)請將下列運算式轉換成後序運算式，即後綴表示法(ReversePolishNotation)，再用運算式二元樹表示。 1+2*3+4/5

(b)已知走訪一棵二元樹得到的中序與後序的結果：

中序走訪順序：DBFEAHCGI

後序走訪順序：DFEBHIGCA

請根據上述走訪順序，建立這一棵二元樹。

(c)承上題，這一棵二元樹的前序走訪順序為何?

2.二元樹(binarytree)的定義是:樹的每個內部節點(internalnode)最多只有兩個子節點。如下圖的二元樹所示，每個節點最多只有兩個子節點，亦即最多只可以有兩棵子樹(subtree)。它有一個性質:例如第3階層最多有2³⁻¹=2²=4個節點，據此推論，第五階層最多應該有2⁵⁻¹=16個節點。只要簡單畫出幾階層滿滿的二元樹，應該可以看出其規律性。請使用數學歸納法(MathematicalInduction)分成三個步驟證明「高度為i階層的二元樹所有節點數目最多為2ⁱ−1個」。(11分)

3.給定二元搜尋樹(BinarySearchTree)，請寫出在給定的二元搜尋樹，找到最大值資料所在節點(node)的演算法。(6分)

4.Kruskal演算法：假設節點數為n，Kruskal演算法是將各邊先依成本(權重值)的大小由小到大排列，接著從成本(權重值)最低的邊開始加入最小成本生成樹,如果加入的邊會造成循環(迴路)則捨棄不用，直到加了n-1個邊為止。如何判斷邊是否造成循環(迴路)?(6分)

(一)在霍夫曼樹(HuffmanTree)中，針對每個節點，將連至左子樹的邊標為0，將連至右子樹的邊標示為1。霍夫曼樹(HuffmanTree) 的每個葉節點代表一個相異字元，且葉節點的個數恰等於相異字元的個數。

(二)針對每個由根節點至葉節點的路徑，將其所經過邊的標示連結起來，並指派給對應葉節點所代表的字元，此即霍夫曼編碼(HuffmanCode):

針對相異字元, 統計其出現的次數如下，輸出A, B, C, D, E, F, G對應到的霍夫曼編碼位元數(長度)

112年 - 112 桃園市立高級中等學校教師聯合甄選試題:資料處理#113999

試卷資訊

選擇題 (13)

申論題 (12)