[考題] 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是怎麼出來的 -- ◆ From: 111.242.192.141
※ 批踢踢實業坊(ptt.cc)
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1371256858.A.C76.html

推 GLTY:第二題是a吧@@ 樹畫出來b根本亂走 06/15 10:32

推 Jian152692:第二題我算出來也是A 是答案有錯嗎? 06/15 14:38

推 SeekTheBest:第二題是a...答案應該有誤 06/15 15:15

推 gayi6:第二題我也是算A… 06/15 19:25