繁體中文
選單

資料結構與演算法

以三選一題型學習時間複雜度（大O符號）、陣列與鏈結串列、堆疊與佇列、雜湊表、二分搜尋、各種排序的步驟與穩定性、二元搜尋樹與堆積、圖的搜尋與最短路徑，以及遞迴、動態規劃與貪婪演算法，也介紹與快取及 GPU 的關係。

練習10題從本領域隨機抽取10題 · 約5分鐘 練習這個領域以隨機順序出題，涵蓋這個領域的所有題目 弱項題目只重做最近答錯的題目

虛擬碼執行與追蹤工具 →

排序演算法視覺化工具 →

戴克斯特拉演算法計算工具 →

二元搜尋樹與堆積視覺化工具 →

雜湊表計算工具 →

時間複雜度（大O）比較工具 →

逆波蘭表示法轉換工具 →

資料結構與演算法的重點

即使是解決相同問題的程式，所使用的資料結構與演算法不同，資料增加時的速度也會相差好幾個數量級。以時間複雜度估算工作量的增加方式，並選擇符合資料使用方式的結構，是寫出快速程式的起點。

本單元以逐步追蹤演算法步驟的計算題為主，學習陣列與鏈結串列、堆疊與佇列、雜湊表、二元搜尋樹與堆積、圖的表示法等基本資料結構，以及二分搜尋，泡沫、選擇、插入、合併、快速、堆積等排序，廣度優先搜尋、深度優先搜尋、戴克斯特拉演算法，與遞迴、動態規劃、貪婪演算法，有助於準備資訊相關證照考試的演算法領域。此外也介紹與硬體效能的關係，例如適合快取的資料排列方式，以及在 GPU 上的平行排序。

資料結構與演算法的題目列表（40題）
  1. 對於有 n 個元素的陣列，將所有不同的兩個元素組合各比較一次的處理（以雙重迴圈將第 i 個元素與其後的所有元素比較，並讓 i 逐一前進），其時間複雜度為下列何者？
  2. 某個時間複雜度為 O(n²) 的程式，在資料數為1,000時處理時間為0.5秒。若資料數變為4,000，處理時間約為幾秒？
  3. 以從開頭逐一比較的線性搜尋，在存有100個不同值的陣列中尋找目標值。若目標值一定在陣列中，且位於各位置的機率相等，則比較次數的平均為多少？
  4. 與陣列相比，鏈結串列（各元素持有指向下一個元素位置之指標的串列）的特徵，下列何者正確？
  5. 對空的堆疊依序進行 push 1、push 2、pop、push 3、push 4、pop、pop 的操作。依序排列以 pop 取出的值，下列何者正確？
  6. 對空的佇列依序放入 A、B、C，取出1個，放入 D 後取出1個，再放入 E 後取出1個。依序排列取出的元素，下列何者正確？
  7. 以逆波蘭表示法（後序式）寫成的算式「3 4 + 2 * 5 −」，用「遇到數字就推入堆疊，遇到運算子就取出2個值計算並推入結果」的方法求值。結果為多少？其中運算子左側的值是先推入的那一個。
  8. 關於雜湊表中碰撞（collision）的說明，下列何者正確？
  9. 在大小為7（位置0～6）的雜湊表中，以雜湊函數 h(k) = k mod 7 依序存放鍵10、17、24、3。發生碰撞時，使用把位置逐一往後移（6的下一個是0）來尋找空位置的線性探測法。鍵3會存放在哪個位置？
  10. 比較處理雜湊表碰撞的鏈結法（以鏈結串列串接相同位置的元素）與開放定址法（在表中尋找其他空位置），下列說明何者正確？負載因子為存放的元素數除以表的大小所得的值。
  11. 與陣列中央的元素比較、每次將搜尋範圍縮小一半的二分搜尋，其使用的前提條件為下列何者？
  12. 以二分搜尋在依升冪排序的1,000個不同值中尋找某個值。若1次比較就能得知「相等、較小、較大」，包含找得到與找不到的情況，比較次數最多為幾次？
  13. 以二分搜尋在依升冪排列的陣列 a[0]～a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60 中尋找38。搜尋範圍從下端 lo = 0、上端 hi = 9 開始，中央位置為 (lo + hi) ÷ 2 無條件捨去。依序排列與38比較的元素值，下列何者正確？
  14. 以泡沫排序將陣列 5, 3, 8, 1, 4 依升冪排列。從開頭比較相鄰的兩個元素，若左側較大就交換，這樣的操作進行到末尾1次（1輪）後，陣列為下列何者？
  15. 以選擇排序（從未排序部分找出最小值，並與未排序部分的開頭交換）將陣列 29, 10, 14, 37, 13 依升冪排列。進行此操作2次後，陣列為下列何者？
  16. 以插入排序將有10個元素的陣列依升冪排列。依序取出第2個以後的元素，從左側相鄰的元素開始依序比較，直到找到小於或等於取出值的元素，或到達開頭為止。一開始就是升冪時與一開始是降冪時，比較次數的組合為下列何者？
  17. 即使在最差情況下時間複雜度也是 O(n log n)，且幾乎不使用工作用陣列等額外記憶體就能排序的演算法為下列何者？
  18. （姓名, 分數）的資料 (A, 80)、(B, 70)、(C, 80)、(D, 70) 依此順序排列。以穩定排序依分數升冪重新排列時，姓名的順序為下列何者？
  19. 快速排序的時間複雜度變成 O(n²) 的典型情況為下列何者？
  20. 在合併排序中，把已依升冪排序的兩個序列 1, 4, 7, 9 與 2, 3, 8, 10，以「比較兩者開頭並輸出較小者」的方式反覆進行，合併成一個序列。其中一個序列變空時，其餘部分不比較直接輸出。比較次數為幾次？
  21. 將二元堆積以根為 a[0] 的陣列 a[0], a[1], a[2], … 存放，從上層開始每層由左往右依序填入。a[4] 的子節點與父節點為下列何者？
  22. 以根為 a[0] 的陣列表示父節點值大於或等於子節點值的最大堆積。對堆積 50, 30, 40, 10, 20, 35 加入45：先放在末尾，只要比父節點大就與父節點交換。操作後的陣列為下列何者？
  23. 以中序走訪（依左子樹、該節點、右子樹的順序拜訪）走訪二元搜尋樹時，拜訪到的節點值會如何排列？假設所有值都不相同。
  24. 對空的二元搜尋樹依序插入 50, 30, 70, 20, 40, 60, 80。以後序走訪（依左子樹、右子樹、該節點的順序拜訪）走訪此樹時，順序為下列何者？
  25. 對空的二元搜尋樹依序插入 1, 2, 3, …, 1000（不做平衡的操作）。在這棵樹中尋找1000時，從根部開始比較，到找到為止要比較幾個節點？
  26. 資料庫與檔案系統的索引常使用 B 樹（包含 B+ 樹）而非二元搜尋樹，其主要原因為下列何者？
  27. 像頂點約100萬個、邊約300萬條的道路網這樣，邊數相對於頂點數很少的（稀疏）圖，適合以下列何種方式存放在記憶體中？
  28. 在邊沒有權重的圖中，想求出從起點到各頂點的最少邊數。適合的搜尋方法與所使用的資料結構組合為下列何者？
  29. 在無向圖中，各頂點的相鄰頂點如下：A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。從頂點 A 進行遞迴的深度優先搜尋。相鄰頂點依此處列出的順序檢查，一找到尚未拜訪的頂點就立刻前往。拜訪頂點的順序為下列何者？
  30. 在無向圖中，各邊的權重（距離）為 S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、A−T: 6。以戴克斯特拉演算法求從 S 到 T 的最短路徑時，路徑與長度為下列何者？
  31. 要以戴克斯特拉演算法求出正確的最短路徑，關於圖的條件，下列何者正確？
  32. 工作 A～E 有「A 在 C 之前」「B 在 C 之前」「C 在 D 之前」「B 在 E 之前」「E 在 D 之前」的順序限制。滿足所有限制的工作順序（拓撲排序的結果）為下列何者？
  33. 函數 f(x, y) 定義為「若 y 為0則回傳 x，否則回傳 f(y, x mod y)」。呼叫 f(84, 36) 時的回傳值，以及 f 被呼叫的次數（含第一次呼叫）的組合為下列何者？
  34. 以遞迴將求費氏數的函數 fib(n) 定義為「若 n 在1以下則回傳 n，否則回傳 fib(n−1) + fib(n−2)」。呼叫 fib(5) 時，含第一次呼叫在內，fib 被呼叫幾次？
  35. 以1圓、4圓、6圓3種硬幣支付8圓。以從大硬幣開始盡量使用的貪婪演算法決定時的枚數，與最少枚數的關係，下列何者正確？
  36. 從（重量, 價值）為 (2, 3)、(3, 4)、(4, 5)、(5, 6) 的4件物品中選擇，放入容量為8的背包。每件物品只有1個，且不能分割。在重量合計8以下的條件下，價值合計的最大值為多少？
  37. 關於在字串中尋找樣式的 BM 法（Boyer-Moore 演算法）的特徵，下列何者正確？
  38. 某個可變長度陣列在容量已滿時加入元素，會重新配置2倍容量的區域並複製所有元素。對容量為1的空陣列逐一加入1,000個元素時，被複製的元素總數為多少？
  39. 在元素很多、負載因子維持在0.5左右的雜湊表中，使用線性探測的開放定址法往往比鏈結法（以鏈結串列串接的方法）快，最適當的原因為下列何者？
  40. 在 GPU 這類平行處理裝置上排序時，有時會使用雙調排序（bitonic sort）這類比較與交換步驟固定的排序（排序網路），其理由為下列何者？

電腦系統的其他領域