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