資料結構與演算法複習試題(出自：全國資訊競賽89, 91、IOI 2002, 2003)

Size: px

Start display at page:

Download "資料結構與演算法複習試題(出自：全國資訊競賽89, 91、IOI 2002, 2003)"

甸胖水
5 years ago
Views:

1 資料結構與演算法複習試題 ( 出自 : 全國資訊競賽 89, 91 IOI 2002, 2003) Stack and Queue 1. 假設指令 ENQ X 的動作是將暫存器 X 的值存入佇列, 指令 DEQ X 的動作是自佇列取出一個數目存入暫存器 X 中若暫存器 A B C D 的內含值分別為時, 依序執行 ENQ A ENQ B DEQ C DEQ D ENQ C ENQ B DEQ A DEQ B 後, 暫存器 A 的內容為何? (a)6 (b)7 (c)8 (d)9 2. 堆疊資料結構通常不適合用來做 (1) 走迷宮 (2) 副程式返回 (3) 遞迴 (4) 緩衝區有一空的堆疊, 以下子程式 (subroutine) 對此堆疊從事資料存取及運算 : PUSH X : 把 X 這個整數存入堆疊最上方 POP : 把堆疊最上方資料取出, 並列印在螢幕上 SWAP : 把堆疊最上方兩個資料交換位置 ADD : 取出堆疊最上方兩個資料, 相加後再 PUSH 到堆疊 3. 假設堆疊剛開始不存放任何資料, 執行 PUSH 5 PUSH 6 SWAP POP 後, 則此堆疊的內容由上而下為 (1)5 6 (2)6 5 (3)5 (4)6 4. 假設堆疊剛開始不存放任何資料, 執行 PUSH 3 PUSH 4 ADD PUSH 5 後, 則此堆疊的內容的由上而下為 (1)7 5 (2)5 3 4 (3)5 7 (4) 假設堆疊剛開始不存放任何資料, 執行 PUSH 101 PUSH 33 POP PUSH 29 ADD POP 北一女中暑期資訊能力競賽選手選訓營隊講義 1

2 後, 則最後一個 POP 會列印 (1)33 (2)101 (3)130 (4)134 有一佇列 (Queue), 以下子程式 (subroutine) 對其從事資料存取及運算 : ADDQ X: 把 X 這個整數加到佇列最後方 DELQ : 把佇列最前方資料取出, 並列印在營幕上 REVQ : 把佇列中所有資料的先後循序相反, 也就是原先最前方的資料變成最後, 第二個變成例數第二, 以此類推 6. 假設佇列剛開始不存放任何資料, 執行 ADDQ 1 ADDQ 2 ADDQ 3 DELQ ADDQ 4 後, 則此佇列的內容由前到後為 : (1) (2)4 3 2 (3)2 3 4 (4) 假設佇列剛開始不存放任何資料, 執行 ADDQ 7 ADDQ 8 ADDQ 9 DELQ ADDQ 10 REVQ 後, 則佇列的內容由前到後為 (1) (2) (3)7 8 9 (4) 下列那一種資料結構是先進後出 (First In Last Out)? (a) 陣列 (array) (b) 樹 (tree) 北一女中暑期資訊能力競賽選手選訓營隊講義 2

3 (c) 佇列 (queue) (d) 堆疊 (stack) 9. 在電腦教室中,30 台個人電腦共享一台以印表伺服器管理的雷射印表機在印表伺服器中使用何種資料結構來管理印表工作? (a) 二元樹 (binary tree) (b) 堆疊 (stack) (c) 佇列 (queue) (d) 陣列 (array) 10. 有一個佇列 queue 初始時為空的, 接著執行以下動作 : AddQ A ; AddQ B ; AddQ C ; DeleteQ ; AddQ D ; AddQ E ; DeleteQ 請問最後一個 DeleteQ 會取出何值? (a) E (b) D (c) C (d) B 11. 有一個堆疊 Stack 初始時為空的, 接著執行以下動作 : Push A ; Push B ; Push C ; Pop ; Push D ; Push E ; Pop 請問最後一個 Pop 會取出何值? (a) E (b) D (c) C (d) B 12. 使用 Stack 的資料結構, 依序放入 2,3,5,7 四個元素, 拿出兩個元素後, 再放入 11,13 二個元素, 再拿出 1 個元素, 最後再放入 17, 請問結果為何? ( 由上至下的順序表示 ) (a) 17,11,13,2 (b) 17,13,5,7 (c) 7,11,13,17 (d) 17,11,3,2 13. 依序將 1, 2, 3, 4, 5 push 到堆疊 (Stack) 中, 再 pop 出四筆資料然後依 pop 出的順序 enqueue 到佇列 (Queue) 中當我們從此佇列 dequeue 取出資料時, 第三筆為何? (a) 1 (b) 2 (c) 3 (d) INSERT(S, 2); INSERT(S, 3); INSERT(S, 6); INSERT(S, DELETE(S)+DELETE(S)); Writeln(DELETE(S)); 北一女中暑期資訊能力競賽選手選訓營隊講義 3

4 假設 S 是一個堆疊 (Stack),INSERT(S, x) 表示將資料 x 存入 S 中, 而 DELETE(S) 會從 S 中取出一筆資料傳回請問執行上述程式片段, 螢幕上會印出什麼結果? (a) 2 (b) 3 (c) 6 (d) 9 Linked List 15. 在串列 (linked list) 的資料結構中, 假設 head 是指向一個串列的頭的指標,next 是用來指向下一個串列元件的指標現在有一個新增的元件為 p, 要加到此串列的最前頭, 則下列何者為正確的步驟? (1)head->next=p; (2)p->next=head; head=p; (3)head=p; p->next=head->next; (4)p->next=head->next; head=p; 16. 反轉 (reverse) 一單向鏈結串列 (Singly Linked List), 如下圖所示 Header a b z Reverse a b z Header 若欲完成此功能, 則至少需使用幾個暫存的指標? (a)1 個 (b)2 個 (c)3 個 (d)4 個北一女中暑期資訊能力競賽選手選訓營隊講義 4

5 Tree 17. 下列何者不是樹? (a) 一個沒有迴路 (cycle) 的連通圖 (b) 一個節點 (vertex) 的圖 (c) 一個邊數比節點數少 1 的圖 (d) 一個邊數比節點數少 1 而且沒有迴路的圖北一女中暑期資訊能力競賽選手選訓營隊講義 5

6 18. 有一種資料結構其為樹狀結構, 且在任何位置中其父節點的值恆大於子節點的值? (a) 二元樹 (binary tree) (b) 二元搜尋樹 (binary search tree) (c) 堆 (heap) (d) 堆疊 (stack) 19. 設 T 為一個 m 元樹, 也就是 T 中的每一個節點之分支度小於或等於 m 若 T 中共有 n 個節點, 其中內部節點數為 i, 葉節點數為 j, 且共有 k 個分枝則以下何者不恆為真? (1) k = i + j - 1 (2) j (m-1) i (3) n m i + 1 (4) i k/m 個節點所能排出的二元樹之個數有多少? (a) 10 (b) 14 (c) 20 (d) 樹的深度 (depth) 為葉子 (leaves) 到根 (root) 最長路徑之長度試問一個深度為 h 的完整二元樹 (complete binary tree) 共有幾個節點? (a) 2 h-1 (b) 2 h-1-1 (c) 2 h+1 (d) 2 h 在二元樹中, 根節點屬於第 1 層, 其子節點屬於第 2 層, 第 2 層節點之子節點屬於第 3 層, 依此類推給一個二元樹, 樹的深度為 k (k 4) 樹中的每一個節點存有一筆不同值的資料, 且對於每個位於奇數層的節點 O,O 的資料為以 O 為根節點之子樹中的最小值, 對於每個位於偶數層的節點 E,E 的資料為以 E 為根節點之子樹中的最大值請問整棵樹中最大的資料會出現在此樹的第幾層? (a) 第 1 層 (b) 第 2 層 (c) 第 3 層 (d) 第 4 層 23. 延續上題, 請問整棵樹中第二小的資料會出現在此樹的第幾層? (a) 第 2 層 (b) 第 1 層或第 2 層 (c) 第 2 層或第 3 層 (d) 第 3 層北一女中暑期資訊能力競賽選手選訓營隊講義 6

7 Tree Traversal 24. 下列何者為中置式 (Infix Expression) (A+B)*C-D/E 的後置式 (Postfix Expression)? (a) AB+C*DE/- (b) ABC*+DE-/ (c) AB+C*D-E/ (d) ABCDE+*-/ 25. A + (B + C) 之前置表示法 (Pre-Order) 為 (a) A+B+C (b) ABC++ (c) +A+BC (d) ++ABC 26. 下列何者為 A*B+C/(D-E) 的後續式 (postfix) 表示法? (a) DE-C/B+A* (b) DE-CB/+A* (c) AB*CDE-/+ (d) BCDE-/*A+ 27. 已知在一棵二元樹 T 中包含 7 個節點,7 個節點分別存放 A, B, C, D, E, F, G, 且資料不重複今由根節點開始, 以前序 (preorder traversal) 來追蹤此二元樹, 且每走到一個節點便印出節點中的資料, 得到 BDFAGEC 的結果, 以後序 (postorder traversal) 來追蹤這棵二元樹, 得到 AFECGDB 的結果, 則下列何者不可能為由根節點開始以中序 (inorder traversal) 來追蹤這棵二元樹的節點順序? (1) BAFDEGC (2) FADEGCB (3) BDFGAEC (4) AFDEGCB 28. 假設一二元樹 (binary tree) 經前序 (Preorder) 追蹤可得一次序為 ABCDEFGH, 經中序 (Inorder) 追蹤可得一次序為 CDBAFEHG, 則此樹經後序 (Postorder) 追蹤後的次序為? (a)cdbaefgh (b)dcbfhgea (c)hgfeabcd (d)abecfgdh 29. 將中序 (infix) 的運算式 A/B-C+D*E-A 轉換成後序 (postfix) 的運算式將是? (a)a B C D E A / - + * - (b)a B / + C * D E A (c)a B / C - D E *+ A (d)a B / C D - E * +A 北一女中暑期資訊能力競賽選手選訓營隊講義 7

8 30. 下列 A 與 B 兩樹分別用什麼樣的追蹤方式會得到相同的結果 A F B C E C D D A E F B A 樹 B 樹 (a)a 用後序追蹤 B 用前序追蹤 (b)a 前序追蹤 B 用中序追蹤 (c)a 後序追蹤 B 用中序追蹤 (d)a 用中序追蹤 B 用後序追蹤 Graph 31. 那個邊 (edge) 存在於下圖的最小成本生成樹 (minimum-cost spanning trees) 中? A 5 D C 12 F B 25 E (a)ab (b)cd (c)ce (d)ef 32. 從頂點 0 開始, 利用 depth-first search 的方法走訪下圖, 則所有點會以何種順序被走過? 北一女中暑期資訊能力競賽選手選訓營隊講義 8

9 (a)0,1,2,3,4,5,6,7 (b)0,1,3,4,2,5,6,7 (c)0,1,3,4,7,2,5,6 (d)0,1,3,7,4,5,2,6 33. 下圖中的最小成本擴張樹 (Minimum cost spanning tree) 的成本為 A (a)17 (b)20 (c)22 (d) B C 7 6 D E Sort, Search && Algorithm 34. 某校有學生人, 且已按姓氏筆劃排序, 以二分搜尋法找學生姓名及資料, 最多需要比較幾次? (a) 8 (b) 15 (c) (d) 從 n 個數中找出第二小的數最少可在幾次比較下完成? (a) n+θ(logn) (b) 2 n (c) nlog n (d) 2n 下列時間複雜度 (time complexity) 何者的時間最少? (a) O (log log n) 北一女中暑期資訊能力競賽選手選訓營隊講義 9

10 (b) O (logn) (c) O (n) (d) O (log 2 n) 37. 以下演算法之時間複雜度分析的敘述中,n 為輸入大小, 則下列敘述何者為真? (a) 一個 0(n^2) 時間的演算法一定比 0(n) 時間的演算法快 (b) 一個最佳執行時間為 20 秒且最糟執行時間為 100 秒的演算法的平均執行時間為 60 秒 (c) 如果不說明, 演算法的時間複雜度通常指該演算法最糟執行狀況下的情形 (d) 沒有任何排序演算法的時間複雜度為 0(n) 38. 下列那一個排序演算法在資料量很大的時候, 其排序的速度最快? (a) Heap sort (b) Bubble sort (c) Insertion sort (d) Selection sort 39. 下列那一型態的演算法策略, 當資料量很大的時候, 其執行的時間複雜度將呈指數成長 (exponential growth)? (a) Branch-and-Bound methods (b) Greedy methods (c) Dynamic programming methods (d) Divide-and-Conquer methods 40. 在甚麼狀況下, 只能使用循序搜尋法 (sequential search) 而不能使用二元搜尋法 (binary search) 來尋找一個含有 n 個元素的陣列 A 中的某個元素 x? (a) 陣列 A 中的 n 個元素都已排序好了 (b) 陣列 A 中的 n 個元素都還沒有排序好 (c) x 的數值是實數, 無法用整數的運算來比較 (d) 電腦 CPU 速度太慢時, 只能使用循序搜尋法 41. 下列那些問題, 已經存在有效率的解決的方法, 也就是說, 其執行的時間複雜度為多項式時間 (polynomial time)? (a) 旅行推銷員問題 (traveling salesperson problem) (b) 0/1 背包問題 (0/1 knapsack problem) (c) 凸包問題 (convex hull problem) (d) 著色問題 (coloring problem) 42. 給一串由 n 個不同整數所形成的數列, 一個 flip 的動作定義為 : 將數列從開頭依序選擇前 k 個數 (k 為任一個大於等於 1 且小於等於 n 之整數 ), 並將此 k 個數之排列順序反轉例如給一串數列 3, 4, 6, 9, 8, 2, 1, 7, 5, 將其前 4 個數做一次 flip, 則得到 9, 6, 4, 3, 8, 2, 1, 7, 5 請問給任何一串由 n 個不同數所形成的數列, 假設已知最大值的所在位置, 最多需要幾次 flip 的動作方可將最大值置於數列最後位置? 北一女中暑期資訊能力競賽選手選訓營隊講義 10

11 (a) 1 次 (b) 2 次 (c) n-1 次 (d) n 次 43. 下列的排序法中, 哪一個在對 7, 13, 45, 68, 91, 154, 189, 225 這組資料做排序時使用的比較次數最少? (a) 堆積排序 (Heap Sort) (b) 快速排序 (Quick Sort) (c) 插入排序 (Insertion Sort) (d) 合併排序 (Merge Sort) 44. 在 250 筆資料當中, 以二分搜尋法 (Binary Search) 尋找某一筆資料時, 至多只要搜尋幾次即可找到? (a) 6 次 (b) 7 次 (c) 8 次 (d) 9 次 45. 下列何種順序所建造的二元搜尋樹 (Binary Search Tree) 最平衡 (Balanced)? (a) 30,20,50,5,25,41,80 (b) 5,20,25,30,41,50,80 (c) 80,50,41,30,25,20,5 (d) 50,80,41,30,25,20,5 46. 給定 1000 筆資料儲存在陣列中, 下列有關搜尋 (Search) 的敘述何者錯誤? (a) 經資料排序過後, 利用二分搜尋法最多只需要比較約 10 次 (b) 未排序過的資料, 利用二分搜尋法最多需要比較 1000 次 (c) 如果資料是中文, 經排序後, 二分搜尋法最多只需要比較 10 次 (d) 排序過的資料, 利用循序搜尋法最少只需要比較 1 次 47. 分別以鏈結串列 (Linked List) 與循序串列 (Sequential List, Array) 儲存 10 萬筆資料, 下列敘述何者錯誤? (a) 排序過的鏈結串列利用二分搜尋法可以加速查詢 (b) 鏈結串列加入或刪除資料比循序串列所需時間少 (c) 鏈結串列需要額外的空間儲存鏈結 (d) 找第 K 大的資料, 排序過的循序串列比排序過的鏈結串列所需的時間少 48. 如果依序輸入六筆資料, 下列何者所建立的二元搜尋樹 (Binary Search Tree) 層數最少? (a) 100, 200, 300, 400, 500, 600 (b) 300, 200, 500, 400, 100, 600 (c) 600, 500, 400, 300, 200, 100 (d) 400, 100, 500, 100, 200, 對 N 個範圍在的數字排序, 所需花的最少時間為何? (a)o(n) 北一女中暑期資訊能力競賽選手選訓營隊講義 11

12 (b)o(nlg n) (c)o(1000) (d)o(n 2 ) 50. 下列何者是 T(n)=lgn+2T(n/4) 這個遞迴式 (Recurrence) 的解? (a)o(lgn) (b)o(n) (c)o(n 1/2 ) (d)o(n 2 ) 51. 將兩個長度為 m 及 n 的已排序數字串列合併所需花的最少時間為何? (a)o(m+n) (b)o((m+n) 2 ) (c)o(m*n) (d)o((m+n)lg(m+n)) 52. 有關循序搜尋法 (Sequential Search) 的敘述何者錯誤? (a) 檔案資料未排序時才能使用 (b) 搜尋時是將檔案資料一筆一筆逐一比對 (c) 其演算法的時間複雜度為 O(n) (d) 在磁帶上搜尋資料一般都用此法 53. 某個問題涉及 n 個資料的處理, 四名學生的解 ( 演算法 ) 皆正確, 但分別需要約 n 2 n 0.5 logn 及 n! 個計算, 那麼這個問題的複雜度可能為何? (a)n 2 (b)n 0.5 (c)log n (d)n! 54. 從五個不同數字中要找出中間值至少需要幾次比較? (a)5 次 (b)6 次 (c)7 次 (d)8 次 55. 假設某候選員需要親訪 15 個鄉鎮, 任兩個鄉鎮間都有專屬道路, 在一次走完且任一鄉鎮不重複拜訪的條件下, 從某個鄉鎮出發, 共有幾種走法? (a)14! (b) (c) 14 2 (d) 以上皆非 56. 雜湊法 (hashing) 可用來將資料表 (table) 中的紀錄 (record) 先平均打散成 n 群, 以降低整體的北一女中暑期資訊能力競賽選手選訓營隊講義 12

13 搜尋時間若 n 為 10, 則某 3 筆紀錄中至少兩筆會被分配到同一群的機率約為何? (a)0.7 (b)0.6 (c)0.3 (d) 如欲使用二元搜尋法, 則資料必須具備以下何種特性? (1) 資料必先經過排序 (2) 資料必須不重複 (3) 資料必須全為正數或全為負數 (4) 資料必須為整數 58. 有一個數列按照二元樹 (binary tree) 的資料結構儲存, 假設欲搜尋的數字為 9, 那麼在搜尋完成前, 至少需要幾次的比較? (1) 1 (2) 2 (3) 3 (4) 把一個問題切割成若干個小問題, 然後分別去解決個別的小問題, 最後再把小問題的答案結合成大問題的解答, 這樣的方法稱之為 : (1) divide and conquer (2) dynamic programming (3) greedy (4) search 60. 有 25 位同學彼此不認識, 每天在圓桌聚餐一次, 每次聚餐後每個人便會與相鄰的二人認識, 則最少需要多少天後才會使得每個人皆彼此認識? (1) 5 (2) 12 (3) 13 (4) 25 北一女中暑期資訊能力競賽選手選訓營隊講義 13

14 資料結構與演算法複習試題解答 ( 出自 : 全國資訊競賽 89, 91 IOI 2002, 2003) 1. a d 9. c 10. d 11. a 12. d 13. c 14. d c 17. c 18. c b 21. d 22. b 23. d 24. a 25. c 26. c b 29. c 30. c 31. a 32. d 33. a 34. b 35. d 36. a 37. d 38. a 39. a 40. b 41. b 42. b 43. c 44. c 45. a 46. b 47. a 48. b 49. a 50. c 51. a 52. a 53. c 54. b 55. a 56. c 北一女中暑期資訊能力競賽選手選訓營隊講義 14

<4D F736F F D20B8EAB054B0F2A5BBAFE0A44F>

<4D F736F F D20B8EAB054B0F2A5BBAFE0A44F> 2002 年國際資訊奧林匹亞研習營甄試資訊基本能力測驗本測驗共 50 題, 測驗時間為 50 分鐘 1 下列那一個元件不屬於 CPU? (1) 算數邏輯單元 (ALU) (2) 控制單元 (control unit) (3) 暫存器 (register) (4) 記憶體 (memory) 2 某電腦具有 16MB 記憶體, 其中 16MB 所指為何? (1) 16 2 10 bits (2) 16