阿摩線上測驗 登入

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 分）