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 dạng bài tập quen thuộc thường gặp trong đề thi. Các câu hỏi được sắp xếp từ dễ đến khó giúp bạn học mà không cảm thấy áp lực. Đặc biệt phù hợp với người chuẩn bị cho các kỳ kiểm tra quan trọng. Thông qua quá trình làm bài, bạn có thể biết được nội dung nào cần ôn lại. Điều này giúp việc học trở nên có mục tiêu rõ ràng hơn.
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: 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 2: Một vòng lặp 'for' duyệt qua một mảng n phần tử nhưng chỉ nhảy cách 2 bước một lần (ví dụ: duyệt các vị trí 0, 2, 4...) có độ phức tạp thời gian là bao nhiêu?
- - O(1)
- - O(n)
- - O(log n)
- - O(n / 2)
Câu 3: Bài toán sinh tất cả các hoán vị có thể có của một tập hợp chứa n phần tử phân biệt sẽ có độ phức tạp thời gian rơi vào lớp nào?
- - O(n^2)
- - O(2^n)
- - O(n!)
- - O(n^3)
Câu 4: Một vòng lặp 'for' chạy chính xác 1000 lần bất kể kích thước của dữ liệu đầu vào n là bao nhiêu, sẽ có độ phức tạp thời gian là gì?
- - O(1000)
- - O(n)
- - O(1)
- - O(n / 1000)
Câu 5: Một vòng lặp 'for' duyệt qua một mảng có n phần tử và thực hiện phép in giá trị có độ phức tạp thời gian là bao nhiêu?
- - O(n log n)
- - O(1)
- - O(n^2)
- - O(n)
Câu 6: 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 7: Ý nghĩa cốt lõi của việc đánh giá tiệm cận bằng O lớn (Big O) là gì?
- - Tập trung vào sự tăng trưởng của thời gian chạy khi kích thước đầu vào n tiến tới vô cùng
- - Tính toán chính xác số thao tác mà máy tính thực hiện cho mọi giá trị n
- - Xác định xem thuật toán có bị lỗi bộ nhớ khi n lớn hay không
- - Tìm ra kích thước tối đa của n mà thuật toán có thể chạy dưới 1 giây
Câu 8: Phép gán 'a = b + c' trong ngôn ngữ lập trình có độ phức tạp thời gian là bao nhiêu?
- - O(n)
- - O(log n)
- - O(1)
- - O(n^2)
Câu 9: Đoạn mã gồm vòng lặp ngoài 'i' chạy từ 0 đến n-1, vòng lặp trong 'j' chạy từ 0 đến i có độ phức tạp thời gian là bao nhiêu?
- - O(n^2)
- - O(n)
- - O(n log n)
- - O(1)
Câu 10: Thuật toán có hai vòng lặp 'for' lồng nhau, mỗi vòng chạy từ 1 đến n, sẽ có độ phức tạp thời gian là bao nhiêu?
- - O(n)
- - O(n^2)
- - O(2n)
- - O(log n)
Câu 11: Khái niệm 'trường hợp tốt nhất' (best case) của một thuật toán thể hiện điều gì?
- - Tình huống thuật toán tiêu thụ nhiều bộ nhớ nhất nhưng chạy nhanh nhất
- - Tình huống dữ liệu đầu vào làm cho thuật toán gặp lỗi và kết thúc sớm
- - Tình huống dữ liệu đầu vào giúp thuật toán thực hiện ít số bước nhất
- - Trạng thái máy tính có CPU trống nhiều nhất khi thuật toán thực thi
Câu 12: Thuật toán giải quyết bài toán Tháp Hà Nội cổ điển với n đĩa có độ phức tạp thời gian là bao nhiêu?
- - O(2^n)
- - O(n^3)
- - O(n log n)
- - O(n^2)
Câu 13: Đoạn mã có hai vòng lặp tuần tự không lồng nhau: vòng đầu chạy n lần, vòng sau chạy m lần. Độ phức tạp thời gian tổng quát là bao nhiêu?
- - O(n + m)
- - O(n * m)
- - O(n)
- - O(m)
Câu 14: Thuật toán tìm kiếm nhị phân trên một mảng đã sắp xếp có n phần tử có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?
- - O(1)
- - O(n)
- - O(n log n)
- - O(log n)
Câu 15: Nếu một thuật toán gồm hai bước tuần tự 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 thuật toán là gì?
- - O(n^2)
- - O(n^3)
- - O(n)
- - O(1)
Câu 16: Mục đích chính của việc xác định độ phức tạp thời gian của thuật toán là gì?
- - Đánh giá hiệu quả của thuật toán độc lập với phần cứng và ngôn ngữ lập trình
- - Đo lường chính xác số mili-giây mà CPU cần để chạy chương trình
- - Xác định dung lượng RAM tối đa mà chương trình sẽ sử dụng
- - Tìm ra ngôn ngữ lập trình chạy nhanh nhất cho một đoạn mã cụ thể
Câu 17: Một vòng lặp 'while' có điều kiện (n > 1) và biểu thức thay đổi là 'n = n / 2' có độ phức tạp thời gian là bao nhiêu?
- - O(1)
- - O(log n)
- - O(n)
- - O(n^2)
Câu 18: Thuật toán sắp xếp trộn (Merge Sort) nổi tiếng với hiệu suất ổn định, có độ phức tạp thời gian trong mọi trường hợp (tốt, xấu, trung bình) là bao nhiêu?
- - O(n log n)
- - O(n)
- - O(log n)
- - O(n^2)
Câu 19: Ký hiệu nào sau đây được sử dụng phổ biến nhất để biểu diễn độ phức tạp thời gian trong trường hợp xấu nhất?
- - Omega lớn (Big Omega)
- - O lớn (Big O)
- - Theta lớn (Big Theta)
- - Nhỏ o (Little o)
Câu 20: Sắp xếp các độ phức tạp sau theo thứ tự tăng dần về thời gian chạy (từ nhanh nhất đến chậm nhất khi n đủ lớn): O(n), O(1), O(n^2), O(log n).
- - O(1), O(n), O(log n), O(n^2)
- - O(1), O(log n), O(n), O(n^2)
- - O(log n), O(1), O(n), O(n^2)
- - O(n^2), O(n), O(log n), O(1)
Câu 21: Khi đánh giá một thuật toán, ngoài độ phức tạp thời gian, người ta thường quan tâm đến yếu tố nào khác để đo lường hiệu quả sử dụng bộ nhớ?
- - Độ phức tạp mạng lưới
- - Độ phức tạp phần cứng
- - Độ phức tạp không gian
- - Độ phức tạp mã nguồn
Câu 22: Thuật toán sắp xếp chọn (Selection Sort) luôn tìm phần tử nhỏ nhất trong mảng chưa sắp xếp để đưa về đầu, độ phức tạp thời gian trường hợp trung bình của thuật toán này là bao nhiêu?
- - O(n log n)
- - O(1)
- - O(n)
- - O(n^2)
Câu 23: Nếu một thuật toán có độ phức tạp tuyến tính O(n) mất 2 giây để xử lý 10.000 bản ghi dữ liệu, dự kiến nó sẽ mất khoảng bao lâu để xử lý 50.000 bản ghi tương tự?
- - 25 giây
- - 10 giây
- - 4 giây
- - 50 giây
Câu 24: Trong việc tìm kiếm tuần tự, thao tác kiểm tra một phần tử có nằm trong một mảng chưa sắp xếp n phần tử mất thời gian bao nhiêu trong trường hợp xấu nhất?
- - O(n log n)
- - O(n)
- - O(1)
- - O(log n)
Câu 25: 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)