阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
102年 - 102年地方三等考試-三等資料結構#43740
>
題組內容
一、請參考圖 1:
⑴由 a 點出發,做 depth-first traversal(深度優先拜訪),請問那些節點(node)不 會被訪問到?(3 分)
其他申論題
一、文藝復興時期在西方的歷史中具有關鍵性的地位。試問:人文學者(humanist)的 核心觀念是什麼?他們怎樣評論古希臘、羅馬和所謂「中古時代」的歷史意義?列 舉一位重要的人文學者及其著作,並說明他的重要性。(25 分)
#141793
二、試分別說明何謂保守主義、自由主義和社會主義?並各舉一位重要的思想家及其思 想。(25 分)
#141794
三、荷蘭東印度公司(the Dutch East India Company)是在怎樣的歷史背景下成立?如何 在臺灣運作?(25 分)
#141795
四、第二次世界大戰結束,全世界進入冷戰時期。請問:各國之間分成那兩個陣營?當 時德國柏林扮演怎樣的地位?朝鮮半島又怎樣引起了國際間的緊張關係?(25 分)
#141796
⑵由 a 點出發,做 breadth-first traversal(寬度優先拜訪),請問那些節點(node) 不會被訪問到?(2 分)
#141798
【已刪除】 ⑶假設圖 1 代表 heap 上各個節點(node)及其相互指向的關係。p、q、r 三節點代 表全域變數(global variables),其他的節點代表 heap 上的記憶體區塊。如果 p→a 的指標被消除,那些節點會變成無用的垃圾節點?你必須詳細描述尋找垃圾 節點的方法及所需之資料結構。你的演算法只能從 a 節點出發,它必須指出所有 的垃圾節點,並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演 算法必須在每一個節點儲存那些資料?(15 分)
#141799
⑴請問 F(11) =?(5 分)
#141800
⑵請證明對於任何正整數 w,我們都可以在有限時間內計算 F(w)。(提示:每個奇 數可以寫成(2i + 1)2k – 1 的形式,再採用數學歸納法來證明。)(15 分)
#141801
【已刪除】三、Knuth,Morris 及 Pratt 發明了一個快速的字串比對方法(string pattern matching)。 他們的方法採用一個失敗函數(failure function)。失敗函數其實就是一個輔助的資 料結構,用來加速比對。請依他們的方法計算下列字串的失敗函數。你必須說明失 敗函數的定義為何,以及失敗函數如何加速比對。(15 分)
#141802
【已刪除】四、請參考圖 2。每一條線段上的數字代表兩節點間的距離。請找出 a 節點到 k 節點的 最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。(15 分)
#141803