全新功能【寫作批改】正式登場，歡迎大家使用看看！ 前往查看
【站僕】摩檸Morning>試卷(2021/12/15)

公職◆資料結構題庫 下載題庫

110 年 - 110 地方政府特種考試_三等_資訊處理：資料結構#104908　

選擇:0題,非選:11題 我要補題 回報試卷錯誤
【非選題】
1.

一、61b98d570c8a8.jpg


【題組】(一)請分別寫出下圖二元樹的前序走訪法（preorder traversal） 、中序走訪法 （inorder traversal）、後序走訪法（postorder traversal）的結果（6 分）



【非選題】
2.【題組】(二)請在無法預知二元樹的節點數條件下，設計在程式中表示二元樹的資 料結構。再假設二元樹已依前述結構儲存在程式，設計一副程式（或 函式）的演算法，在提供樹根給此副程式（或函式）後，其執行二元 樹中序走訪法的程序並輸出走訪結果。此副程式（或函式）不可使用 遞迴呼叫技術但可添加其他資料結構，演算法的時間複雜度和空間複 雜度須均為 O(n)，n 為二元樹的節點個數。演算法可以虛擬碼（pseudo- code）或以高階語言如 C 呈現。需分析說明副程式（或函式）演算法 的時間複雜度和空間複雜度均為 O(n)。（提醒：若用遞迴呼叫技術設 計，演算法部分不給分） （13 分）



【非選題】
3.【題組】(三)請分別說明在程式執行過程，以第(二)子題非遞迴呼叫技術設計相較於 以遞迴呼叫技術設計在時間與空間的效能優勢各為何？（6 分）



【非選題】
4.

二、二維方陣 A 大小為 nn，方陣中的元素除了主對角線之元素以及緊鄰它的 上下兩條對角線之元素的值可能不為零外，方陣 A 其他元素之值一定為 零，以 55 方陣為例如下圖。請以一維陣列 B 設計儲存此方陣 A 之結構， 陣列 B 之索引值自 0 開始，且陣列 B 的元素數量須小於或等於 3n-2。設 計的結構須包含如何有效率地決定儲存方陣 A 之元素 aij 以及如何自陣 列 B 中取得或決定方陣中元素 aij 值，其中 0 ≤ i, j ≤ n-1 而 i 與 j 分別為元 素在方陣 A 中之列號與行號。（20 分）
61b98dd2d6a9a.jpg



【非選題】
5.

三、(一)請畫出下圖以鏈結串列（link list）為基礎的相鄰串列（adjacency list） 結構表示之結果。（5 分）
61b98df227ccd.jpg



【非選題】
6.

三、(一)請畫出下圖以鏈結串列（link list）為基礎的相鄰串列（adjacency list） 結構表示之結果。（5 分）
61b98dfeb39e5.jpg


【題組】(二)請運用一維陣列設計一資料結構採循序串列（sequential list）架構，其 仍舊以類似子題(一)相鄰串列策略表示無向圖（undirected graph）節點 與邊的關係，但僅以一維陣列呈現第(一)子題之相鄰串列概念。圖之節 點與邊的關係僅以此一維陣列元素記錄並呈現，不可使用其他資料結 構，另外，陣列中亦需記錄此陣列中用來記錄與圖相關資訊之元素個 數；除了說明資料結構外，也請寫出下圖以此資料結構表示之一維陣 列結果。（8 分）



【非選題】
7.
三、(一)請畫出下圖以鏈結串列（link list）為基礎的相鄰串列（adjacency list） 結構表示之結果。（5 分）
61b98dfeb39e5.jpg
 (二)請運用一維陣列設計一資料結構採循序串列（sequential list）架構，其 仍舊以類似子題(一)相鄰串列策略表示無向圖（undirected graph）節點 與邊的關係，但僅以一維陣列呈現第(一)子題之相鄰串列概念。圖之節 點與邊的關係僅以此一維陣列元素記錄並呈現，不可使用其他資料結 構，另外，陣列中亦需記錄此陣列中用來記錄與圖相關資訊之元素個 數；除了說明資料結構外，也請寫出下圖以此資料結構表示之一維陣 列結果。（8 分）

【題組】(三)請列出兩項在程式中以第(一)子題之以鏈結串列（link list）表示圖比以 第(二)子題一維陣列表示圖適合的應用情境或效能優勢。另外，也請列 出兩項在程式中以第(二)子題一維陣列表示圖比以第(一)子題鏈結串列 （link list）表示圖適合的應用情境或效能優勢。（12 分）



【非選題】
8.四、區間堆積（interval heap）是一種優先佇列（priority queue） ，請回答下列 相關的問題。 (一)從一個沒有元素的區間堆積開始，依序插入 40, 30, 60, 15, 14, 19, 80, 12, 90 等元素。請畫出最後區間堆積的樹狀結構圖。 （9 分）



【非選題】
9.
四、區間堆積（interval heap）是一種優先佇列（priority queue） ，請回答下列 相關的問題。

 (一)從一個沒有元素的區間堆積開始，依序插入 40, 30, 60, 15, 14, 19, 80, 12, 90 等元素。請畫出最後區間堆積的樹狀結構圖。 （9 分）

【題組】(二)請自第(一)子題建構的區間堆積中刪除元素 12，並畫出刪除該元素後區 間堆積的樹狀結構圖。（3 分）



【非選題】
10.【題組】(三)請以一維陣列設計資料結構儲存區間堆積，該資料結構可以透過節點 對應之陣列索引值 index 構成的數學式計算出其父節點 parent、左子 節點 left、右子節點 right 與兄弟節點 brother 等在陣列中的索引值。假 設此一維陣列之起始索引值為 0，請列出由 index 構成的計算 parent、 left、right、brother 的數學式。並請畫出以此一維陣列儲存第(一)子題建 構完成的區間堆積的結果。 （12 分）



【非選題】
11.【題組】(四)舉例並說明一既需要提供最高優先元素，也需要提供最低優先元素的 優先佇列的應用實例或系統。（6 分）



懸賞詳解

X

未分類

...

10 x

前往解題

110 年 - 110 地方政府特種考試_三等_資訊處理：資料結構#104908-阿摩線上測驗

110 年 - 110 地方政府特種考試_三等_資訊處理：資料結構#104908