100原住民計算機概要 - 考試

[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處

8 自 n 筆資料中依據指定之鍵值（Key value）尋找資料稱為資料搜尋（Search）或簡稱
搜尋。下列為資
料搜尋方法相關敘述：
（1）循序搜尋（Sequential search）法是所有搜尋方法中，空間複雜度
（Space complexity）與時間複雜度（Time complexity）皆最差之搜尋方法。
（2）使用循序搜尋（Sequential search）法、費氏搜尋（Fibonacci search）法、
內插搜尋（Interpolation search）法、索引搜尋（Index search）法等方法
進行資料搜尋（Searching）時，必須先將資料依據鍵值（Key value）完成排
序（Sort）。
（3）使用內插搜尋（Interpolation search）法時，必須先將資料依據鍵值
（Key value）完成排序（Sort），故資料搜尋實際之時間複雜度（Time
complexity）應包含排序所需之時間而表示為O(n^2)+O(log2 n)或
O(n. log2 n)+O(log2 n)。
（4）使用搜尋樹（Search tree）法進行資料搜尋（Searching）時，必須使用額外
之記憶體儲存空間建立樹（Tree）形結構，故實際之空間複雜度（Space
complexity）表示為O(n)+O(log2 n)。
（5）若某資料搜尋方法之時間複雜度（Time complexity）為O(n. log2 n)，則進
行資料搜尋時不應選用此資料搜尋方法。
請由下列選項中選出最適合者。
（A）(3)正確；(2)(5)錯誤 （B）(5)正確；(2)(4)錯誤
（C）(1)正確；(3)(4)錯誤 （D）(2)(4)(5)錯誤

答案（B）

這題我想問選項(4)是錯在需要額外的記憶體儲存空間建立樹嗎？

還有選項(5)有搜尋方法是O(n. log2 n)嗎？搜尋方法中最差不是循序搜尋嗎？



9 有一棵二元樹（binary tree）的後序走訪（postorder traversal）結果為 DEBFGCA，
中序走訪（inorder
traversal）為 DBEAFCG，請問此樹的前序走訪（preorder traversal）結果為何？
（A） ABDECFG （B） ABCDFEG （C） ADBECFG （D） ABDCEGF

答案（B）

這題我怎麼畫都是A耶，可是考選部答案B，想請問版上各位大大B是怎麼出來的

--