Trắc nghiệm Tin học 11 Kết nối tri thức KHMT bài 24 Đánh giá độ phức tạp thời gian thuật toán giúp bạn rèn luyện phản xạ làm bài hiệu quả thông qua nhiều dạng câu hỏi phổ biến.
Trắc nghiệm Tin học 11 Kết nối tri thức KHMT bài 24 Đánh giá độ phức tạp thời gian thuật toán
⏱ Thời gian còn lại: --:--
Tiến độ hoàn thành
0/0 câu
🏆 BẢNG VÀNG TOP 5 ĐIỂM TỐT NHẤT
Đang tải bảng xếp hạng...
Câu 1: Thuật toán nào sau đây không thể đạt độ phức tạp O(n)
- - Tìm kiếm phần tử trong mảng không sắp xếp
- - Tìm giá trị lớn nhất trong mảng
- - Tìm kiếm nhị phân
- - Tính tổng các phần tử của mảng
Câu 2: Thuật toán nào sau đây có độ phức tạp thời gian O(log n)?
- - Tìm kiếm tuần tự
- - Sắp xếp chọn
- - Tìm kiếm nhị phân
- - Duyệt mảng một chiều
Câu 3: Mục đích chính của việc đánh giá độ phức tạp thời gian thuật toán là gì
- - Xác định chính xác số giây thực tế thuật toán chạy
- - Ước lượng sự tăng trưởng của thời gian thực thi theo kích thước đầu vào
- - Tìm cách làm cho thuật toán chạy nhanh hơn trên mọi phần cứng
- - Đo lường dung lượng bộ nhớ mà thuật toán tiêu tốn
Câu 4: Độ phức tạp O(1) thường gắn liền với thao tác nào trong cấu trúc dữ liệu
- - Duyệt toàn bộ mảng
- - Truy cập trực tiếp một phần tử qua chỉ số
- - Sắp xếp mảng
- - Tìm kiếm phần tử lớn nhất
Câu 5: Nếu thuật toán cần tìm một phần tử trong một dãy đã sắp xếp, phương pháp nào tốt nhất?
- - Tìm kiếm tuyến tính O(n)
- - Tìm kiếm nhị phân O(log n)
- - Sắp xếp lại rồi tìm kiếm
- - Duyệt toàn bộ mảng O(n^2)
Câu 6: Một thuật toán có độ phức tạp thời gian là O(1) có đặc điểm gì?
- - Thời gian chạy tỉ lệ thuận với n
- - Thời gian chạy tỉ lệ với n bình phương
- - Thời gian chạy là hằng số, không phụ thuộc vào kích thước dữ liệu
- - Thời gian chạy tăng theo hàm mũ
Câu 7: Nếu một thuật toán có hai vòng lặp lồng nhau, mỗi vòng lặp chạy n lần, độ phức tạp thời gian thường là bao nhiêu?
- - O(n^2)
- - O(n)
- - O(log n)
- - O(n^3)
Câu 8: Nếu một thuật toán có thời gian chạy là T(n) = 3n + 5, độ phức tạp thời gian của thuật toán đó theo kí hiệu Big O là gì?
- - O(n)
- - O(n^2)
- - O(1)
- - O(log n)
Câu 9: Khi kích thước đầu vào n tăng gấp đôi, thời gian chạy của thuật toán O(n^2) sẽ thay đổi như thế nào
- - Tăng gấp đôi
- - Tăng gấp bốn
- - Không đổi
- - Tăng lên 8 lần
Câu 10: Việc so sánh độ phức tạp O(n) và O(n^2) cho thấy điều gì?
- - O(n^2) luôn chạy nhanh hơn O(n)
- - O(n) hiệu quả hơn O(n^2) khi n đủ lớn
- - Hai độ phức tạp này tương đương nhau
- - Không thể so sánh được
Câu 11: Nếu một thuật toán thực hiện phép tính 2 mũ n, đây gọi là độ phức tạp gì?
- - Độ phức tạp đa thức
- - Độ phức tạp hàm mũ
- - Độ phức tạp tuyến tính
- - Độ phức tạp hằng số
Câu 12: Thuật toán có độ phức tạp thời gian O(1) được gọi là gì?
- - Thời gian hằng số
- - Thời gian tuyến tính
- - Thời gian đa thức
- - Thời gian lũy thừa
Câu 13: Độ phức tạp O(n + m) có ý nghĩa gì nếu n và m là kích thước của hai tập dữ liệu khác nhau
- - Thời gian chạy phụ thuộc vào tổng kích thước hai tập dữ liệu
- - Thời gian chạy là tích của n và m
- - Thuật toán chỉ chạy trên tập n
- - Thuật toán không phụ thuộc vào dữ liệu
Câu 14: Khi n = 1000, thuật toán nào chạy nhanh nhất?
- - Thuật toán O(n bình phương)
- - Thuật toán O(n)
- - Thuật toán O(2 mũ n)
- - Thuật toán O(n log n)
Câu 15: Thuật toán nào có độ phức tạp thời gian tồi tệ nhất trong các loại thường gặp?
- - O(log n)
- - O(n)
- - O(n log n)
- - O(n!)
Câu 16: Một thuật toán có độ phức tạp thời gian là O(1) nghĩa là gì?
- - Thời gian thực hiện tỉ lệ thuận với kích thước đầu vào
- - Thuật toán không thực hiện lệnh nào
- - Thời gian thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào
- - Thời gian thực hiện tăng theo hàm mũ
Câu 17: Độ phức tạp của thuật toán duyệt qua tất cả các cặp phần tử trong một danh sách là bao nhiêu?
- - O(n)
- - O(log n)
- - O(n^2)
- - O(n log n)
Câu 18: Đoạn mã có 3 vòng lặp lồng nhau, mỗi vòng chạy n lần, có độ phức tạp là bao nhiêu?
- - O(3n)
- - O(n bình phương)
- - O(n mũ 3)
- - O(n + 3)
Câu 19: Biểu thức 3n + 5 thuộc độ phức tạp nào theo kí hiệu Big O?
- - O(1)
- - O(n)
- - O(n^2)
- - O(log n)
Câu 20: Một thuật toán duyệt mảng có độ phức tạp O(n). Nếu kích thước mảng tăng gấp 10 lần, thời gian dự kiến tăng bao nhiêu lần?
- - 100 lần
- - 10 lần
- - 20 lần
- - Không đổi
Câu 21: Việc phân tích độ phức tạp thời gian giúp ích gì nhất cho lập trình viên?
- - Viết mã ngắn gọn hơn
- - Chọn được giải pháp phù hợp với quy mô dữ liệu dự kiến
- - Tăng tốc phần cứng máy tính
- - Thay thế các ngôn ngữ lập trình
Câu 22: Tại sao cần bỏ qua các hằng số trong biểu thức độ phức tạp (ví dụ O(2n) thành O(n))?
- - Vì hằng số không có giá trị
- - Vì mục tiêu là xác định tốc độ tăng trưởng khi n tiến tới vô cùng
- - Vì máy tính xử lý hằng số rất nhanh
- - Vì quy ước viết gọn của toán học
Câu 23: Một vòng lặp chạy n/2 lần có độ phức tạp là bao nhiêu?
- - O(n)
- - O(n^2)
- - O(log n)
- - O(1)
Câu 24: Việc giảm độ phức tạp từ O(n^2) xuống O(n log n) mang lại tác động gì?
- - Thuật toán chạy chậm hơn đáng kể
- - Thuật toán chạy nhanh hơn đáng kể với n lớn
- - Không thay đổi gì đáng kể
- - Thuật toán tốn nhiều bộ nhớ hơn
Câu 25: Độ phức tạp O(n + log n) được viết gọn lại thành gì?
- - O(n)
- - O(log n)
- - O(n log n)
- - O(1)