Trắc Nghiệm Tin Học 11 Cánh Diều Khoa Học Máy Tính Chủ đề FCS Bài 5: Đánh giá thuật toán là nội dung thuộc môn Tin học, được biên soạn dưới dạng đề ôn tập tham khảo dành cho học sinh lớp 11 theo chương trình sách giáo khoa Cánh Diều. Bộ đề tập trung vào các kiến thức quan trọng như tiêu chí đánh giá thuật toán, độ phức tạp thời gian – không gian, cách so sánh hai thuật toán và vận dụng vào các bài toán thực tiễn. Nội dung mở đầu có sử dụng định dạng trắc nghiệm Tin học 11 Khoa học máy tính Cánh Diều, được biên soạn năm 2024 bởi thầy Đỗ Minh Tài – giáo viên Tin học Trường THPT Trưng Vương (TP. Hồ Chí Minh). Tài liệu được đăng tải trên detracnghiem.edu.vn nhằm hỗ trợ học sinh ôn tập hiệu quả và hệ thống.
Trắc nghiệm môn Tin học 11 ở bài học này bao gồm các câu hỏi phân hoá từ nhận biết đến vận dụng cao, giúp học sinh hiểu rõ cách phân tích độ phức tạp, đánh giá tính hiệu quả của thuật toán và lựa chọn phương pháp giải quyết tối ưu cho từng bài toán. Khi luyện tập trên detracnghiem.edu.vn, học sinh có thể xem đáp án chi tiết, theo dõi sự tiến bộ và rèn luyện tư duy thuật toán một cách bài bản. Bộ đề là tài liệu quan trọng giúp học sinh chuẩn bị tốt cho các bài kiểm tra định kỳ và nâng cao năng lực lập trình Trắc nghiệm lớp 11.
Trắc Nghiệm Tin Học 11 Cánh Diều Khoa Học Máy Tính
Chủ đề FCS: Giải quyết vấn đề với sự trợ giúp của máy tính
Bài 5: Đánh giá thuật toán
Câu 1: Độ phức tạp thời gian của thuật toán là khái niệm dùng để đánh giá yếu tố nào sau đây của thuật toán?
A. Độ khó khi viết mã nguồn.
B. Dung lượng ổ cứng cần thiết.
C. Thời gian thực hiện thuật toán.
D. Số lượng dòng lệnh của chương trình.
Câu 2: Ký hiệu O lớn (Big-O) trong đánh giá thuật toán thường được dùng để biểu diễn điều gì?
A. Giới hạn trên của độ phức tạp.
B. Thời gian chạy chính xác từng giây.
C. Số lượng biến nhớ được sử dụng.
D. Giới hạn dưới của độ phức tạp.
Câu 3: Nếu thời gian thực hiện thuật toán không phụ thuộc vào kích thước dữ liệu đầu vào n, độ phức tạp thời gian là:
A. O(n)
B. O(n²)
C. O(1)
D. O(log n)
Câu 4: Cho đoạn chương trình sau:
for i in range(n): print(i)
Độ phức tạp thời gian của đoạn chương trình này là bao nhiêu?
A. O(1)
B. O(n)
C. O(n²)
D. O(log n)
Câu 5: Khi đánh giá thuật toán, ta thường quan tâm nhất đến trường hợp nào?
A. Trường hợp tốt nhất (Best case).
B. Trường hợp trung bình (Average case).
C. Trường hợp xấu nhất (Worst case).
D. Trường hợp dữ liệu bằng rỗng.
Câu 6: Độ phức tạp O(n²) thường xuất hiện trong cấu trúc điều khiển nào sau đây?
A. Một vòng lặp đơn.
B. Các câu lệnh tuần tự.
C. Cấu trúc rẽ nhánh if-else.
D. Hai vòng lặp lồng nhau.
Câu 7: Thuật toán tìm kiếm tuần tự (Linear Search) có độ phức tạp thời gian trong trường hợp xấu nhất là:
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
Câu 8: Sắp xếp các độ phức tạp sau theo thứ tự tăng dần về thời gian thực hiện?
A. O(n) < O(1) < O(n²)
B. O(1) < O(n²) < O(n)
C. O(1) < O(n) < O(n²)
D. O(n²) < O(n) < O(1)
Câu 9: Cho đoạn lệnh: a = 10; b = 20; c = a + b. Số lượng phép tính cơ bản phụ thuộc n như thế nào?
A. Tăng tuyến tính theo n.
B. Tăng theo bình phương n.
C. Không phụ thuộc n.
D. Tăng theo log n.
Câu 10: Trong thuật toán tìm kiếm nhị phân (Binary Search), mỗi bước lặp giúp không gian tìm kiếm thay đổi ra sao?
A. Giảm đi 1 đơn vị.
B. Giảm đi 2 đơn vị.
C. Tăng lên gấp đôi.
D. Giảm đi một nửa.
Câu 11: Cho đoạn chương trình:
for i in range(n):
for j in range(n):
print(i, j)
Số lần câu lệnh print được thực hiện là:
A. n lần.
B. 2n lần.
C. n² lần.
D. n/2 lần.
Câu 12: Độ phức tạp không gian (Space Complexity) đo yếu tố nào?
A. Thời gian CPU xử lý.
B. Bộ nhớ máy tính cần dùng.
C. Số dòng lệnh.
D. Tốc độ mạng.
Câu 13: n tăng gấp đôi → thời gian của O(n) thay đổi:
A. Gấp bốn
B. Không đổi
C. Gấp đôi
D. +1
Câu 14: Truy cập phần tử mảng A[i] có độ phức tạp:
A. O(1)
B. O(n)
C. O(log n)
D. O(n²)
Câu 15:
for i in range(n): x = x + 1
for j in range(n): y = y – 1
Độ phức tạp tổng thể:
A. O(n²)
B. O(n)
C. O(1)
D. O(2n²)
Câu 16: Thuật toán O(n!) được coi là:
A. Rất nhanh
B. Nhanh hơn O(n)
C. Rất chậm khi n lớn
D. = O(1)
Câu 17: Yếu tố không ảnh hưởng đến đánh giá độ phức tạp:
A. Số vòng lặp
B. Cấu trúc dữ liệu
C. Kích thước đầu vào
D. Tốc độ CPU
Câu 18: if n % 2 == 0: print(“Chẵn”) có độ phức tạp:
A. O(n)
B. O(1)
C. O(n²)
D. O(log n)
Câu 19: Với n = 10⁹, cần tránh thuật toán:
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
Câu 20: Bubble Sort trung bình:
A. O(n)
B. O(log n)
C. O(n log n)
D. O(n²)
Câu 21:
i = 1
while i < n:
i = i * 2
Độ phức tạp:
A. O(n)
B. O(n²)
C. O(log n)
D. O(1)
Câu 22: A: O(n), B: O(n²) → khi n lớn:
A. A nhanh hơn
B. B nhanh hơn
C. Bằng nhau
D. Không so sánh được
Câu 23: len(A) trong Python:
A. O(n)
B. O(log n)
C. O(1)
D. O(n²)
Câu 24: Trong T(n) = C × n, bỏ qua C vì:
A. C luôn bằng 1
B. C quá lớn
C. n lớn → C ít ảnh hưởng
D. Máy không hiểu C
Câu 25: Đoạn mã O(1):
A. for i in range(n)
B. a = n * (n + 1) / 2
C. while n > 0: n -= 1
D. sum(i for i in range(n))
Câu 26: Hoán đổi dùng biến temp cần bao nhiêu ô nhớ?
A. n
B. n²
C. 1 ô nhớ (O(1))
D. log n
Câu 27: Thuật toán kiểm tra số nguyên tố tối ưu nhất (kiểm tra đến √n):
A. O(n)
B. O(1)
C. O(√n)
D. O(n²)
Câu 28:
count = 0
for i in range(n):
for j in range(i):
count += 1
Số lần thực hiện phép cộng:
A. n
B. n²
C. n(n−1)/2
D. n log n
Câu 29: Sắp xếp O(n log n) + hai con trỏ O(n):
A. O(n²)
B. O(n)
C. O(n log n)
D. O(1)
Câu 30: Vì sao O(log n) tốt hơn O(n)?
A. log n luôn nguyên
B. log n dốc hơn
C. O(n) tốn ít bộ nhớ
D. log n tăng rất chậm khi n lớn
