阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
102年 - 102年專利商標審查人員三等資料結構(包括資料庫)#44088
>
題組內容
一、
⑴請使用 C 或 Java 語言,寫一遞迴(recursive)副程式,此副程式的輸入為一個未 排序的(unsorted)且長度為 n 的整數陣列 A[0:n−1],副程式將在此整數陣列中, 以遞迴的方式,尋找此整數陣列中的最大值,並回傳此最大值。(15 分)
其他申論題
⑵假設一 n 個 nodes 之 k-ary tree(即分支度為 k 之樹)T,每一個 node 有一固定大 小之欄位如下,請說明共有多少欄位是 Null?(8 分)
#144085
⑴請說明紅黑樹(red-black tree)之特性。(4 分)
#144086
⑵建立一紅黑樹,其數字依序為 10、72、14、68、20、58、30、50、65、63。(10 分)
#144087
⑶請一步一步刪除圖 5 紅黑樹之節點,依序為 10、18、3、16、13、12、17。其中 在圖 5 之節點 7、12、20 為紅色節點。(10 分)
#144088
⑵請分析 此副程式的時間複雜度以 order 的方式表示。(5 分)(注意:不可將此陣列數值進 行排序,請加註解說明程式碼作法)。
#144090
⑴請繪出此二元樹。 (10 分)
#144091
⑵列出此二元樹之後序尋訪序列(postorder traversal)。(5 分)
#144092
⑶列出 此二元樹階層尋訪序列(level order traversal or breadth first search traversal)。(5 分)
#144093
⑴請設計一個 Greedy 的演算法,來解決一個圖形著色的問題。使用最少的顏色, 對一個圖形(Graph)上的所有頂點(vertex)進行著色(coloring),使得任兩個相 連(鄰)的頂點,不著相同的顏色。(15 分)
#144094
⑵請問你的 Greedy 演算法的解法是 否能保證永遠為最佳解?試舉例說明。(5 分)
#144095