Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) 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) Bài 24: Đánh Giá Độ Phức Tạp Thời Gian Thuật Toán tổng hợp câu hỏi trắc nghiệm chứa đựng nhiều dạng bài tập, bài thi, cũng như các câu hỏi trắc nghiệm và bài kiểm tra, trong bộ Trắc Nghiệm Tin Học 11 – Kết Nối Tri Thức. Nội dung trắc nghiệm nhấn mạnh phần kiến thức nền tảng và chuyên môn sâu của học phần này. Mọi bộ đề trắc nghiệm đều cung cấp câu hỏi, đáp án cùng hướng dẫn giải cặn kẽ. Mời bạn thử sức làm bài nhằm ôn luyện và làm vững chắc kiến thức cũng như đánh giá năng lực bản thân!

Đề 01

Đề 02

Đề 03

Đề 04

Đề 05

Đề 06

Đề 07

Đề 08

Đề 09

Đề 10

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 01

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, ký hiệu O lớn (Big O) biểu thị điều gì?

Thời gian chạy chính xác của thuật toán.

Thời gian chạy tốt nhất (trường hợp lý tưởng) của thuật toán.

Cận trên (trường hợp xấu nhất) của tốc độ tăng trưởng thời gian chạy khi kích thước đầu vào lớn.

Lượng bộ nhớ mà thuật toán sử dụng.

Ký hiệu O lớn dùng để mô tả cận trên (trường hợp xấu nhất) của tốc độ tăng trưởng thời gian chạy của thuật toán khi kích thước đầu vào (n) tiến tới vô cùng, bỏ qua các hằng số và các số hạng bậc thấp.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 2: Giả sử một chương trình thực hiện các bước sau theo trình tự: một khối lệnh tốn O(n^2) thời gian, sau đó là một khối lệnh tốn O(n) thời gian, và cuối cùng là một khối lệnh tốn O(1) thời gian. Sử dụng quy tắc cộng, độ phức tạp thời gian tổng thể của chương trình này là gì?

O(n^3)

O(n^2 + n + 1)

O(n)

O(n^2)

Quy tắc cộng cho phép tính độ phức tạp của các khối lệnh thực hiện nối tiếp nhau bằng cách lấy độ phức tạp của khối lệnh có bậc cao nhất. Trong trường hợp này, O(n^2) là bậc cao nhất so với O(n) và O(1).

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 3: Một thuật toán tìm kiếm nhị phân trên một mảng đã sắp xếp có độ phức tạp thời gian là O(log n). Điều này có ý nghĩa gì khi kích thước mảng (n) tăng lên?

Thời gian chạy tăng rất chậm khi n tăng, hiệu quả với dữ liệu lớn.

Thời gian chạy tăng tuyến tính với n.

Thời gian chạy tăng theo bình phương của n.

Thời gian chạy không phụ thuộc vào n.

Độ phức tạp O(log n) nghĩa là thời gian chạy tăng rất chậm khi n tăng lên. Ví dụ, nếu n gấp đôi, thời gian chạy chỉ tăng thêm một lượng nhỏ (tương ứng với log₂(2n) = log₂n + 1).

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 4: Xem xét đoạn mã giả sau:
```
for i = 1 to n:
for j = 1 to n:
// Thực hiện một phép toán cơ bản (O(1))
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(log n)

O(n^2)

O(n log n)

Đây là cấu trúc vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần. Với mỗi lần lặp của vòng ngoài, vòng lặp trong chạy n lần. Tổng số lần phép toán cơ bản được thực hiện là n * n = n^2. Sử dụng quy tắc nhân, độ phức tạp là O(n^2).

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 5: Tại sao các hằng số và các số hạng bậc thấp thường bị bỏ qua khi đánh giá độ phức tạp thời gian bằng ký hiệu Big O?

Chúng làm cho việc tính toán trở nên quá phức tạp.

Khi kích thước đầu vào (n) rất lớn, tốc độ tăng trưởng của số hạng bậc cao nhất là yếu tố chi phối.

Chúng chỉ quan trọng trong trường hợp tốt nhất.

Việc bỏ qua chúng giúp thuật toán chạy nhanh hơn.

Khi n rất lớn, sự đóng góp của các số hạng bậc cao là chi phối. Các hằng số nhân hoặc cộng, cùng với các số hạng bậc thấp, trở nên không đáng kể so với tốc độ tăng trưởng của số hạng bậc cao nhất.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 6: Thuật toán nào sau đây (nếu được triển khai một cách điển hình) có độ phức tạp thời gian O(n) trong trường hợp xấu nhất?

Tìm kiếm tuyến tính (Linear Search)

Tìm kiếm nhị phân (Binary Search)

Sắp xếp chọn (Selection Sort)

Sắp xếp nổi bọt (Bubble Sort)

Tìm kiếm tuyến tính duyệt qua từng phần tử của danh sách tuần tự cho đến khi tìm thấy mục tiêu hoặc duyệt hết danh sách. Trong trường hợp xấu nhất (phần tử ở cuối hoặc không có), nó cần duyệt n phần tử, do đó có độ phức tạp O(n). Sắp xếp chọn và sắp xếp nổi bọt điển hình là O(n^2), tìm kiếm nhị phân là O(log n).

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 7: Một thuật toán được mô tả có thời gian chạy là T(n) = 5n^2 + 2n + 10. Độ phức tạp thời gian của thuật toán này theo ký hiệu Big O là gì?

O(n)

O(n^2)

O(n^3)

O(1)

Để xác định độ phức tạp Big O, ta chỉ giữ lại số hạng có bậc cao nhất và bỏ qua hằng số. Số hạng bậc cao nhất là 5n^2. Bỏ qua hằng số 5, ta được O(n^2).

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 8: Xem xét đoạn mã giả sau:
```
a = 10
b = 20
if a > b:
print(a)
else:
print(b)
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(log n)

O(n^2)

O(1)

Đoạn mã chỉ chứa các phép gán, so sánh và in đơn giản. Số lượng thao tác không phụ thuộc vào kích thước đầu vào 'n' (nếu có). Do đó, thời gian chạy là hằng số, được biểu diễn là O(1).

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 9: Khi so sánh hiệu suất của hai thuật toán có độ phức tạp O(n log n) và O(n^2) với cùng một kích thước đầu vào n rất lớn, thuật toán nào thường được ưu tiên hơn?

Thuật toán O(n log n) vì nó tăng trưởng chậm hơn O(n^2).

Thuật toán O(n^2) vì nó có số mũ cao hơn.

Cả hai đều có hiệu suất tương đương khi n lớn.

Không thể so sánh nếu không biết các hằng số cụ thể.

Đối với n đủ lớn, hàm n log n tăng chậm hơn đáng kể so với hàm n^2. Do đó, thuật toán có độ phức tạp O(n log n) sẽ chạy nhanh hơn và hiệu quả hơn so với thuật toán có độ phức tạp O(n^2).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 10: Quy tắc nhân trong tính độ phức tạp thời gian của thuật toán được áp dụng trong trường hợp nào?

Khi hai khối lệnh được thực hiện nối tiếp.

Khi chọn một trong hai nhánh của câu lệnh điều kiện (if-else).

Khi một cấu trúc lặp (hoặc thuật toán) nằm bên trong một cấu trúc lặp khác.

Khi tính tổng thời gian của tất cả các phép toán đơn lẻ.

Quy tắc nhân được sử dụng khi một khối lệnh (hoặc một thuật toán) được thực hiện lặp đi lặp lại bên trong một cấu trúc lặp, hoặc khi hai khối lệnh/thuật toán lồng nhau. Độ phức tạp tổng thể là tích độ phức tạp của các phần lồng nhau.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 11: Xem xét đoạn mã giả sau:
```
for i = 1 to n:
// Thực hiện một phép toán cơ bản (O(1))
for j = 1 to n*n:
// Thực hiện một phép toán cơ bản (O(1))
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n log n)

O(n^3)

O(n^2)

Đoạn mã gồm hai vòng lặp thực hiện nối tiếp. Vòng lặp đầu tiên tốn O(n) thời gian. Vòng lặp thứ hai tốn O(n^2) thời gian. Áp dụng quy tắc cộng, độ phức tạp tổng thể là max(O(n), O(n^2)) = O(n^2).

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 12: Độ phức tạp O(1) nghĩa là gì?

Thời gian chạy là một hằng số, không phụ thuộc vào kích thước đầu vào n.

Thời gian chạy tăng tuyến tính với n.

Thời gian chạy tăng theo logarit của n.

Thời gian chạy là rất nhanh.

O(1) biểu thị độ phức tạp hằng số, nghĩa là thời gian chạy của thuật toán không thay đổi đáng kể khi kích thước đầu vào (n) thay đổi. Số lượng thao tác là một hằng số, không phụ thuộc vào n.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 13: Thuật toán sắp xếp nào sau đây thường có độ phức tạp thời gian O(n log n) trong trường hợp trung bình và xấu nhất?

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp trộn (Merge Sort)

Sắp xếp chọn (Selection Sort)

Các thuật toán sắp xếp hiệu quả dựa trên kỹ thuật chia để trị như Merge Sort (Sắp xếp trộn) và Heap Sort (Sắp xếp vun đống), cũng như Quick Sort (Sắp xếp nhanh) trong trường hợp trung bình, có độ phức tạp O(n log n). Sắp xếp nổi bọt và sắp xếp chèn là O(n^2).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 14: Tại sao việc đánh giá độ phức tạp thời gian lại quan trọng trong việc phát triển phần mềm, đặc biệt là khi xử lý dữ liệu lớn?

Chỉ để biết thuật toán nào viết ngắn gọn hơn.

Để dự đoán và lựa chọn thuật toán hiệu quả nhất khi xử lý dữ liệu có kích thước lớn.

Để xác định số lượng dòng mã trong chương trình.

Để kiểm tra chương trình có lỗi cú pháp hay không.

Độ phức tạp thời gian giúp dự đoán hiệu suất của thuật toán khi kích thước dữ liệu tăng lên. Với dữ liệu lớn, sự khác biệt giữa các độ phức tạp khác nhau (ví dụ: O(n) vs O(n^2)) có thể là rất lớn, ảnh hưởng trực tiếp đến khả năng mở rộng và tốc độ xử lý của ứng dụng.

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 15: Xem xét đoạn mã giả sau:
```
for i = 1 to n:
for j = 1 to 10:
// Thực hiện một phép toán cơ bản (O(1))
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(10n)

O(n^2)

O(1)

Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy 10 lần (một hằng số) cho mỗi lần lặp của vòng ngoài. Tổng số thao tác là n * 10. Khi sử dụng ký hiệu Big O, hằng số bị bỏ qua, nên độ phức tạp là O(n).

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 16: Hàm nào sau đây tăng trưởng nhanh nhất khi n tiến tới vô cùng?

O(n)

O(n^2)

O(n log n)

O(2^n)

Khi n rất lớn, hàm mũ (2^n) tăng trưởng nhanh hơn nhiều so với bất kỳ hàm đa thức nào (n^k) hoặc hàm logarit (log n). O(1) là hằng số, O(n) là tuyến tính, O(n log n) tăng nhanh hơn O(n) nhưng chậm hơn O(n^2), O(n^2) là đa thức bậc 2, còn O(2^n) là hàm mũ.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 17: Giả sử bạn có hai thuật toán để giải cùng một bài toán. Thuật toán A có độ phức tạp O(n log n), thuật toán B có độ phức tạp O(n^1.5). Với n đủ lớn, thuật toán nào có khả năng chạy nhanh hơn?

Thuật toán A (O(n log n))

Thuật toán B (O(n^1.5))

Cả hai có hiệu suất tương đương.

Không thể xác định mà không biết các hằng số cụ thể.

Để so sánh n log n và n^1.5, ta có thể chia cả hai cho n (với n > 0) để so sánh log n và n^0.5 (hay căn bậc hai của n). Khi n đủ lớn (ví dụ n > 256), log n tăng chậm hơn đáng kể so với căn bậc hai của n. Do đó, n log n tăng chậm hơn n^1.5. Thuật toán A (O(n log n)) sẽ chạy nhanh hơn.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 18: Khi phân tích độ phức tạp thời gian của một thuật toán chứa câu lệnh điều kiện (if-else), ta thường xét trường hợp nào để đánh giá bằng Big O?

Trường hợp tốt nhất (nhánh có thời gian chạy ít nhất).

Thời gian chạy trung bình của cả hai nhánh.

Trường hợp xấu nhất (nhánh có thời gian chạy lớn nhất).

Tổng thời gian chạy của cả hai nhánh.

Ký hiệu Big O thường biểu thị cận trên hoặc trường hợp xấu nhất. Do đó, khi có câu lệnh điều kiện, ta xét nhánh có thời gian chạy lớn nhất để đảm bảo đánh giá được hiệu suất trong tình huống tốn kém nhất.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 19: Xem xét đoạn mã giả sau:
```
i = 1
while i < n: // Thực hiện một phép toán cơ bản (O(1)) i = i * 2 ``` Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(log n)

O(n^2)

O(1)

Biến điều khiển vòng lặp (i) bắt đầu từ 1 và nhân đôi sau mỗi lần lặp (1, 2, 4, 8, ..., 2^k). Vòng lặp dừng khi 2^k >= n. Số lần lặp k thỏa mãn k >= log₂(n). Do đó, số lần lặp tỷ lệ với log n. Độ phức tạp là O(log n).

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 20: Độ phức tạp thời gian của việc truy cập một phần tử theo chỉ số trong một mảng (ví dụ: `arr[i]`) là bao nhiêu?

O(n)

O(log n)

O(n^2)

O(1)

Trong hầu hết các ngôn ngữ lập trình, truy cập một phần tử tại một chỉ số cụ thể trong mảng là một thao tác mất thời gian hằng số. Địa chỉ bộ nhớ của phần tử có thể được tính trực tiếp từ chỉ số và địa chỉ cơ sở của mảng, không phụ thuộc vào kích thước của mảng.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 21: Mục đích chính của việc đánh giá độ phức tạp thời gian của thuật toán là gì?

Để so sánh hiệu quả của các thuật toán một cách độc lập với phần cứng cụ thể và kích thước dữ liệu.

Để tìm ra lỗi logic trong thuật toán.

Để xác định ngôn ngữ lập trình nào là tốt nhất.

Để đo thời gian chạy thực tế trên một máy tính cụ thể.

Mục đích chính là có một cách tiêu chuẩn để so sánh hiệu quả của c??c thuật toán khác nhau cho cùng một bài toán, đặc biệt là khi xử lý với lượng dữ liệu lớn, và dự đoán cách thời gian chạy sẽ thay đổi khi kích thước đầu vào tăng lên.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 22: Cho hai thuật toán, một có độ phức tạp O(n) và một có độ phức tạp O(n log n). Khi n rất nhỏ (ví dụ n = 10), thuật toán nào có thể nhanh hơn?

Thuật toán O(n log n).

Thuật toán O(n).

Cả hai đều chậm như nhau.

Không thể chắc chắn chỉ dựa vào Big O; hằng số có thể chi phối với n nhỏ.

Với n nhỏ, các hằng số và các số hạng bậc thấp bị bỏ qua trong phân tích Big O có thể đóng vai trò đáng kể. Thuật toán O(n log n) có thể có hằng số lớn hơn khiến nó chạy chậm hơn thuật toán O(n) khi n nhỏ. Phân tích Big O chủ yếu quan trọng khi n lớn.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 23: Xem xét đoạn mã giả sau:
```
for i = 1 to n:
// O(1) operation
for j = 1 to n:
for k = 1 to n:
// O(1) operation
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n^2)

O(n^3)

O(n log n)

Đoạn mã gồm hai khối lệnh thực hiện nối tiếp. Khối đầu tiên là một vòng lặp đơn, tốn O(n). Khối thứ hai là hai vòng lặp lồng nhau, tốn O(n^2). Áp dụng quy tắc cộng, độ phức tạp tổng thể là max(O(n), O(n^2)) = O(n^2).

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 24: Độ phức tạp thời gian của việc thêm một phần tử vào cuối danh sách liên kết (linked list) đơn là bao nhiêu (giả sử bạn đã có con trỏ tới nút cuối cùng)?

O(1)

O(n)

O(log n)

O(n^2)

Nếu đã có con trỏ tới nút cuối cùng, việc thêm một nút mới chỉ bao gồm việc tạo nút mới, cập nhật con trỏ của nút cuối cùng hiện tại trỏ tới nút mới, và cập nhật con trỏ cuối cùng trỏ tới nút mới. Đây là một số thao tác cố định, không phụ thuộc vào số lượng phần tử n trong danh sách. Do đó, độ phức tạp là O(1).

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 25: Thuật toán nào sau đây có độ phức tạp thời gian O(n log n)?

Tìm kiếm tuyến tính.

Tìm kiếm nhị phân.

Sắp xếp nhanh (Quick Sort) trong trường hợp trung bình.

Sắp xếp chọn.

Quick Sort (sắp xếp nhanh) trong trường hợp trung bình có độ phức tạp O(n log n). Tìm kiếm tuyến tính là O(n), tìm kiếm nhị phân là O(log n), sắp xếp chọn là O(n^2).

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 26: Độ phức tạp thời gian O(n!) (n giai thừa) thuộc loại nào trong các loại độ phức tạp cơ bản?

Logarit.

Đa thức.

Mũ (Exponential).

Giai thừa (Factorial).

Độ phức tạp O(n!) tăng trưởng cực kỳ nhanh, nhanh hơn cả hàm mũ O(2^n). Đây là một ví dụ của độ phức tạp siêu đa thức (superpolynomial) hoặc chính xác hơn là giai thừa (factorial).

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 27: Khi phân tích độ phức tạp của một thuật toán đệ quy, phương pháp nào thường được sử dụng?

Sử dụng các phương pháp như Phương pháp Thầy (Master Theorem) hoặc cây đệ quy.

Chỉ cần đếm số lần hàm được gọi.

Luôn luôn là O(n).

Không thể phân tích độ phức tạp của thuật toán đệ quy.

Các phương pháp phổ biến để phân tích độ phức tạp của thuật toán đệ quy bao gồm: Phương pháp thay thế (Substitution Method), Phương pháp cây đệ quy (Recursion Tree Method), và Phương pháp Thầy (Master Theorem).

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 28: Cho một thuật toán có thời gian chạy T(n) = 2n + log n + 100. Độ phức tạp thời gian của thuật toán này theo ký hiệu Big O là gì?

O(log n)

O(n)

O(n log n)

O(1)

Để xác định độ phức tạp Big O, ta chỉ giữ lại số hạng có bậc cao nhất và bỏ qua hằng số. Số hạng 2n là bậc cao nhất (tuyến tính) so với log n (logarit) và 100 (hằng số). Bỏ qua hằng số 2, ta được O(n).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 29: Tại sao trong phân tích độ phức tạp Big O, chúng ta quan tâm đến hành vi khi n tiến tới vô cùng (asymptotic behavior)?

Vì nó giúp tính toán thời gian chạy chính xác cho bất kỳ n nào.

Vì nó chỉ quan trọng khi n là số nguyên tố.

Vì nó cho thấy cách hiệu suất thay đổi đối với các tập dữ liệu rất lớn, nơi sự khác biệt giữa các thuật toán trở nên rõ rệt.

Vì các thuật toán chỉ được sử dụng với dữ liệu vô hạn.

Hành vi tiệm cận mô tả cách hiệu suất của thuật toán thay đổi đối với các tập dữ liệu rất lớn. Đây là nơi sự khác biệt giữa các lớp độ phức tạp khác nhau trở nên rõ rệt nhất và là yếu tố then chốt quyết định khả năng mở rộng của thuật toán.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 30: Khi so sánh các độ phức tạp thời gian O(1), O(log n), O(n), O(n log n), O(n^2), sắp xếp theo thứ tự từ nhanh nhất đến chậm nhất (với n đủ lớn) là gì?

O(n^2), O(n log n), O(n), O(log n), O(1)

O(1), O(log n), O(n), O(n log n), O(n^2)

O(log n), O(1), O(n), O(n^2), O(n log n)

O(1), O(n), O(log n), O(n log n), O(n^2)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Thứ tự tăng trưởng tốc độ từ chậm nhất (nhanh nhất về thời gian chạy) đến nhanh nhất (chậm nhất về thời gian chạy) là: Hằng số (O(1)) -> Logarit (O(log n)) -> Tuyến tính (O(n)) -> Tuyến tính-Logarit (O(n log n)) -> Đa thức bậc 2 (O(n^2)).

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 02

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, tại sao chúng ta thường chỉ quan tâm đến số lượng các phép toán cơ bản (như gán, so sánh, cộng, trừ) thay vì thời gian thực thi chính xác trên một máy tính cụ thể?

Thời gian thực thi chính xác quá khó để đo lường.

Các phép toán cơ bản luôn mất cùng một lượng thời gian trên mọi máy tính.

Chỉ có các phép toán cơ bản mới ảnh hưởng đến hiệu suất thuật toán.

Số lượng phép toán cơ bản cung cấp ước lượng hiệu suất độc lập với phần cứng và môi trường thực thi.

Câu hỏi kiểm tra sự hiểu biết về mục đích của phân tích độ phức tạp thời gian. Thời gian thực thi chính xác phụ thuộc vào nhiều yếu tố bên ngoài (tốc độ CPU, ngôn ngữ lập trình, hệ điều hành...), trong khi số phép toán cơ bản cung cấp một thước đo độc lập với phần cứng và môi trường, cho phép so sánh hiệu quả của thuật toán một cách tổng quát khi kích thước đầu vào lớn.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 2: Độ phức tạp thời gian O(n) mô tả mối quan hệ giữa thời gian thực thi và kích thước đầu vào n như thế nào?

Thời gian thực thi không đổi khi n tăng.

Thời gian thực thi tăng tỷ lệ thuận (tuyến tính) với n.

Thời gian thực thi tăng theo hàm bình phương của n.

Thời gian thực thi tăng theo hàm logarit của n.

Câu hỏi kiểm tra định nghĩa và ý nghĩa của ký hiệu Big O(n). O(n) biểu thị thời gian thực thi tăng tuyến tính với kích thước đầu vào n.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 3: Cho đoạn mã giả sau:

```
function process(arr, n):
sum = 0
for i from 0 to n-1:
sum = sum + arr[i]
return sum
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu, với n là kích thước của mảng `arr`?

O(1)

O(log n)

O(n)

O(n^2)

Câu hỏi yêu cầu phân tích đoạn mã có vòng lặp đơn. Vòng lặp chạy n lần, mỗi lần thực hiện một số phép toán cơ bản (cộng, gán). Các phép toán bên ngoài vòng lặp là hằng số. Do đó, thời gian thực thi tỷ lệ thuận với n.

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 4: Cho đoạn mã giả sau:

```
function find_max(arr, n):
max_val = arr[0]
for i from 1 to n-1:
if arr[i] > max_val:
max_val = arr[i]
return max_val
```

Độ phức tạp thời gian của đoạn mã này trong trường hợp xấu nhất (worst-case) là bao nhiêu, với n là kích thước của mảng `arr`?

O(1)

O(log n)

O(n)

O(n log n)

Câu hỏi yêu cầu phân tích đoạn mã tìm giá trị lớn nhất. Vòng lặp chạy n-1 lần (từ i=1 đến n-1). Trong mỗi lần lặp, có một phép so sánh và có thể có một phép gán. Số lần lặp tỷ lệ tuyến tính với n. Do đó, độ phức tạp là O(n).

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 5: Thuật toán tìm kiếm nhị phân trên một mảng đã được sắp xếp có độ phức tạp thời gian là O(log n). Điều này có nghĩa là gì?

Thời gian tìm kiếm tăng gấp đôi khi kích thước mảng tăng gấp đôi.

Thời gian tìm kiếm giảm đi một nửa khi kích thước mảng tăng gấp đôi.

Thời gian tìm kiếm tăng theo bình phương của kích thước mảng.

Thời gian tìm kiếm tăng rất chậm khi kích thước mảng tăng lên đáng kể.

Câu hỏi kiểm tra sự hiểu biết về ý nghĩa của độ phức tạp logarit. O(log n) nghĩa là khi kích thước đầu vào n tăng lên, thời gian thực thi tăng rất chậm, tỷ lệ với logarit của n. Ví dụ, nếu n tăng gấp đôi, thời gian chỉ tăng thêm một lượng hằng số.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 6: Cho đoạn mã giả sau:

```
function print_pairs(arr, n):
for i from 0 to n-1:
for j from 0 to n-1:
print(arr[i], arr[j])
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu, với n là kích thước của mảng `arr`?

O(n)

O(n log n)

O(log n)

O(n^2)

Câu hỏi yêu cầu phân tích đoạn mã có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần. Vòng lặp trong cũng chạy n lần cho MỖI lần lặp của vòng ngoài. Tổng số lần in (phép toán cơ bản) là n * n = n^2. Do đó, độ phức tạp là O(n^2).

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 7: Khi so sánh hai thuật toán A có độ phức tạp O(n) và thuật toán B có độ phức tạp O(n^2) để giải cùng một bài toán với kích thước đầu vào n rất lớn, thuật toán nào thường được ưu tiên hơn và vì sao?

Thuật toán A (O(n)) vì thời gian thực thi tăng chậm hơn nhiều so với O(n^2) khi n lớn.

Thuật toán B (O(n^2)) vì nó có thể xử lý dữ liệu lớn hơn.

Cả hai thuật toán đều có hiệu quả như nhau với n lớn.

Không thể xác định chỉ dựa vào độ phức tạp Big O.

Câu hỏi kiểm tra khả năng so sánh các bậc độ phức tạp khác nhau. Với n lớn, hàm bậc thấp hơn (n) sẽ tăng chậm hơn nhiều so với hàm bậc cao hơn (n^2). Do đó, thuật toán có độ phức tạp O(n) sẽ hiệu quả hơn đáng kể.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 8: Quy tắc cộng trong phân tích độ phức tạp thời gian được áp dụng khi nào?

Khi các khối lệnh hoặc hàm được thực thi nối tiếp nhau.

Khi có các vòng lặp lồng nhau.

Khi các khối lệnh hoặc hàm được thực thi song song.

Khi kích thước đầu vào được chia nhỏ.

Câu hỏi kiểm tra kiến thức về quy tắc cộng. Quy tắc cộng áp dụng khi các phần của thuật toán được thực thi NỐI TIẾP nhau. Độ phức tạp tổng thể là độ phức tạp của phần chiếm ưu thế nhất (bậc cao nhất).

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 9: Quy tắc nhân trong phân tích độ phức tạp thời gian được áp dụng khi nào?

Khi các khối lệnh được thực thi nối tiếp nhau.

Khi một khối lệnh (hoặc vòng lặp) được thực hiện bên trong một cấu trúc lặp khác.

Khi thuật toán sử dụng phép nhân số học.

Khi kết hợp độ phức tạp của hai thuật toán khác nhau.

Câu hỏi kiểm tra kiến thức về quy tắc nhân. Quy tắc nhân áp dụng khi một khối lệnh hoặc vòng lặp được thực thi NHIỀU LẦN bên trong một cấu trúc lặp khác (ví dụ: vòng lặp lồng nhau) hoặc khi một hàm được gọi bên trong một vòng lặp.

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 10: Cho đoạn mã giả sau:

```
function example(n):
for i from 1 to 100:
print(i)
for j from 1 to n:
print(j)
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(1)

O(100)

O(n)

O(100n)

Câu hỏi yêu cầu áp dụng quy tắc cộng. Đoạn mã có hai phần thực thi nối tiếp. Phần đầu là vòng lặp cố định 100 lần, có độ phức tạp O(1) (hằng số, không phụ thuộc vào n). Phần sau là vòng lặp chạy n lần, có độ phức tạp O(n). Áp dụng quy tắc cộng, O(1) + O(n) = O(n) vì O(n) có bậc cao hơn.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 11: Thuật toán nào sau đây thường có độ phức tạp thời gian tốt nhất (hiệu quả nhất) khi kích thước đầu vào n rất lớn?

O(1)

O(log n)

O(n)

O(n log n)

Câu hỏi kiểm tra sự so sánh các bậc độ phức tạp phổ biến. O(1) là bậc thấp nhất, biểu thị thời gian hằng số, là hiệu quả nhất.

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 12: Độ phức tạp thời gian O(n^2) thường xuất hiện trong các thuật toán có cấu trúc như thế nào?

Chỉ có các phép toán cơ bản.

Một vòng lặp đơn chạy n lần.

Hai vòng lặp lồng nhau, mỗi vòng lặp chạy khoảng n lần.

Sử dụng đệ quy chia đôi.

Câu hỏi kiểm tra nhận biết cấu trúc mã dẫn đến độ phức tạp O(n^2). Cấu trúc phổ biến nhất là hai vòng lặp lồng nhau, mỗi vòng lặp chạy khoảng n lần.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 13: Tại sao các hằng số và các thành phần bậc thấp thường bị bỏ qua trong ký hiệu Big O?

Chúng không ảnh hưởng đến thời gian thực thi.

Khi n rất lớn, thành phần bậc cao nhất chi phối sự tăng trưởng của hàm thời gian.

Việc tính toán chúng rất phức tạp.

Chúng chỉ quan trọng trong trường hợp tốt nhất.

Câu hỏi kiểm tra sự hiểu biết về bản chất của ký hiệu Big O. Big O quan tâm đến hành vi tiệm cận của hàm thời gian khi n tiến tới vô cùng. Khi n rất lớn, các hằng số và các thành phần bậc thấp trở nên không đáng kể so với thành phần bậc cao nhất.

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 14: Cho đoạn mã giả sau:

```
function example(arr, n):
if n <= 1: return // Chia mảng làm đôi mid = n / 2 left_half = arr[0...mid-1] right_half = arr[mid...n-1] // Gọi đệ quy trên hai nửa example(left_half, mid) example(right_half, n - mid) // Các thao tác kết hợp (ví dụ: trộn mảng đã sắp xếp) // ... (thực hiện trong thời gian O(n)) ``` Đây là cấu trúc của một thuật toán 'chia để trị' điển hình (ví dụ: Merge Sort). Độ phức tạp thời gian của các thuật toán dạng này thường là bao nhiêu?

O(n^2)

O(n)

O(log n)

O(n log n)

Câu hỏi kiểm tra nhận biết độ phức tạp của các thuật toán 'chia để trị' phổ biến như Merge Sort. Cấu trúc chia đôi và kết hợp tuyến tính dẫn đến độ phức tạp O(n log n).

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 15: Tại sao việc đánh giá độ phức tạp thời gian (và không gian) của thuật toán lại quan trọng trong việc phát triển phần mềm?

Giúp dự đoán hiệu suất của chương trình với các bộ dữ liệu đầu vào lớn và so sánh hiệu quả giữa các thuật toán khác nhau.

Chỉ cần thiết khi lập trình trên các hệ thống nhúng với bộ nhớ hạn chế.

Là yêu cầu bắt buộc của mọi ngôn ngữ lập trình hiện đại.

Chỉ giúp tìm ra lỗi logic trong mã nguồn.

Câu hỏi kiểm tra ý nghĩa thực tế của việc phân tích thuật toán. Việc này giúp dự đoán hiệu suất khi dữ liệu lớn, so sánh các giải pháp khác nhau và chọn ra giải pháp hiệu quả nhất, đặc biệt quan trọng khi tài nguyên (thời gian, bộ nhớ) bị hạn chế.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 16: Cho đoạn mã giả:

```
function example(n):
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(log n)

O(n^2)

O(1)

Câu hỏi yêu cầu phân tích vòng lặp với biến điều khiển tăng theo cấp số nhân (nhân 2). Số lần lặp cần thiết để `i` đạt đến `n` là k, sao cho 2^k >= n. Điều này tương đương với k >= log₂(n). Do đó, số lần lặp tỷ lệ với log n.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 17: Thuật toán nào dưới đây, khi triển khai một cách cơ bản, thường có độ phức tạp thời gian là O(n^2)?

Sắp xếp chọn (Selection Sort)

Tìm kiếm nhị phân (Binary Search)

Sắp xếp trộn (Merge Sort)

Sắp xếp nhanh (Quick Sort) - trung bình

Câu hỏi kiểm tra kiến thức về độ phức tạp của các thuật toán sắp xếp cơ bản. Sắp xếp chọn (Selection Sort) và Sắp xếp nổi bọt (Bubble Sort) có cấu trúc hai vòng lặp lồng nhau, dẫn đến độ phức tạp O(n^2).

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 18: Giả sử một thuật toán có độ phức tạp thời gian là T(n) = 5n^2 + 3n + 10. Khi sử dụng ký hiệu Big O để biểu diễn độ phức tạp, kết quả đúng là gì?

O(n)

O(5n^2)

O(n^2 + n)

O(n^2)

Câu hỏi kiểm tra cách áp dụng quy tắc bỏ qua hằng số và các thành phần bậc thấp trong Big O. Thành phần bậc cao nhất là 5n^2. Bỏ hằng số 5, ta được O(n^2).

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 19: Trường hợp tốt nhất (best-case) của một thuật toán là gì?

Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian ngắn nhất.

Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian dài nhất.

Bộ dữ liệu đầu vào trung bình.

Trường hợp thuật toán không có lỗi.

Câu hỏi kiểm tra khái niệm trường hợp tốt nhất. Trường hợp tốt nhất là bộ dữ liệu đầu vào mà thuật toán thực thi nhanh nhất.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 20: Trường hợp xấu nhất (worst-case) của một thuật toán là gì?

Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian ngắn nhất.

Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian dài nhất.

Bộ dữ liệu đầu vào trung bình.

Trường hợp thuật toán hoạt động chính xác.

Câu hỏi kiểm tra khái niệm trường hợp xấu nhất. Trường hợp xấu nhất là bộ dữ liệu đầu vào mà thuật toán thực thi chậm nhất. Phân tích Big O thường tập trung vào trường hợp xấu nhất để đảm bảo hiệu suất không vượt quá giới hạn đó.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 21: Cho đoạn mã giả:

```
function example(n):
sum = 0
for i from 1 to n:
sum = sum + i
j = 1
while j < n: print(j) j = j * 3 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(log n)

O(n log n)

O(n)

O(n + log n)

Câu hỏi yêu cầu áp dụng quy tắc cộng cho hai phần nối tiếp. Phần đầu là vòng lặp chạy n lần (O(n)). Phần thứ hai là vòng lặp với biến tăng theo cấp số nhân (nhân 3), có độ phức tạp O(log₃ n), hay O(log n). Áp dụng quy tắc cộng: O(n) + O(log n) = O(n) vì O(n) có bậc cao hơn.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 22: Thuật toán tìm kiếm tuyến tính (Linear Search) trên một mảng 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?

O(1)

O(log n)

O(n)

O(n^2)

Câu hỏi kiểm tra độ phức tạp của tìm kiếm tuyến tính. Trong trường hợp xấu nhất (phần tử cần tìm ở cuối mảng hoặc không có trong mảng), thuật toán phải duyệt qua tất cả n phần tử. Do đó, độ phức tạp là O(n).

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 23: Độ phức tạp thời gian O(1) có nghĩa là gì?

Thời gian thực thi không thay đổi khi kích thước đầu vào n thay đổi.

Thời gian thực thi tăng tuyến tính với n.

Thời gian thực thi là 1 đơn vị.

Thuật toán rất nhanh.

Câu hỏi kiểm tra ý nghĩa của O(1). O(1) biểu thị thời gian thực thi là hằng số, không phụ thuộc vào kích thước đầu vào n.

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 24: Cho đoạn mã giả:

```
function example(n):
for i from 1 to n:
for j from 1 to i:
print(i, j)
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(log n)

O(n^2)

Câu hỏi yêu cầu phân tích vòng lặp lồng nhau với giới hạn bên trong phụ thuộc vào biến lặp bên ngoài. Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy 1 lần (khi i=1), 2 lần (khi i=2), ..., n lần (khi i=n). Tổng số lần thực hiện phép in là 1 + 2 + ... + n = n*(n+1)/2, là một hàm bậc hai của n. Do đó, độ phức tạp là O(n^2).

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 25: Khi phân tích độ phức tạp thời gian của thuật toán, 'kích thước đầu vào' (input size) n thường được định nghĩa là gì?

Số dòng mã lệnh của chương trình.

Một tham số đo lường quy mô của dữ liệu mà thuật toán xử lý (ví dụ: số phần tử, số bit).

Thời gian chạy thực tế của chương trình.

Số lượng biến được sử dụng trong thuật toán.

Câu hỏi kiểm tra khái niệm kích thước đầu vào. Kích thước đầu vào là một tham số đo lường quy mô của dữ liệu mà thuật toán xử lý, ví dụ: số phần tử trong mảng, số đỉnh/cạnh của đồ thị, số chữ số của số.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 26: Giả sử bạn có hai thuật toán để giải quyết một bài toán: Thuật toán X có độ phức tạp O(n log n) và Thuật toán Y có độ phức tạp O(n^2). Với n = 1000, thuật toán nào có khả năng chạy nhanh hơn và tại sao?

Thuật toán X (O(n log n)) vì n log n tăng chậm hơn nhiều so với n^2 khi n lớn.

Thuật toán Y (O(n^2)) vì n^2 lớn hơn n log n.

Cả hai thuật toán sẽ chạy với tốc độ tương đương nhau.

Không thể xác định nếu không biết hằng số ẩn trong ký hiệu Big O.

Câu hỏi yêu cầu áp dụng kiến thức về so sánh bậc độ ph??c tạp. log₂(1000) xấp xỉ 10. n log n ≈ 1000 * 10 = 10000. n^2 = 1000^2 = 1000000. Rõ ràng 10000 << 1000000. Do đó, O(n log n) sẽ nhanh hơn O(n^2) với n=1000.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 27: Thuật toán sắp xếp nào dưới đây, khi triển khai hiệu quả, có độ phức tạp thời gian trung bình là O(n log n)?

Sắp xếp chèn (Insertion Sort)

Sắp xếp trộn (Merge Sort)

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chọn (Selection Sort)

Câu hỏi kiểm tra kiến thức về độ phức tạp của các thuật toán sắp xếp nâng cao. Sắp xếp trộn (Merge Sort) và Sắp xếp nhanh (Quick Sort - trung bình) có độ phức tạp O(n log n). Sắp xếp chèn (Insertion Sort) và Sắp xếp nổi bọt (Bubble Sort) là O(n^2).

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 28: Nếu một thuật toán có độ phức tạp thời gian là O(2^n), điều gì sẽ xảy ra với thời gian thực thi khi kích thước đầu vào n tăng lên một lượng nhỏ (ví dụ: tăng thêm 1 hoặc 2)?

Thời gian thực thi tăng tuyến tính.

Thời gian thực thi tăng logarit.

Thời gian thực thi tăng theo bình phương.

Thời gian thực thi tăng theo cấp số nhân (rất nhanh).

Câu hỏi kiểm tra sự hiểu biết về độ phức tạp mũ. O(2^n) tăng trưởng rất nhanh. Khi n tăng thêm 1, thời gian tăng gấp đôi (2^(n+1) = 2 * 2^n). Khi n tăng thêm 2, thời gian tăng gấp bốn lần (2^(n+2) = 4 * 2^n).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 29: Cho đoạn mã giả:

```
function example(arr, n):
if n <= 0: return 0 if n == 1: return arr[0] // Giả sử hàm sum_array_recursive(arr, n) tính tổng n phần tử // bằng cách gọi đệ quy trên n-1 phần tử và cộng thêm phần tử cuối. // Độ phức tạp của hàm này là O(n). return sum_array_recursive(arr, n) ``` Độ phức tạp thời gian của hàm `example` gọi `sum_array_recursive` như mô tả là bao nhiêu?

O(1)

O(log n)

O(n)

O(n^2)

Câu hỏi yêu cầu phân tích một hàm đơn giản gọi một hàm khác đã biết độ phức tạp. Hàm `example` chỉ thực hiện một vài phép so sánh (O(1)) rồi gọi hàm `sum_array_recursive` một lần. Độ phức tạp của `sum_array_recursive` là O(n). Áp dụng quy tắc cộng O(1) + O(n) = O(n).

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 30: Khi so sánh hiệu quả của hai thuật toán A (O(n log n)) và B (O(n^2)) cho một bài toán, có trường hợp nào mà thuật toán B có thể chạy nhanh hơn thuật toán A không?

Không bao giờ, vì O(n log n) luôn tốt hơn O(n^2).

Có thể, khi kích thước đầu vào n rất nhỏ, hằng số ẩn trong ký hiệu Big O có thể làm thay đổi kết quả so sánh.

Có thể, nhưng chỉ trong trường hợp tốt nhất của thuật toán B.

Chỉ khi thuật toán B được viết bằng ngôn ngữ lập trình nhanh hơn.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Câu hỏi kiểm tra sự hiểu biết sâu hơn về Big O. Big O mô tả hành vi tiệm cận khi n rất lớn. Đối với các giá trị n nhỏ, hằng số ẩn trong ký hiệu Big O có thể chi phối thời gian thực thi. Nếu thuật toán B có hằng số rất nhỏ và thuật toán A có hằng số rất lớn, B có thể nhanh hơn A cho các n nhỏ.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 03

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 1: Khái niệm 'độ phức tạp thời gian' của một thuật toán chủ yếu đo lường điều gì?

Tổng dung lượng bộ nhớ mà thuật toán sử dụng.

Số lượng dòng mã lệnh trong thuật toán.

Số lượng phép toán cơ bản mà thuật toán thực hiện, phụ thuộc vào kích thước đầu vào.

Thời gian chạy thực tế của thuật toán trên một máy tính cụ thể.

Độ phức tạp thời gian đo lường số lượng phép toán cơ bản mà thuật toán thực hiện, từ đó ước tính thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào thay đổi. Nó tập trung vào cách thời gian chạy *tăng trưởng* theo kích thước đầu vào.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 2: Tại sao khi đánh giá độ phức tạp thời gian bằng ký hiệu Big O (O), chúng ta thường chỉ quan tâm đến hạng tử có bậc cao nhất và bỏ qua các hệ số hằng?

Vì khi kích thước đầu vào rất lớn, hạng tử có bậc cao nhất sẽ chi phối tốc độ tăng trưởng của hàm thời gian.

Vì các hệ số hằng và hạng tử bậc thấp không ảnh hưởng đến thời gian chạy thực tế.

Để làm cho việc tính toán độ phức tạp trở nên đơn giản hơn.

Vì chúng ta chỉ quan tâm đến trường hợp xấu nhất của thuật toán.

Ký hiệu Big O tập trung vào hành vi tiệm cận của thuật toán khi kích thước đầu vào (n) trở nên rất lớn. Đối với n lớn, hạng tử có bậc cao nhất sẽ tăng trưởng nhanh hơn đáng kể so với các hạng tử bậc thấp hơn và các hệ số hằng, do đó nó chi phối tổng thời gian chạy.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 3: Xét đoạn mã giả sau:
```
a = 10
b = 20
if n > 0:
for i from 1 to n:
c = a + b
```
Với `n` là kích thước đầu vào, độ phức tạp thời gian của đoạn mã này là gì?

O(1)

O(log n)

O(n)

O(n^2)

Các lệnh gán `a = 10` và `b = 20` là các phép toán hằng số (O(1)). Lệnh `if n > 0` cũng là O(1). Vòng lặp `for i from 1 to n` chạy `n` lần. Bên trong vòng lặp, lệnh `c = a + b` là O(1). Tổng thời gian là O(1) + O(1) + O(1) + n * O(1) = O(n). Khi n lớn, hạng tử O(n) chi phối.

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 4: Xét đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
for j from 1 to n:
sum = sum + 1
```
Với `n` là kích thước đầu vào, độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n log n)

O(n^3)

O(n^2)

Lệnh gán `sum = 0` là O(1). Vòng lặp ngoài chạy `n` lần. Vòng lặp trong chạy `n` lần cho *mỗi* lần chạy của vòng lặp ngoài. Lệnh `sum = sum + 1` bên trong là O(1). Tổng số lần thực hiện lệnh bên trong vòng lặp lồng nhau là n * n = n^2. Do đó, độ phức tạp là O(n^2).

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 5: Cho hai thuật toán A và B lần lượt có độ phức tạp thời gian là O(n log n) và O(n^2). Khi kích thước đầu vào `n` tăng lên rất lớn, thuật toán nào sẽ có hiệu suất (thời gian chạy) tốt hơn?

Thuật toán A (O(n log n)) vì n log n tăng trưởng chậm hơn n^2.

Thuật toán B (O(n^2)) vì n^2 là bậc cao hơn.

Cả hai thuật toán có hiệu suất tương đương cho n lớn.

Không thể xác định nếu không biết hệ số hằng của mỗi thuật toán.

Để so sánh hiệu suất cho n lớn, ta so sánh tốc độ tăng trưởng của các hàm độ phức tạp. Hàm n log n tăng trưởng chậm hơn hàm n^2. Do đó, thuật toán có độ phức tạp O(n log n) sẽ chạy nhanh hơn thuật toán có độ phức tạp O(n^2) khi n lớn.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 6: Quy tắc cộng trong phân tích độ phức tạp thời gian được áp dụng khi nào?

Khi có các vòng lặp lồng nhau.

Khi các khối lệnh hoặc các phần của thuật toán được thực hiện một cách tuần tự.

Khi một hàm gọi một hàm khác.

Khi phân tích độ phức tạp không phụ thuộc vào kích thước đầu vào.

Quy tắc cộng được áp dụng khi một thuật toán bao gồm nhiều phần (hoặc các khối lệnh) được thực hiện một cách tuần tự (nối tiếp nhau). Độ phức tạp tổng thể sẽ là độ phức tạp của phần có bậc cao nhất.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 7: Quy tắc nhân trong phân tích độ phức tạp thời gian được áp dụng khi nào?

Khi một khối lệnh được thực hiện lặp đi lặp lại bên trong một cấu trúc lặp (ví dụ: vòng lặp lồng nhau).

Khi các khối lệnh được thực hiện tuần tự.

Khi so sánh độ phức tạp của hai thuật toán khác nhau.

Khi thuật toán sử dụng bộ nhớ phụ trợ.

Quy tắc nhân được áp dụng khi một khối lệnh (hoặc một thuật toán con) được thực hiện lặp đi lặp lại nhiều lần, ví dụ như trong cấu trúc vòng lặp, đặc biệt là vòng lặp lồng nhau.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 8: Độ phức tạp thời gian O(1) có ý nghĩa gì?

Thời gian chạy tăng tuyến tính với kích thước đầu vào n.

Thời gian chạy tăng theo logarit của kích thước đầu vào n.

Thời gian chạy tăng theo bình phương của kích thước đầu vào n.

Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào n.

Độ phức tạp O(1) (hằng số) có nghĩa là thời gian thực hiện của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào (n). Số lượng phép toán là cố định, không thay đổi dù n lớn hay nhỏ.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 9: Thuật toán tìm kiếm nhị phân (Binary Search) trên một 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)

Tìm kiếm nhị phân hoạt động bằng cách liên tục chia đôi phạm vi tìm kiếm. Số lần chia đôi một tập hợp kích thước n cho đến khi còn 1 phần tử là log₂n. Do đó, độ phức tạp thời gian là O(log n).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 10: Xét đoạn mã giả sau:
```
result = 0
for i from 1 to 100:
result = result + i
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(1)

O(n)

O(100)

O(log n)

Vòng lặp `for i from 1 to 100` chạy một số lần cố định (100 lần), không phụ thuộc vào biến `n` (kích thước đầu vào). Lệnh bên trong vòng lặp là O(1). Do đó, tổng thời gian là 100 * O(1) = O(100), mà trong ký hiệu Big O, các hằng số được bỏ qua. Độ phức tạp là O(1).

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 11: Khi phân tích độ phức tạp thời gian của một thuật toán, 'trường hợp xấu nhất' (worst-case) thường được quan tâm nhất vì lý do gì?

Vì nó dễ phân tích hơn trường hợp trung bình và tốt nhất.

Vì nó xảy ra thường xuyên nhất trong thực tế.

Vì nó cung cấp giới hạn trên về thời gian chạy, đảm bảo thuật toán không bao giờ vượt quá hiệu suất đó.

Vì nó giúp so sánh thuật toán trên các bộ dữ liệu khác nhau.

Phân tích trường hợp xấu nhất cung cấp một giới hạn trên (upper bound) cho thời gian chạy của thuật toán. Điều này đảm bảo rằng thuật toán sẽ không bao giờ mất nhiều thời gian hơn giới hạn này, cho phép chúng ta đưa ra cam kết về hiệu suất tối đa mà người dùng có thể gặp phải.

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 12: Một thuật toán có độ phức tạp thời gian O(n log n). Điều này có nghĩa là gì về mối quan hệ giữa thời gian chạy và kích thước đầu vào n?

Thời gian chạy tăng tuyến tính với n.

Thời gian chạy tăng theo n nhân với logarit của n.

Thời gian chạy tăng theo bình phương của n.

Thời gian chạy là hằng số.

Độ phức tạp O(n log n) có nghĩa là thời gian chạy của thuật toán tăng trưởng tỷ lệ với n nhân với logarit của n. Tốc độ tăng trưởng này nhanh hơn O(n) nhưng chậm hơn O(n^2).

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 13: Xét đoạn mã giả sau:
```
for i from 1 to n:
j = 1
while j < n: print(i, j) j = j * 2 ``` Với `n` là kích thước đầu vào, độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n^2)

O(n log n)

O(log n)

Vòng lặp ngoài chạy `n` lần. Vòng lặp trong (while) bắt đầu với `j=1` và nhân đôi `j` sau mỗi lần lặp cho đến khi `j >= n`. Số lần lặp của vòng while là số lần cần thiết để 2^k >= n, tức là k >= log₂n. Do đó, vòng while chạy O(log n) lần. Tổng thời gian là n * O(log n) = O(n log n).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 14: Thuật toán sắp xếp chọn (Selection Sort) 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 log n)

O(n^2)

Sắp xếp chọn hoạt động bằng cách lặp qua mảng n lần. Trong mỗi lần lặp thứ i, nó tìm phần tử nhỏ nhất trong phần còn lại của mảng (kích thước n-i) và đổi chỗ với phần tử ở vị trí i. Việc tìm phần tử nhỏ nhất trong n-i phần tử mất O(n-i) thời gian. Tổng thời gian là (n-1) + (n-2) + ... + 1, là một cấp số cộng có tổng O(n^2).

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 15: Cho một thuật toán có hàm thời gian T(n) = 5n³ + 20n² + 100. Độ phức tạp thời gian của thuật toán này theo ký hiệu Big O là gì?

O(n³)

O(n²)

O(n)

O(1)

Khi sử dụng ký hiệu Big O, ta chỉ giữ lại hạng tử có bậc cao nhất và bỏ qua các hệ số hằng. Trong hàm T(n) = 5n³ + 20n² + 100, hạng tử có bậc cao nhất là 5n³. Bỏ qua hệ số 5, ta được O(n³).

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 16: Một thuật toán có độ phức tạp O(2^n). Điều này có ý nghĩa gì đối với việc sử dụng thuật toán này với kích thước đầu vào `n` lớn?

Thuật toán rất hiệu quả và có thể xử lý dữ liệu lớn dễ dàng.

Thời gian chạy tăng trưởng tuyến tính, nên phù hợp với mọi kích thước đầu vào.

Thời gian chạy tăng trưởng rất nhanh (theo cấp số mũ), khiến thuật toán không khả thi cho các giá trị n lớn.

Thuật toán có thời gian chạy hằng số, không phụ thuộc vào n.

Độ phức tạp O(2^n) là độ phức tạp mũ, tăng trưởng cực kỳ nhanh. Ngay cả với các giá trị n tương đối nhỏ (ví dụ: n=40, n=50), thời gian chạy sẽ trở nên không thể chấp nhận được trên các máy tính hiện đại. Thuật toán này chỉ khả thi cho các giá trị n rất nhỏ.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 17: Khi phân tích độ phức tạp của một cấu trúc điều kiện (if-else), độ phức tạp tổng thể thường được tính bằng cách nào?

Bằng tổng độ phức tạp của nhánh if và nhánh else.

Bằng độ phức tạp của nhánh có thời gian chạy lớn nhất (trong trường hợp xấu nhất).

Bằng tích độ phức tạp của nhánh if và nhánh else.

Bằng độ phức tạp của điều kiện (biểu thức logic) của if.

Trong trường hợp xấu nhất, chúng ta xét nhánh lệnh có độ phức tạp cao nhất giữa nhánh `if` và nhánh `else`. Độ phức tạp của toàn bộ khối điều kiện sẽ là độ phức tạp của nhánh tốn nhiều thời gian nhất.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 18: Xét đoạn mã giả sau:
```
func process_array(arr, n):
# Đoạn 1: Tìm phần tử nhỏ nhất (O(n))
min_val = arr[0]
for i from 1 to n-1:
if arr[i] < min_val: min_val = arr[i] # Đoạn 2: In ra 10 lần giá trị min_val (O(1)) for k from 1 to 10: print(min_val) ``` Độ phức tạp thời gian tổng thể của hàm `process_array` là gì?

O(1)

O(n^2)

O(n)

O(n log n)

Đoạn 1 có một vòng lặp chạy n-1 lần, mỗi lần lặp thực hiện hằng số phép toán, nên độ phức tạp là O(n). Đoạn 2 có một vòng lặp chạy cố định 10 lần, mỗi lần lặp thực hiện hằng số phép toán, nên độ phức tạp là O(10) = O(1). Hai đoạn này thực hiện tuần tự, áp dụng quy tắc cộng: O(n) + O(1) = O(max(n, 1)) = O(n) khi n lớn.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 19: Thứ tự tăng trưởng từ chậm nhất đến nhanh nhất của các độ phức tạp phổ biến là gì?

O(n), O(log n), O(n^2), O(n log n)

O(1), O(log n), O(n), O(n log n), O(n^2)

O(n^2), O(n log n), O(n), O(log n), O(1)

O(log n), O(1), O(n), O(n^2), O(n log n)

Thứ tự tăng trưởng từ chậm đến nhanh nhất là: O(1) (hằng số), O(log n) (logarit), O(n) (tuyến tính), O(n log n) (tuyến tính-logarit), O(n^2) (bình phương), O(n^k) (đa thức bậc k), O(2^n) (mũ).

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 20: Giả sử một thuật toán có độ phức tạp thời gian là O(n^2). Nếu kích thước đầu vào `n` tăng gấp đôi, thì thời gian chạy của thuật toán sẽ tăng lên khoảng bao nhiêu lần (đối với n đủ lớn)?

Gấp đôi (2 lần)

Gấp ba (3 lần)

Gấp log n lần

Gấp bốn lần (4 lần)

Nếu thời gian chạy là T(n) ≈ C * n² (với C là hằng số), khi n tăng gấp đôi thành 2n, thời gian chạy mới sẽ là T(2n) ≈ C * (2n)² = C * 4n² = 4 * (C * n²) = 4 * T(n). Thời gian chạy tăng khoảng 4 lần.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 21: Giả sử một thuật toán có độ phức tạp thời gian là O(log n). Nếu kích thước đầu vào `n` tăng gấp đôi, thì thời gian chạy của thuật toán sẽ tăng lên khoảng bao nhiêu (đối với n đủ lớn)?

Tăng thêm một lượng hằng số.

Tăng gấp đôi.

Tăng theo log của log n.

Không thay đổi.

Nếu thời gian chạy là T(n) ≈ C * log(n), khi n tăng gấp đôi thành 2n, thời gian chạy mới sẽ là T(2n) ≈ C * log(2n) = C * (log(2) + log(n)) = C * log(2) + C * log(n). Thời gian chạy tăng thêm một lượng cố định (C * log(2)), không phải tăng theo tỷ lệ gấp đôi hay gấp nhiều lần.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 22: Ký hiệu O lớn (Big O) dùng để chỉ điều gì khi phân tích độ phức tạp thời gian?

Giới hạn trên (trường hợp xấu nhất) về tốc độ tăng trưởng thời gian chạy.

Giới hạn dưới (trường hợp tốt nhất) về tốc độ tăng trưởng thời gian chạy.

Thời gian chạy trung bình của thuật toán.

Thời gian chạy chính xác của thuật toán.

Ký hiệu Big O cung cấp một giới hạn trên (upper bound) cho tốc độ tăng trưởng của thời gian chạy (hoặc số phép toán) của thuật toán trong trường hợp xấu nhất. Nó mô tả hiệu suất tối đa mà chúng ta có thể gặp phải.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 23: Một chương trình thực hiện ba phần tuần tự: Phần 1 có độ phức tạp O(n), Phần 2 có độ phức tạp O(n²), và Phần 3 có độ phức tạp O(log n). Độ phức tạp thời gian tổng thể của chương trình là gì?

O(n + n² + log n)

O(n log n)

O(n)

O(n²)

Khi các phần được thực hiện tuần tự, áp dụng quy tắc cộng. Độ phức tạp tổng thể là O(max(độ phức tạp Phần 1, độ phức tạp Phần 2, độ phức tạp Phần 3)). So sánh O(n), O(n²), và O(log n). Với n lớn, n² tăng trưởng nhanh nhất. Do đó, độ phức tạp tổng thể là O(n²).

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 24: Xét đoạn mã giả sau:
```
func process(n):
if n <= 1: return for i from 1 to 10: print(i) process(n/2) process(n/2) ``` Đoạn mã này mô tả cấu trúc gì và độ phức tạp thời gian của phần đệ quy (không xét vòng lặp cố định) thường rơi vào loại nào?

Đệ quy, thường O(n log n) hoặc O(n) trong các trường hợp điển hình như chia để trị.

Vòng lặp lồng nhau, thường O(n^2).

Vòng lặp đơn, thường O(n).

Cấu trúc hằng số, O(1).

Hàm gọi chính nó hai lần với kích thước đầu vào giảm một nửa (n/2). Đây là cấu trúc đệ quy. Cấu trúc đệ quy dạng T(n) = 2*T(n/2) + O(f(n)) thường dẫn đến độ phức tạp O(n log n) hoặc O(n^2) hoặc O(n) tùy thuộc vào f(n). Tuy nhiên, nếu chỉ có các lời gọi đệ quy mà không có công việc phụ thuộc n (chỉ có vòng lặp cố định O(10) = O(1)), cấu trúc T(n) = 2T(n/2) + O(1) có độ phức tạp là O(n).

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 25: Việc phân tích độ phức tạp thời gian của thuật toán giúp ích gì cho lập trình viên?

Giúp tìm lỗi cú pháp trong mã nguồn.

Giúp giảm thiểu việc sử dụng bộ nhớ.

Giúp dự đoán thời gian chạy chính xác trên mọi máy tính.

Giúp đánh giá hiệu suất của thuật toán khi xử lý dữ liệu lớn và so sánh các thuật toán khác nhau.

Hiểu độ phức tạp giúp lập trình viên dự đoán hiệu suất của thuật toán khi dữ liệu lớn, so sánh các thuật toán khác nhau để chọn ra thuật toán hiệu quả nhất cho bài toán, và xác định xem một thuật toán có khả thi để giải quyết vấn đề trong giới hạn thời gian cho phép hay không.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 26: Xét đoạn mã giả sau:
```
func example(arr, n):
for i from 0 to n-1:
if arr[i] == target_value:
return True
return False
```
Đây là thuật toán tìm kiếm tuyến tính (Linear Search). Độ phức tạp thời gian trong trường hợp xấu nhất của nó là gì?

O(log n)

O(n)

O(n log n)

O(n^2)

Trong trường hợp xấu nhất (phần tử cần tìm không có trong mảng hoặc nằm ở cuối mảng), vòng lặp sẽ phải duyệt qua toàn bộ `n` phần tử của mảng. Mỗi lần lặp thực hiện hằng số phép toán (so sánh). Do đó, độ phức tạp là O(n).

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 27: Cho một thuật toán có độ phức tạp O(n^3). Nếu một máy tính có thể chạy thuật toán này với n=100 trong 1 giây, ước tính thời gian cần thiết để chạy thuật toán với n=200 trên cùng máy tính đó là bao nhiêu?

2 giây

4 giây

6 giây

8 giây

Thời gian chạy tỷ lệ với n³. T(n) = C * n³. T(100) = C * 100³ = 1 giây. T(200) = C * 200³ = C * (2*100)³ = C * 8 * 100³ = 8 * (C * 100³) = 8 * T(100). Nếu T(100) là 1 giây, thì T(200) sẽ là khoảng 8 giây.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 28: Khi so sánh hai thuật toán có độ phức tạp O(n) và O(n log n), điều gì đúng khi n rất lớn?

Thuật toán O(n) sẽ chạy nhanh hơn thuật toán O(n log n).

Thuật toán O(n log n) sẽ chạy nhanh hơn thuật toán O(n).

Hai thuật toán có hiệu suất tương đương.

Không thể so sánh vì cần biết hệ số hằng.

Hàm n tăng trưởng nhanh hơn hàm n log n. Điều này có vẻ ngược với trực giác ban đầu, nhưng log n tăng rất chậm. Ví dụ, log₂(1024) = 10, log₂(1,048,576) = 20. Khi n lớn, n log n sẽ lớn hơn n. Do đó, O(n) hiệu quả hơn O(n log n).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 29: Xét đoạn mã giả sau:
```
func weird_loop(n):
count = 0
for i from 1 to n:
for j from i to n:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n log n)

O(n³)

O(n²)

Vòng lặp ngoài chạy từ i=1 đến n. Vòng lặp trong chạy từ j=i đến n. Số lần chạy của vòng lặp trong phụ thuộc vào i. Khi i=1, j chạy từ 1 đến n (n lần). Khi i=2, j chạy từ 2 đến n (n-1 lần). ... Khi i=n, j chạy từ n đến n (1 lần). Tổng số lần thực hiện lệnh `count = count + 1` là n + (n-1) + ... + 1 = n(n+1)/2. Đây là một hàm bậc hai của n. Do đó, độ phức tạp là O(n²).

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 30: Mục tiêu chính của việc đánh giá độ phức tạp thời gian thuật toán là gì?

Để so sánh hiệu quả và khả năng mở rộng của các thuật toán khác nhau khi xử lý dữ liệu lớn.

Để xác định số lượng bộ nhớ cần thiết cho thuật toán.

Để tìm ra thuật toán có ít dòng mã nhất.

Để đảm bảo thuật toán không bao giờ gặp lỗi.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Mục tiêu chính là có một cách định lượng và tiêu chuẩn hóa để so sánh hiệu quả của các thuật toán khác nhau trong việc giải cùng một bài toán, đặc biệt là khả năng mở rộng của chúng khi kích thước dữ liệu đầu vào tăng lên.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 04

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 1: Tại sao việc đánh giá độ phức tạp thời gian của thuật toán lại quan trọng trong khoa học máy tính?

Giúp xác định số dòng code trong chương trình.

Chỉ cần thiết cho các thuật toán sắp xếp.

Giúp tìm ra lỗi cú pháp trong code.

Giúp dự đoán hiệu suất của thuật toán khi kích thước dữ liệu đầu vào tăng lên và so sánh hiệu quả giữa các thuật toán.

Câu hỏi kiểm tra hiểu biết về mục đích của việc phân tích độ phức tạp. Việc này giúp dự đoán hiệu suất thuật toán với dữ liệu lớn và so sánh các thuật toán khác nhau.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 2: Khi phân tích độ phức tạp thời gian, chúng ta thường quan tâm đến trường hợp nào của dữ liệu đầu vào và tại sao?

Trường hợp tốt nhất, vì nó thể hiện tốc độ nhanh nhất có thể.

Trường hợp trung bình, vì nó phản ánh hiệu suất thực tế thường gặp.

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 mức ước lượng đó.

Trường hợp tốt nhất và trung bình có ý nghĩa như nhau.

Câu hỏi kiểm tra kiến thức về trường hợp phân tích phổ biến nhất. Trường hợp xấu nhất (worst-case) được quan tâm vì nó cung cấp giới hạn trên (upper bound) về thời gian chạy, đảm bảo thuật toán không bao giờ chạy chậm hơn mức đó.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 3: Ký hiệu Big O (O) được sử dụng để làm gì trong đánh giá độ phức tạp thời gian?

Biểu thị thời gian chạy chính xác của thuật toán trên một máy cụ thể.

Mô tả giới hạn trên về tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào rất lớn.

Đếm chính xác tổng số phép toán cơ bản.

Đo lường dung lượng bộ nhớ mà thuật toán sử dụng.

Câu hỏi kiểm tra ý nghĩa của ký hiệu Big O. Nó mô tả tốc độ 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ỏ qua các hằng số và các số hạng bậc thấp.

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 4: Một thuật toán có độ phức tạp thời gian O(1) nghĩa là gì?

Thời gian thực hiện không đổi, không phụ thuộc vào kích thước đầu vào n.

Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.

Thời gian thực hiện tăng theo hàm logarit của n.

Thời gian thực hiện tăng theo bình phương của n.

Câu hỏi kiểm tra ý nghĩa của độ phức tạp hằng số O(1). Nó chỉ ra rằng thời gian th??c hiện của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào.

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 5: Cho đoạn mã Python sau:
```python
result = 0
for i in range(n):
result += i
```
Độ phức tạp thời gian của đoạn mã này là gì theo ký hiệu Big O, với n là kích thước đầu vào?

O(1)

O(n^2)

O(n)

O(log n)

Câu hỏi yêu cầu phân tích độ phức tạp của vòng lặp đơn giản. Vòng lặp chạy n lần, mỗi lần thực hiện một phép cộng và gán (coi là O(1)). Tổng cộng là n * O(1) = O(n).

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 6: Cho đoạn mã Python sau:
```python
result = 0
for i in range(n):
for j in range(n):
result += i * j
```
Độ phức tạp thời gian của đoạn mã này là gì theo ký hiệu Big O, với n là kích thước đầu vào?

O(n)

O(n^2)

O(n log n)

O(2^n)

Câu hỏi yêu cầu phân tích độ phức tạp của vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần, vòng lặp trong cũng chạy n lần cho mỗi lần lặp của vòng ngoài. Tổng số phép toán cơ bản là khoảng n * n = n^2. Do đó, độ phức tạp là O(n^2).

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 7: Cho hai đoạn mã A và B. Đoạn A có độ phức tạp O(n), đoạn B có độ phức tạp O(n^2). Nếu thực hiện đoạn mã A rồi đến đoạn mã B, độ phức tạp thời gian tổng thể là gì theo ký hiệu Big O?

O(n + n^2)

O(n^2)

O(n)

O(n^3)

Câu hỏi áp dụng quy tắc cộng cho độ phức tạp. Khi các phần của chương trình được thực hiện nối tiếp, độ phức tạp tổng thể là độ phức tạp của phần có tốc độ tăng trưởng lớn nhất. O(n^2) tăng trưởng nhanh hơn O(n).

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 8: Một thuật toán tìm kiếm trên một mảng đã được sắp xếp bằng phương pháp chia đôi (tìm kiếm nhị phân) có độ phức tạp thời gian là gì?

O(n)

O(n^2)

O(1)

O(log n)

Câu hỏi kiểm tra kiến thức về độ phức tạp của thuật toán tìm kiếm nhị phân. Thuật toán này loại bỏ một nửa phần tử còn lại sau mỗi bước so sánh, dẫn đến độ phức tạp logarit.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 9: Sắp xếp các độ phức tạp thời gian sau theo thứ tự từ tốt nhất (nhanh nhất) đến tệ nhất (chậm nhất) khi n rất lớn: O(n^2), O(n), O(1), O(n log n).

O(n^2), O(n log n), O(n), O(1)

O(n), O(n^2), O(1), O(n log n)

O(1), O(n), O(n log n), O(n^2)

O(log n), O(n), O(n log n), O(n^2)

Câu hỏi kiểm tra khả năng so sánh các lớp độ phức tạp Big O. Thứ tự tăng trưởng từ chậm nhất đến nhanh nhất là O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 10: Một thuật toán xử lý tất cả các cặp phần tử trong một tập hợp n phần tử. Ví dụ: so sánh mọi cặp phần tử với nhau. Độ phức tạp thời gian phổ biến nhất cho hoạt động này là gì?

O(n)

O(n^2)

O(n log n)

O(log n)

Câu hỏi mô tả một hoạt động thường dẫn đến độ phức tạp O(n^2), điển hình là các thuật toán sắp xếp đơn giản hoặc xử lý ma trận vuông.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 11: Cho đoạn mã Python sau:
```python
def process_data(data):
n = len(data)
for i in range(n // 2):
print(data[i])
```
Độ phức tạp thời gian của hàm `process_data` là gì theo ký hiệu Big O, với n là kích thước danh sách `data`?

O(n^2)

O(log n)

O(n)

O(1)

Câu hỏi yêu cầu phân tích vòng lặp với cận `n // 2`. Vòng lặp vẫn chạy một số lần tỷ lệ thuận với n (khoảng n/2 lần). Các hằng số (như 1/2) bị bỏ qua trong ký hiệu Big O. Do đó, độ phức tạp là O(n).

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 12: Cho đoạn mã Python sau:
```python
def find_element(data, target):
for item in data:
if item == target:
return True
return False
```
Trong trường hợp xấu nhất, độ phức tạp thời gian của hàm `find_element` (tìm kiếm tuyến tính) là gì theo ký hiệu Big O, với n là kích thước danh sách `data`?

O(n)

O(log n)

O(n^2)

O(1)

Câu hỏi phân tích tìm kiếm tuyến tính trong trường hợp xấu nhất (phần tử không có trong danh sách hoặc ở cuối). Vòng lặp sẽ phải duyệt qua tất cả n phần tử. Do đó, độ phức tạp là O(n).

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 13: Giả sử một thuật toán có thời gian chạy được mô tả bởi hàm T(n) = 5n^3 + 2n^2 + 100. Độ phức tạp thời gian của thuật toán này theo ký hiệu Big O là gì?

O(n)

O(n^2)

O(1)

O(n^3)

Câu hỏi kiểm tra khả năng xác định bậc cao nhất trong hàm thời gian. Khi n rất lớn, số hạng 5n^3 chi phối các số hạng còn lại. Trong ký hiệu Big O, chúng ta chỉ giữ lại số hạng bậc cao nhất và bỏ qua hệ số hằng số. Do đó, độ phức tạp là O(n^3).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 14: Khi so sánh thuật toán A có độ phức tạp O(n log n) và thuật toán B có độ phức tạp O(n^2), thuật toán nào hiệu quả hơn (chạy nhanh hơn) khi kích thước đầu vào n rất lớn?

Thuật toán A (O(n log n))

Thuật toán B (O(n^2))

Cả hai thuật toán có hiệu quả tương đương.

Không thể xác định nếu không biết giá trị cụ thể của n.

Câu hỏi yêu cầu so sánh tốc độ tăng trưởng của O(n log n) và O(n^2). O(n log n) tăng trưởng chậm hơn đáng kể so với O(n^2) khi n lớn. Do đó, thuật toán có độ phức tạp O(n log n) hiệu quả hơn.

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 15: Cho đoạn mã Python sau:
```python
def example(n):
for i in range(100):
print(i)
for j in range(n):
print(j)
```
Độ phức tạp thời gian của hàm `example` là gì theo ký hiệu Big O, với n là kích thước đầu vào?

O(100 + n)

O(100n)

O(n)

O(1)

Câu hỏi áp dụng quy tắc cộng. Vòng lặp đầu tiên chạy 100 lần, có độ phức tạp O(1) (vì 100 là hằng số, không phụ thuộc vào n). Vòng lặp thứ hai chạy n lần, có độ phức tạp O(n). Khi hai phần này chạy nối tiếp, độ phức tạp tổng thể là O(max(1, n)), khi n lớn thì là O(n).

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 16: Cho đoạn mã Python sau:
```python
def another_example(n):
i = 1
while i < n: print(i) i *= 2 ``` Độ phức tạp thời gian của hàm `another_example` là gì theo ký hiệu Big O, với n là kích thước đầu vào?

O(n)

O(n^2)

O(1)

O(log n)

Câu hỏi phân tích vòng lặp với bước nhảy nhân đôi. Biến `i` tăng theo cấp số nhân (1, 2, 4, 8, ...). Số lần lặp k để i đạt đến n (hoặc vượt quá) là khi 2^k ≈ n, tức là k ≈ log₂(n). Do đó, độ phức tạp là O(log n).

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 17: Khi phân tích độ phức tạp thời gian, tại sao chúng ta thường bỏ qua các hằng số và các số hạng bậc thấp trong hàm thời gian T(n)?

Vì chúng không ảnh hưởng đến thời gian chạy thực tế.

Vì chúng chỉ ảnh hưởng nhỏ khi kích thước đầu vào n rất lớn và ký hiệu Big O quan tâm đến tốc độ tăng trưởng tiệm cận.

Vì chúng chỉ liên quan đến dung lượng bộ nhớ, không phải thời gian.

Vì chúng làm cho việc tính toán trở nên phức tạp.

Câu hỏi kiểm tra hiểu biết về bản chất của ký hiệu Big O. Big O mô tả hành vi tiệm cận của thuật toán khi n rất lớn. Ở quy mô lớn, tốc độ tăng trưởng của số hạng bậc cao nhất chi phối hoàn toàn, làm cho các hằng số và số hạng bậc thấp trở nên không đáng kể.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 18: Thuật toán sắp xếp nổi bọt (Bubble Sort) đơn giản có độ phức tạp thời gian trong trường hợp xấu nhất là gì?

O(n)

O(n log n)

O(n^2)

O(log n)

Câu hỏi kiểm tra kiến thức về độ phức tạp của thuật toán sắp xếp nổi bọt. Thuật toán này sử dụng hai vòng lặp lồng nhau, mỗi vòng chạy khoảng n lần (trong trường hợp xấu nhất hoặc trung bình), dẫn đến độ phức tạp O(n^2).

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 19: Một bài toán yêu cầu duyệt qua tất cả các tập con có thể có của một tập hợp n phần tử. Độ phức tạp thời gian của thuật toán giải quyết bài toán này có khả năng là gì?

O(2^n)

O(n^2)

O(n log n)

O(n!)

Câu hỏi yêu cầu suy luận độ phức tạp từ mô tả bài toán. Một tập hợp n phần tử có 2^n tập con. Duyệt qua tất cả chúng thường đòi hỏi ít nhất O(2^n) thời gian, đây là độ phức tạp mũ.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 20: Cho đoạn mã Python sau:
```python
def process_matrix(matrix, n):
for i in range(n):
for j in range(n):
# Thao tác O(1) trên matrix[i][j]
pass
for k in range(n):
# Thao tác O(1)
pass
```
Độ phức tạp thời gian của hàm `process_matrix` là gì theo ký hiệu Big O, với n là kích thước (số hàng/cột) của ma trận vuông?

O(n)

O(n + n^2)

O(n^2)

O(n^3)

Câu hỏi kết hợp quy tắc nhân và quy tắc cộng. Phần đầu có vòng lặp lồng nhau O(n^2). Phần sau có vòng lặp đơn O(n). Khi thực hiện nối tiếp, độ phức tạp tổng là O(max(n^2, n)) = O(n^2).

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 21: Độ phức tạp thời gian O(n log n) thường xuất hiện trong các thuật toán nào?

Tìm kiếm tuyến tính, tìm kiếm nhị phân.

Các thuật toán sắp xếp hiệu quả như Sắp xếp trộn (Merge Sort), Sắp xếp nhanh (Quick Sort).

Các phép toán cơ bản (cộng, trừ, nhân, chia).

Duyệt qua tất cả các tập con của một tập hợp.

Câu hỏi kiểm tra kiến thức về các thuật toán có độ phức tạp O(n log n), đây là độ phức tạp hiệu quả cho nhiều bài toán sắp xếp.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 22: Nếu một thuật toán có độ phức tạp O(n) và chạy mất 1 giây cho n=1000, ước tính thời gian chạy cho n=2000 là bao nhiêu?

Khoảng 2 giây.

Khoảng 4 giây.

Khoảng 0.5 giây.

Không thể ước tính vì không biết hệ số hằng số.

Câu hỏi yêu cầu áp dụng hiểu biết về độ phức tạp tuyến tính. Với O(n), thời gian chạy tỷ lệ thuận với n. Nếu n tăng gấp đôi (từ 1000 lên 2000), thời gian chạy cũng sẽ tăng gấp đôi.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 23: Nếu một thuật toán có độ phức tạp O(n^2) và chạy mất 1 giây cho n=1000, ước tính thời gian chạy cho n=2000 là bao nhiêu?

Khoảng 2 giây.

Khoảng 4 giây.

Khoảng 0.5 giây.

Khoảng 8 giây.

Câu hỏi yêu cầu áp dụng hiểu biết về độ phức tạp bình phương. Với O(n^2), thời gian chạy tỷ lệ thuận với n^2. Nếu n tăng gấp đôi (từ 1000 lên 2000, tức là 2n), thời gian chạy sẽ tăng theo (2n)^2 = 4n^2, tức là tăng gấp 4 lần.

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 24: Cho đoạn mã Python sau:
```python
def process_pairs(data):
n = len(data)
for i in range(n):
for j in range(i, n):
# Thao tác O(1) với data[i] và data[j]
pass
```
Độ phức tạp thời gian của hàm `process_pairs` là gì theo ký hiệu Big O, với n là kích thước danh sách `data`?

O(n)

O(n log n)

O(n^2)

O(log n)

Câu hỏi phân tích vòng lặp lồng nhau mà vòng trong chạy từ `i` đến `n-1`. Tổng số lần lặp là n + (n-1) + (n-2) + ... + 1 ≈ n^2 / 2. Số hạng bậc cao nhất vẫn là n^2, nên độ phức tạp là O(n^2).

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 25: Trong phân tích độ phức tạp, 'kích thước đầu vào' (input size) của một thuật toán là gì?

Một đại lượng đo lường quy mô của dữ liệu mà thuật toán xử lý (ví dụ: số phần tử trong danh sách).

Số dòng code trong chương trình.

Thời gian chạy thực tế của thuật toán.

Lượng bộ nhớ mà thuật toán sử dụng.

Câu hỏi kiểm tra khái niệm 'kích thước đầu vào'. Nó là một đại lượng đo lường quy mô của dữ liệu mà thuật toán xử lý, thường là số phần tử trong danh sách, kích thước của ma trận, số bit của số, v.v.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 26: Độ phức tạp thời gian O(n!) (n giai thừa) thuộc loại độ phức tạp nào và nó thường xuất hiện trong các bài toán gì?

Đa thức, thường trong các bài toán tìm kiếm.

Logarit, thường trong các bài toán chia để trị.

Mũ, thường trong các bài toán duyệt tất cả tập con.

Siêu đa thức, thường trong các bài toán liên quan đến hoán vị.

Câu hỏi kiểm tra kiến thức về độ phức tạp O(n!). Đây là độ phức tạp rất cao, thuộc loại siêu đa thức, thường xuất hiện trong các bài toán liên quan đến hoán vị (ví dụ: bài toán người du lịch Brute Force).

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 27: Khi nào thì độ phức tạp thời gian của một thuật toán được coi là chấp nhận được trong thực tế?

Khi độ phức tạp là đa thức (ví dụ: O(n), O(n log n), O(n^2)) với bậc nhỏ.

Chỉ khi độ phức tạp là O(1) hoặc O(log n).

Khi độ phức tạp là mũ (ví dụ: O(2^n)).

Chỉ khi thời gian chạy thực tế dưới 1 giây.

Câu hỏi yêu cầu đánh giá tính thực tiễn của các lớp độ phức tạp. Các độ phức tạp đa thức (O(n^k) với k là hằng số nhỏ) thường được coi là chấp nhận được, trong khi độ phức tạp mũ, giai thừa thường chỉ dùng cho n rất nhỏ.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 28: Cho đoạn mã Python sau:
```python
def strange_loop(n):
count = 0
for i in range(n):
for j in range(i):
count += 1
```
Độ phức tạp thời gian của hàm `strange_loop` là gì theo ký hiệu Big O, với n là kích thước đầu vào?

O(n)

O(n^2)

O(n log n)

O(log n)

Câu hỏi phân tích vòng lặp lồng nhau với cận thay đổi. Vòng trong chạy từ 0 đến i-1. Tổng số lần lặp của vòng trong là 0 + 1 + 2 + ... + (n-1) = n(n-1)/2. Đây là một hàm bậc hai theo n. Do đó, độ phức tạp là O(n^2).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 29: Tại sao việc phân tích độ phức tạp thời gian thường tập trung vào trường hợp xấu nhất?

Vì trường hợp xấu nhất dễ phân tích nhất.

Vì trường hợp xấu nhất luôn xảy ra trong thực tế.

Vì nó cung cấp giới hạn trên về thời gian chạy, đảm bảo thuật toán không bao giờ chạy chậm hơn mức đó.

Vì nó thể hiện hiệu suất trung bình của thuật toán.

Câu hỏi làm rõ lý do chọn phân tích trường hợp xấu nhất. Nó đảm bảo rằng thuật toán sẽ hoạt động trong giới hạn thời gian đó ngay cả trong điều kiện khó khăn nhất, cung cấp sự đảm bảo về hiệu suất.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 30: Cho một thuật toán thực hiện hai bước độc lập. Bước 1 có độ phức tạp O(log n), Bước 2 có độ phức tạp O(n). Độ phức tạp tổng thể của thuật toán là gì?

O(log n)

O(n)

O(n log n)

O(log n + n)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Câu hỏi áp dụng quy tắc cộng. Khi các bước được thực hiện nối tiếp, độ phức tạp tổng thể là độ phức tạp của bước có tốc độ tăng trưởng lớn hơn. O(n) tăng trưởng nhanh hơn O(log n).

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 05

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 1: Khi đánh giá độ phức tạp thời gian của một thuật toán, chúng ta thường quan tâm đến yếu tố nào của đầu vào?

Giá trị cụ thể của từng phần tử trong đầu vào.

Kích thước của dữ liệu đầu vào (thường ký hiệu là n).

Thời gian thực tế mà chương trình chạy trên một máy tính cụ thể.

Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 2: Độ phức tạp thời gian O(1) biểu thị điều gì về thời gian thực hiện của một thuật toán?

Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.

Thời gian thực hiện tăng theo logarit của kích thước đầu vào n.

Thời gian thực hiện là hằng số, không phụ thuộc vào kích thước đầu vào n.

Thời gian thực hiện tăng theo bình phương của kích thước đầu vào n.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 3: Cho đoạn mã Python sau:
```python
def process_array(arr):
total = 0
for x in arr:
total += x
return total
```
Với `n` là kích thước của mảng `arr`, độ phức tạp thời gian của hàm `process_array` là gì?

O(n)

O(n^2)

O(log n)

O(1)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 4: Cho đoạn mã Python sau:
```python
def find_pair(arr):
n = len(arr)
for i in range(n):
for j in range(n):
if arr[i] + arr[j] == 0:
return True
return False
```
Với `n` là kích thước của mảng `arr`, độ phức tạp thời gian của hàm `find_pair` là gì?

O(n)

O(n^2)

O(n log n)

O(log n)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 5: Khi phân tích độ phức tạp thời gian bằng ký hiệu Big O, chúng ta thường bỏ qua các yếu tố nào?

Chỉ số của vòng lặp.

Tên biến.

Số lượng tham số của hàm.

Các hằng số nhân và các số hạng bậc thấp.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 6: Một thuật toán có thời gian thực hiện được mô tả bởi hàm T(n) = 3n^2 + 5n + 100. Độ phức tạp thời gian theo ký hiệu Big O của thuật toán này là gì?

O(n)

O(log n)

O(n^2)

O(n^3)

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 7: Quy tắc cộng trong đánh giá độ phức tạp thời gian được áp dụng khi nào?

Khi các khối lệnh hoặc hàm được thực hiện nối tiếp nhau.

Khi có các vòng lặp lồng nhau.

Khi một hàm gọi một hàm khác.

Khi có các phép toán số học đơn giản.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 8: Quy tắc nhân trong đánh giá độ phức tạp thời gian được áp dụng khi nào?

Khi các khối lệnh hoặc hàm được thực hiện nối tiếp nhau.

Khi một khối lệnh (có độ phức tạp T1) được thực hiện bên trong một vòng lặp hoặc khối lệnh khác (có độ phức tạp T2).

Khi so sánh hai thuật toán khác nhau.

Khi tính tổng thời gian thực hiện của tất cả các lệnh.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 9: Cho đoạn mã Python sau:
```python
def example_func(n):
if n <= 1: return 1 else: print('Hello') return example_func(n-1) + example_func(n-2) ``` Độ phức tạp thời gian của hàm đệ quy này (ví dụ tính số Fibonacci cơ bản) là gì?

O(n)

O(n^2)

O(log n)

O(2^n)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 10: Thuật toán Tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có độ phức tạp thời gian trung bình là gì?

O(n)

O(n^2)

O(log n)

O(1)

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 11: Độ phức tạp thời gian O(n log n) thường xuất hiện trong các loại thuật toán nào?

Các thuật toán sắp xếp hiệu quả (ví dụ: Merge Sort, Quick Sort).

Các thuật toán tìm kiếm tuyến tính.

Các thuật toán có vòng lặp lồng nhau đơn giản.

Các thuật toán có thời gian thực hiện không đổi.

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 12: Giả sử thuật toán A có độ phức tạp O(n) và thuật toán B có độ phức tạp O(n^2). Khi kích thước đầu vào n rất lớn, thuật toán nào sẽ có thời gian thực hiện tốt hơn?

Thuật toán A (O(n)).

Thuật toán B (O(n^2)).

Thời gian thực hiện của cả hai thuật toán là như nhau.

Không thể xác định nếu không biết hằng số.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 13: Tại sao việc đánh giá độ phức tạp thời gian lại quan trọng trong lập trình, đặc biệt khi xử lý dữ liệu lớn?

Giúp chương trình chạy nhanh hơn trên mọi máy tính.

Giúp giảm dung lượng bộ nhớ mà chương trình sử dụng.

Giúp xác định lỗi cú pháp trong mã nguồn.

Giúp dự đoán hiệu suất của thuật toán khi kích thước đầu vào tăng lên và so sánh các thuật toán khác nhau.

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 14: Cho đoạn mã Python:
```python
def simple_ops(a, b):
c = a + b
d = c * 2
return d / 3
```
Độ phức tạp thời gian của hàm `simple_ops` là gì?

O(n) (phụ thuộc vào giá trị của a, b)

O(log n)

O(n^2)

O(1)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 15: Khi nói về độ phức tạp thời gian của thuật toán, trường hợp 'xấu nhất' (worst-case) có ý nghĩa gì?

Thời gian thực hiện tối đa mà thuật toán có thể mất cho một đầu vào có kích thước n.

Thời gian thực hiện trung bình cho một đầu vào có kích thước n.

Thời gian thực hiện tối thiểu cho một đầu vào có kích thước n.

Thời gian thực hiện khi thuật toán gặp lỗi.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 16: Cho đoạn mã Python sau:
```python
def process_data(arr):
n = len(arr)
# Block 1
for i in range(n):
print(arr[i])
# Block 2
for i in range(n):
for j in range(n):
print(arr[i], arr[j])
```
Với `n` là kích thước mảng `arr`, độ phức tạp thời gian của hàm `process_data` là gì?

O(n)

O(n^2)

O(n log n)

O(n + n^2)

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 17: Một thuật toán có độ phức tạp O(log n) có nghĩa là gì?

Thời gian thực hiện tăng chậm khi kích thước đầu vào n tăng, thường liên quan đến việc chia nhỏ bài toán.

Thời gian thực hiện tăng rất nhanh khi kích thước đầu vào n tăng.

Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.

Thời gian thực hiện không đổi với mọi kích thước đầu vào.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 18: Sắp xếp các độ phức tạp thời gian sau từ hiệu quả nhất đến kém hiệu quả nhất khi n rất lớn: O(n^2), O(log n), O(n), O(n log n).

O(n^2), O(n log n), O(n), O(log n)

O(n), O(log n), O(n^2), O(n log n)

O(log n), O(n), O(n log n), O(n^2)

O(log n), O(n log n), O(n), O(n^2)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 19: Nếu một thuật toán có độ phức tạp O(n) mất 5 giây để xử lý đầu vào có kích thước n = 1000, thì ước tính nó sẽ mất bao lâu để xử lý đầu vào có kích thước n = 2000?

Khoảng 10 giây.

Khoảng 20 giây.

Khoảng 5 giây.

Khoảng 25 giây.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 20: Nếu một thuật toán có độ phức tạp O(n^2) mất 2 giây để xử lý đầu vào có kích thước n = 100, thì ước tính nó sẽ mất bao lâu để xử lý đầu vào có kích thước n = 300?

Khoảng 6 giây.

Khoảng 18 giây.

Khoảng 36 giây.

Khoảng 18 giây (kích thước tăng 3 lần, thời gian tăng 3^2=9 lần, 2*9=18).

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 21: Cho đoạn mã Python sau:
```python
def mystery(n):
count = 0
i = 1
while i < n: count += 1 i *= 2 return count ``` Với `n` là số nguyên dương, độ phức tạp thời gian của hàm `mystery` là gì?

O(n)

O(log n)

O(n^2)

O(1)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 22: Trong phân tích độ phức tạp thời gian, ký hiệu Ω (Omega lớn) biểu thị điều gì?

Giới hạn trên chặt của thời gian thực hiện (worst-case).

Giới hạn trung bình của thời gian thực hiện (average-case).

Giới hạn dưới của thời gian thực hiện (best-case).

Độ phức tạp chính xác.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 23: Một thuật toán duyệt qua tất cả các cặp phần tử có thể có trong một danh sách n phần tử. Độ phức tạp thời gian điển hình của thuật toán này là gì?

O(n)

O(log n)

O(n log n)

O(n^2)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 24: Tại sao các hằng số và các số hạng bậc thấp lại bị bỏ qua trong ký hiệu Big O khi n đủ lớn?

Vì khi n rất lớn, sự đóng góp của các số hạng bậc cao hơn trở nên chi phối hoàn toàn.

Vì chúng luôn bằng 0.

Vì chúng chỉ ảnh hưởng đến độ phức tạp không gian, không phải thời gian.

Vì chúng chỉ quan trọng đối với các đầu vào nhỏ.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 25: 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)

O(n^2)

O(n log n)

O(log n)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 26: Cho đoạn mã Python sau:
```python
def another_func(n):
total = 0
for i in range(100): # Vòng lặp chạy 100 lần cố định
total += i
for j in range(n):
total += j
return total
```
Với `n` là kích thước đầu vào, độ phức tạp thời gian của hàm `another_func` là gì?

O(n)

O(100 + n)

O(100n)

O(1)

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 27: Khi so sánh hai thuật toán A (O(n log n)) và B (O(n^2)), thuật toán nào sẽ trở nên vượt trội hơn khi kích thước dữ liệu n tăng lên đáng kể?

Thuật toán A (O(n log n))

Thuật toán B (O(n^2))

Cả hai thuật toán có hiệu suất tương đương.

Không thể xác định mà không biết giá trị cụ thể của n.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 28: Trường hợp 'tốt nhất' (best-case) của độ phức tạp thời gian của một thuật toán biểu thị điều gì?

Thời gian thực hiện trung bình cho một đầu vào có kích thước n.

Thời gian thực hiện tối đa mà thuật toán có thể mất cho một đầu vào có kích thước n.

Thời gian thực hiện khi bộ nhớ đầy.

Thời gian thực hiện tối thiểu mà thuật toán có thể mất cho một đầu vào có kích thước n.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 29: Cho đoạn mã Python sau:
```python
def process_matrix(matrix):
rows = len(matrix)
cols = len(matrix[0]) # Giả sử ma trận không rỗng
for i in range(rows):
for j in range(cols):
print(matrix[i][j])
```
Với ma trận có kích thước `m` hàng và `n` cột, độ phức tạp thời gian của hàm `process_matrix` là gì?

O(m)

O(n)

O(m * n)

O(m + n)

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 30: Mục đích chính của việc sử dụng ký hiệu Big O là để làm gì?

Tính toán chính xác số mili giây mà thuật toán sẽ chạy.

Mô tả cách thời gian thực hiện của thuật toán thay đổi khi kích thước đầu vào tăng lên.

So sánh hiệu quả của thuật toán trên các phần cứng máy tính khác nhau.

Xác định ngôn ngữ lập trình tốt nhất để cài đặt thuật toán.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 06

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 1: Khi đánh giá độ phức tạp thời gian của một thuật toán, yếu tố nào sau đây được xem là quan trọng nhất khi kích thước đầu vào (n) trở nên rất lớn?

Các hằng số nhân và các số hạng bậc thấp.

Tốc độ xử lý của máy tính cụ thể.

Bộ nhớ mà thuật toán sử dụng.

Tốc độ tăng trưởng của số phép toán cơ bản theo n.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 2: Một đoạn chương trình có cấu trúc như sau: `for i in range(n): # Thực hiện một phép toán cơ bản ở đây`. Độ phức tạp thời gian của đoạn chương trình này theo ký hiệu Big O là gì?

O(1)

O(log n)

O(n)

O(n^2)

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 3: Cho đoạn chương trình có cấu trúc: `for i in range(n): for j in range(n): # Thực hiện một phép toán cơ bản ở đây`. Độ phức tạp thời gian của đoạn chương trình này theo ký hiệu Big O là gì?

O(n)

O(n log n)

O(2n)

O(n^2)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 4: Một thuật toán thực hiện hai công việc nối tiếp nhau. Công việc thứ nhất có độ phức tạp O(n), công việc thứ hai có độ phức tạp O(n^2). Độ phức tạp thời gian tổng thể của thuật toán này là gì?

O(n)

O(n^2)

O(n + n^2)

O(n * n^2) = O(n^3)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 5: Một thuật toán sử dụng vòng lặp `while` trong đó biến điều khiển được nhân đôi (hoặc chia đôi) sau mỗi lần lặp cho đến khi đạt đến kích thước đầu vào n. Độ phức tạp thời gian của loại vòng lặp này thường là gì?

O(log n)

O(n)

O(n/2)

O(1)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 6: Tại sao trong ký hiệu Big O, các hằng số nhân (ví dụ: 2 trong 2n) và các số hạng bậc thấp (ví dụ: n trong n^2 + n) thường bị bỏ qua khi n rất lớn?

Vì chúng không ảnh hưởng đến thời gian chạy thực tế.

Vì chúng chỉ quan trọng với kích thước đầu vào nhỏ.

Vì tốc độ tăng trưởng của số hạng bậc cao nhất sẽ chi phối hoàn toàn khi n đủ lớn.

Vì việc tính toán chúng rất phức tạp.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 7: Cho hai thuật toán A có độ phức tạp O(n log n) và thuật toán B có độ phức tạp O(n^1.5). Khi kích thước đầu vào n rất lớn, thuật toán nào có hiệu quả hơn (chạy nhanh hơn)?

Thuật toán A.

Thuật toán B.

Cả hai thuật toán có hiệu quả như nhau.

Không thể xác định nếu không biết giá trị cụ thể của n.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 8: Độ phức tạp thời gian O(1) biểu thị điều gì về thời gian chạy của thuật toán?

Thời gian chạy tăng tuyến tính theo kích thước đầu vào n.

Thời gian chạy tăng theo logarit của kích thước đầu vào n.

Thời gian chạy tăng theo bình phương của kích thước đầu vào n.

Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào n.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 9: Thuật toán tìm kiếm nào trong một mảng đã sắp xếp có thể đạt được độ phức tạp thời gian O(log n) trong trường hợp xấu nhất?

Tìm kiếm tuyến tính (Linear Search).

Tìm kiếm nhị phân (Binary Search).

Tìm kiếm theo chiều sâu (Depth-First Search).

Tìm kiếm theo chiều rộng (Breadth-First Search).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 10: Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất?

Sắp xếp chọn (Selection Sort).

Sắp xếp trộn (Merge Sort).

Sắp xếp nhanh (Quick Sort) - trung bình.

Sắp xếp vun đống (Heap Sort).

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 11: Cho hàm T(n) = 5n^3 + 200n + 10000. Độ phức tạp thời gian của hàm này theo ký hiệu Big O là gì?

O(n)

O(n^2)

O(n^3)

O(10000)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 12: Một đoạn mã thực hiện các bước sau: 1) Duyệt qua toàn bộ mảng kích thước n (O(n)), sau đó 2) Thực hiện một số phép tính cố định (O(1)). Độ phức tạp thời gian tổng thể của đoạn mã này là gì?

O(1)

O(n)

O(n + 1)

O(n*1) = O(n)

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 13: Một đoạn mã gọi một hàm khác bên trong một vòng lặp. Vòng lặp chạy n lần, và hàm được gọi có độ phức tạp O(log n). Độ phức tạp thời gian tổng thể của đoạn mã này là gì?

O(n + log n)

O(max(n, log n))

O(log n)

O(n log n)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 14: Trường hợp nào sau đây thường dẫn đến độ phức tạp thời gian O(2^n) hoặc cao hơn (như O(n!))?

Các bài toán tìm kiếm vét cạn không có hiệu quả (ví dụ: bài toán người du lịch).

Các thuật toán sắp xếp hiệu quả (ví dụ: Merge Sort).

Các thuật toán tìm kiếm trên dữ liệu đã sắp xếp (ví dụ: Binary Search).

Các phép toán truy cập trực tiếp vào bộ nhớ (ví dụ: truy cập phần tử mảng theo chỉ số).

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 15: Tại sao việc phân tích độ phức tạp thời gian trường hợp xấu nhất (worst-case) lại quan trọng trong đánh giá thuật toán?

Vì trường hợp xấu nhất luôn xảy ra phổ biến nhất.

Vì nó cung cấp giới hạn trên cho thời gian chạy, đảm bảo thuật toán sẽ không bao giờ chậm hơn mức đó.

Vì trường hợp xấu nhất là dễ phân tích nhất.

Vì nó phản ánh hiệu suất trung bình của thuật toán.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 16: Cho đoạn mã sau: `def process(data): n = len(data); for i in range(n // 2): print(data[i])`. Độ phức tạp thời gian của hàm `process` là gì?

O(1)

O(log n)

O(n)

O(n^2)

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 17: Cho đoạn mã sau: `def example(data): n = len(data); for i in range(n): pass; for j in range(n): pass`. Độ phức tạp thời gian của hàm `example` là gì?

O(n^2)

O(n)

O(2n)

O(log n)

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 18: Độ phức tạp O(n log n) thường xuất hiện trong các thuật toán nào?

Các thuật toán sắp xếp dựa trên so sánh hiệu quả (Merge Sort, Quick Sort trung bình).

Các thuật toán tìm kiếm trên mảng không sắp xếp (Linear Search).

Các phép toán hằng số (Constant time operations).

Các thuật toán có vòng lặp lồng nhau đơn giản (Bubble Sort).

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 19: Nếu một bài toán có thể giải quyết được bằng thuật toán O(n^2) và một thuật toán khác là O(n), khi n đủ lớn, sự khác biệt về thời gian chạy giữa hai thuật toán sẽ như thế nào?

Thuật toán O(n^2) sẽ chạy nhanh hơn.

Thời gian chạy của hai thuật toán sẽ gần như bằng nhau.

Thuật toán O(n^2) sẽ chạy chậm hơn đáng kể so với O(n).

Không thể dự đoán được sự khác biệt.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 20: Truy cập một phần tử bất kỳ trong mảng bằng chỉ số (ví dụ: `arr[i]`) trong hầu hết các ngôn ngữ lập trình có độ phức tạp thời gian là bao nhiêu?

O(1)

O(log n)

O(n)

O(i)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 21: Ký hiệu O lớn (Big O) mô tả giới hạn nào của thời gian chạy thuật toán?

Giới hạn dưới (best-case).

Giới hạn trên (worst-case).

Trường hợp trung bình (average-case).

Độ chính xác của kết quả.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 22: Nếu một thuật toán có độ phức tạp O(log n), điều này có nghĩa là gì khi kích thước đầu vào tăng gấp đôi?

Thời gian chạy cũng tăng gấp đôi.

Thời gian chạy tăng theo bình phương.

Thời gian chạy chỉ tăng một lượng nhỏ (một hằng số).

Thời gian chạy giảm đi một nửa.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 23: Cho đoạn mã: `def analyze(data): n = len(data); if n > 1000: for i in range(n): print(data[i]) else: print('Data too small')`. Độ phức tạp thời gian trường hợp xấu nhất của hàm `analyze` là gì?

O(1)

O(1000)

O(n)

O(n^2)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 24: Điều gì xảy ra với độ phức tạp thời gian Big O của một thuật toán nếu bạn tăng gấp đôi tốc độ của bộ xử lý máy tính?

Độ phức tạp Big O giảm đi một nửa.

Độ phức tạp Big O tăng gấp đôi.

Độ phức tạp Big O chuyển sang bậc thấp hơn.

Độ phức tạp Big O không thay đổi, chỉ có hằng số thời gian thực tế thay đổi.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 25: Tại sao việc phân tích độ phức tạp thời gian lại quan trọng đối với lập trình viên, đặc biệt khi làm việc với dữ liệu lớn?

Giúp dự đoán hiệu suất của thuật toán khi kích thước dữ liệu tăng và lựa chọn thuật toán phù hợp.

Giúp xác định số dòng code tối thiểu cần thiết.

Giúp cải thiện giao diện người dùng của chương trình.

Giúp giảm thiểu lỗi cú pháp trong code.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 26: Cho hàm T(n) = log₂(n) + 5. Độ phức tạp thời gian của hàm này theo ký hiệu Big O là gì?

O(1)

O(log n)

O(n)

O(log n + 5)

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 27: So với O(n^2), độ phức tạp O(n log n) được coi là hiệu quả hơn đáng kể cho các bài toán sắp xếp trên tập dữ liệu lớn. Điều này là do:

log n luôn lớn hơn n khi n lớn.

n log n tăng trưởng nhanh hơn n^2.

n log n chỉ áp dụng cho dữ liệu đã sắp xếp.

n log n tăng trưởng chậm hơn đáng kể so với n^2 khi n lớn.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 28: Một thuật toán có độ phức tạp O(n!). Đối với kích thước đầu vào n = 20, thuật toán này có khả năng:

Chạy rất chậm và không khả thi trong thực tế.

Chạy gần như tức thời.

Chạy với tốc độ tương đương một thuật toán O(n^2).

Chỉ khả thi nếu chạy trên siêu máy tính.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 29: Trong phân tích độ phức tạp thời gian, 'phép toán cơ bản' (basic operation) là gì?

Luôn là phép gán giá trị.

Luôn là phép so sánh.

Một thao tác có thời gian thực hiện không phụ thuộc vào kích thước đầu vào, được sử dụng làm đơn vị đo lường.

Bất kỳ dòng lệnh nào trong chương trình.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 30: Nếu một thuật toán có độ phức tạp thời gian O(n), điều này có nghĩa là khi kích thước đầu vào tăng gấp 3 lần, thời gian chạy (xấp xỉ) sẽ:

Giảm đi 3 lần.

Tăng gấp 3 lần.

Tăng gấp 9 lần.

Không thay đổi.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 07

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 1: Tại sao việc đánh giá độ phức tạp thời gian của thuật toán lại quan trọng trong lập trình?

Để biết chính xác thời gian chạy trên một máy tính cụ thể.

Để so sánh tốc độ thực thi giữa các ngôn ngữ lập trình khác nhau.

Để xác định số dòng code cần viết cho thuật toán.

Để dự đoán sự thay đổi về thời gian chạy khi kích thước dữ liệu đầu vào tăng lên.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 2: Khi phân tích độ phức tạp thời gian, chúng ta thường quan tâm đến trường hợp nào của dữ liệu đầu vào để đánh giá 'tồi nhất' về hiệu suất?

Trường hợp tốt nhất (best-case).

Trường hợp trung bình (average-case).

Trường hợp xấu nhất (worst-case).

Trường hợp kích thước dữ liệu nhỏ.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 3: Ký hiệu O lớn (Big O notation) được sử dụng để làm gì trong đánh giá độ phức tạp thời gian?

Để tính chính xác số lượng phép toán cơ bản mà thuật toán thực hiện.

Để biểu diễn tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào rất lớn.

Để so sánh thời gian chạy giữa hai thuật toán trên cùng một máy tính.

Để đo lường lượng bộ nhớ chính xác mà thuật toán sử dụng.

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 4: Một thuật toán có độ phức tạp thời gian được biểu diễn bởi hàm T(n) = 5n² + 3n + 10. Độ phức tạp thời gian theo ký hiệu O lớn của thuật toán này là gì?

O(n)

O(n³)

O(1)

O(n²)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 5: Xét đoạn mã giả sau:

`tong = 0`
`cho i tu 1 den n:`
`tong = tong + i`

Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là gì?

O(n²)

O(n)

O(log n)

O(1)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 6: Xét đoạn mã giả sau:

`cho i tu 1 den n:`
`cho j tu 1 den n:`
`in ra i * j`

Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là gì?

O(n²)

O(n)

O(2n)

O(log n)

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 7: Một thuật toán tìm kiếm trên một danh sách đã sắp xếp hoạt động bằng cách liên tục chia đôi danh sách tìm kiếm. Nếu danh sách có kích thước n, độ phức tạp thời gian của thuật toán này (trong trường hợp xấu nhất) là gì?

O(n)

O(n²)

O(log n)

O(1)

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 8: Quy tắc cộng trong đánh giá độ phức tạp thời gian được áp dụng khi nào?

Khi có các vòng lặp lồng nhau.

Khi các khối lệnh được thực hiện theo trình tự nối tiếp.

Khi thuật toán gọi chính nó (đệ quy).

Khi thực hiện các phép toán số học đơn giản.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 9: Giả sử chương trình P bao gồm hai phần: Phần A có độ phức tạp O(n²) và Phần B có độ phức tạp O(n log n). Nếu Phần A chạy xong rồi đến Phần B chạy, độ phức tạp tổng thể của chương trình P là gì?

O(n²)

O(n log n)

O(n² + n log n)

O(n³ log n)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 10: Quy tắc nhân trong đánh giá độ phức tạp thời gian được áp dụng khi nào?

Khi các khối lệnh được thực hiện theo trình tự nối tiếp.

Khi thuật toán có nhiều điều kiện rẽ nhánh (if-else).

Khi chỉ có một phép toán cơ bản được thực hiện.

Khi một khối lệnh có độ phức tạp T₁ được thực hiện lặp đi lặp lại M lần, với M có thể phụ thuộc vào kích thước đầu vào n.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 11: Xét đoạn mã giả sau:

`cho i tu 1 den 100:`
`cho j tu 1 den n:`
`thuc hien phep tinh`

Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là gì?

O(n²)

O(n)

O(100n)

O(1)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 12: Thuật toán nào sau đây có độ phức tạp thời gian điển hình là O(1)?

Truy cập một phần tử tại chỉ số cho trước trong mảng.

Tìm kiếm một phần tử trong danh sách chưa sắp xếp.

Sắp xếp một danh sách bằng thuật toán sắp xếp nổi bọt.

Tìm kiếm một phần tử trong danh sách đã sắp xếp bằng tìm kiếm nhị phân.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 13: So sánh hai thuật toán: Thuật toán A có độ phức tạp O(n log n) và Thuật toán B có độ phức tạp O(n²). Với kích thước đầu vào n rất lớn, thuật toán nào thường có hiệu suất tốt hơn (chạy nhanh hơn)?

Thuật toán A (O(n log n))

Thuật toán B (O(n²))

Cả hai thuật toán có hiệu suất như nhau.

Không thể so sánh nếu không biết giá trị cụ thể của n.

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 14: Xét đoạn mã giả sau:

`i = 1`
`while i < n:` `thuc hien phep tinh` `i = i * 2` Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là gì?

O(n)

O(n/2)

O(log n)

O(1)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 15: Tại sao khi phân tích độ phức tạp thời gian bằng ký hiệu O lớn, chúng ta thường bỏ qua các hằng số và các số hạng bậc thấp?

Vì chúng không ảnh hưởng đáng kể đến tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào rất lớn.

Vì chúng rất khó để tính toán chính xác.

Vì chúng chỉ liên quan đến tốc độ của máy tính, không phải thuật toán.

Vì chúng chỉ quan trọng trong trường hợp tốt nhất của thuật toán.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 16: Một thuật toán xử lý từng phần tử trong một mảng n phần tử một lần duy nhất. Độ phức tạp thời gian của thuật toán này có khả năng là gì?

O(n²)

O(log n)

O(1)

O(n)

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 17: Xét đoạn mã giả sau:

`nua_n = n / 2`
`cho i tu 1 den nua_n:`
`thuc hien phep tinh`

Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là gì?

O(log n)

O(n)

O(n/2)

O(1)

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 18: Đâu là thứ tự tăng dần về tốc độ tăng trưởng của độ phức tạp thời gian khi n rất lớn?

O(n), O(log n), O(n²), O(1)

O(n²), O(n log n), O(n), O(log n)

O(1), O(log n), O(n), O(n log n), O(n²)

O(log n), O(1), O(n), O(n²)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 19: Một thuật toán có độ phức tạp thời gian O(2^n). Điều này có ý nghĩa gì đối với hiệu suất của thuật toán khi n tăng lên?

Thời gian chạy tăng rất nhanh theo cấp số nhân khi n tăng, chỉ phù hợp với n nhỏ.

Thời gian chạy tăng tuyến tính với n, rất hiệu quả.

Thời gian chạy hầu như không đổi khi n tăng.

Thời gian chạy tăng theo logarit của n, rất hiệu quả với n lớn.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 20: Xét hai chương trình A và B. Chương trình A gồm một vòng lặp chạy n lần, mỗi lần lặp mất O(1) thời gian. Chương trình B gồm hai vòng lặp lồng nhau, vòng ngoài chạy n lần, vòng trong chạy log n lần. Độ phức tạp của chương trình A và B lần lượt là gì?

A: O(n²), B: O(n log n)

A: O(log n), B: O(n²)

A: O(1), B: O(n log n)

A: O(n), B: O(n log n)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 21: Khi phân tích một thuật toán, nếu thời gian thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào n (ví dụ: luôn thực hiện một số phép toán cố định), thì độ phức tạp thời gian của thuật toán đó là gì?

O(1)

O(n)

O(log n)

O(n²)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 22: Cho một đoạn mã giả có cấu trúc như sau:

`// Đoạn 1`
`cho i tu 1 den n:`
`thuc hien phep tinh O(1)`

`// Đoạn 2`
`cho j tu 1 den 1000:`
`thuc hien phep tinh O(1)`

Độ phức tạp thời gian tổng thể của đoạn mã này là gì?

O(1000)

O(n + 1000)

O(n)

O(n * 1000)

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 23: Thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp một danh sách n phần tử có độ phức tạp thời gian trong trường hợp xấu nhất là gì?

O(n log n)

O(n²)

O(n)

O(log n)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 24: Xét đoạn mã giả sau:

`sum = 0`
`i = 1`
`while i <= n:` `sum = sum + i` `i = i + 1` Đoạn mã này thực hiện một vòng lặp đơn giản. Độ phức tạp thời gian của nó là gì?

O(n²)

O(log n)

O(1)

O(n)

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 25: Một thuật toán xử lý dữ liệu theo kiểu 'chia để trị', chia bài toán thành các bài toán con có kích thước bằng một nửa và kết hợp kết quả. Nếu việc chia và kết hợp mất thời gian tuyến tính O(k) trên bài toán con kích thước k, độ phức tạp điển hình của thuật toán này có thể là gì?

O(n log n)

O(n²)

O(log n)

O(n)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 26: Khi so sánh hai thuật toán A (O(n log n)) và B (O(n²)), có thể tồn tại một ngưỡng giá trị n₀ sao cho với mọi n < n₀, thuật toán B chạy nhanh hơn thuật toán A. Điều này có ý nghĩa gì?

Ký hiệu Big O là hoàn toàn không chính xác.

Luôn luôn chọn thuật toán có Big O tốt nhất, bất kể kích thước n.

Hiệu suất thực tế với n nhỏ có thể bị ảnh hưởng bởi các hằng số và số hạng bậc thấp, khác với dự đoán của Big O cho n lớn.

Điều này chỉ xảy ra nếu có lỗi trong việc tính toán Big O.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 27: Xét đoạn mã giả sau:

`cho i tu 1 den n:`
`cho j tu i den n:`
`thuc hien phep tinh`

Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là gì?

O(n)

O(n log n)

O(log n)

O(n²)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 28: Nếu một thuật toán có độ phức tạp O(n!), nó thường được coi là không khả thi (intractable) đối với các giá trị n tương đối nhỏ. Tại sao?

Vì thuật toán sử dụng quá nhiều bộ nhớ.

Vì thời gian chạy tăng trưởng cực kỳ nhanh khi n tăng, ngay cả với n nhỏ.

Vì thuật toán luôn mắc lỗi khi n lớn.

Vì thuật toán chỉ hoạt động trên dữ liệu đã sắp xếp.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 29: Khi phân tích độ phức tạp thời gian, thuật ngữ 'phép toán cơ bản' (basic operation) thường được hiểu là gì?

Một hành động có thời gian thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào n.

Toàn bộ một vòng lặp hoặc một hàm.

Một khối lệnh phức tạp bao gồm nhiều phép toán.

Chỉ các phép toán nhập/xuất dữ liệu.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 30: Một thuật toán tìm kiếm tuyến tính (Linear Search) trên một danh sách n phần tử có độ phức tạp thời gian trong trường hợp xấu nhất là gì?

O(log n)

O(n²)

O(n)

O(1)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 08

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 1: Khi đánh giá độ phức tạp thời gian của một thuật toán, chúng ta thường quan tâm đến đại lượng nào để thể hiện kích thước của bài toán?

Số lượng biến sử dụng

Tốc độ xử lý của máy tính

Ngôn ngữ lập trình

Kích thước dữ liệu đầu vào (n)

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 2: Ký hiệu O lớn (Big O notation) được sử dụng để làm gì trong phân tích độ phức tạp thời gian thuật toán?

Biểu diễn cận trên của tốc độ tăng trưởng thời gian thực hiện khi kích thước đầu vào rất lớn.

Biểu diễn thời gian thực hiện chính xác của thuật toán cho mọi kích thước đầu vào.

Biểu diễn thời gian thực hiện trung bình của thuật toán.

Biểu diễn lượng bộ nhớ mà thuật toán sử dụng.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 3: Xét đoạn mã giả sau:
```
a = b + 5
print(a)
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(1)

O(log n)

O(n^2)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 4: Xét đoạn mã giả sau, với n là kích thước dữ liệu đầu vào:
```
for i from 1 to n:
print(i)
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(1)

O(log n)

O(n)

O(n^2)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 5: Xét đoạn mã giả sau, với n là kích thước dữ liệu đầu vào:
```
for i from 1 to n:
for j from 1 to n:
print(i * j)
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(log n)

O(n log n)

O(n^2)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 6: Một thuật toán tìm kiếm trên một mảng đã sắp xếp bằng cách liên tục chia đôi phạm vi tìm kiếm. Độ phức tạp thời gian điển hình của thuật toán này (tìm kiếm nhị phân) là bao nhiêu trong trường hợp xấu nhất?

O(log n)

O(n)

O(n log n)

O(n^2)

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 7: Quy tắc cộng trong phân tích độ phức tạp thời gian được áp dụng khi nào?

Khi có các vòng lặp lồng nhau.

Khi gọi một hàm bên trong một vòng lặp.

Khi hai hoặc nhiều đoạn mã được thực hiện một cách tuần tự (nối tiếp nhau).

Khi so sánh hai thuật toán khác nhau.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 8: Quy tắc nhân trong phân tích độ phức tạp thời gian được áp dụng khi nào?

Khi hai đoạn mã được thực hiện song song.

Khi một đoạn mã (ví dụ: một vòng lặp hoặc lời gọi hàm) được thực hiện nhiều lần bên trong một cấu trúc lặp khác.

Khi các lệnh đơn được thực hiện tuần tự.

Khi kích thước đầu vào n rất lớn.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 9: Cho hàm thời gian thực hiện của một thuật toán là T(n) = 5n^3 + 2n^2 + 100. Độ phức tạp thời gian của thuật toán này theo ký hiệu O lớn là gì?

O(n^2)

O(n^3 + n^2)

O(n^3 + 100)

O(n^3)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 10: Tại sao khi sử dụng ký hiệu O lớn, chúng ta bỏ qua các hệ số hằng số và các số hạng bậc thấp?

Vì ký hiệu O lớn mô tả tốc độ tăng trưởng của thời gian thực hiện khi n tiến tới vô cùng, lúc đó các số hạng bậc cao chiếm ưu thế.

Vì các hệ số hằng số và số hạng bậc thấp phụ thuộc vào ngôn ngữ lập trình.

Vì chúng không ảnh hưởng đến tổng thời gian thực hiện.

Vì chúng chỉ quan trọng đối với kích thước đầu vào nhỏ.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 11: Sắp xếp các độ phức tạp thời gian sau theo thứ tự từ tốt nhất (nhanh nhất) đến tệ nhất (chậm nhất) khi n rất lớn: O(n^2), O(n), O(log n), O(1), O(n log n).

O(n^2), O(n log n), O(n), O(log n), O(1)

O(1), O(log n), O(n), O(n log n), O(n^2)

O(1), O(n), O(log n), O(n log n), O(n^2)

O(log n), O(1), O(n), O(n log n), O(n^2)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 12: Một thuật toán có độ phức tạp thời gian O(n log n). Điều này có nghĩa là gì?

Thời gian thực hiện tăng gấp đôi khi kích thước đầu vào tăng gấp đôi.

Thời gian thực hiện không phụ thuộc vào kích thước đầu vào.

Thời gian thực hiện tăng nhanh hơn tuyến tính nhưng chậm hơn bình phương khi kích thước đầu vào tăng.

Thời gian thực hiện tăng theo hàm mũ của kích thước đầu vào.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 13: Xét đoạn mã giả sau, với n là kích thước dữ liệu đầu vào:
```
sum = 0
for i from 1 to 100:
sum = sum + i
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(1)

O(n)

O(100)

O(log n)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 14: Tại sao việc đánh giá độ phức tạp thời gian (thường là trường hợp xấu nhất) lại quan trọng đối với lập trình viên?

Để biết chính xác thời gian chạy trên mọi máy tính.

Để dự đoán hiệu suất của thuật toán khi xử lý dữ liệu lớn và so sánh các thuật toán khác nhau.

Để xác định thuật toán nào tiêu tốn ít bộ nhớ nhất.

Để tìm ra lỗi cú pháp trong mã nguồn.

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 15: Một thuật toán có độ phức tạp thời gian O(2^n). Kiểu độ phức tạp này thường xuất hiện trong các bài toán nào?

Các bài toán tìm kiếm trên mảng.

Các bài toán sắp xếp hiệu quả.

Các bài toán xử lý dữ liệu lớn theo luồng.

Các bài toán vét cạn (brute force) hoặc đệ quy theo kiểu sinh cây nhị phân.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 16: Xét đoạn mã giả sau:
```
for i from 1 to n:
# Lệnh đơn
for j from 1 to n*n:
# Lệnh đơn
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n) + O(n^2)

O(n^2)

O(n^3)

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 17: Xét đoạn mã giả sau:
```
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(log n)

O(n/2)

O(1)

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 18: Tại sao O(n) lại được xem là hiệu quả hơn O(n^2) khi n rất lớn?

Vì tốc độ tăng trưởng của n chậm hơn nhiều so với n^2 khi n tăng.

Vì O(n) sử dụng ít bộ nhớ hơn O(n^2).

Vì O(n^2) chỉ áp dụng cho các bài toán sắp xếp.

Vì O(n) có hệ số hằng số nhỏ hơn.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 19: Cho một thuật toán có thời gian thực hiện được mô tả bằng hàm T(n) = 3n + 5. Độ phức tạp thời gian của thuật toán này là gì?

O(1)

O(3n)

O(n)

O(n+5)

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 20: Xét một hàm đệ quy đơn giản gọi chính nó một lần với đầu vào giảm đi 1, ví dụ `f(n) = f(n-1) + 1` với điều kiện dừng khi n=0. Độ phức tạp thời gian của hàm này (nếu mỗi bước tính toán là O(1)) là gì?

O(log n)

O(n log n)

O(n^2)

O(n)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 21: Khi so sánh hai thuật toán A (độ phức tạp O(n log n)) và B (độ phức tạp O(n^2)) trên dữ liệu có kích thước n rất lớn, thuật toán nào thường được ưu tiên?

Thuật toán A, vì O(n log n) tăng chậm hơn O(n^2).

Thuật toán B, vì O(n^2) thường dễ cài đặt hơn.

Cả hai thuật toán có hiệu suất tương đương.

Không thể xác định nếu không biết hệ số hằng số.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 22: Xét đoạn mã giả sau, với n là kích thước dữ liệu đầu vào:
```
for i from 1 to n:
for j from i to n:
print(i, j)
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 23: Thuật toán sắp xếp nổi bọt (Bubble Sort) đơn giản nhất có độ phức tạp thời gian trong trường hợp xấu nhất và trung bình là bao nhiêu?

O(n)

O(n^2)

O(n log n)

O(log n)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 24: Độ phức tạp thời gian O(1) có nghĩa là gì?

Thời gian thực hiện là hằng số, không phụ thuộc vào kích thước đầu vào n.

Thời gian thực hiện tăng tuyến tính theo n.

Thời gian thực hiện rất nhanh.

Thời gian thực hiện chỉ gồm 1 phép toán.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 25: Khi phân tích một đoạn mã chứa lời gọi đến một hàm khác, làm thế nào để xác định độ phức tạp thời gian của đoạn mã đó?

Luôn xem lời gọi hàm là O(1).

Bỏ qua lời gọi hàm vì nó là một đơn vị riêng biệt.

Chỉ xem xét độ phức tạp của các lệnh bên ngoài hàm.

Phân tích độ phức tạp của hàm được gọi và kết hợp nó với độ phức tạp của đoạn mã gọi (dùng quy tắc cộng hoặc nhân tùy cấu trúc).

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 26: Xét đoạn mã giả sau:
```
if condition:
for i from 1 to n:
print(i)
else:
for i from 1 to 100:
print(i)
```
Độ phức tạp thời gian của đoạn mã này trong trường hợp xấu nhất là bao nhiêu?

O(100)

O(n)

O(n + 100)

O(n^2)

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 27: Tại sao việc ước lượng độ phức tạp thời gian theo trường hợp xấu nhất (worst-case) lại phổ biến trong lý thuyết khoa học máy tính?

Vì nó là trường hợp dễ phân tích nhất.

Vì nó luôn phản ánh đúng hiệu suất thực tế.

Vì nó cung cấp một đảm bảo về giới hạn trên của thời gian thực hiện, giúp dự đoán hiệu suất đáng tin cậy.

Vì hầu hết các thuật toán đều đạt đến trường hợp xấu nhất khi chạy.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 28: Một thuật toán xử lý từng cặp phần tử trong một tập hợp n phần tử (ví dụ: so sánh mọi cặp). Độ phức tạp thời gian của thuật toán này có thể là bao nhiêu?

O(n)

O(n log n)

O(log n)

O(n^2)

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 29: Xét đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to 10:
print(i, j)
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(10n)

O(n)

O(n^2)

O(10)

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 30: Trong các độ phức tạp sau, độ phức tạp nào cho thấy hiệu suất của thuật toán *kém nhất* khi n rất lớn?

O(n log n)

O(n^2)

O(2^n)

O(n!)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 09

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 1: Tại sao việc đánh giá độ phức tạp thời gian của thuật toán lại quan trọng trong lập trình, đặc biệt khi xử lý dữ liệu lớn?

Chỉ để so sánh các thuật toán trên lý thuyết.

Để biết chính xác thời gian chạy trên một máy tính cụ thể.

Để làm cho mã nguồn ngắn gọn hơn.

Để dự đoán hiệu năng của thuật toán khi kích thước dữ liệu đầu vào tăng lên.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 2: Ký hiệu Big O (ví dụ: O(n)) trong phân tích độ phức tạp thời gian biểu thị điều gì về thời gian chạy của thuật toán?

Giới hạn trên (tốc độ tăng trưởng tối đa) của thời gian chạy khi kích thước đầu vào rất lớn.

Thời gian chạy chính xác của thuật toán.

Giới hạn dưới (thời gian chạy tối thiểu) của thuật toán.

Thời gian chạy trung bình của thuật toán.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 3: Xem xét đoạn mã giả sau: `print('Hello'); a = 5 + 3; b = a * 2;`. Độ phức tạp thời gian của đoạn mã này là gì?

O(1)

O(n)

O(log n)

O(n^2)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 4: Đoạn mã giả sau tính tổng các phần tử trong một danh sách có kích thước n: `tong = 0; for i from 0 to n-1: tong = tong + danh_sach[i];`. Độ phức tạp thời gian của đoạn mã này là gì?

O(1)

O(n)

O(n log n)

O(n^2)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 5: Đoạn mã giả sau thực hiện sắp xếp nổi bọt (Bubble Sort) trên một danh sách có kích thước n: `for i from 0 to n-2: for j from 0 to n-i-2: if danh_sach[j] > danh_sach[j+1]: swap(danh_sach[j], danh_sach[j+1]);`. Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán này là gì?

O(n)

O(n log n)

O(log n)

O(n^2)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 6: Thuật toán tìm kiếm nhị phân (Binary Search) trên một danh sách đã được sắp xếp với n phần tử có độ phức tạp thời gian là O(log n). Điều này có nghĩa là gì?

Thời gian tìm kiếm tăng tuyến tính với n.

Thời gian tìm kiếm không phụ thuộc vào n.

Thời gian tìm kiếm tăng rất chậm khi n tăng lên, thường liên quan đến số lần chia đôi danh sách.

Thời gian tìm kiếm tăng theo bình phương của n.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 7: Các thuật toán sắp xếp hiệu quả như Merge Sort hoặc Quick Sort thường có độ phức tạp thời gian là O(n log n). So với O(n^2), O(n log n) có ưu điểm gì khi n rất lớn?

Tốc độ tăng trưởng thời gian nhanh hơn.

Tốc độ tăng trưởng thời gian chậm hơn đáng kể.

Sử dụng ít bộ nhớ hơn.

Dễ cài đặt hơn.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 8: Nếu một chương trình bao gồm hai phần chạy nối tiếp nhau: Phần A có độ phức tạp O(n) và Phần B có độ phức tạp O(n^2). Độ phức tạp thời gian tổng thể của chương trình này là gì theo quy tắc cộng?

O(n)

O(n log n)

O(n^3)

O(n^2)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 9: Nếu một vòng lặp chạy n lần và bên trong vòng lặp đó gọi một hàm mất thời gian O(log n) cho mỗi lần gọi. Độ phức tạp thời gian tổng thể của đoạn mã này là gì theo quy tắc nhân?

O(n + log n)

O(max(n, log n))

O(n log n)

O(n^2 log n)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 10: Khi so sánh các độ phức tạp thời gian O(n) và O(n^2) cho cùng một bài toán, phát biểu nào sau đây là đúng khi kích thước đầu vào n trở nên rất lớn?

Thuật toán O(n) sẽ chạy nhanh hơn đáng kể so với thuật toán O(n^2).

Thuật toán O(n^2) sẽ chạy nhanh hơn đáng kể so với thuật toán O(n).

Hai thuật toán sẽ có thời gian chạy tương đương nhau.

Không thể so sánh hiệu suất chỉ dựa vào ký hiệu Big O.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 11: Xem xét đoạn mã giả sau: `for i from 0 to n-1: print(i); for j from 0 to n-1: print(j);`. Độ phức tạp thời gian của đoạn mã này là gì?

O(n^2)

O(log n)

O(n)

O(1)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 12: Xem xét đoạn mã giả sau: `for i from 0 to n-1: for j from 0 to i: print(i, j);`. Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n log n)

O(log n)

O(n^2)

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 13: Trong phân tích độ phức tạp thời gian, tại sao chúng ta thường chỉ quan tâm đến hạng tử có bậc cao nhất và bỏ qua các hệ số hằng số?

Vì các hạng tử bậc thấp và hằng số không ảnh hưởng đến thời gian chạy.

Vì khi n rất lớn, hạng tử bậc cao nhất sẽ chi phối tốc độ tăng trưởng của thời gian chạy.

Để làm cho việc tính toán độ phức tạp đơn giản hơn.

Vì chúng ta chỉ quan tâm đến trường hợp tốt nhất.

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 14: Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất (hiệu quả nhất) khi n rất lớn?

O(log n)

O(n)

O(n log n)

O(n^2)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 15: Nếu một thuật toán có độ phức tạp O(n) và mất 5 giây để xử lý dữ liệu có kích thước n = 1000. Ước lượng thời gian cần thiết để xử lý dữ liệu có kích thước n = 2000 là bao nhiêu?

5 giây

10 giây

Khoảng 10 giây

Khoảng 20 giây

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 16: Nếu một thuật toán có độ phức tạp O(n^2) và mất 2 giây để xử lý dữ liệu có kích thước n = 100. Ước lượng thời gian cần thiết để xử lý dữ liệu có kích thước n = 200 là bao nhiêu?

4 giây

8 giây

Khoảng 4 giây

Khoảng 8 giây

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 17: Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) trên một danh sách n phần tử (trong trường hợp xấu nhất) là gì?

O(log n)

O(n)

O(n log n)

O(n^2)

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 18: Xem xét đoạn mã giả sau: `i = n; while i > 1: print(i); i = i / 2;`. Độ phức tạp thời gian của đoạn mã này là gì?

O(log n)

O(n)

O(n log n)

O(sqrt(n))

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 19: Thuật toán có độ phức tạp thời gian O(2^n) được gọi là thuật toán có độ phức tạp gì?

Đa thức

Logarit

Mũ (Exponential)

Tuyến tính

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 20: Đối với một kích thước đầu vào n đủ lớn, thứ tự hiệu quả từ TỐT NHẤT đến KÉM NHẤT của các độ phức tạp sau là gì: O(n log n), O(n^2), O(n), O(log n)?

O(n^2), O(n log n), O(n), O(log n)

O(log n), O(n), O(n log n), O(n^2)

O(n), O(log n), O(n log n), O(n^2)

O(log n), O(n log n), O(n), O(n^2)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 21: Khi phân tích độ phức tạp thời gian, trường hợp nào thường được quan tâm nhất và tại sao?

Trường hợp xấu nhất, vì nó đảm bảo rằng thuật toán sẽ không bao giờ mất nhiều thời gian hơn mức ước lượng.

Trường hợp tốt nhất, vì nó cho biết hiệu suất tối đa có thể đạt được.

Trường hợp trung bình, vì nó phản ánh hiệu suất điển hình.

Cả ba trường hợp đều quan trọng như nhau.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 22: Xem xét đoạn mã giả sau: `for i from 0 to n-1: print(i); for j from 0 to n*n-1: print(j);`. Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n log n)

O(n + n^2)

O(n^2)

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 23: Một thuật toán xử lý mỗi cặp phần tử trong một tập hợp n phần tử. Ví dụ, so sánh mọi phần tử với mọi phần tử khác. Độ phức tạp thời gian điển hình của thuật toán này là gì?

O(n)

O(n log n)

O(n^2)

O(2^n)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 24: Nếu một thuật toán có độ phức tạp O(log n) và mất 0.1 giây để xử lý dữ liệu có kích thước n = 1024. Ước lượng thời gian cần thiết để xử lý dữ liệu có kích thước n = 4096 là bao nhiêu? (Lưu ý: log₂1024 = 10, log₂4096 = 12)

0.2 giây

Khoảng 0.12 giây

0.4 giây

Khoảng 0.1 giây

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 25: Xem xét đoạn mã giả sau: `for i from 0 to n-1: for j from 0 to 10: print(i, j);`. Độ phức tạp thời gian của đoạn mã này là gì?

O(n^2)

O(n)

O(10n)

O(log n)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 26: Thuật toán có độ phức tạp O(n!) là cực kỳ kém hiệu quả. Bài toán điển hình nào có thể dẫn đến độ phức tạp này nếu giải bằng phương pháp vét cạn?

Bài toán người du lịch (Traveling Salesperson Problem) khi tìm tất cả các hoán vị đường đi.

Tìm kiếm một phần tử trong danh sách đã sắp xếp.

Tính tổng các phần tử trong mảng.

Sắp xếp danh sách bằng Merge Sort.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 27: Khi phân tích độ phức tạp thời gian của một thuật toán đệ quy, yếu tố chính nào thường quyết định đến Big O của nó?

Số lượng dòng code trong hàm đệ quy.

Tên của hàm đệ quy.

Kiểu dữ liệu trả về của hàm.

Số lượng lời gọi đệ quy và chi phí xử lý tại mỗi cấp đệ quy.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 28: Một thuật toán duyệt qua tất cả các tập con có thể có của một tập hợp n phần tử. Độ phức tạp thời gian điển hình của thuật toán này là gì?

O(n)

O(n^2)

O(2^n)

O(n log n)

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 29: Xem xét đoạn mã giả sau: `tong = 0; for i from 0 to n-1: tong = tong + i; for j from 0 to n-1: for k from 0 to n-1: print(j, k);`. Độ phức tạp thời gian tổng thể của đoạn mã này là gì?

O(n)

O(n log n)

O(n + n^2)

O(n^2)

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 30: Điều gì xảy ra với hiệu năng của một thuật toán có độ phức tạp O(2^n) khi kích thước đầu vào n tăng chỉ một lượng nhỏ (ví dụ từ n=20 lên n=21)?

Thời gian chạy tăng lên gấp đôi.

Thời gian chạy tăng lên một lượng nhỏ.

Thời gian chạy tăng lên theo bình phương.

Thời gian chạy tăng lên theo logarit.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức 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 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Đề 10

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 1: 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ì?

Để biết thuật toán chạy mất bao nhiêu giây trên một máy tính cụ thể.

Để xác định số dòng code cần thiết cho thuật toán.

Để ước lượng tốc độ tăng trưởng thời gian chạy của thuật toán khi kích thước đầu vào tăng lên.

Để kiểm tra xem thuật toán có chạy đúng với mọi trường hợp hay không.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 2: Ký hiệu O lớn (Big O notation) O(g(n)) trong phân tích độ phức tạp thời gian của thuật toán thường được dùng để biểu thị điều gì?

Giới hạn trên (upper bound) tiệm cận của thời gian chạy khi kích thước đầu vào n đủ lớn.

Thời gian chạy chính xác của thuật toán với mọi kích thước đầu vào n.

Giới hạn dưới (lower bound) tiệm cận của thời gian chạy.

Thời gian chạy trung bình của thuật toán.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 3: Giả sử một chương trình gồm hai phần thực hiện nối tiếp nhau. Phần thứ nhất có độ phức tạp O(n), phần thứ hai có độ phức tạp O(n²). Theo quy tắc cộng, độ phức tạp thời gian tổng thể của chương trình này là bao nhiêu?

O(n)

O(n log n)

O(n³)

O(n²)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 4: Một vòng lặp `for` chạy từ 1 đến n, và mỗi lần lặp thực hiện một số lượng thao tác cố định (không phụ thuộc vào n). Độ phức tạp thời gian của vòng lặp này là gì?

O(1)

O(n)

O(log n)

O(n²)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 5: Xét đoạn mã giả sau: `for i from 1 to n: for j from 1 to m: perform_constant_operation()` (với n và m là kích thước đầu vào). Độ phức tạp thời gian của đoạn mã này là gì?

O(n * m)

O(n + m)

O(max(n, m))

O(n²)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 6: Khi tính độ phức tạp thời gian O lớn, chúng ta thường bỏ qua các hằng số nhân và các số hạng bậc thấp. Ví dụ, nếu thời gian chạy thực tế là T(n) = 3n² + 5n + 10, thì độ phức tạp O lớn là gì?

O(3n²)

O(n² + n)

O(n²)

O(1)

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 7: Thuật toán có độ phức tạp thời gian O(1) nghĩa là gì?

Thời gian chạy tăng tuyến tính với kích thước đầu vào.

Thời gian chạy là một hằng số và không phụ thuộc vào kích thước đầu vào (khi n đủ lớn).

Thời gian chạy tăng theo hàm logarit của kích thước đầu vào.

Thời gian chạy tăng theo bình phương của kích thước đầu vào.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 8: Thuật toán tìm kiếm tuyến tính trên một mảng n phần tử (duyệt qua từng phần tử để tìm) 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²)

O(1)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 9: Thuật toán sắp xếp chọn (Selection Sort) trên một mảng n phần tử có độ phức tạp thời gian là O(n²). Điều này có ý nghĩa gì khi so sánh với thuật toán có độ phức tạp O(n log n)?

Sắp xếp chọn luôn nhanh hơn O(n log n) với mọi n.

Với n đủ lớn, O(n log n) sẽ chạy chậm hơn sắp xếp chọn.

Độ phức tạp O(n²) không ảnh hưởng đến hiệu suất thực tế.

Với n đủ lớn, sắp xếp chọn (O(n²)) sẽ chạy chậm hơn đáng kể so với thuật toán O(n log n).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 10: Thuật toán tìm kiếm nhị phân trên một mảng đã sắp xếp n phần tử có độ phức tạp thời gian là bao nhiêu?

O(n)

O(log n)

O(n²)

O(n log n)

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 11: So sánh tốc độ tăng trưởng của O(n) và O(n²). Với giá trị n rất lớn, thuật toán có độ phức tạp nào sẽ hiệu quả hơn?

O(n) hiệu quả hơn O(n²).

O(n²) hiệu quả hơn O(n).

Hai độ phức tạp này có hiệu quả tương đương với n lớn.

Không thể so sánh chỉ dựa vào ký hiệu O lớn.

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 12: Độ phức tạp thời gian O(n!) (giai thừa) thường xuất hiện trong các bài toán nào?

Các bài toán tìm kiếm trên mảng.

Các bài toán sắp xếp thông thường.

Các bài toán liên quan đến việc thử tất cả các hoán vị hoặc tổ hợp (ví dụ: bài toán người bán hàng - Brute Force).

Các bài toán đơn giản chỉ có các phép gán và tính toán cơ bản.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 13: Xét đoạn mã giả sau: `sum = 0; for i from 1 to 100: sum = sum + i;`. Kích thước đầu vào n không ảnh hưởng đến số lần lặp của vòng lặp. Độ phức tạp thời gian của đoạn mã này là gì?

O(1)

O(n)

O(log n)

O(100)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 14: Xét đoạn mã giả sau: `for i from 1 to n: perform_operation_O_of_n();`. Giả sử `perform_operation_O_of_n()` là một hàm có độ phức tạp O(n). Độ phức tạp thời gian tổng thể của đoạn mã này là gì?

O(n)

O(log n)

O(n log n)

O(n²)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 15: Khi phân tích độ phức tạp thời gian, tại sao chúng ta lại đếm số lượng các 'thao tác cơ bản' thay vì đo thời gian chạy thực tế bằng đồng hồ?

Việc đếm thao tác cơ bản dễ thực hiện hơn.

Việc đếm thao tác cơ bản giúp đánh giá hiệu suất thuật toán một cách độc lập với tốc độ phần cứng và các yếu tố môi trường khác.

Việc đếm thao tác cơ bản cho kết quả chính xác hơn thời gian chạy thực tế.

Thời gian chạy thực tế không cung cấp thông tin hữu ích về thuật toán.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 16: Xét đoạn mã giả sau: `if condition_is_true: block_A() else: block_B()`. Giả sử `block_A()` có độ phức tạp O(n²) và `block_B()` có độ phức tạp O(n). Độ phức tạp thời gian của toàn bộ cấu trúc điều kiện này là gì trong trường hợp xấu nhất?

O(n)

O(n³)

O(n²)

O(n + n²)

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 17: Độ phức tạp O(log n) thường xuất hiện trong các thuật toán sử dụng kỹ thuật nào?

Chia để trị (Divide and Conquer) làm giảm phạm vi tìm kiếm/xử lý theo cấp số nhân (ví dụ: tìm kiếm nhị phân).

Duyệt qua tất cả các cặp phần tử.

Truy cập trực tiếp vào một phần tử bằng chỉ số.

Lặp qua toàn bộ danh sách một lần.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 18: Xét đoạn mã giả sau: `i = 1; while i < n: print(i); i = i * 2;`. Độ phức tạp thời gian của vòng lặp này là gì?

O(n)

O(log n)

O(n²)

O(1)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 19: Thuật toán có độ phức tạp thời gian nào sau đây được coi là kém hiệu quả nhất khi xử lý dữ liệu có kích thước n rất lớn?

O(n log n)

O(n²)

O(n³)

O(2^n)

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 20: Trong phân tích độ phức tạp O lớn, 'trường hợp xấu nhất' (worst-case) thường được tập trung phân tích vì lý do gì?

Trường hợp xấu nhất luôn xảy ra thường xuyên nhất.

Trường hợp xấu nhất dễ phân tích nhất.

Trường hợp xấu nhất cung cấp giới hạn trên về hiệu suất, đảm bảo rằng thuật toán sẽ không bao giờ chạy chậm hơn mức đó.

Trường hợp xấu nhất là trường hợp duy nhất có thể phân tích bằng O lớn.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 21: Xét đoạn mã giả sau: `for i from 1 to n: for j from i to n: perform_constant_operation()`. Độ phức tạp thời gian của đoạn mã này là gì?

O(n)

O(n log n)

O(m * n) nếu m=n

O(n²)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 22: Thuật toán sắp xếp trộn (Merge Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

O(n²)

O(n)

O(n log n)

O(log n)

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 23: Phát biểu nào sau đây là đúng khi so sánh các độ phức tạp thời gian cho giá trị n đủ lớn?

O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)

O(n²) < O(n log n) < O(n) < O(log n) < O(2^n)

O(2^n) < O(n²) < O(n log n) < O(n) < O(log n)

O(log n) < O(n log n) < O(n) < O(n²) < O(2^n)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 24: Một thuật toán có độ phức tạp thời gian O(n³). Nếu kích thước đầu vào n tăng gấp đôi, thời gian chạy của thuật toán sẽ tăng lên khoảng bao nhiêu lần?

2 lần

4 lần

6 lần

8 lần

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 25: Độ phức tạp thời gian O(n log n) thường được coi là hiệu quả cho các bài toán sắp xếp trên tập dữ liệu lớn. Ví dụ nào sau đây có độ phức tạp O(n log n)?

Sắp xếp nổi bọt (Bubble Sort).

Sắp xếp nhanh (Quick Sort).

Sắp xếp chèn (Insertion Sort).

Sắp xếp chọn (Selection Sort).

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 26: Xét một thuật toán thực hiện lần lượt các bước sau: Bước 1: Tìm kiếm nhị phân (O(log n)). Bước 2: Duyệt qua mảng (O(n)). Bước 3: Sắp xếp chèn (O(n²)). Độ phức tạp thời gian tổng thể của thuật toán này là gì?

O(log n)

O(n)

O(n log n)

O(n²)

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 27: Xét đoạn mã giả sau: `for i from 1 to n: perform_operation_A(); perform_operation_B();`. Giả sử `perform_operation_A()` có độ phức tạp O(1) và `perform_operation_B()` có độ phức tạp O(n). Độ phức tạp thời gian tổng thể của đoạn mã này là gì?

O(n)

O(n log n)

O(n²)

O(1)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 28: Đâu là yếu tố chính mà ký hiệu O lớn (Big O) tập trung vào khi đánh giá hiệu suất thuật toán?

Tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào rất lớn (hành vi tiệm cận).

Số lượng bộ nhớ mà thuật toán sử dụng.

Khả năng đọc hiểu của mã nguồn.

Thời gian chạy chính xác trên một máy tính cụ thể.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 29: Thuật toán nhân hai số nguyên n chữ số bằng phương pháp thông thường có độ phức tạp O(n²). Thuật toán Karatsuba cải tiến có độ phức tạp xấp xỉ O(n^1.585). Điều này cho thấy điều gì?

Thuật toán Karatsuba chỉ hiệu quả với n nhỏ.

Với n đủ lớn, thuật toán Karatsuba sẽ nhanh hơn đáng kể so với phương pháp thông thường.

Sự khác biệt về độ phức tạp không đáng kể.

Độ phức tạp O(n^1.585) thực tế là O(n²).

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 30: Trong phân tích độ phức tạp, đâu là độ phức tạp thời gian tốt nhất có thể đạt được cho một thuật toán (trừ O(0) không có ý nghĩa)?

O(1)

O(log n)

O(n)

O(n log n)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Đề trắc nghiệm liên quan:

Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 5: Kết Nối Máy Tính Với Các Thiết Bị Số
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 22: Thực Hành Bài Toán Sắp Xếp
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 28: Tạo Ảnh Động
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 17: Dữ Liệu Mảng Một Chiều Và Hai Chiều
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 27: Thực Hành Thiết Kế Chương Trình Theo Phương Pháp Làm Mịn Dần

Đề 01

Đề 02

Đề 03

Đề 04

Đề 05

Đề 06

Đề 07

Đề 08

Đề 09

Đề 10

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Đề trắc nghiệm liên quan:

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha