105年 - 105年高等三級暨普通考高考三級資料結構 #54337

科目：公職◆資料結構 | 年份：105年 | 選擇題數：0 | 申論題數：11

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (11)

⑴使用堆疊（stack），從 S 開始，進行深度優先走訪（depth-first traversal），請寫出走訪結果。（10 分）

⑵使用佇列（queue），從 S 開始，進行廣度優先走訪（breadth-first traversal），請寫出走訪結果。（10 分）

二、⑴請將下列值 2, 1, 4, 5, 9, 3, 6, 7 依序插入原來為空的紅黑樹（red-black tree），請寫出結果。作答時，請標示節點如下：例如節點 2B 表示其值為 2 的黑（Black）節點，又如節點 5R 表示其值為 5 的紅（Red）節點。（10 分）

⑵請畫出與上面⑴小題相對應的 2-3-4 樹（2-3-4 tree）（10 分）。

【已刪除】三、請對下面的樹，分別做前序（preOrder）、中序（inOrder）、後序（postOrder）及廣度優先（breadth-first）四種走訪（traversals），請分別寫出結果。（20 分）

四、⑴依序插入 2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆（min heap），請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）

⑵從上面⑴小題的結果刪除兩個元素，請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）

⑴ for (int i = 0; i * i < n; i++) S

⑵ for (int i = 1; i < n+1; i*=2) S

【已刪除】 ⑶

【已刪除】 ⑷