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 ô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 thiết kế khoa học giúp bạn tiếp cận kiến thức từng bước. Đặc biệt phù hợp với những bạn đang ôn thi. 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 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: Xét thuật toán có độ phức tạp O(n^2), điều gì xảy ra nếu kích thước đầu vào tăng gấp đôi?
- - Thời gian chạy giữ nguyên
- - Thời gian chạy tăng gấp đôi
- - Thời gian chạy tăng gấp bốn
- - Thời gian chạy không thể xác định
Câu 2: Nếu một vòng lặp chạy n lần, và trong mỗi vòng lặp lại có một vòng lặp lồng nhau chạy m lần, độ phức tạp là gì?
- - O(n + m)
- - O(n * m)
- - O(n^m)
- - O(m^n)
Câu 3: Độ phức tạp thời gian O(2^n) thường được coi là gì?
- - Rất hiệu quả
- - Hiệu quả trung bình
- - Không hiệu quả với n lớn
- - Chỉ áp dụng cho máy tính siêu mạnh
Câu 4: Độ phức tạp O(log n) thường gắn liền với cấu trúc thuật toán nào?
- - Chia đôi dữ liệu liên tục
- - Duyệt danh sách từ đầu đến cuối
- - Lồng ghép vòng lặp
- - Duyệt tất cả các tổ hợp
Câu 5: Ký hiệu Big O được dùng để biểu thị giới hạn nào của thời gian chạy?
- - Giới hạn trên
- - Giới hạn dưới
- - Giới hạn trung bình
- - Giới hạn tuyệt đối
Câu 6: Khi phân tích độ phức tạp thời gian, ta thường quan tâm đến điều gì nhất?
- - Trường hợp tốt nhất
- - Trường hợp xấu nhất
- - Trường hợp trung bình
- - Thời gian thực thi trên phần cứng cũ
Câu 7: Một vòng lặp for chạy từ 1 đến 1000, bên trong là phép tính O(1), độ phức tạp là gì?
- - O(1)
- - O(1000)
- - O(n)
- - Không thể xác định
Câu 8: Tại sao việc thiết kế thuật toán tối ưu là quan trọng?
- - Để giảm chi phí tài nguyên và nâng cao trải nghiệm người dùng
- - Để làm cho code trở nên khó hiểu hơn
- - Để thuật toán chạy chậm hơn khi cần thiết
- - Để không cần sử dụng máy tính mạnh
Câu 9: 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 10: Đâu là thuật toán thường có độ phức tạp thời gian O(n log n)?
- - Sắp xếp nổi bọt (Bubble sort)
- - Sắp xếp chọn (Selection sort)
- - Sắp xếp trộn (Merge sort)
- - Tìm kiếm tuyến tính
Câu 11: Phép gán x = y + z có độ phức tạp thời gian là bao nhiêu?
- - O(n)
- - O(log n)
- - O(1)
- - O(n^2)
Câu 12: Khi nói một thuật toán là 'hiệu quả', điều đó thường ám chỉ gì về độ phức tạp của nó?
- - Nó có độ phức tạp đa thức thấp (như O(n) hoặc O(n log n))
- - Nó có độ phức tạp hàm mũ
- - Nó luôn chạy trong 1 giây
- - Nó chỉ chạy được trên phần cứng hiện đại
Câu 13: 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 14: Mục đích chính của việc đánh giá độ phức tạp thời gian của một thuật toán là gì?
- - Xác định chính xác thời gian thực thi của thuật toán trên một máy tính cụ thể
- - Đánh giá tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào tăng lên
- - Tìm kiếm phương pháp tối ưu để giảm dung lượng bộ nhớ sử dụng
- - Chứng minh thuật toán luôn cho kết quả đúng với mọi dữ liệu
Câu 15: 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 16: Thuật toán 'In ra từng phần tử của một danh sách' có độ phức tạp là bao nhiêu?
- - O(1)
- - O(n)
- - O(n^2)
- - O(log n)
Câu 17: Khi nào độ phức tạp O(n log n) được coi là hợp lý?
- - Khi giải quyết bài toán sắp xếp quy mô lớn
- - Khi cần đọc một biến duy nhất
- - Khi cần cộng hai số nguyên
- - Khi tìm kiếm trong một phần tử
Câu 18: 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 19: Để đánh giá thuật toán, người ta thường bỏ qua các số hạng có bậc thấp. Tại sao?
- - Vì chúng chiếm ít thời gian khi n rất lớn
- - Vì chúng không tồn tại
- - Vì chúng làm phức tạp thêm các phép toán
- - Vì chúng luôn luôn bằng 0
Câu 20: Độ phức tạp thời gian O(n) thường xuất hiện trong thuật toán nào?
- - Duyệt qua danh sách n phần tử một lần duy nhất
- - Sắp xếp danh sách bằng thuật toán nổi bọt
- - Tìm kiếm nhị phân trên dãy đã sắp xếp
- - Truy cập trực tiếp vào một phần tử thông qua chỉ số
Câu 21: Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trên n phần tử là gì?
- - O(n)
- - O(log n)
- - O(n log n)
- - O(n^2)
Câu 22: Trong ký hiệu O-lớn (Big O notation), cái gì được sử dụng để mô tả độ phức tạp?
- - Tốc độ của bộ vi xử lý máy tính
- - Số lượng phép toán cơ bản
- - Thời gian chạy đo bằng giây
- - Dung lượng bộ nhớ RAM tiêu thụ
Câu 23: Sự khác biệt giữa độ phức tạp thời gian và thời gian chạy thực tế là gì?
- - Không có sự khác biệt
- - Thời gian chạy phụ thuộc phần cứng, độ phức tạp là lý thuyết trừu tượng
- - Độ phức tạp phụ thuộc phần cứng, thời gian chạy là lý thuyết
- - Thời gian chạy tính bằng số lượng phép toán
Câu 24: Độ 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 25: Tại sao trong Big O chúng ta thường bỏ qua các hằng số (ví dụ O(2n) thành O(n))?
- - Vì hằng số không làm thay đổi tốc độ tăng trưởng của thuật toán
- - Vì hằng số làm phép tính trở nên khó hơn
- - Vì hằng số luôn bằng 1
- - Vì lập trình viên không cần biết về hằng số