Font size
WorksheetsTOÁN RỜI RẠC - BÀI 3
Total questions: 30
Worksheet time: 20mins
Độ phức tạp không gian của thuật toán phản ánh điều gì?
Thời gian chạy thực tế của chương trình
Số lượng bước thực hiện của thuật toán
Số lượng biến sử dụng
Lượng ô nhớ cần thiết để thực hiện thuật toán
O(1)
O(n)
O(log n)
O(n2)
O(n)
O(n log n)
O(n3)
O(n2)
O(n3)
O(n log n)
O(n)
O(n2)
O(nlog n)
O(n2)
O(2n)
O(n)
Hãy chọn định nghĩa đúng nhất về chương trình con đệ quy?
Chương trình con được gọi là đệ quy nếu nó có tính hữu hạn
Một chương trình con được gọi là đệ quy nếu trong chương trình đó có lời gọi tới chính nó
Chương trình con đệ quy là chương trình tuần tự
Chương trình con được gọi là đệ quy nếu trong chương trình đó có độ phức tạp thời gian là đa thức đối với dữ liệu đầu vào
Trong các định nghĩa về giai thừa của một số tự nhiên n, định nghĩa nào là định nghĩa đệ quy?
n! = n
n! = 12...(n-1)n
n! = n(n-1)(n-2)*...1
n! = n(n-1)!, 0! = 1
Hãy cho biết f(4)?
(a)
return f
if (n<2) f=1
Tất cả các ý
f=f(n-1)+f(n-2)
return f
f=f(n-1)+f(n-2)
if (n<2) f=1
Tất cả các ý
Kết quả khi chạy chương trình này là:
(a)
5
8
6
16
5
13
8
21
1011
1001
1111
1101
6
120
24
12
Kết quả chạy chương trình này là: 1500
ĐÚNG
SAI
Kết quả chạy chương trình này là: 2000
ĐÚNG
SAI
Kết quả chạy chương trình này là: 15000
ĐÚNG
SAI
Kết quả chạy chương trình này là: 15
ĐÚNG
SAI
25
5
10
15
3
2
1
4
4
1
3
6
15
9
6
10
Yếu tố nào sau đây không ảnh hưởng tới thời gian thực hiện thuật toán?
Màn hình máy tính
Ngôn ngữ lập trình
Bộ vi xử lý thực hiện chương trình cài đặt của thuật toán
Kích thước dữ liệu
Cho chương trình P gồm 2 đoạn chương trình tuần tự P1 và P2 lần lượt có độ phức tạp thuật toán là T1(n)=O(n log n) và T2(n)=O(n2). Hãy cho biết độ phức tạp thuật toán ứng với P?
O(n3 / log n)
O(n3 log n)
O(n2)
O(n log n)
Sơ đồ khối (flowchart) thường được sử dụng để làm gì trong biểu diễn thuật toán?
Mô tả các bước thực hiện của thuật toán
Mô tả các biến và hàm trong thuật toán
Viết mã nguồn của thuật toán
Xác định độ phức tạp của thuật toán
Phương pháp biểu diễn thuật toán nào sau đây giúp lập trình viên dễ dàng chuyển đổi sang mã nguồn thuận lợi nhất?
Pseudocode (mã giả)
Biểu đồ khối (flowchart)
Biểu đồ tuần tự (sequence diagram)
Biểu đồ hoạt động (activity diagram)
Độ phức tạp thời gian của thuật toán thường được biểu diễn bằng:
Thời gian chạy thực tế của chương trình
Số lượng dòng mã trong chương trình
Số lượng các phép tính cơ bản của thuật toán
Số lượng biến sử dụng
Cho chương trình đệ quy sau:
#include <stdio.h>
int towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
return 1;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}
int main() {
int result = towerOfHanoi(3, 'A', 'C', 'B');
printf("%d\n", result);
return 0;
}
Kết quả sau khi chạy chương trình này biến result có giá trị là:
(a)
Cho chương trình P gồm 2 đoạn chương trình P1, P2. Trong đó P1 có độ phức tạp thuật toán là T1(n) = 3n log n và P2 thực hiện n lần P1. Hãy cho biết độ phức tạp thuật toán ứng với P?
O(n log n)
O(3n log n + 2n)
O(n2)
O(n2log n)
Đặc trưng nào sau đây không phải đặc trưng của thuật toán?
Tính không xác định
Tính hiệu quả
Tính hữu hạn
Tính đúng đắn
Phương pháp nào sau đây không phải là một phương pháp biểu diễn thuật toán?
Pseudocode (mã giả)
Biểu đồ khối (flowchart)
Biểu đồ lớp (class diagram)
Lưu đồ (diagram)
O(n)
O(n3)
O(n logn)
O(n2)
