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