資訊文生研習室 : TQC+ 軟體開發知識第一類第176~200題

176.

如附圖所示，請將此圖中的樹轉換成二元樹，依階度順序列出的結果，下列哪一項正確？
(A) 1、2、5、3、6、4
(B) 1、2、3、5、4、6
(C) 1、2、5、6、3、4
(D) 1、2、3、4、5、6　
Ans: A

177. 假設一個二元樹擁有300個節點，請問其最小高度，下列哪一項正確？
(A) 12
(B) 9
(C) 6
(D) 4
Ans: B

178.

如附圖所示，請問樹的深度下列哪一項正確？
(A) 1
(B) 2
(C) 3
(D) 4
Ans: D

179. 假如一個二元樹只有三個節點，因其可以組合成多種型態，下列組合數量哪一項正確？
(A) 5種
(B) 4種
(C) 3種
(D) 2種
Ans: A

180.

如附圖所示，圖中所示為一個運算子的二元樹，試問其前序（Prefix）下列哪一項正確？
(A) 選項　A
(B) 選項　B
(C) 選項　C
(D) 選項　D
Ans: D

181. 有一個字串資料如下：2、5、6、9、11、14、16、18、24、33、37、40、45、48、50，若用二元搜尋法（Binary　Search）找37，下列比較次數哪一項正確？
(A) 3
(B) 4
(C) 5
(D) 6
Ans: B

182. 假設有一個陣列，其中資料為：4、2、6、5、1、7、3、8，我們用快速排序法（Quick　Sort）由小排到大，用最左邊的元素當軸，請問第一階段的排序結果下列哪一項正確？
(A) 12346758
(B) 12345768
(C) 23145768
(D) 23146758
Ans: C

183. 使用氣泡排序法（Bubble　Sort）處理n筆資料，最快只需要比較幾次即可完成排序？
(A) n
(B) n-1
(C) n+n2
(D) (n+n2)/2
Ans: B

184.

如附圖所示，在河內塔（Tower　of　Hanoi）的問題中，若今天要搬動3個盤子，到最右側的圓柱，並且此3個盤子從上而下的排列必須由小到大，則最少必須搬動的次數，下列哪一項正確？
(A) 3次
(B) 10次
(C) 7次
(D) 6次
Ans: C

185. 當輸入資料中有多個相同的資料，其排序前跟排序後，任二個相同的資料前後順序不變者，即為穩定排序法（Stable　Sort），請問下列哪一項排序法為穩定排序法？
(A) 堆積排序法（Heap　Sort）
(B) 快速排序法（Quick　Sort）
(C) 合併排序法（Merge　Sort）
(D) 泡泡排序法（Bubble　Sort）
Ans: D

186.

如附圖所示，若演算法的時間複雜度（Time　Complexity）由小到大排序，下列哪一項正確？
(A) 選項　A
(B) 選項　B
(C) 選項　C
(D) 選項　D
Ans: C

187.

如附圖所示，若演算法的時間複雜度（Time　Complexity）由小到大排序，下列哪一項正確？
(A) 選項　A
(B) 選項　B
(C) 選項　C
(D) 選項　D
Ans: A

188.

如附圖所示，下列敘述哪一項正確？
(A) 選項　A
(B) 選項　B
(C) 選項　C
(D) 選項　D
Ans: A

189.

如附圖所示之遞迴程式碼，當n=3時，下列輸出結果哪一項正確？
(A) ABABABAB
(B) AAAABBBB
(C) ABABAABB
(D) AABBAABB
Ans: C

190. 關於堆積（Heap）的敘述，下列哪一項正確？
(A) 可應用於資料壓縮
(B) 可視為一棵紅黑樹（Red-Black　Tree）
(C) 可視為一棵二元搜尋樹（Binary　Search　Tree）
(D) 只要利用一維陣列即可表示堆積的資料結構　
Ans: D

191. 下列排序方法，哪一項在最壞情況所需時間複雜度為O(n　log　n)？
(A) 合併排序法（Merge　Sort）
(B) 快速排序法（Quick　Sort）
(C) 選擇排序法（Selection　Sort）　
(D) 謝爾排序法（Shell　Sort）
Ans: A

192. 演算法之計算效率為O(log　n)，若資料量n為1000，計算時間為110ms；當資料量n為4000時，計算時間130ms；當資料量n增加至8000時，推論該演算法之計算時間，下列哪一項正確？
(A) 130ms
(B) 140ms
(C) 150ms
(D) 160ms
Ans: B

193. 若資料量n為100，演算法之計算時間為0.5ms，若該演算法之計算效率為O(n)；當資料量n增加至1000時，可推論該演算法之計算時間，下列哪一項正確？
(A) 5ms
(B) 15ms
(C) 30ms
(D) 45ms
Ans: A

194. 若資料量n為100，演算法之計算時間為0.5ms，若演算法之計算效率為O(n　log　n)；當資料量n增加至1000時，可推論該演算法之計算時間，下列哪一項正確？
(A) 3ms
(B) 7.5ms
(C) 10ms
(D) 15ms　
Ans: B

195. 若資料量n為100，演算法之計算時間為0.5ms，若該演算法之計算效率為O(n3)；當資料量n增加至1000時，我們可推論該演算法之計算時間，下列哪一項正確？
(A) 10ms
(B) 50ms
(C) 100ms
(D) 500ms
Ans: D

196. 有關計算最小生成樹（Minimum　Spanning　Tree）的Kruskal's演算法之敘述，下列那一項正確？
(A) 該演算法一定從具有最低成本（Cost）的邊（Edge）選取
(B) 權重最大的生成樹就是最小生成樹
(C) 演算過程中每次都從加進的邊中選取最大成本者
(D) 該演算法是一個Dynamic　Programming　Algorithm
Ans: A

197. 二元樹（Binary　Tree）之中序走訪（Inorder　Traversal）為ABCDEFGHJK，後序走訪（Postorder　Traversal）為ACEDBJHKGF，下列對於該二元樹之性質，下列敘述那一項正確？
(A) 葉節點（Leaf　Node）共5個
(B) A、J均屬於葉節點（Leaf　Node）
(C) 前序走訪（Preorder　Traversal）為FBADCEGKJH
(D) E節點之親代節點（Parent　Node）為C
Ans: B

198.