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

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

A O(n) B O(log n) C O(n^2) D O(n log n)

A O(n + m) B O(n * m) C O(n^m) D O(m^n)

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ũ

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)

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

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ử

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

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

A O(n) B O(log n) C O(n log n) D O(n^2)

A O(1) B O(1000) C O(n) D Không thể xác định

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

A O(n) B O(log n) C O(1) D O(n^2)

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

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

A O(1) B O(n) C O(n^2) D O(log 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ố

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ũ

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ố

A O(log n) B O(n) C O(n log n) D O(n!)

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ụ

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

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

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

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