Trắc nghiệm Tin học 11 Kết nối tri thức KHMT bài 25 Xác định độ phức tạp thời gian thuộc toán giúp bạn ôn tập kiến thức một cách có hệ thống thông qua hệ thống câu hỏi đa dạng.
Trắc nghiệm Tin học 11 Kết nối tri thức KHMT bài 25 Xác định độ phức tạp thời gian thuộc 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: Theo quy tắc xác định độ phức tạp Big O, biểu thức O(5n + 10) sẽ được đơn giản hóa thành gì?
- - O(1)
- - O(n^2)
- - O(15n)
- - O(n)
Câu 2: Cho một vòng lặp 'for' chạy từ 1 đến n, bên trong nó chứa một vòng lặp 'for' khác chạy từ 1 đến n, độ phức tạp thời gian của đoạn mã này là gì?
- - O(2n)
- - O(n^2)
- - O(n)
- - O(n log n)
Câu 3: Trong các nhóm độ phức tạp sau, nhóm nào biểu thị thuật toán chạy nhanh nhất khi dữ liệu n cực kỳ lớn?
- - Thuật toán có độ phức tạp O(1)
- - Thuật toán có độ phức tạp O(n)
- - Thuật toán có độ phức tạp O(n log n)
- - Thuật toán có độ phức tạp O(log n)
Câu 4: Một vòng lặp 'for' chạy với biến i bắt đầu từ 1, tăng theo bước nhảy là 2 (i = i + 2) cho đến khi i vượt qua n. Độ phức tạp của vòng lặp này là gì?
- - O(n^2)
- - O(log n)
- - O(n)
- - O(1)
Câu 5: Khi xử lý một tập dữ liệu rất lớn (ví dụ n = 1.000.000), thuật toán có độ phức tạp nào sau đây thường sẽ không khả thi về mặt thời gian thực thi trong thực tế?
- - O(n^2)
- - O(1)
- - O(n)
- - O(log n)
Câu 6: Đoạn mã hoán đổi giá trị hai biến số nguyên 't = a; a = b; b = t' có độ phức tạp thời gian là bao nhiêu?
- - O(n)
- - O(3)
- - O(log n)
- - O(1)
Câu 7: Sắp xếp chọn (Selection Sort) hoặc Sắp xếp nổi bọt (Bubble Sort) thông thường có độ phức tạp thời gian là bao nhiêu?
- - O(1)
- - O(n^2)
- - O(n)
- - O(log n)
Câu 8: Trong một chương trình, bạn thực hiện khởi tạo mảng mất thời gian O(n), sau đó sắp xếp mảng đó mất thời gian O(n log n). Độ phức tạp thời gian của toàn bộ chương trình là gì?
- - O(n + n log n)
- - O(n log n)
- - O(n)
- - O(n^2)
Câu 9: Một vòng lặp 'for' lặp cố định đúng 1000 lần bất kể kích thước dữ liệu đầu vào n là bao nhiêu. Độ phức tạp của đoạn mã này là gì?
- - O(n)
- - O(1)
- - O(1000)
- - O(n / 1000)
Câu 10: Sắp xếp các độ phức tạp thời gian sau đây theo thứ tự tốc độ tăng từ chậm đến nhanh (tương đương từ thuật toán hiệu quả nhất đến kém nhất khi n lớn)?
- - O(n^2) < O(n) < O(log n) < O(1)
- - O(1) < O(n) < O(log n) < O(n^2)
- - O(log n) < O(1) < O(n) < O(n^2)
- - O(1) < O(log n) < O(n) < O(n^2)
Câu 11: Trong phân tích thuật toán, tại sao người ta thường quan tâm nhất đến độ phức tạp trong trường hợp xấu nhất?
- - Vì nó đảm bảo thuật toán sẽ không bao giờ chạy chậm hơn giới hạn đó, giúp dự trù tài nguyên an toàn
- - Vì trường hợp xấu nhất luôn xảy ra trong mọi lần chạy thực tế
- - Vì nó dễ tính toán hơn so với trường hợp tốt nhất
- - Vì trường hợp xấu nhất cho biết thuật toán chạy nhanh nhất là bao lâu
Câu 12: Trong một câu lệnh điều kiện: 'if (điều_kiện_O(1)): thực_hiện_đoạn_mã_O(n) else: thực_hiện_đoạn_mã_O(n^2)'. Độ phức tạp thời gian trong trường hợp xấu nhất là gì?
- - O(n)
- - O(1)
- - O(n^3)
- - O(n^2)
Câu 13: Một vòng lặp có dạng 'k = n; while k > 0: k = k // 2' (chia đôi k sau mỗi bước). Độ phức tạp thời gian là bao nhiêu?
- - O(1)
- - O(n)
- - O(n log n)
- - O(log n)
Câu 14: Trong các kỳ thi lập trình, với giới hạn thời gian chạy là 1 giây (khoảng 10^7 đến 10^8 phép toán), nếu n = 10^6, thuật toán có độ phức tạp nào sau đây là phù hợp nhất để không bị quá thời gian (Time Limit Exceeded)?
- - O(n^2)
- - O(2^n)
- - O(n)
- - O(n^3)
Câu 15: Trong khoa học máy tính, ký hiệu nào phổ biến nhất được dùng để biểu diễn giới hạn trên của độ phức tạp thời gian?
- - Ký hiệu O lớn (Big O)
- - Ký hiệu T lớn (Big T)
- - Ký hiệu N lớn (Big N)
- - Ký hiệu C lớn (Big C)
Câu 16: Khi phân tích cấu trúc rẽ nhánh 'if điều_kiện: khối_lệnh_1(có O(n)) else: khối_lệnh_2(có O(n^2))', độ phức tạp tổng thể trong trường hợp xấu nhất là gì?
- - O(n)
- - O(n^2)
- - O(n^3)
- - O(1)
Câu 17: Theo quy tắc bỏ hằng số trong đánh giá độ phức tạp thuật toán, O(5n) sẽ được diễn đạt lại thành gì?
- - O(n)
- - O(5)
- - O(n^5)
- - O(1)
Câu 18: Độ phức tạp O(n^3 + 2n^2 + n + 100) sẽ được đánh giá tiệm cận thành biểu thức nào?
- - O(n^2)
- - O(n^3)
- - O(100)
- - O(n)
Câu 19: Vòng lặp có bước nhảy lớn 'for i in range(0, n, 5):' sẽ sở hữu độ phức tạp thời gian tiệm cận nào?
- - O(1)
- - O(n)
- - O(n^2)
- - O(log n)
Câu 20: Khi phân tích hai khối lệnh tuần tự có độ phức tạp lần lượt là O(f(n)) và O(g(n)), độ phức tạp tổng cộng của cả hai khối lệnh là gì?
- - O(max(f(n), g(n)))
- - O(f(n) * g(n))
- - O(f(n) - g(n))
- - O(min(f(n), g(n)))
Câu 21: Hai vòng lặp lồng nhau dạng 'for i in range(n): for j in range(n):' có độ phức tạp thời gian là bao nhiêu?
- - O(n^2)
- - O(2n)
- - O(n)
- - O(n log n)
Câu 22: Phép toán kiểm tra một số nguyên x có phải là số chẵn hay không (dùng phép chia lấy dư x % 2 == 0) có độ phức tạp là bao nhiêu?
- - O(x)
- - O(log x)
- - O(1)
- - O(x^2)
Câu 23: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự (Linear Search) trong trường hợp xấu nhất là gì?
- - O(n^2)
- - O(1)
- - O(log n)
- - O(n)
Câu 24: Trong trường hợp tốt nhất, thuật toán tìm kiếm tuần tự có độ phức tạp thời gian là bao nhiêu?
- - O(1)
- - O(n)
- - O(log n)
- - O(n^2)
Câu 25: Nếu một chương trình gồm hai đoạn mã chạy nối tiếp nhau có độ phức tạp lần lượt là O(n) và O(n^2), độ phức tạp tổng thể của chương trình là bao nhiêu?
- - O(n^3)
- - O(n)
- - O(n^2)
- - O(n + n^2)