阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
109年 - 109 高等考試_三級_資訊處理:資料結構#88766
> 申論題
題組內容
(三)二元堆積(Binary Heap)是一個優先佇列的資料結構,因為我們考慮鍵值小的物件有高的優先權,所以又可稱為最小堆積(Minimum Heap)。
(2)請說明二元堆積中何謂堆積特性(Heap Property)?
相關申論題
(一)數字1到n的何種排列會有最大的反向數?最大反向數是多少?
#360140
(二)若給定一個數字1到n的排列P,請提出一個線性遞迴(Linear Recursive) 的方式來算出排列P的反向數,並提供虛擬碼(Pseudo-code)與時間複 雜度分析。
#360141
二、優先佇列(Priority Queue)是依管理物件的優先權來考量,在此我們考慮 管理物件的鍵值(Key)愈小其優先權愈高,兩個主要操作則分別為加入 (Insert)與擷取最小者(Delete_Min)。 (一)請說明如何利用優先佇列對n個鍵值進行排序。
#360142
(1)若有n個鍵值,請說明兩個主要操作(加入(Insert)與擷取最小者 (Delete_Min))的時間複雜度。
#360143
(2)請判斷下面的敘述是否為真,並請說明原因: 若以此優先佇列進行排序(Sorting),其所對應的排序原理為插入排 序(Insertion Sort)。
#360144
(1)在結構上最小堆積為一個完全二元樹(Complete Binary Tree),若使 用一個陣列來實作最小堆積,陣列中物件的鍵值放置如下,請描述此 陣列對應的完全二元樹(以樹狀結構表示)。
#360145
(3)前揭「在結構上最小堆積為一個完全二元樹(Complete Binary Tree),若使 用一個陣列來實作最小堆積,陣列中物件的鍵值放置如下,請描述此 陣列對應的完全二元樹(以樹狀結構表示)。」中的完全二元樹並未有堆積特性,請將其進行堆積化 (Heapify),並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。
#360147
(一)我們欲將所管理的鍵值(Key)依序列出,請問是否可以利用一個AVL 樹對鍵值來進行排序(Sorting)?若不行,請說明原因;如果可以,請描述方法及時間複雜度。
#360148
(二)請提供一個線性時間的演算法來判斷一個二元搜尋樹是否為AVL樹。
#360149
(三)在AVL樹上進行一個加入(Insert)操作後,是否最多只需要一次的重構 (Restructuring)即可恢復其平衡的特性?請說明原因。
#360150
相關試卷
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