Trắc Nghiệm Cấu Trúc Dữ Liệu Và Giải Thuật - Bài 07
1-
Dạng tổng quát của một phương trình đệ quy sẽ là:
A -
B -
C -
D -
2-
Phương pháp để giải phương trình đệ quy là:
A -
Phương pháp truy hồi
B -
Phương pháp đoán nghiệm
C -
Lời giải tổng quát của một lớp các phương trình đệ quy
D -
Tất cả đều đúng
3-
Phương pháp truy hồi là:
A -
Dùng đệ quy để thay thế bất kỳ T(m) với m < n vào phía phải của phương trình cho đến khi tất cả T(m) với m > 1 được thay thế bởi biểu thức của các T(1) hoặc T(0).
B -
Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n) ≤ f(n) với mọi n.
C -
Lấy một đơn vị thời gian và thời gian để chia bài toán kích thước n thành các bài toán con kích thước
D -
Tất cả đều sai
4-
Phương pháp đoán nghiệm là:
A -
Dùng đệ quy để thay thế bất kỳ T(m) với m < n vào phía phải của phương trình cho đến khi tất cả T(m) với m > 1 được thay thế bởi biểu thức của các T(1) hoặc T(0).
B -
Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n) ≤ f(n) với mọi n.
C -
Lấy một đơn vị thời gian và thời gian để chia bài toán kích thước n thành các bài toán con kích thước
D -
Tất cả đều sai
5-
Giải phương trình :
A -
T(n) = T(0) + nC2 = C1 + n C2 = O(n)
B -
T(n) = T(0) - nC2 = C1 - n C2 = O(n)
C -
T(n) = T(0) + nC2 = C1 + n C2 = O(n)
D -
T(n) = T(0) - nC2 = C1 - n C2 = O(n)
6-
Giải phương trình :
A -
T(n) = nT(0) - lognC2 n = C1 n - C2 nlogn = O(nlogn).
B -
T(n) = nT(0) + lognC2 n = C1 n + C2 nlogn = O(nlogn).
C -
T(n) = nT(0) + lognC2 n = C1 n + C2 nlogn = O(nlogn).
D -
T(n) = nT(1) + lognC2 n = C1 n + C2 nlogn = O(nlogn).
7-
Giải phương trình đệ quy :
A -
T(n) ≤ (C1 + C 2)nlogn +C1 Với mọi n
B -
T(n) ≤ (C1 - C 2)nlogn + C1 Với mọi n
C -
T(n) ≤ (C1 - C 2)nlogn - C1 Với mọi n
D -
Tất cả đều sai
8-
Trong phương trình đệ quy (I.1) hàm thời gian d(n) được gọi là:
được gọi là: