[考題] 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是怎麼出來的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.242.192.141
推
06/15 10:32, , 1F
06/15 10:32, 1F
推
06/15 14:38, , 2F
06/15 14:38, 2F
推
06/15 15:15, , 3F
06/15 15:15, 3F
推
06/15 19:25, , 4F
06/15 19:25, 4F