單元4 測驗/堆疊與佇列 返回
123 + 4* - 567* + 89* - - 為一個後序表示法（Postfix）的算式，其中每個數字都是個位數，則運算結果為：
  • A. 2
    20% (4)
  • B. 6
    25% (5)
  • C. -2
    20% (4)
  • D. -48
    35% (7)
解說:
要計算後序表示法（Postfix notation）的算式，我們需要使用堆疊（stack）來逐步計算。後序表示法的特點是運算符（operator）在操作數（operand）後面。計算步驟如下：
給定的後序表示法算式是：123 + 4* - 567* + 89* - -
計算步驟：
1.初始化空堆疊。
2.從左到右讀取每個符號：
(1)遇到數字時，將其推入堆疊。
(2)遇到運算符時，從堆疊中彈出所需的數字，進行運算，然後將結果推回堆疊。
詳細步驟：
1.處理 123：
堆疊：[1, 2, 3]
2.處理 +：
彈出 3 和 2，計算 2+3=52 + 3 = 52+3=5
堆疊：[1, 5]
3.處理 4：
堆疊：[1, 5, 4]
4.處理 *：
彈出 4 和 5，計算 5∗4=205 * 4 = 205∗4=20
堆疊：[1, 20]
5.處理 -：
彈出 20 和 1，計算 1−20=−191 - 20 = -191−20=−19
堆疊：[-19]
6.處理 567：
堆疊：[-19, 5, 6, 7]
7.處理 *：
彈出 7 和 6，計算 6∗7=426 * 7 = 426∗7=42
堆疊：[-19, 5, 42]
8.處理 +：
彈出 42 和 5，計算 5+42=475 + 42 = 475+42=47
堆疊：[-19, 47]
9.處理 89：
堆疊：[-19, 47, 8, 9]
10.處理 *：
彈出 9 和 8，計算 8∗9=728 * 9 = 728∗9=72
堆疊：[-19, 47, 72]
11.處理 -：
彈出 72 和 47，計算 47−72=−2547 - 72 = -2547−72=−25
堆疊：[-19, -25]
12.處理 -：
彈出 -25 和 -19，計算 −19−(−25)=−19+25=6-19 - (-25) = -19 + 25 = 6−19−(−25)=−19+25=6
堆疊：[6]
最終結果：
後序表示法算式 123 + 4* - 567* + 89* - - 的運算結果是 6。
答對率 : 25 %
一個有順序的資料列，有兩端分別稱為頭端（head）和尾端（tail）。此資料列中，新的資料可以加入，也可以刪除。但是若加入資料與刪除資料都在資料列的頭端，我們稱這樣的資料列為：
  • A. 鏈結串列（Linked list）
    5% (1)
  • B. 搜尋樹（Search Tree）
    0% (0)
  • C. 堆疊（Stack）
    60% (12)
  • D. 佇列（Queue)
    35% (7)
解說:
根據描述，這個資料結構的特點是資料的插入和刪除都在資料列的頭端進行。這樣的資料結構稱為 堆疊（Stack）。
以下是對各選項的解釋：
(A) 鏈結串列（Linked list）：
鏈結串列是一種靈活的資料結構，其中每個節點包含一個資料項和指向下一個節點的指標。鏈結串列的插入和刪除操作可以在任何位置進行，並不限定於頭端。
(B) 搜尋樹（Search Tree）：
搜尋樹（例如二元搜尋樹）是一種具有層次結構的資料結構，用於高效地搜尋、插入和刪除資料。操作不僅限於頭端，也涉及到樹的結構來確定操作位置。
(C) 堆疊（Stack）：
堆疊是一種遵循後進先出（LIFO, Last In First Out）原則的資料結構。所有的插入（push）和刪除（pop）操作都在堆疊的頭端（即堆疊的頂部）進行。
(D) 佇列（Queue）：
佇列是一種遵循先進先出（FIFO, First In First Out）原則的資料結構。插入（enqueue）發生在尾端，而刪除（dequeue）發生在頭端。
因此，當插入和刪除操作都在資料結構的頭端進行時，這種資料結構是 堆疊（Stack）。
答對率 : 60 %
將後序表示式（postfix expression）abc*+de-*進行轉換，下列敘述何者正確？
  • A. 中序表示式（infix expression）為 a+b*c*d-e
    15% (3)
  • B. 中序表示式（infix expression）為(a+b)*c*(d-e)
    10% (2)
  • C. 中序表示式（infix expression）為(a+b*c)*(d-e)
    65% (13)
  • D. 中序表示式（infix expression）為 a+b*(c*d-e)
    5% (1)
  • 未填寫
    5% (1)
解說:
要將後序表示式（postfix expression）abc*+de-* 轉換為中序表示式（infix expression），我們可以按照以下步驟進行：
後序表示式（Postfix Expression）：
abc*+de-* 
轉換步驟：
1.初始化一個空堆疊。
2.從左到右逐個處理每個符號：
(1)遇到operand（例如 a, b, c, d, e），將其推入堆疊。
(2)遇到operator（例如 *, +, -），彈出堆疊中的兩個operand，並將它們與operator組合形成一個新的中序表達式，然後將這個中序表達式推回堆疊。
詳細轉換過程：
1.處理 a：
堆疊：[a]
2.處理 b：
堆疊：[a, b]
3.處理 c：
堆疊：[a, b, c]
4.處理 *：
彈出 c 和 b，計算 b * c，並形成 (b * c)
堆疊：[a, (b * c)]
5.處理 +：
彈出 (b * c) 和 a，計算 a + (b * c)，並形成 (a + (b * c))
堆疊：[(a + (b * c))]
6.處理 d：
堆疊：[(a + (b * c)), d]
7.處理 e：
堆疊：[(a + (b * c)), d, e]
8.處理 -：
彈出 e 和 d，計算 d - e，並形成 (d - e)
堆疊：[(a + (b * c)), (d - e)]
9.處理 *：
彈出 (d - e) 和 (a + (b * c))，計算 (a + (b * c)) * (d - e)，並形成 ((a + (b * c)) * (d - e))
堆疊：[((a + (b * c)) * (d - e))]
結果：
後序表示式 abc*+de-* 的中序表示式為 ((a + (b * c)) * (d - e))。
答對率 : 65 %
一個原來為空的堆疊，經過 Push(a), Push(b), Pop(), Push(c), Pop(), Push(d), Push(e)，則堆疊中的資料，由上而下順序：
  • A. cba
    5% (1)
  • B. abc
    5% (1)
  • C. ade
    40% (8)
  • D. eda
    50% (10)
解說:
操作：
1.Push(a)：
將 a 推入堆疊。
堆疊狀態：[a]
2.Push(b)：
將 b 推入堆疊。
堆疊狀態：[a, b]
3.Pop()：
從堆疊中彈出頂部元素 b。
堆疊狀態：[a]
4.Push(c)：
將 c 推入堆疊。
堆疊狀態：[a, c]
5.Pop()：
從堆疊中彈出頂部元素 c。
堆疊狀態：[a]
6.Push(d)：
將 d 推入堆疊。
堆疊狀態：[a, d]
7.Push(e)：
將 e 推入堆疊。
堆疊狀態：[a, d, e]
結果：
堆疊中的資料，由上而下順序為：e, d, a。
答對率 : 50 %
撰寫老鼠走迷宮程式時，需記錄走過路徑，以作為無路可走時後退的依據。下列何種資料結構最適合用來記錄走過路徑？
  • A. 佇列
    20% (4)
  • B. 堆疊
    70% (14)
  • C. 二元樹
    0% (0)
  • D. 鏈結串列
    10% (2)
解說:
在撰寫老鼠走迷宮的程式時，記錄走過的路徑以便在遇到死胡同時能夠回溯，最適合使用的資料結構是 堆疊（Stack）。
原因：
堆疊（Stack） 遵循後進先出（LIFO, Last In First Out）原則，這意味著最近加入的元素會最先被移除。在迷宮中，這正符合回溯的需求：當走到死胡同時，我們需要回到上一個步驟並嘗試另一條路。堆疊能夠有效地記錄和管理這種「後進先出」的回溯過程。
 
佇列（Queue）：佇列遵循先進先出（FIFO, First In First Out）原則，這適合於需要按順序處理的情境，比如廣度優先搜尋（BFS），但不適合用於需要回溯的情況。
 
二元樹（Binary Tree）：二元樹是一種具有層次結構的資料結構，通常用於表示樹狀關係，不適合用於記錄和回溯路徑。
 
鏈結串列（Linked List）：雖然鏈結串列能夠動態地增長和縮短，但它不是專門為回溯設計的資料結構。堆疊在處理回溯時更為直接和有效。

因此，最適合用來記錄走過路徑以作為無路可走時後退的依據的資料結構是 堆疊（Stack）。
答對率 : 70 %
下載答題分析