資料結構
CHAPTER 1 導論
1. 請分別說明資料與資訊的意義及兩者之間的關係
Data → processing → Information
Data is raw and unprocessed facts.
Information is processed data that becomes meaningful and
useful.
2. 請説明程式，演算法和資料結構之間的關係
A program is made up of data structures (how data is stored) and
algorithms (how data is processed).
Program = Data Structure + Algorithm.
3. 何謂演算法？而在填選演算法應遵守哪些原則？
Algorithm is a step-by-step method to solve a problem.
It must follow 5 rules: Input, Definiteness, Finiteness,
Correctness, Output.
4. 請問一個好程式需要滿足哪些條件?
A good program must satisfy three conditions:
1️⃣ Correctness –gives the right result.
2️⃣ Efficiency – it runs fast and uses few resources.
3️⃣ Maintainable – it is easy to read and update later.
5. 何謂結構化程式設計？有哪三種結構?
Structured programming means writing programs step by step
using a clear, top-down modular design.
1️⃣ Sequence – execute instructions in order.
2️⃣ Selection – choose actions by conditions (if/else).
3️⃣ Repetition – repeat actions (loops).
6. 請計算下列程式中變數 SUM 被執行的次數。
a. sum = sum + 1 O(1)
b. for (i = 1; i <= n; i++)
sum = sum + 1; O(n)
c. for (i = 1; i <= n; i++)
for(j = 1; j <= n; i++)
sum = sum + 1; O(n²)
7. Big O
8. 利用時間複雜度 Big O 符號來表示
a. 2n + 3 O(n)
b. 2n² + 2n + 2 O(n²)
c. 2n³ + 4n² + 2n + 2 O(n³)
9. 最有效的選項：O(n)
10. 大小
O(n!) O(2ⁿ) O(n³) O(logn)
11. Flowchart
12. 請利用虛擬嗎填寫一個求兩個整數相減之絕對值的演算法
13.輸入數值並判別奇數或偶數的流程圖表示法
14.利用虛擬碼填寫一個尋找最大值的演算法
15.請繪出一下的流程圖
輸入平時成績，期中成績和期末成績
繪出平均成績和是否及格的判斷。欲知平均成績是否及格，則應對平均成績加以判斷是否大等於 60 分
16.
n(n+1)/2 O(n²)
17.
The loop stops when i ≤ 1 n/(2^k−1)≤1 O(log n)
18. O(n³)
19. 證明 f(n) = 4n + 10, 可用 O(n) 表示
1️⃣ By definition, f (n)=O(n)if there exist constants c >0and n 0> 0such that
f ( n ) ≤ c ⋅nfor all n ≥ n0.
2️⃣ Let f (n)=4 n+10.
3️⃣ Choose c=5 . Then 4 n+10 ≤5 n when n ≥ 10.
4️⃣ Thus, f ( n ) ≤ 5 nfor n ≥ 10.
✅ Therefore, f (n)=O(n).
20. 證明 f(n) = 2n^2 + 3n + 1 可用 O(n^2) 表示
We start from 2 n2 +3 n+1 ≤ c ⋅n2.
Simplify to 3 n+1 ≤(c−2) n2.
To make it true for all n ≥ 1, we need (c−2) n2bigger than 3 n+1.
So f (n)=2 n2 +3 n+1 ≤ 6 n2⇒ f (n)=O(n2).
If we pick c−2=4 → c=6, then 3 n+1 ≤ 4 n 2is always true.
[Link] sequential and binary search
Item Sequential Search Binary Search
Data Unsorted Sorted
Method Check one by one Divide by half each time
Best case O(1) O(1)
Worst case O(n) O(log n)
Speed Slower Faster
Use Small or unsorted data Large and sorted data