阿摩線上測驗 登入

99年 - 099年高等三級資料結構#46742

科目：公職◆資料結構 | 年份：99年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (14)

⑴請分別寫出下列程式第一行（line 1）到第五行（line 5）的執行次數（frequency count），於試卷上請標明是第幾行，次數是多少。（10 分） 
⑵於下列程式，請計算指令 x++；一共會執行多少次？（5 分）
⑶請根據下列表格的數據，size是問題量（或問題大小），count是程式指令的總執 行次數，來推測程式執行的時間複雜度（time complexity），請以Big-Theta Θ 表 示之（例如：Θ(3n)）。（5 分） 
⑴假設本文是：THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED， 欲找尋的樣式（pattern）為 GENTLE，問： 1.總共比較多少次？（5 分） 2.一共比較多少個字元？（5 分）
⑵假設本文是一千個 " 0"，欲找尋的樣式（pattern）為 01010，請問： 1.總共比較多少次？（5 分） 2.一共比較多少個字元？（5 分）
⑴說明樹（tree）與二元樹（binary tree）有那三項主要的不同？（5 分）
⑵已知某一樹其分支度（degree）為 1 的節點（node）有 5 個，分支度為 2 的節點 有 4 個，分支度為 3 的節點有 3 個，分支度為 4 的節點有 2 個，分支度為 5 的節 點有 1 個，請問此樹一共有幾個節點？（5 分）
⑶證明：於任意一個二元樹中，若n0代表分支度為 0 的節點數目，n1代表分支度為 1 的節點數目，n2代表分支度為 2 的節點數目，則n0 =n2+1。（10 分）
⑴說明什麼是拓樸排序？（5 分）
⑵舉出一種拓樸排序的應用。（3 分）
⑶於下圖中找出一種拓樸排序，要寫出產生的過程，最後畫出拓樸排序圖。（12 分）
⑴寫出找尋 70 的比較過程（沒寫過程不予計分）。（8 分）
⑵列出比較次數最多的所有數字。（6 分）
⑶假設現有 100,000 個數字已經依由小而大的次序排列好，請分別使用二元搜尋 （binary search）與循序搜尋（sequential search），計算兩者成功找尋（successful search）的平均比較次數，並說明兩者大概相差多少倍？（6 分）