計概16-01堆疊－公職試題

【選擇題】

【D】01.關於圖形拜訪(graph traversal)的方法，下列何者正確？ (A)廣度優先搜尋先拜訪子節點再派訪父節點 (B)深度優先搜尋先拜訪兄弟節點再派訪子節點 (C)廣度優先搜尋實作時通常使用集合結構 (D)深度優先搜尋實作時通常使用堆疊結構。[109普考電子]

(A)深度優先。(B)廣度優先。(C)佇列(queue)結構。

 

【B】02.堆疊資料結構通常適合用來實作下列何種功能？ (A)緩衝區 (B)程式遞迴 (C)網路封包處理 (D)廣度優先搜尋(Breadth First Search)。[110身心五等]

堆疊：先進後出(FILO, First In Last Out)，最後放入(push)的資料，最先取出(pop)，應用於回溯、遞迴、深度優先搜尋。

 

【D】03.下列何者不是堆疊(Stack)資料結構固有特性的應用？ (A)反轉一個字串(String)的字元(Characters)順序 (B)檢查左括號與右括號是否正確配對 (C)遞迴(Recursive)程式的執行 (D)將一個資料串列分成兩大類。[110普考電子]

堆疊的應用：1.遞迴程式的呼叫及返還。2.中斷之處理。3.堆疊機器。4.回溯。5.中序式、前序式與後序式之間的相互轉換。6.後序運算式的計算。7.深度優先搜尋。8.字串反轉。

 

【A】04.假設有一個空的堆疊(stack)，依序執行下列動作：push(3)、push(10)、push(25)、push(5)、pop()、push(10)、pop()、pop()、pop()，堆疊最上面的一個數字為何？ (A)3 (B)5 (C)10 (D)25。[110關務四等]

步驟

push(3)

push(10)

push(25)

push(5)

pop()

push(10)

pop()

pop()

pop()

stack

3

10

3

25

10

3

5

25

10

3

25

10

3

10

25

10

3

25

10

3

10

3

3

 

【B】05.下列那一個不是堆疊(Stack)的特性？ (A)後進先出(Last in first out) (B)常用於程序(Process)記憶體的動態配置 (C)插入資料的動作在頂端(Top) (D)刪除資料的動作在頂端。[110鐵路員級]

堆疊的應用：1.主副程式間訊息傳送。2.遞迴程式的的呼叫和返回。3.CPU中斷處理。4.中序式、前序式與後序式間的轉換。5.後序式求值計算。6.堆疊機器。

 

【C】06.有甲、乙、丙三顆實心球，由左向右依序滾動跌入垂直管，如圖所示，有一機械手臂可從垂直管頂部一次取出一球，球取出的順序，下列何者是不可能的？ (A)丙、乙、甲 (B)甲、丙、乙 (C)丙、甲、乙 (D)乙、丙、甲。[111地方四等電子]

 (A)Push 甲、Push 乙、Push 丙、Pop 丙、Pop 乙、Pop 甲

(B)Push 甲、Pop 甲、Push 乙、Push 丙、Pop 丙、Pop 乙

(D)Push 甲、Push 乙、Pop 乙、Push 丙、Pop 丙、Pop 甲


 

【B】07.有一初始空的堆疊，執行下列命令：push 35，push 27，pop，push 100，push 55，pop，請問堆疊中的內容由頂端(top)向下依序為何？ (A)55 100 27 35 (B)100 35 (C)27 35 (D)55 100。[111身心五等]

push 35

push 27

pop

push 100

push 55

pop

35

27

35

35

100

35

55

100

35

100

35

 

【B】08.對一個堆疊(Stack)可以執行推入(Push)、彈出(Pop)和清空(Empty)等基本運算。現在接連對一個空堆疊連續執行推入A、推入B、清空、推入C、推入D、推入E、彈出，最後執行推入F。在執行以上運算後，堆疊中共存在多少元素？ (A)2 (B)3 (C)4 (D)5。[111身心四等]

推入A → A

推入B → AB

清空 →

推入C → C

推入D → CD

推入E → CDE

彈出 → CD

推入F → CDF

 

【C】09.在一個圖(Graph)中進行深度優先搜尋(Depth-first Search)，應使用下列那種資料結構設計，可使得搜尋的過程最符合深度優先的順序？ (A)佇列(Queue) (B)堆積(Heap) (C)堆疊(Stack) (D)雜湊表(Hash Table)。[111身心四等]

堆疊的應用：1.遞迴程式的呼叫及返還，2.中斷之處理(Interrupt Handling)，3.堆疊機器(Stack Machine)，4.回溯(Backtracking)，5.中序式、前序式與後序式之間的相互轉換，6.後序運算式的計算，7.深度優先搜尋，8.字串反轉。

 

【A】10.下列那一個結構，具有後進先出(Last In, First Out)的特色？ (A)堆疊(Stack) (B)佇列(Queue) (C)最大堆積(Max Heap) (D)二元搜尋樹(Binary Search Tree)。[111鐵路員級]

堆疊：後進先出(LIFO)，先進後出(FILO)，最後放入(push)，最先取出(pop)。

 

【C】11.正在執行的A程式可被中斷(Interrupt)暫停，而去執行B程式，等B程式執行完後再回到A程式繼續執行。下列那種資料結構最適合用於設計這樣的機制？ (A)環形佇列(Circular Queue) (B)先進先出佇列(FIFO Queue) (C)堆疊(Stack) (D)雜湊表(Hash Table)。[112地方四等電子]

堆疊：先進後出(FILO, First In Last Out)，最後放入(push)的資料，最先取出(pop)。

執行A → Push A 被中斷

執行B → Push B

B執行完畢 → Pop

A執行完畢 → Pop

 

【C】12.有4個元素的資料序列{A,B,C,D}，以A、B、C、D的順序(A最先)經過堆疊(Stack)改變資料輸出的順序，堆疊可用推入(Push)、彈出(Pop)的動作，下列那種資料輸出順序是不可能的？ (A)CBAD (B)BACD (C)ADBC (D)DCBA。[112地方四等電子]

(A)Push A → Push B → Push C → Pop → Pop → Pop → Push D → Pop → 輸出順序CBAD

(B)Push A → Push B → Pop → Pop → Push C → Pop → Push D → Pop → 輸出順序BACD

(C)Push A → Pop → 應為Push B，不可能Push D

(D)Push A → Push B → Push C → Push D → Pop → Pop → Pop → Pop → 輸出順序DCBA

 

【B】13.已知資料來源的先後順序是：a、b、c、d(a最先、d最後)，利用堆疊(Stack)做為緩衝區。將來源資料輸入、輸出堆疊，即存入(Push)或取出(Pop)，下列何者是可能的資料輸出順序？ (A)c、d、a、b(c最先、b最後) (B)c、d、b、a(c最先、a最後) (C)a、d、b、c(a最先、c最後) (D)d、c、a、b(d最先、b最後)。[112身心五等]

Push a → Push b → Push c → Pop c → Push d → Pop d → Pop b → Pop a

 

【D】14.作業系統是採用那種資料結構，來存取程式撰寫中遞迴函式呼叫(recursive function call)的整個過程？ (A)陣列(Array) (B)佇列(Queue) (C)平行佇列(Parallel Queue) (D)堆疊(Stack)。[112身心五等]

堆疊：先進後出(FILO, First In Last Out)，最後放入(push)的資料，最先取出(pop)，應用於回溯、遞迴、深度優先搜尋。

 

【B】15.資料結構的表示法中，運算元及運算子的位置會形成所謂前序或後序的表示法。若有兩個後序表示法，第一個是10 8 + 6 5 * -而第二個後序表示法是6 3 5 * - 2 4 - + 2 -。請問這兩個後序表示法若用堆疊法運算後，將個別的答案加起來，結果是多少？ (A)-30 (B)-25 (C)27 (D)-8。[112初考資處]

 

【C】16.假設兩個堆疊(stack)S1與S2，一開始它們的內容都是空的(empty)。那麼執行下列的演算法後

push(S1, 5)

push(S1, 3)

push(S1, 2)

push(S2, 6)

push(S2, 7)

pop(S1)

while(not empty(S2)) push(S1, pop(S2))

S1的內容為何？(由左至右的順序代表堆疊的底部到上面) (A)5 3 2 7 6 (B)3 2 7 6 (C)5 3 7 6 (D)5 3 6 7。[112國安五等]

S1 = (5 3 2), S2 = (6 7)

POP(S1) → S1取出2

S1 = (5 3), S2 = (6 7)

執行while迴圈，將S2的6 7移到S1

S1= (5 3 6 7)

 

【D】17. 假設有堆疊S1、S2與佇列Q1、Q2、Q3，以下圖方式連結，且Q1有三個資料A、B、C(A在佇列前端)，其餘堆疊與佇列皆為空。

今有四個指令如下：

●若Q1非空，從Q1刪除一個資料並push到S1中

●若S1非空，從S1pop出一個資料並加入到Q2中

●若Q2非空，從Q2刪除一個資料並push到S2中

●若S2非空，從S2pop出一個資料並加入到Q3中

我們可用任何順序執行這四個指令，直到所有資料皆存入Q3。下列敘述何者正確？ (A)資料被加入Q3的順序不可能是A、C、B (B)資料被加入Q3的順序不可能是B、A、C (C)資料被加入Q3的順序不可能是C、A、B (D)資料被加入Q3的順序可以是A、B、C的任意排列順序。[112普考電子]

堆疊是先進後出，佇列是先進先出。

Q1資料A、B、C依序移入到S1，接著從S1移至Q2，再從Q2移入S2，最後從S2移至Q3，Q3的順序是A、B、C。

 

【C】18.關於堆疊(Stack)資料結構，下列敘述何者錯誤？ (A)可以使用鏈結串列(Linked list)實作堆疊 (B)堆疊的頂端(Top)總是存放最新插入的元素 (C)堆疊是FIFO的資料結構 (D)可以使用陣列(Array)實作堆疊。[112鐵路員級]

堆疊：先進後出(FILO, First-in-last-out)的資料結構，主要的操作有放入資料(push)和取出資料(pop)。

 

【B】19.下列那個序列是下圖中以0為起點的Depth-first search順序？ (A)0、1、2、3、4、5 (B)0、1、3、2、4、5 (C)0、1、2、4、3、5 (D)0、1、3、5、2、4。[112鐵路員級]

深度優先搜尋法(DFS)，(A)(C)1、2沒相連，(D)5、2沒相連。

 

留言

張貼留言

這個網誌中的熱門文章

計概16-09後序－公職試題

圖片
【選擇題】 【 C 】 01. 以後序 (postorder) 方式走訪下圖中的運算樹，且輸出走訪到的節點內容，下列何者為輸出的字串？ (A)*A+BC (B)A*B+C (C)ABC+* (D)ABC*+ 。 [109 地方四等電子 ] 後序走訪順序：左子樹 → 右子樹 → 根節點。   【 D 】 02. 某二元樹有 3 個節點，經後序走訪 (postorder traversal) 結果輸出 C 、 B 、 A ，該二元樹有幾種可能？ (A)3 (B)9 (C)7 (D)5 。 [109 地方四等電子 ]   【 D 】 03. 將中序運算式 (Infix Expression)1(23/4)*5+- 轉換為後序運算式 (Postfix Expression) 的結果為何？ (A)12+34/5*- (B)12+345*/- (C)123-4/5*+ (D)1234/-5*+ 。 [109 關務四等 ] 1+(2-3/4)*5 → 1+((2-(3/4))*5) → 1234/-5*+ 由右往左，將運算子取代最近的右括號   【 C 】 04. 某一個二元樹的前序 (pre-order) 順序為 ABCDEFGHI ，中序 (in-order) 順序為 BCAEDGHFI ，則其後序 (post-order) 順序為何？ (A)ABDCEFGIH (B)BCADGFIE (C)CBEHGIFDA (D)DHGFEICBA 。 [109 鐵路員級 ] 前序找最前，中序分左右，後序找最後。 前序： ABCDEFGHI ，最前為 (A) 中序： BCAEDGHFI ，以 (A) 為中，分成左 (BC) ，右 (EDGHFI) 後序的順序為 " 左右中 " ， A 放在最後，則左 (BC) 右 (EDGHFI) 中 (A) ，選 (C) 。   【 B 】 05. 如果某一個二元樹的前序與中序表示法為： c, a, b, d, g, e, f 與 b, a, g, d, c, e, f ，則其後序表示法為何？ (A)b, d, g, a, f, e, c (B)b, g, d, a, f, e, c (C)b, g, d, a, e, f, c (D)c, a, b,
閱讀完整內容

計概16-06樹－公職試題

圖片
【選擇題】 【 B 】 01. 關於一個有 n 個節點的紅黑樹 (red-black tree) ，下列敘述何者錯誤？ (A) 根節點 (root) 是黑色 (B) 如果一個節點是黑色，它的兩個子節點都會是紅色 (C) 葉節點 (leaf) 是黑色 (D) 從根節點到葉節點的每個路徑中，黑色節點的數量必須一樣。 [109 地方四等資處 ] 紅黑樹的特性： 1. 根節點是黑色。 2. 葉節點是黑色。 3. 從根節點到葉節點的每個路徑中，黑色節點的數量必須一樣。 4. 每個節點，可紅可黑。 5. 節點是紅色，子節點必為黑色。節點是黑色，子節點可紅可黑。   【 A 】 02. 若從數列 [1, 3, 5, 7] 中，依序取出其中的數字來建立二元搜尋樹 (binary search tree) ，則該樹為下列何者？ [109 地方四等電子] 二元搜尋樹 (binary search tree) ：小      中      大 第 1 個數字 1 當樹根。第 2 個數字 3 ， 1 ＜ 3 ， 3 放在 1 的右邊。 第 3 個數字 5 ， 3 ＜ 5 ， 5 放在 3 的右邊。第 4 個數字 7 ， 5 ＜ 7 ， 7 放在 5 的右邊。   【 B 】 03. 關於下圖二元搜尋樹 (binary search tree ， BST) ，下列何者正確？ (A) 若對 BST 做中序瀏覽 (inorder traversal) 可以產生一個依降冪排列的有序串列 (B) 若對 BST 做廣度優先瀏覽 (breadth first traversal) 產生的串列並沒有一定的秩序 (C) 若對 BST 做後序瀏覽 (postorder traversal) 可以產生一個依昇冪排列的有序串列 (D) 若對 BST 做前序瀏覽 (preorder traversal) 可以產生一個依昇冪排列的有序串列。 [109 身心五 等 ] 對 BST 做 中序瀏覽 產生升 冪排列的有序串列。廣度優先瀏覽產生的串 列並無唯一解。   【 C 】 04. 下列有關高度為 h 、節點數為 n 的二元搜尋樹之敘述，何者錯誤？ (A) 搜尋特定節點所需時間與 h 成正比 (B) 依由小到大之次序輸出所有結點資料
閱讀完整內容

計概16-09後序－統測試題

圖片
【二技試題】 【 C 】 01. 中序式 (Infix form) 表示的運算式 B-C+D*E/(F-G) ， 如果轉換成為後序式 (Postfix form) 應為 (A)+-BC/*DE-FG (B)BCDEFG+-*/- (C)BC-DE*FG-/+ (D)GF-E/D*C+B- 。 [91 護理 ]   【 D 】 02. 某個二元樹 (binary tree) 的前序式 (preorder) 為 ABDFGEC ，中序式 (inorder) 為 FDGBAEC ，則其後序式 (postorder) 為何？ (A)FDGBECA (B)FGDBECA (C)FDGBCEA (D)FGDBCEA 。 [92 管理 ]   【 A 】 03. 假設 a = 5, b = 4, c = 3, d = 2 ，則依後序 (postfix) 運算式 ab * cd + / 之計算值為何？ (A)4 (B)11.5 (C)0.25 (D)10.5 。 [92 護理 ]   【 C 】 04. 後序 (postfix) 運算式 6,3,/,3,-,5,2,*,+ 之計算結果為何？ (A)3 (B)6 (C)9 (D)11 。 [95 護理 ]   【 A 】 05. 有一個中序 (infix) 表示式為 (a/(b-c+d)) × e-a × c ，則此式之後序 (postfix) 表示式為何？ (A)abc-d+/e×ac×- (B)ab/c-de×+ac×- (C)abcdeac-+/-×× (D)abcd-+/ea-c×× 。 [96 電機 ]   【 D 】 06. 假設 W = 4, X = 2, Y = 5, Z = 3 ，後序 (posrfix) 運算式為 WX/YZ-+X* 的值為何？ (A)6 (B)7 (C)12 (D)8 。 [97 管理 ]   【 D 】 07. 若有一個中序 (infix) 式為 ((a+b)+c × (p-q))/(r-s/t) ，其後序式應為下列何者？ (A)abc+-p+/q×rst/- (B)ab/c-p+q+rst×-/ (C)ab+cpqrst-+/-×/ (D)ab+cpq-×+rst/-/ 。 [98 電機 ]   【 C 】 08.
閱讀完整內容