阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
110年 - 110 地方政府特種考試_三等_資訊處理:資料結構#104908
> 申論題
四、區間堆積(interval heap)是一種優先佇列(priority queue) ,請回答下列 相關的問題。 (一)從一個沒有元素的區間堆積開始,依序插入 40, 30, 60, 15, 14, 19, 80, 12, 90 等元素。請畫出最後區間堆積的樹狀結構圖。 (9 分)
相關申論題
(一)請分別寫出下圖二元樹的前序走訪法(preorder traversal) 、中序走訪法 (inorder traversal)、後序走訪法(postorder traversal)的結果(6 分)
#444771
(二)請在無法預知二元樹的節點數條件下,設計在程式中表示二元樹的資 料結構。再假設二元樹已依前述結構儲存在程式,設計一副程式(或 函式)的演算法,在提供樹根給此副程式(或函式)後,其執行二元 樹中序走訪法的程序並輸出走訪結果。此副程式(或函式)不可使用 遞迴呼叫技術但可添加其他資料結構,演算法的時間複雜度和空間複 雜度須均為 O(n),n 為二元樹的節點個數。演算法可以虛擬碼(pseudo- code)或以高階語言如 C 呈現。需分析說明副程式(或函式)演算法 的時間複雜度和空間複雜度均為 O(n)。(提醒:若用遞迴呼叫技術設 計,演算法部分不給分) (13 分)
#444772
(三)請分別說明在程式執行過程,以第(二)子題非遞迴呼叫技術設計相較於 以遞迴呼叫技術設計在時間與空間的效能優勢各為何?(6 分)
#444773
二、二維方陣 A 大小為 nn,方陣中的元素除了主對角線之元素以及緊鄰它的 上下兩條對角線之元素的值可能不為零外,方陣 A 其他元素之值一定為 零,以 55 方陣為例如下圖。請以一維陣列 B 設計儲存此方陣 A 之結構, 陣列 B 之索引值自 0 開始,且陣列 B 的元素數量須小於或等於 3n-2。設 計的結構須包含如何有效率地決定儲存方陣 A 之元素 aij 以及如何自陣 列 B 中取得或決定方陣中元素 aij 值,其中 0 ≤ i, j ≤ n-1 而 i 與 j 分別為元 素在方陣 A 中之列號與行號。(20 分)
#444774
三、(一)請畫出下圖以鏈結串列(link list)為基礎的相鄰串列(adjacency list) 結構表示之結果。(5 分)
#444775
(二)請運用一維陣列設計一資料結構採循序串列(sequential list)架構,其 仍舊以類似子題(一)相鄰串列策略表示無向圖(undirected graph)節點 與邊的關係,但僅以一維陣列呈現第(一)子題之相鄰串列概念。圖之節 點與邊的關係僅以此一維陣列元素記錄並呈現,不可使用其他資料結 構,另外,陣列中亦需記錄此陣列中用來記錄與圖相關資訊之元素個 數;除了說明資料結構外,也請寫出下圖以此資料結構表示之一維陣 列結果。(8 分)
#444776
(三)請列出兩項在程式中以第(一)子題之以鏈結串列(link list)表示圖比以 第(二)子題一維陣列表示圖適合的應用情境或效能優勢。另外,也請列 出兩項在程式中以第(二)子題一維陣列表示圖比以第(一)子題鏈結串列 (link list)表示圖適合的應用情境或效能優勢。(12 分)
#444777
(二)請自第(一)子題建構的區間堆積中刪除元素 12,並畫出刪除該元素後區 間堆積的樹狀結構圖。(3 分)
#444779
(三)請以一維陣列設計資料結構儲存區間堆積,該資料結構可以透過節點 對應之陣列索引值 index 構成的數學式計算出其父節點 parent、左子 節點 left、右子節點 right 與兄弟節點 brother 等在陣列中的索引值。假 設此一維陣列之起始索引值為 0,請列出由 index 構成的計算 parent、 left、right、brother 的數學式。並請畫出以此一維陣列儲存第(一)子題建 構完成的區間堆積的結果。 (12 分)
#444780
(四)舉例並說明一既需要提供最高優先元素,也需要提供最低優先元素的 優先佇列的應用實例或系統。(6 分)
#444781
相關試卷
114年 - 114 地方政府公務特種考試_三等_資訊處理:資料結構#134706
114年 · #134706
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
114年 · #133251
114年 - 114 高等考試_三級_資訊處理:資料結構#128753
114年 · #128753
114年 - 114 關務特種考試_三等_資訊處理(選試英文):資料結構#126563
114年 · #126563
114年 - 114 身心障礙特種考試_三等_資訊處理:資料結構#126562
114年 · #126562
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理:資料結構#124511
113年 · #124511
113年 - 113 高等考試_三級_資訊處理:資料結構#121217
113年 · #121217
113年 - 113 關務特種考試_三等_資訊處理(選試英文):資料結構#119489
113年 · #119489
112年 - 112 地方政府特種考試_三等_資訊處理:資料結構#118368
112年 · #118368
112年 - 112 公務升官等考試_薦任_資訊處理:資料結構#117327
112年 · #117327