阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
101年 - 101年三等關務特考資料結構#45156
>
題組內容
五、
⑵將收 到的 1001010101001011110010111100 字串解碼,列出文字訊息。(20 分) [註 1:建立霍夫曼樹時,比重較小的子樹成左邊子樹,比重較大的子樹成右邊子樹。 註 2:當編碼時,左邊(left edge)是 0,右邊(right edge)是 1。]
其他申論題
三、當飛機航班客滿或超額預約(overbooked)時,在機場航空公司櫃台常有機位候補 (standby)的長龍。候補優先次序是由乘客的購票價格、累積里程數及要求候補的 時間先後等因素決定優先權(priority)。請設計一個有效率的資料結構及其運算 (operations)來處理候補,並說明其時間複雜度。(15 分)
#151011
⑴描述 Kruskal 演算法對一個無向權重圖(undirected weighted graph)找出最小生成 樹(minimum spanning tree)的步驟,並分析其計算複雜度。
#151012
⑵設計合適的資料結 構以儲存在過程中產生的多個連結組件(connected components),並能有效率的決 定是否採用或丟棄端點為(u,w)的一個邊(edge(u,w)),請說明。(20 分)
#151013
⑴資料壓縮可以減少資料儲存空間或網路資料傳輸量,文字資料常使用霍夫曼編碼 (Huffman coding)作壓縮。在文件中現有六個文字訊息 A, B, C, D, E, F,其出現的次 數各為 16, 12, 9, 6, 7, 2。請建立霍夫曼樹,並列出 A, B, C, D, E, F 的霍夫曼碼。
#151014
(1)2-3 樹(2-3 tree)
#151016
(2)AVL 樹(AVL tree)
#151017
(3)最大堆(Max-Heap) (4)排序陣列(sorted array increasing order),試就搜尋(search key)、刪除(delete key)、插入(insert key)、列印全部排序(print all nodes in order)及找最大值 (find Max)等運算,比較其時間複雜度。(20 分) [註:請以表格列表呈現]
#151018
⑴畫出無異曲線(indifference curve)並解釋其意義。(5 分)
#151019
⑵以無異曲線圖形畫出消費者效用極大均衡解,並以文字或數學式解釋均衡條件。 (10 分)
#151020
⑶需求法則說「當 PX 提高時,消費者對 X 商品之需求量會下降」。請以無異曲線 圖形分析及文字解釋此論點。(10 分)
#151021