首頁 > 線上測驗 > 公職考試>高考/三等>資訊處理 > 99年公務人員高等考試三級 資料結構
關於字串樣式比對(string pattern matching),最簡單的方法是使用窮舉 樣式比對法(exhaustive pattern matching),此即將樣式(pattern)的字 元逐一比較本文(text)的字元,若不對則移下一字元繼續比對,直到比 對成功或本文剩下的字元數目少於樣式長度。 (1) 假設本文是:THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS _SPEED,欲找尋的樣式(pattern)為GENTLE,問: 總共比較多少次? 一共比較多少個字元? (2) 假設本文是一千個"0",欲找尋的樣式(pattern)為01010,請問: 總共比較多少次? 一共比較多少個字元?
一個有向圖形(directed graph),若圖形的任何路徑(path)沒有環路 (cycle),則此圖形可找到拓樸排序(topological sorting),問: (1) 說明什麼是拓樸排序? (2) 舉出一種拓樸排序的應用。 (3) 於下圖中找出一種拓樸排序,要寫出產生的過程,最後畫出拓樸排序 圖。
假設有一個陣列A[0..12],儲存13 個數字:4,14,25,31,37,42,56, 70,73,83,86,90,94。今使用二元搜尋(binary search),問: (1) 寫出找尋70 的比較過程(沒寫過程不予計分)。 (2) 列出比較次數最多的所有數字。 (3) 假設現有100,000 個數字已經依由小而大的次序排列好,請分別使用 二元搜尋(binary search)與循序搜尋(sequential search),計算兩者 成功找尋(successful search)的平均比較次數,並說明兩者大概相差 多少倍?
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)