阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
107年 - 107 高考三級 資料結構#70742
> 申論題
一、⑴請說明並比較二分搜尋(binary search)與一般二元搜尋樹(binary search tree)兩 者在儲存鍵值並應用來進行搜尋鍵值功能時,在'建置'與'搜尋'程序上作法與效能的 差異(13 分)。
相關申論題
⑵若有 n 個鍵值,以下列甲和乙兩種資料結構策略儲存: 策略甲:由小到大依序儲存在一陣列中 策略乙:以 AVL tree 架構儲存 請以 Big-O 觀念比較後續六種不同功能獨立運作時,這兩種策略何者效能較優或 兩者效能相近:1.尋找特定鍵值 k;2.尋找排序為 j 的鍵值;3.刪除特定鍵值 k; 4..刪除排序為 j 的鍵值;5.插入新鍵值;6.依序輸出所有鍵值。 (12 分)
#283418
二、一非空的二元樹(binary tree) ,如果有 n0 個葉節點(leaf node)且 n2 個節點之分支 度(degree)為 2,請證明 n0 = n2+1。(25 分)
#283419
三、一無向圖 G 之節點集合為 G(V)={0,1,2,3,4,5,6,7,8,9},邊集合為 G(E)={(0,1), (1,2), (1,3), (2,4), (3,4), (3,5), (5,6), (5,7), (6,7), (7,8), (7,9)};請列出 G 之接合點(articulation point)和畫出 G 的所有雙連通元件(biconnected component),雙連通元件須以節點 和邊構成之子圖方式表示。 (20 分)
#283420
⑴請說明 SMMH 特性並說明以 SMMH 建構之優先佇列與以一般的堆積(heap)建 構 之 優 先 佇 列 功 能 有 何 不 同 ? 並 從 一 個 空 的 SMMH 開 始 , 依 序 插 入 30,20,50,5,4,9,70,2,80。請畫出最後 SMMH 的樹狀結構圖。(10 分)
#283421
⑵請畫出第⑴小題建構的 SMMH,刪除數字 2 後 SMMH 的樹狀結構圖。 (5 分)
#283422
⑶請以一維陣列設計一資料結構儲存 SMMH,該資料結構可以使節點透過其對應之 陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點 p、左子節點 l、右子節 點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為 0,請列出 由 x 構成之計算 g、p、l、r、s 的數學式。並請畫出以此一維陣列儲存第⑴小題建 構完成的 SMMH 的結果。(15 分)
#283423
(五)若 n = 10,且每一組球生產後放上裝箱輸送帶的 球的大小順序非固定順序 。假設輸送帶上原本配置 n 個機器人,若改成配置 2n 個機器人, 整組球順序排好的速度可以加快多少?請說明。
#560494
(四)若每一組球生產後放上裝箱輸送帶的 球的大小順序非固定順序 ,請說明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排到小?
#560493
(三)若 n = 6,且輸送帶上配有 4 個機器人,請給一組放上裝箱輸送帶的球的大小順序,使得其經過這 4 個機器人後,整組球的順序仍未能排好。
#560492
(二)若 n = 20,且生產後放上裝箱輸送帶的球的大小為 11, 12, 20, 16, 3, 1, 7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17,請說明輸送帶上最少該配置幾個機器人才能將球的順序由大排到小?
#560491
相關試卷
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