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 25 Xác định độ phức tạp thời gian thuộc 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 25 Xác định độ phức tạp thời gian thuộc toá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 Số câu25Quiz ID40964 Làm bài Câu 1 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? A O(n) B O(log n) C O(1) D O(n^2) Câu 2 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ì? A Tình huống thuật toán tiêu thụ nhiều bộ nhớ nhất nhưng chạy nhanh nhất B 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 C 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 D 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 3 Đ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? A O(n + m) B O(n * m) C O(n) D O(m) Câu 4 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? A O(2^n) B O(n^3) C O(n log n) D O(n^2) Câu 5 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ớ? A Độ phức tạp mạng lưới B Độ phức tạp phần cứng C Độ phức tạp không gian D Độ phức tạp mã nguồn Câu 6 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ế? A O(n^2) B O(1) C O(n) D O(log n) Câu 7 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ì? A O(n) B O(5) C O(n^5) D O(1) Câu 8 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? A O(n^2) B O(2^n) C O(n!) D O(n^3) Câu 9 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? A O(n) B O(n^2) C O(2n) D O(log n) Câu 10 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ự? A 25 giây B 10 giây C 4 giây D 50 giây Câu 11 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? A O(n log n) B O(1) C O(n^2) D O(n) Câu 12 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ì? A O(1000) B O(n) C O(1) D O(n / 1000) Câu 13 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? A O(1) B O(log n) C O(n) D O(n^2) Câu 14 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? A O(n log n) B O(1) C O(n) D O(n^2) Câu 15 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? A Omega lớn (Big Omega) B O lớn (Big O) C Theta lớn (Big Theta) D Nhỏ o (Little o) Câu 16 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). A O(1), O(n), O(log n), O(n^2) B O(1), O(log n), O(n), O(n^2) C O(log n), O(1), O(n), O(n^2) D O(n^2), O(n), O(log n), O(1) Câu 17 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? A O(1) B O(n) C O(log n) D O(n / 2) Câu 18 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? A O(n log n) B O(n) C O(1) D O(log n) Câu 19 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ì? A Đá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 B Đo lường chính xác số mili-giây mà CPU cần để chạy chương trình C Xác định dung lượng RAM tối đa mà chương trình sẽ sử dụng D 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 20 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ì? A O(n + n log n) B O(n log n) C O(n) D O(n^2) Câu 21 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? A O(n log n) B O(n) C O(log n) D O(n^2) Câu 22 Đ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? A O(n^2) B O(n) C O(n log n) D O(1) Câu 23 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ì? A O(n^2) B O(n^3) C O(n) D O(1) Câu 24 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? A O(1) B O(n) C O(n log n) D O(log n) Câu 25 Ý 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ì? A 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 B 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 C Xác định xem thuật toán có bị lỗi bộ nhớ khi n lớn hay không D 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 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 26 Phương pháp làm mịn dần trong thiết kế chương trình
