Trắc Nghiệm Cấu Trúc Dữ Liệu Và Giải Thuật - Bài 05
1-
Trong giải thuật, Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và N0 sao cho :
A -
T(n) ≤ Cf(n) với mọi n ≥ N0
B -
T(n) ≥ Cf(n) với mọi n ≥ N0
C -
T(n) ≤ Cf(n) với mọi n ≤ N0
D -
T(n) ≥ Cf(n) với mọi n ≥ N0
2-
Trong tỷ suất tăng, ta có thể chứng minh được rằng:
A -
"Cho một hàm không âm T(n) bất kỳ, ta luôn tìm được tỷ suất tăng f(n) của nó"
B -
"Cho một hàm không dương T(n) bất kỳ, ta luôn tìm được tỷ suất tăng f(n) của nó"
C -
"Cho một hàm T(n) bất kỳ, ta luôn tìm được tỷ suất tăng f(n) của nó"
D -
Tất cả đều đúng
3-
Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2, Ðặt N0 = 1 và C = 4 thì với mọi n ≥1 chúng ta dễ dàng chứng minh được rằng:
A -
T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2
B -
T(n) = (n+1)2 ≥ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2
C -
T(n) = (n+1)2 = 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2
D -
Không thể chứng minh T(n) = (n+1)2
4-
Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho N0 = 0 và C = 5 ta dễ dàng chứng minh rằng :
A -
Với mọi n = 0 thì 3n3 + 2n2 ≤ 5n3
B -
Với mọi n ≤ 0 thì 3n3 + 2n2 ≤ 5n3
C -
Với mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3
D -
Với mọi n = 0 thì 3n3 + 2n2 ≥ 5n3
5-
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3 ) . Giải thuật nào sẽ thực hiện nhanh hơn?
A -
Câu trả lời phụ thuộc vào kích thước dữ liệu vào
B -
Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)
C -
Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)
D -
Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)
6-
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3 ) . Với n < 20 , giải thuật nào sẽ thực hiện nhanh hơn?
A -
Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)
B -
Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)
C -
Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)
D -
Câu trả lời phụ thuộc vào kích thước dữ liệu vào
7-
Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3 ) . Với n > 20 , giải thuật nào sẽ thực hiện nhanh hơn?
A -
Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)
B -
Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)
C -
Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)
