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 theo dõi sự tiến bộ của bản thân thông qua nhiều dạng câu hỏi phổ biế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: Khái niệm 'trường hợp tốt nhất' (best case) trong phân tích thuật toán có nghĩa là gì?
- - Thời gian chạy trung bình của thuật toán trên mọi bộ dữ liệu
- - Thời gian chạy lâu nhất mà thuật toán cần để hoàn thành
- - Thời gian chạy ít nhất mà thuật toán cần để hoàn thành với một bộ dữ liệu cụ thể
- - Trạng thái khi thuật toán không sử dụng bất kỳ bộ nhớ nào
Câu 2: Khối lệnh chứa hai vòng lặp lồng nhau chạy qua hai biến đầu vào khác biệt: 'for i in range(n): for j in range(m):' có giới hạn Big O là bao nhiêu?
- - O(n * m)
- - O(n + m)
- - O(m^2)
- - O(n^2)
Câu 3: Đoạn mã khởi tạo một mảng chứa n phần tử bằng giá trị 0 như 'arr = [0] * n' mang độ phức tạp thuật toán là gì?
- - O(n)
- - O(1)
- - O(n log n)
- - O(n^2)
Câu 4: Thuật toán tìm kiếm nhị phân (Binary Search) trên mảng đã sắp xếp có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?
- - O(n)
- - O(log n)
- - O(n^2)
- - O(1)
Câu 5: 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 6: 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 7: Tại sao khi đánh giá độ phức tạp thuật toán trong khoa học máy tính, người ta thường đếm số lượng phép toán thay vì đo thời gian chạy bằng giây?
- - Vì máy tính hiện đại quá nhanh không thể đo được thời gian bằng giây
- - Vì không có phần mềm nào có thể đo thời gian chạy của một chương trình
- - Vì thời gian chạy bằng giây luôn luôn là một hằng số cố định
- - Vì thời gian chạy bằng giây phụ thuộc vào tốc độ phần cứng máy tính và ngôn ngữ lập trình
Câu 8: Đoạn mã giả 'for i = 1 to 1000000: a = a + 1' có độ phức tạp thời gian là bao nhiêu?
- - O(1)
- - O(n)
- - O(1000000)
- - O(n^2)
Câu 9: 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 10: Giả sử bạn phải kiểm tra một danh sách gồm n chuỗi văn bản, trong đó mỗi chuỗi dài tối đa m ký tự. Việc tìm kiếm một ký tự cụ thể trong toàn bộ danh sách tốn thời gian tối đa là bao nhiêu?
- - O(n * m)
- - O(m)
- - O(n + m)
- - O(n)
Câu 11: Thuật toán sắp xếp nổi bọt (Bubble Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là gì?
- - O(n log n)
- - O(1)
- - O(n^2)
- - O(n)
Câu 12: Độ 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 13: 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 14: Khái niệm 'trường hợp xấu nhất' (Worst Case) trong phân tích độ phức tạp thuật toán mang ý nghĩa chính xác là gì?
- - Thuật toán gặp lỗi runtime và dừng đột ngột
- - Người dùng nhập sai định dạng dữ liệu đầu vào
- - Cấu hình dữ liệu đầu vào khiến thuật toán phải thực hiện số lượng phép toán nhiều nhất
- - Máy tính hết bộ nhớ RAM khi đang chạy thuật toán
Câu 15: 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 16: Khi biểu thức tính thời gian chạy của thuật toán là T(n) = 3n^3 + 5n^2 + 100, độ phức tạp O lớn của thuật toán là gì?
- - O(n^2)
- - O(n^3)
- - O(3n^3)
- - O(100)
Câu 17: 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 18: Xét đoạn mã: vòng lặp ngoài biến i chạy từ 1 đến n, vòng lặp trong biến j chạy từ 1 đến i. Độ phức tạp của đoạn mã này là gì?
- - O(n^2)
- - O(n)
- - O(n log n)
- - O(n^3)
Câu 19: Cho đoạn mã 'for i in range(n): for j in range(i): x += 1', vòng lặp trong phụ thuộc vòng lặp ngoài thì độ phức tạp thời gian là bao nhiêu?
- - O(n^2)
- - O(n)
- - O(n log n)
- - O(n^3)
Câu 20: 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 21: 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 22: 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 23: Kí hiệu O lớn (Big O) trong phân tích thuật toán chủ yếu được sử dụng để làm gì?
- - Đánh giá không gian bộ nhớ tối đa mà thuật toán cần sử dụng
- - Mô tả giới hạn trên của thời gian thực thi thuật toán theo kích thước dữ liệu đầu vào
- - Đo lường thời gian chạy thực tế của thuật toán tính bằng giây
- - Xác định số lượng dòng mã nguồn cần thiết để lập trình thuật toán
Câu 24: Độ phức tạp của đoạn mã gồm hai vòng lặp lồng nhau nhưng vòng lặp trong phụ thuộc vòng lặp ngoài: 'for i in range(n): for j in range(i):' là gì?
- - O(n log n)
- - O(n^2)
- - O(1)
- - O(n)
Câu 25: Độ phức tạp O(2^n) thường xuất hiện trong loại thuật toán nào và được đánh giá ra sao về hiệu suất?
- - Thường gặp ở thuật toán sinh vét cạn hoặc đệ quy phân nhánh, có hiệu suất rất kém khi n lớn
- - Thường gặp ở tìm kiếm nhị phân, là thuật toán cực kỳ tối ưu
- - Thường gặp ở vòng lặp đơn, có tốc độ xử lý rất nhanh
- - Thường gặp ở thuật toán sắp xếp nổi bọt, tốc độ trung bình