DS98-02_98年公務人員特種考試身心障礙人員考試_3等_資訊處理_資料結構

範本檔案下載網址：DS98-02_98年公務人員特種考試身心障礙人員考試_3等_資訊處理_資料結構

98年公務人員特種考試身心障礙人員考試試題 代號：31170

等 別： 三等考試

類 科： 資訊處理

科 目： 資料結構

考試時間： 2 小時

一、假設原有N筆資料以排序方式（ordered）存放於陣列，試計算插入一筆新資料平均需移動幾筆資料？（10分）

二、請解釋堆疊（stack）的資料結構及運作（operation），並列舉一些常使用堆疊的應用。（15分）

三、試討論使用陣列（array）及鏈結串列（linked list）實作佇列（queue）之優缺點。（15分）

四、請說明在作資料排序時，選擇一個合適的排序演算法（sorting algorithm）必須考慮那些因素？（15分）

五、將二元搜尋樹（binary search tree）所有節點資料從小到大按順序列印出來，請說明用下列那種樹尋訪演算法（tree traversal）可以達成：中序尋訪法（inorder），先序尋訪法（preorder），後序尋訪法（postorder）。（15分）

六、請說明使用雜湊表（Hash Table）實作一個編譯器中常用關鍵詞表（symbol table）之優缺點。（15分）

七、請說明最大堆積（Max Heap）的資料結構及運作（operation），並討論使用最大堆積來實作優先權佇列（priority queue）之優點。（15分）