所屬科目:教甄◆電腦科專業
8.執行下列程式片段,輸出結果為何?(A)3(B)4(C)5(D)6(E)7
12.數字迷宮為一個二維的數字陣列。可以用上、下、左、右方向在迷宮中尋訪。假設每一 格的數字代表造訪該格的成本,那麼求出從入口(左上角)走到出口(右下角)所需的最小成本。何種演算法能找出最小成本?(A)Bellman-FordAlgorithm(B)Dijkstra Algorithm (C) Floyd-Warshall (D) Kruskal Algorithm (E) Prim Algorithm
2.從兩個數字中找出最大的一個而不使用判斷描述,修改下列程式碼 空白 內容為何?
2.二元樹(binarytree)的定義是:樹的每個內部節點(internalnode)最多只有兩個子節點。如下圖的二元樹所示,每個節點最多只有兩個子節點,亦即最多只可以有兩棵子樹(subtree)。 它有一個性質:例如第3階層最多有23−1=22=4個節點,據此推論,第五階層最多應該 有25−1=16個節點。只要簡單畫出幾階層滿滿的二元樹,應該可以看出其規律性。請使用數學歸納法(MathematicalInduction)分成三個步驟證明「高度為i階層的二元樹所有節 點數目最多為2i−1個」。(11分)
(一)在霍夫曼樹(HuffmanTree)中,針對每個節點,將連至左子樹的邊標為0,將連至右子樹的邊標示為1。霍夫曼樹(HuffmanTree) 的每個葉節點代表一個相異字元,且葉節點的個數恰等於相異字元的個數。
(二)針對每個由根節點至葉節點的路徑,將其所經過邊的標示連結起來,並指派給對應葉節點所代表的字元,此即霍夫曼編碼(HuffmanCode):針對相異字元, 統計其出現的次數如下,輸出A, B, C, D, E, F, G對應到的霍夫曼編碼位元數(長度)