阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 100年 - 100年高等資料結構(包括資料庫)#46089
100年 - 100年高等資料結構(包括資料庫)#46089
科目:
公職◆資料結構 |
年份:
100年 |
選擇題數:
0 |
申論題數:
12
試卷資訊
所屬科目:
公職◆資料結構
選擇題 (0)
申論題 (12)
⑴現在伺服器處理下一個工作時,從最大堆積取出(delete)最高優先權的工作,請 以陣列形式列出刪除運作後最大堆積的內容,並說明一個刪除運作(delete)的 時間複雜度。
【已刪除】 ⑵接著有一個新工作要求進來(insert),其優先權是 66,請以陣列形式列出插入 運作後最大堆積的內容,並說明一個插入運作(insert)的時間複雜度。
二、將二元搜尋樹(binary search tree)每個節點資料稍做修改,加入左子樹大小(leftsize) 的額外資訊,即可達成排序搜尋的功能(search by rank)。一個節點左子樹大小是 左子樹的節點數加 1(根節點自己)。將資料 30, 15, 50, 6, 10, 36, 66 依序插入空的 二元搜尋樹,試繪出完成後的二元排序搜尋樹(binary search tree with rank),每個 節點附上左子樹大小。(10 分)
⑴請說明圖形的資料結構及表示法(representation)。
⑵請描述找出小社群(graph connected components)的方法。
四、請說明編譯器(compiler)如何使用堆疊(stack)檢查一個算術式子(arithmetic expression)的語法(syntax)正確性,請說明如何檢查括弧是否成雙成對出現,沒 有錯誤。(15 分)
⑴請設計此倒置檔的資料結構。
⑵請描述查詢時的運作(operation),以查詢字詞(query term)q1、q2 符合邏輯 條件(logical condition)q1 AND q2 為例說明。
⑴請討論設計一個優良的雜湊表需考量的要素。
⑵請說明運算(search, insert, delete)的時間複雜度及空間複雜度。
⑶請列舉一些使用雜湊表的應用(application)。
七、請描述合併排序法(merge sort)及使用的資料結構,並討論其時間複雜度(time complexity)、空間複雜度(space complexity)及穩定性(stability)。(10 分)