資料結構第一章評量解答

※為節省時間，此解答過程不包含題目，請自行參考課本題目。


1.略

2.程式＝資料結構＋演算法

3.需求、設計、分析、撰寫程式碼、驗證

4.錯。


5.(1)模組化是將工作依據相依性、功能性切割成許多的小工作，而這些小工作可以分開獨立設計。一個小工作就是一個模組。
(2)由上而下的程式設計方法是在面對問題時將大問題分成許多小問題，然後再不斷的細分成更小的問題，一直到各小問題可以獨立存在，然後開始開始撰寫小問題程式，最後再將完成的個別小問題程式組合起來。
(3)模組化是運用由上而下的程式設計方法而形成的一種撰寫程式的方式，由上而下程式設計方法就是模組化最核心的精神。

6.「抽象資料型態」是使用資料抽象化的方法來建立自訂資料型態，不同於由上而下程式設計方法專注於模組分解，抽象資料型態是將資料和操作一起思考，以便建立完善的自訂資料型態。

7. 「.h」、「.c」

8.參考此篇：http://32989010dsweb.blogspot.com/2010/03/blog-post.html

9.略

10.略

11.時間複雜度是取頻率計數函數最高次項目而得，並且不計常數部份。

12.(1)頻率計數：(n＋1)＋(n＋1)²＋(n＋1)³＋(n＋1)³，時間複雜度O(n³)
(2)頻率計數：1＋(n＋1)＋2n，時間複雜度O(n)
(3)頻率計數：1＋(n＋1)＋1＋3n，時間複雜度O(n)
(4)頻率計數：1＋n＋2n＋1，時間複雜度O(n)

13.O(log n)＞O(n)＞O(n²)＞O(2n)

14.略

15.略

16.(B)，應為O(n¹⁰⁰＋2ⁿ)

17.略

18.略