阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
100年 - 100年高等資料結構(包括資料庫)#46089
>
題組內容
五、倒置檔(inverted file)或稱「索引檔」是在網路搜索引擎或大型檢索服務資料庫所 採用的基本檔案結構之一,其作用在於將那些文件包含某一關鍵字的資訊儲存起來 (目的在提高檢索速度)。倒置檔中針對每一個搜索關鍵字(keyword)儲存了一 串文件資訊,如文件代碼及其在資料庫中的位址或網頁的位址。(20 分)
⑴請設計此倒置檔的資料結構。
其他申論題
二、將二元搜尋樹(binary search tree)每個節點資料稍做修改,加入左子樹大小(leftsize) 的額外資訊,即可達成排序搜尋的功能(search by rank)。一個節點左子樹大小是 左子樹的節點數加 1(根節點自己)。將資料 30, 15, 50, 6, 10, 36, 66 依序插入空的 二元搜尋樹,試繪出完成後的二元排序搜尋樹(binary search tree with rank),每個 節點附上左子樹大小。(10 分)
#156612
⑴請說明圖形的資料結構及表示法(representation)。
#156613
⑵請描述找出小社群(graph connected components)的方法。
#156614
四、請說明編譯器(compiler)如何使用堆疊(stack)檢查一個算術式子(arithmetic expression)的語法(syntax)正確性,請說明如何檢查括弧是否成雙成對出現,沒 有錯誤。(15 分)
#156615
⑵請描述查詢時的運作(operation),以查詢字詞(query term)q1、q2 符合邏輯 條件(logical condition)q1 AND q2 為例說明。
#156617
⑴請討論設計一個優良的雜湊表需考量的要素。
#156618
⑵請說明運算(search, insert, delete)的時間複雜度及空間複雜度。
#156619
⑶請列舉一些使用雜湊表的應用(application)。
#156620
七、請描述合併排序法(merge sort)及使用的資料結構,並討論其時間複雜度(time complexity)、空間複雜度(space complexity)及穩定性(stability)。(10 分)
#156621
一、美國國家職業安全衛生署(National Institute for Occupational Safety & Health, NIOSH) 於 1991 年提出抬舉指數(Lifting Index, LI)來評估人工物料搬運作業對人員下背部傷害的 風險。其中 LI=實際抬舉物品重量/RWL,而 RWL 為建議抬舉重量限度(recommended weight limit): RWL = LC × HM × VM × DM × AM × CM × FM 某作業員作業時將箱子由輸送帶(此時手部到地面高度為 60 公分)上抬至物料架 上(此時手部到地面高度為 100 公分),開始抬舉時作業員雙腳腳踝終點連線到手 部握持處的水平距離為 35 公分,物料抬舉時不用轉身。另外,手部握持條件為普 通,因此 CM 為 0.95,物料搬運頻率為每分鐘三件,因此 FM 為 0.55。請問此作業 的建議抬舉重量限度值為多少公斤?(20 分)
#156622