Font size
WorksheetsPTTT 3
Total questions: 72
Worksheet time: 36mins
Một thuật toán được gọi là đệ quy nếu
A. nó giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn một nửa
B. nó giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn
C. nó giải quyết bài toán bằng cách dùng bài toán ban đầu nhưng có dữ liệu đầu vào nhỏ hơn một nửa
D. nó giải quyết bài toán bằng cách dùng bài toán ban đầu nhưng có dữ liệu đầu vào nhỏ hơn
Một khái niệm X gọi là định nghĩa theo đệ quy nếu
trong định nghĩa X không sử dụng khái niệm X
trong định nghĩa X có sử dụng 2 lần khái niệm X
trong định nghĩa X có sử dụng 2 lần trở lên khái niệm X
trong định nghĩa X có sử dụng ngay chính khái niệm X
Phần cơ sở của thuật toán đệ qui bao gồm
các trường hợp dừng mà có thể trực tiếp giải quyết được ngay
các trường hợp chưa dừng nhưng có thể trực tiếp giải quyết được
các trường hợp dừng nhưng chưa thể trực tiếp giải quyết được
các trường hợp chưa dừng lại mà có thể giải quyết trong trường hợp đặc biệt
Một chương trình con P (hàm hoặc thủ tục) được gọi là đệ quy nếu
trong quá trình thực hiện P phải gọi đến P hai lần
trong quá trình thực hiện P phải gọi đến P hai lần trở lên
trong quá trình thực hiện P không cần phải gọi đến P
trong quá trình thực hiện P có phần phải gọi đến chính P
Cấu trúc chính của một chương trình con đệ quy gồm
Phần không cơ sở và phần đệ quy
Phần cơ sở và phần đệ quy
Phần cơ sở và phần không có đệ quy
Phần không cơ sở và phần không đệ quy
Dạng tổng quát của một phương trình đệ qui có dạng: T(n) C(n) F(T(k)) + d(n)
( chọn 2 đáp án)
1.C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui đúng 2.F(T(k)) là một đa thức của các T(k) 3.d(n): là thời gian để tổng hợp các kết quả
1.C(n): là thời gian thực hiện chương trình 2.F(T(k)) là một đa thức của các T(k) 3.d(n): là thời gian để phân chia bài toán
1.C(n): là thời gian thực hiện chương trình 2.F(T(k)) là một đa thức của các T(k) 3.d(n): là thời gian để tổng hợp các kết quả
1.C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui dừng
2.F(T(k)) là một đa thức của các T(k)
3.d(n): là thời gian để phân chia bài toán và tổng hợp các kết quả
Đặc điểm của chương trình con đệ qui
1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán được thu nhỏ đi một nửa 3. Có một trường hợp đặc biệt, là trường hợp dừng của thuật toán và gọi đệ qui cũng kết thúc
1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước 3. Có một trường hợp đặc biệt, là trường hợp dừng của thuật toán và gọi đệ qui cũng kết thúc
1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước 3. Có một trường hợp đặc biệt và gọi đệ qui được tiếp tục
1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán được thu nhỏ đi một nửa 3. Có một trường hợp đặc biệt và gọi đệ qui được tiếp tục
(Trắc nghiệm về công thức C(n), F(T(k)), d(n))
C(n): là thời gian thực hiện chương trình; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để phân chia bài toán
C(n): là thời gian thực hiện chương trình; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để tổng hợp các kết quả
C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui dừng; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để tổng hợp các kết quả
C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui dừng; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để phân chia bài toán và tổng hợp các kết quả
Hàm đệ quy dưới đây tính: int facto(int n) { if (n == 0) return 1; else return n * facto(n-1); }
Tổng các số từ 1 đến n
Trung bình cộng của các số từ 1 đến n
Giai thừa của n
Bình phương của n
Cho Hàm đệ quy int fibo(int n) { if (n <= 2) return 1; else return fibo(n-1) + fibo(n-2); } giá trị của fibo(5) được tính bằng:
3
5
8
13
Cho Hàm đệ quy int US(int a, int b) { if (b == 0) return a; else return US(b, a % b); } giá trị của US(28,20) được tính bằng:
2
4
6
8
Cho Hàm đệ quy int power(int n) { if (n == 0) return 1; else return 2*power(n-1); } giá trị của power (3) được tính bằng:
6
8
12
16
Cho hàm đệ qui int sum(int n) { if (n == 0) return 0; else return n * n + sum(n - 1); } gọi hàm sum(3) trả về giá trị:
A. 14
B. 20
C. 30
D. 16
Giá trị của power(2, 3) với đoạn chương trình sau, được tính bằng: int power(int base, int exp) { if (exp == 0) return 1; else return base * power(base, exp-1); }
A. 8
B. 6
C. 4
D. 2
Giá trị của sum(4) với đoạn mã dưới đây được tính bằng
A. 4
B. 6
C. 10
D. 16
Hàm đệ quy dưới đây tính gì? int sum(int n) { if (n == 0) return 0; else return n + sum(n - 1); }
Tổng các số từ 1 đến n
Tổng các số từ 1 đến n - 1
Tích các số từ 1 đến n
Lũy thừa của n
Hàm đệ quy dưới đây thực hiện chức năng gì
int US(int a, int b) {
if (b == 0) return a;
else return US(b, a % b);
}
Tính tổng của a và b
Tính hiệu của a và b
Tìm ước chung lớn nhất của a và b
Tìm bội chung nhỏ nhất của a và b
Hàm đệ quy sau thực hiện chức năng gì? int countt(int n) { if (n <= 0) return 0; else { printf("%d ", n); return countt(n - 1); }}
Đếm số lượng các số từ n đến 1 và in ra
In tất cả các số từ n, n-1, ... đến 1
Tính tổng các số từ 1 đến n
Tính giai thừa của số nguyên n
Hàm đệ quy sau thực hiện chức năng gì?
int sum(int n) {
if (n <= 0) return 0;
else
if (n % 2 = = 0) return n + sum(n - 2);
else return sum(n - 1);
}
Tính tổng các số chẵn từ 1 đến n
Tính tổng các số lẻ từ 1 đến n
Tính tổng tất cả các số từ 1 đến n
Tính tổng các số nguyên tố từ 1 đến n
Độ phức tạp của thuật toán đệ qui tính số hạng thứ n của dãy Fibonacci :
int fibo(int n)
{ if (n <= 2)
return 1;
return fibo(n-1)+ fibo(n-2);
}
có kết quả bằng
O(n²)
O(2ⁿ)
O(n)
O(n!)
Độ phức tạp của thuật toán đệ qui thực hiện sắp xếp các phần tử của một dãy có n phần tử theo chiều tăng dần bằng phương pháp Quicksort:
Quicksort (int a[], int L, int R) trong trường hợp tốt nhất
{ k=Partion(a, L, R);
Quicksort (a, L, k-1);
Quicksort (a,k,R);
}
O(n)
O(nlogn)
O(n²)
O(2ⁿ)
Độ phức tạp của thuật toán đệ qui thực hiện tìm kiếm giá trị x trong dãy có n phần tử theo phương pháp nhị phân:
int bsearch(int a[], int L, int R, int x)
{ if (L>R)
return -1;
int k=(L+R)/2;
if x= = a[k] return k;
if x>a[k]
return bsearch(a, k+1, R, x);
return bsearch(a, L, k-1, x);
}
có kết quả bằng
O(n)
O(logn)
O(n2)
O(1)
Thuật toán có phương trình đệ quy sau, (T(1)=1)
T(n) = T(5n/9) + 1
được giải theo định lý Master có nghiệm là
O(n)
O(logn)
O(nlogn)
O(n²)
Thuật toán có phương trình đệ quy sau, (T(1)=1)
T(n) = 2T(n/2) + n
được giải theo định lý Master có nghiệm là:
O(n)
O(logn)
O(nlogn)
O(n²)
Thuật toán có phương trình đệ quy sau, (T(1)=1)
T(n)=3T(n/3)+n
được giải theo định lý Master có nghiệm là:
O(n)
O(logn)
O(nlogn)
O(n²)
Thuật toán có phương trình đệ quy sau, (T(1)=1)
T(n)=4T(n/2)+n²
được giải theo định lý Master có nghiệm là:
O(n)
O(n²logn)
O(nlogn)
O(n²)
Thuật toán có phương trình đệ quy sau, (T(1) = 1)
T(n) = 8T(n / 2) + n
được giải theo định lý Master có nghiệm là:
O(n)
O(n²logn)
O(n³)
O(n²)
Thuật toán có phương trình đệ quy sau, (T(1)=1)
T(n) = 16T(n/4) + n
được giải theo định lý Master có nghiệm là:
O(logn)
O(n²)
O(nlogn)
O(n)
Với phương trình đệ quy T(n)=2T(n/2)+n²
Hãy xác định bộ giá trị của (a, b, k) và nghiệm tính được theo định lý Master
(1, 2, 2); O(n)
(2, 1, 2); O(n²)
(2, 2, 2); O(n²)
(2, 2, 2); O(nlogn)
Với phương trình đệ quy T(n) =8T(n/2)+n³
Hãy xác định bộ giá trị của (a, b, k) và nghiệm tính được theo định lý Master
(8, 2, 3); O(n³logn)
(8, 1, 3); O(logn³)
(8, 2, 3); O(nlogn²)
(8, 1, 3); O(n³)
Chọn 2 phương án đúng liên quan đến ứng dụng đệ quy:
Tính tổng các phần tử mảng không thể dùng đệ quy
Trong thuật toán đệ quy, bài toán được thu nhỏ qua mỗi lần gọi
Bài toán đệ quy không cần điều kiện kiểm soát
Tính UCLN(a, b) là ví dụ đệ quy sử dụng phép chia dư
Chọn 2 phương án đúng liên quan đến ưu, nhược điểm của đệ quy:
Đệ quy chỉ dùng được khi dữ liệu là số nguyên
Một số bài toán đòi hỏi bắt buộc phải dùng đệ quy
Đệ quy là cách viết khó hơn và ít ứng dụng hơn vòng lặp
Đệ quy giúp biểu diễn bài toán ngắn gọn hơn
Chọn 2 phương án đúng liên quan đến phần cơ sở trong đệ quy:
Nếu không có phần cơ sở, chương trình sẽ lặp vô hạn
Một chương trình đệ quy phải có phần cơ sở để kết thúc đệ quy
Hàm đệ quy không thể dùng trong Pascal
Phần cơ sở có thể được bỏ qua nếu bài toán nhỏ
Chọn 2 phương án đúng nói về việc lập và sử dụng phương trình đệ quy:
Để tính độ phức tạp thuật toán đệ quy, cần lập phương trình đệ quy
T(n) = T(n) + 1 là phương trình đúng
T(n) = T(n - 1) - C là công thức phổ biến
T(n) = T(n-1) + C có độ phức tạp O(n)
Chọn 2 phương án đúng mô tả về phần thân và lời gọi đệ quy:
A. Trong ví dụ tính n giai thừa, điều kiện if (n == 0) không phải là phần cơ sở
B. Trong ví dụ tính n giai thừa, phần đệ quy là return n * gt(n-1)
C. Một hàm đệ quy có thể không gọi lại chính nó
D. Phần đệ quy là phần gọi lại chính hàm đó
Chọn 2 phương án đúng liên quan đến hàm đệ quy uscin(a, b):
Hàm uscin(a, b) có phần cơ sở là khi b == 0
Phép gọi uscin (b, a % b) là phần đệ quy
Đệ quy không được sử dụng trong các phép chia
Hàm uscin(a, b) sẽ chạy vô hạn nếu b luôn khác 0
Chọn 2 phương án đúng nói về việc sử dụng đệ quy trong bài toán Fibonacci
A. Hàm tính Fibonacci có hai lời gọi đệ quy
B. Fibonacci không thể tính bằng vòng lặp
C. Tính fibo(5) chỉ gọi một lần đệ quy
D. Dãy Fibonacci là ví dụ kinh điển của thuật toán đệ quy
Chọn 2 phương án đúng phát biểu đến khả năng hỗ trợ đệ quy trong các ngôn ngữ lập trình:
Đệ quy không thể dùng trong bài toán tính tổng
Đệ quy có thể thay thế vòng lặp trong một số trường hợp
Tất cả các ngôn ngữ lập trình đều hỗ trợ đệ quy
C và Pascal đều hỗ trợ hàm đệ quy
Chọn 2 phương án đúng nói về đặc điểm và ví dụ của đệ quy:
A. Tháp Hà Nội là bài toán điển hình dùng đệ quy
B. Trường hợp suy biến là điều kiện kết thúc đệ quy
C. Trong đệ quy, không nên gọi chính hàm hiện tại
D. Hàm giai thừa không thể viết bằng đệ quy
Với bài toán "Tháp Hà Nội", để chuyển n đĩa từ cọc A sang cọc B (cọc trung gian C) cần:
Chuyển n-1 đĩa từ A sang C
Lặp lại thao tác 64 lần
Chuyển n-1 đĩa từ C sang B
Chuyển 2 đĩa từ C sang B
Ví dụ nào sau đây là để quy đúng trong lập trình?
Một hàm gọi hàm khác
Một hàm gọi chính nó mà không thay đổi tham số
Một hàm gọi chính nó với tham số giảm dần
Một hàm dùng vòng lặp for
Một chương trình con đệ quy bắt buộc phải có:
A. Lời gọi đến chính nó
B. Phần cơ sở và phần đệ quy
C. Tham số đầu vào là số nguyên
D. Vòng lặp while
Phương trình đệ quy nào dưới đây có thể được phân tích bằng định lý Master?
(Chọn 2 đáp án)
A. T(n) = T(n - 1) + n
B. T(n) = 2T(n - 1) + 1
C. T(n) = 4T(n / 3) + n²
D. T(n) = 3T(n / 2) + n
Các phần bắt buộc để xây dựng một chương trình con đệ quy là gì?
(Chọn 2 đáp án)
Câu lệnh gán
Sử dụng vòng lặp
Lời gọi đệ quy
Điều kiện dừng
Thuật toán A với kích thước dữ liệu đầu vào n gọi là có độ phức tạp đa thức nếu
O(f(n)) với f(n) là hàm đa thức của n
O(f(n)) với f(n) là hàm mũ của n
O(f(n)) với f(n) là hàm logarit của n
O(f(n)) với f(n) là hàm không xác định
Thuật toán A với kích thước dữ liệu đầu vào n gọi là có độ phức tạp đa thức nếu
tồn tại đa thức P(n) mà TA ∀ 0, với C và N0 là các hằng số
tồn tại đa thức P(n) mà TA ∀ 0, với N0 là hằng số
tồn tại đa thức P(n) mà TA ∀ 0, với C và N0 là các hằng số
tồn tại đa thức P(n) mà TA ∀ 0, với C và N0 là các hằng số
Thuật toán đơn định là
Thuật toán mà tại mỗi bước, chỉ có một lựa chọn duy nhất
Thuật toán mà tại mỗi bước, có nhiều lựa chọn
Thuật toán chạy không xác định thời gian
Thuật toán không cần dữ liệu đầu vào
Thuật toán được gọi là đa thức nếu
độ phức tạp về thời gian trong trường hợp tốt nhất của nó là đa thức
độ phức tạp về không gian trong trường xấu nhất của nó là đa thức
độ phức tạp về thời gian trong trường hợp xấu nhất của nó là đa thức
độ phức tạp về không gian trong trường trung bình của nó là đa thức
Thuật toán đơn định đa thức là
thuật toán đơn định có độ phức tạp trong trường hợp tốt nhất là đa thức
thuật toán đơn định có độ phức tạp trong trường hợp trung bình là đa thức
thuật toán đơn định có độ phức tạp là đa thức
thuật toán đơn định có độ phức tạp là trên đa thức (hàm mũ)
Thuật toán không đơn định là
thuật toán mà tại mỗi bước, có một lựa chọn duy nhất
thuật toán mà tại mỗi bước, có nhiều lựa chọn có thể thực hiện thay vì một lựa chọn duy nhất
thuật toán luôn cho kết quả chính xác
thuật toán không có dữ liệu đầu vào
Thuật toán không đơn định có thể:
Chỉ thử một lựa chọn tại mỗi bước
Thử nhiều lựa chọn tại mỗi bước
Chạy mãi mãi mà không kết thúc
Luôn luôn cho kết quả đúng
Một bài toán thuộc lớp P nếu:
Nó có thể được giải quyết trong thời gian đa thức bằng một thuật toán không đơn định
Nó có thể được giải quyết trong thời gian đa thức bằng một thuật toán đơn định
Nó không được giải quyết trong thời gian đa thức
Nó không được giải quyết bằng thuật toán nào cả
Lớp P bao gồm những bài toán:
Không thể giải quyết được
Có thể giải được bằng thuật toán không đơn định trong thời gian hàm mũ
Có thể giải được bằng thuật toán đơn định trong thời gian hàm mũ
Có thể giải được bằng thuật toán đơn định trong thời gian đa thức
NP là lớp các bài toán
mà mọi nghiệm giả định đều không được kiểm chứng trong thời gian đa thức
mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian hàm n giai thừa
mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian hàm mũ
mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian đa thức
Lớp NP bao gồm những bài toán:
Chưa tìm được thuật toán với độ phức tạp đa thức nhưng chỉ ra được phương pháp kiểm định nghiệm của nó (nếu có) với thời gian đa thức
Chưa tìm được thuật toán với độ phức tạp đa thức nhưng chỉ ra được phương pháp kiểm định nghiệm của nó (nếu có) với thời gian hàm mũ
Chưa tìm được thuật toán đơn định với độ phức tạp hàm mũ
Chưa tìm được thuật toán không đơn định với độ phức tạp hàm mũ
Kiểm định nghiệm trong thời gian đa thức có nghĩa là:
Giải quyết bài toán trong thời gian đa thức
Tìm kiếm nghiệm đúng trong thời gian đa thức
Tìm kiếm nghiệm gần đúng trong thời gian đa thức
Kiểm tra một nghiệm có đúng hay không trong thời gian đa thức
Một thuật toán tìm số ước của một số nguyên dương N 1.Nhập N
2. dem=0;
3. for (i=1; i<=N; ++i)
4. if (N%i = =0)
5. dem=dem+1;
6. Xuất dem
được đánh giá là:
Thuật toán đơn định, đa thức
Thuật toán đơn định, hàm mũ
Thuật toán không đơn định, đa thức
Thuật toán không đơn định, hàm mũ
Một thuật toán tính tổng của các số chẵn từ 1 đến N (N là số nguyên dương)
1.Nhập N
2. S=0;
3. for (i=1; i<=N; ++i)
4. if (i%2 ==0)
5. S=S+i;
6. Xuất S
Được đánh giá là :
A. Thuật toán đơn định, đa thức
B. Thuật toán đơn định, hàm mũ
C. Thuật toán không đơn định, đa thức
D. Thuật toán không đơn định, hàm mũ
đáp
A. Thuật toán đơn định, đa thức
B. Thuật toán đơn định, hàm mũ
C. Thuật toán không đơn định, đa thức
D. Thuật toán không đơn định, hàm mũ
đáp án
Thuật toán đơn định, đa thức
Thuật toán đơn định, hàm mũ
Thuật toán không đơn định, đa thức
Thuật toán không đơn định, hàm mũ
Nếu một bài toán thuộc lớp NP nhưng không thuộc lớp P thì:
Lời giải của nó có được kiểm định trong thời gian đa thức nhưng không thể tìm được trong thời gian đa thức
Lời giải của nó có thể tìm thấy trong thời gian đa thức
Lời giải của nó không thể được kiểm định trong thời gian đa thức
Lời giải của nó không tồn tại
Nếu một bài toán có thể được giải quyết trong thời gian đa thức bằng một thuật toán không đơn định, nhưng không thể giải quyết bằng thuật toán đơn định, điều đó có nghĩa là:
Bài toán đó thuộc lớp P
Bài toán đó thuộc lớp NP nhưng không thuộc lớp P
Bài toán đó không thuộc lớp NP
Bài toán đó không thể giải quyết được
Nếu thuật toán tựa ALGOL là đa thức và trong thuật toán chỉ có các phép toán cơ bản, dữ liệu vào có độ phức tạp đa thức theo quan niệm 2 (độ dài mã) thì thuật toán trên máy Turing tương ứng là:
Hằng số
Đa thức
Hàm mũ
Hàm giai thừa
Thuật toán nào sau đây có khả năng giải quyết bài toán NP trong thời gian đa thức?
thuật toán đơn định
Thuật toán không đơn định
Thuật toán heuristic
Không có lựa chọn nào đúng
Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL là đa thức thì:
Thuật toán tương ứng trên máy Turing là không đơn định
Thuật toán tương ứng trên máy Turing là đơn định
Thuật toán tương ứng trên máy Turing chưa chắc là đa thức
Thuật toán tương ứng trên máy Turing là đa thức
Thuật toán trên máy Turing là đa thức thì:
Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng không là đa thức
Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng chưa chắc là đa thức
Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng là đa thức
Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng chưa chắc là trên đa thức
Bài toán “tìm chu trình Euler trong một đồ thị”, có thuộc lớp P?
Chỉ khi đồ thị có số cạnh nhỏ
Chỉ khi sử dụng thuật toán không đơn định
có
không
Bài toán “tìm kiếm tuần tự giá trị k trong một dãy n số nguyên x1, x2, …,xn “, có thuộc lớp P?
có
không
Chỉ khi danh sách rất nhỏ
Chỉ khi sử dụng thuật toán không đơn định
Bài toán “sắp xếp dãy n số nguyên x1, x2, …,xn theo chiều tăng dần” bằng thuật toán QuickSort có thuộc lớp P?
có
không
Chỉ khi danh sách rất nhỏ
Chỉ khi sử dụng thuật toán không đơn định
Bài toán “xác định số nguyên tố”, có thể được giải quyết trong thời gian đa thức bởi thuật toán đơn định không?
có
không
Chỉ khi số nguyên tố rất nhỏ
Chỉ khi sử dụng thuật toán không đơn định
Bài toán “xác định một số nguyên dương N có phải là số nguyên tố hay không” Có thuộc lớp P ?
có
không
Chỉ khi số rất nhỏ
Chỉ khi sử dụng thuật toán không đơn định
Bài toán “tính một số hạng trong dãy Fibonacci” bằng cách không sử dụng thuật toán đệ quy, có thuộc lớp P?
có
không
Chỉ khi số hạng là một số nguyên nhỏ
Chỉ khi sử dụng thuật toán không đơn định
