12+ Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 25: Thực Hành Xác Định Độ Phức Tạp Thời Gian Thuật Toán

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

• A. Lượng bộ nhớ mà thuật toán sử dụng.
• B. Số lượng các phép tính cơ bản thực hiện theo kích thước dữ liệu đầu vào.
• C. Tổng thời gian thực thi thực tế trên một máy tính cụ thể.
• D. Mức độ dễ đọc và hiểu của mã nguồn thuật toán.

Câu 2: Ký hiệu Big O (ví dụ: O(n), O(n^2), O(log n)) trong phân tích độ phức tạp thời gian biểu thị điều gì?

• A. 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 lớn.
• B. Thời gian chạy chính xác của thuật toán trên mọi bộ dữ liệu.
• C. Thời gian chạy trung bình của thuật toán.
• D. Giới hạn dưới (tốc độ tăng trưởng tối thiểu) của thời gian chạy.

Câu 3: Xem xét đoạn mã giả sau:
```
function processArray(arr):
n = length(arr)
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?

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

Câu 4: Xem xét đoạn mã giả sau:
```
function printPairs(arr):
n = length(arr)
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?

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

Câu 5: Xem xét đoạn mã giả sau:
```
function findMax(arr):
n = length(arr)
if n == 0:
return null
max_val = arr[0]
for i from 1 to n-1:
if arr[i] > max_val:
max_val = arr[i]
return max_val
```
Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán tìm giá trị lớn nhất này là bao nhiêu?

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

Câu 6: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp tốt nhất (best-case) là bao nhiêu?

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

Câu 7: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất (worst-case) là bao nhiêu?

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

Câu 8: Thuật toán sắp xếp chọn (Selection Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

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

Câu 9: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

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

Câu 10: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp tốt nhất (best-case) là bao nhiêu?

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

Câu 11: Xem xét đoạn mã giả sau:
```
function example(n):
count = 0
for i from 1 to n:
for j from 1 to i:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(n^3)
• D. O(n^2)

Câu 12: Xem xét đoạn mã giả sau:
```
function process(n):
k = 1
while k < n: print(k) k = k * 2 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

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

Câu 13: 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 dữ liệu đầu vào n rất lớn, phát biểu nào sau đây là đúng nhất về hiệu suất của hai thuật toán?

• A. Thuật toán A (O(n)) sẽ chạy nhanh hơn đáng kể so với thuật toán B (O(n^2)).
• B. Thuật toán B (O(n^2)) sẽ chạy nhanh hơn đáng kể so với thuật toán A (O(n)).
• C. Hai thuật toán sẽ có hiệu suất tương đương.
• D. Không thể so sánh hiệu suất chỉ dựa vào ký hiệu Big O.

Câu 14: Nếu một thuật toán có độ phức tạp thời gian O(n^3) và mất 1 giây để xử lý dữ liệu có kích thước n=100. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=200 là bao nhiêu?

• A. 2 giây
• B. 4 giây
• C. 8 giây
• D. 16 giây

Câu 15: Nếu một thuật toán có độ phức tạp thời gian O(n) và mất 1 giây để xử lý dữ liệu có kích thước n=1000. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=10000 là bao nhiêu?

• A. 1 giây
• B. 5 giây
• C. 50 giây
• D. 10 giây

Câu 16: Trong phân tích độ phức tạp thời gian bằng ký hiệu Big O, khi biểu thức thời gian là một đa thức (ví dụ: 5n^2 + 3n + 10), ta chỉ giữ lại thành phần nào để xác định độ phức tạp?

• A. Thành phần có hệ số lớn nhất.
• B. Tất cả các thành phần và hệ số.
• C. Thành phần có bậc (lũy thừa của n) cao nhất, bỏ qua hệ số.
• D. Thành phần hằng số.

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

• A. Chia đôi phạm vi tìm kiếm/xử lý (ví dụ: tìm kiếm nhị phân).
• B. Duyệt qua tất cả các cặp phần tử trong mảng.
• C. Duyệt qua từng phần tử một lần duy nhất.
• D. Thực hiện một số lượng phép tính cố định, không phụ thuộc vào kích thước đầu vào.

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

• A. Thời gian chạy tăng tuyến tính theo n.
• B. Thời gian chạy tăng theo logarit của n.
• C. Thời gian chạy tăng theo bình phương của n.
• D. 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.

Câu 19: Sắp xếp các độ phức tạp thời gian sau theo thứ tự tăng dần về tốc độ tăng trưởng khi n rất lớn: O(n^2), O(log n), O(n), O(1).

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

Câu 20: Tại sao việc phân tích độ phức tạp thời gian lại quan trọng trong lập trình, đặc biệt với các bài toán lớn?

• A. Chỉ để so sánh các ngôn ngữ lập trình khác nhau.
• B. Để biết chính xác thời gian chạy trên máy tính của bạn.
• C. Để dự đoán hiệu suất (thời gian chạy) của thuật toán khi kích thước dữ liệu đầu vào trở nên rất lớn.
• D. Để tìm lỗi cú pháp trong mã nguồn.

Câu 21: Một thuật toán bao gồm hai phần liên tiếp. Phần thứ nhất có độ phức tạp O(n^2), phần thứ hai có độ phức tạp O(n). Độ phức tạp thời gian tổng thể của thuật toán này là bao nhiêu?

• A. O(n)
• B. O(n + n^2)
• C. O(n log n)
• D. O(n^2)

Câu 22: Xem xét đoạn mã giả sau:
```
function anotherExample(n):
sum1 = 0
for i from 1 to n:
sum1 = sum1 + i
sum2 = 0
for j from 1 to n:
sum2 = sum2 + j*2
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

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

Câu 23: Khi phân tích độ phức tạp thời gian của thuật toán sắp xếp chọn (Selection Sort), tại sao chúng ta thường nói độ phức tạp là O(n^2) cho cả trường hợp tốt nhất, trung bình và xấu nhất?

• A. Số lượng phép so sánh và đổi chỗ luôn tỷ lệ với n^2, bất kể dữ liệu đầu vào.
• B. Thuật toán có thể dừng sớm trong trường hợp tốt nhất.
• C. Chỉ có trường hợp xấu nhất mới có độ phức tạp O(n^2).
• D. Độ phức tạp trung bình là O(n log n).

Câu 24: Cho một đoạn mã có độ phức tạp thời gian là O(n). Nếu chạy đoạn mã này với n = 1000 mất 0.1 giây, ước tính thời gian chạy khi n = 5000 là bao nhiêu?

• A. 0.1 giây
• B. 0.25 giây
• C. 0.5 giây
• D. 1 giây

Câu 25: Xem xét đoạn mã giả sau:
```
function trickyLoop(n):
count = 0
i = 1
while i <= n: count = count + 1 i = i * 3 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(log n)
• C. O(n^2)
• D. O(sqrt(n))

Câu 26: Trong phân tích thuật toán, trường hợp "trung bình" (average-case) của độ phức tạp thời gian mô tả điều gì?

• A. Thời gian chạy nhanh nhất có thể.
• B. Thời gian chạy chậm nhất có thể.
• C. Thời gian chạy trên một bộ dữ liệu đầu vào "điển hình" hoặc "ngẫu nhiên".
• D. Thời gian chạy khi dữ liệu đã được sắp xếp.

Câu 27: Thuật toán nào trong số các thuật toán sắp xếp đơn giản sau đây có độ phức tạp thời gian tốt nhất trong trường hợp mảng đã được sắp xếp?

• A. Bubble Sort
• B. Selection Sort
• C. Tất cả đều có O(n^2) trong trường hợp tốt nhất.
• D. Không có thuật toán nào tốt hơn O(n log n) trong trường hợp tốt nhất.

Câu 28: Xem xét đoạn mã giả sau:
```
function processMatrix(matrix):
rows = matrix.height
cols = matrix.width
sum = 0
for i from 0 to rows-1:
for j from 0 to cols-1:
sum = sum + matrix[i][j]
```
Nếu ma trận có kích thước m x n (rows = m, cols = n), độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(m + n)
• B. O(max(m, n))
• C. O(log(m*n))
• D. O(m * n)

Câu 29: Tại sao các hằng số và các thành phần bậc thấp hơn thường bị bỏ qua trong phân tích độ phức tạp Big O?

• A. Vì chúng không đáng kể so với thành phần có bậc cao nhất khi n rất lớn.
• B. Vì chúng chỉ ảnh hưởng đến trường hợp tốt nhất.
• C. Vì chúng phụ thuộc vào tốc độ của máy tính cụ thể.
• D. Vì chúng chỉ liên quan đến độ phức tạp không gian, không phải thời gian.

Câu 30: Một thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

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

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, chúng ta thường quan tâm đến trường hợp nào nhất để đánh giá hiệu quả của nó với dữ liệu lớn?

• A. Trường hợp tốt nhất (Best-case)
• B. Trường hợp trung bình (Average-case)
• C. Trường hợp xấu nhất (Worst-case)
• D. Tất cả các trường hợp đều quan trọng như nhau

Câu 2: Cho đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
sum = sum + i
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là bao nhiêu?

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

Câu 3: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Nếu phần tử cần tìm nằm ở vị trí cuối cùng của mảng, thì độ phức tạp thời gian của thuật toán trong trường hợp này là gì?

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

Câu 4: Thuật toán sắp xếp chọn (Selection Sort) hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của mảng và đưa nó về đúng vị trí. Tại sao thuật toán này có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất?

• A. Thuật toán sử dụng hai vòng lặp lồng nhau, mỗi vòng lặp chạy gần n lần.
• B. Thuật toán chỉ cần một vòng lặp duy nhất chạy n lần.
• C. Thuật toán chia mảng thành hai nửa trong mỗi bước.
• D. Số lượng hoán đổi luôn là hằng số.

Câu 5: Cho hai thuật toán: Thuật toán A có độ phức tạp O(n^2) và Thuật toán B có độ phức tạp O(n log n). Khi kích thước dữ liệu n rất lớn, nhận định nào sau đây là đúng về hiệu quả thời gian chạy của hai thuật toán?

• A. Thuật toán A sẽ chạy nhanh hơn Thuật toán B.
• B. Thuật toán B sẽ chạy nhanh hơn Thuật toán A.
• C. Thời gian chạy của cả hai thuật toán là tương đương nhau.
• D. Không thể so sánh hiệu quả chỉ dựa vào độ phức tạp O lớn.

Câu 6: Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (Bubble Sort) trong trường hợp mảng đầu vào đã được sắp xếp hoàn toàn là gì?

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

Câu 7: Cho đoạn mã giả sau:
```
count = 0
for i from 1 to n:
for j from 1 to n:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

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

Câu 8: Ký hiệu O lớn (Big O notation) mô tả khía cạnh nào của hiệu quả thuật toán?

• A. Thời gian thực hiện chính xác tính bằng mili giây.
• B. Tốc độ tăng trưởng của thời gian thực hiện khi kích thước đầu vào tăng lên.
• C. Số lượng dòng mã trong thuật toán.
• D. Lượng bộ nhớ RAM mà thuật toán sử dụng.

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

• A. Thời gian thực hiện tăng tuyến tính theo kích thước dữ liệu.
• B. Thời gian thực hiện tăng theo hàm logarit của kích thước dữ liệu.
• C. Thời gian thực hiện là không đổi, không phụ thuộc vào kích thước dữ liệu.
• D. Thời gian thực hiện tăng theo bình phương của kích thước dữ liệu.

Câu 10: Giả sử thuật toán sắp xếp chọn (Selection Sort) mất 4 giây để sắp xếp một mảng có 2000 phần tử. Ước tính thời gian cần thiết để sắp xếp một mảng có 4000 phần tử bằng cùng thuật toán này là bao nhiêu?

• A. 8 giây
• B. 12 giây
• C. 10 giây
• D. 16 giây

Câu 11: Cho đoạn mã giả sau:
```
result = 0
i = 1
while i < n: result = result + 1 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à bao nhiêu?

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

Câu 12: Khi so sánh thuật toán tìm kiếm tuần tự (Linear Search - O(n)) và thuật toán tìm kiếm nhị phân (Binary Search - O(log n)) trên một mảng đã sắp xếp, nhận định nào sau đây là đúng?

• A. Tìm kiếm tuần tự luôn nhanh hơn tìm kiếm nhị phân.
• B. Tìm kiếm nhị phân chỉ hiệu quả khi mảng chưa được sắp xếp.
• C. Độ phức tạp của cả hai thuật toán là như nhau.
• D. Tìm kiếm nhị phân hiệu quả hơn đáng kể so với tìm kiếm tuần tự khi n lớn (áp dụng cho mảng đã sắp xếp).

Câu 13: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from i to n:
// Thực hiện một phép toán cơ bản
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n^3)

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

• A. 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 n rất lớn.
• B. Vì chúng chỉ xuất hiện trong trường hợp tốt nhất của thuật toán.
• C. Vì chúng chỉ liên quan đến không gian bộ nhớ, không phải thời gian.
• D. Vì việc tính toán chúng là quá phức tạp.

Câu 15: Một thuật toán xử lý dữ liệu mất 0.1 giây với n=1000. Nếu thuật toán này có độ phức tạp O(n), ước tính nó sẽ mất bao lâu để xử lý n=10000?

• A. 0.5 giây
• B. 10 giây
• C. 1 giây
• D. 0.01 giây

Câu 16: Cho đoạn mã giả sau:
```
func(n):
if n <= 1: return 1 else: return func(n-1) + func(n-1) ``` (Đây là hàm tính số Fibonacci đệ quy không tối ưu). Độ phức tạp thời gian của hàm `func(n)` này là bao nhiêu?

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

Câu 17: Thuật toán nào trong số các thuật toán sắp xếp sau đây thường có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất?

• A. Selection Sort
• B. Merge Sort
• C. Quick Sort
• D. Binary Search (Đây là tìm kiếm, không phải sắp xếp)

Câu 18: Khi nói về độ phức tạp không gian (Space Complexity), O(n) nghĩa là gì?

• A. Thời gian chạy tăng tuyến tính với n.
• B. Lượng bộ nhớ phụ sử dụng tăng tuyến tính với n.
• C. Thời gian chạy là hằng số.
• D. Lượng bộ nhớ phụ sử dụng là hằng số.

Câu 19: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to 100:
// Thực hiện một phép toán cơ bản
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(100n)
• D. O(n^2)

Câu 20: Thuật toán nào sau đây là ví dụ điển hình của độ phức tạp thời gian O(1)?

• A. Tìm kiếm một phần tử trong danh sách liên kết.
• B. Sắp xếp một mảng bằng Bubble Sort.
• C. Duyệt qua tất cả các phần tử của một mảng.
• D. Truy cập một phần tử tại một chỉ số cho trước trong mảng.

Câu 21: Một thuật toán được mô tả là có độ phức tạp thời gian O(n^3). Nếu thuật toán này mất 1 giây để xử lý dữ liệu có kích thước n=100, thì ước tính nó sẽ mất bao lâu để xử lý dữ liệu có kích thước n=200?

• A. 8 giây
• B. 2 giây
• C. 4 giây
• D. 16 giây

Câu 22: Điều gì xảy ra với hiệu quả của thuật toán sắp xếp nổi bọt (Bubble Sort - O(n^2)) khi kích thước dữ liệu đầu vào (n) tăng lên rất lớn?

• A. Hiệu quả được cải thiện đáng kể.
• B. Hiệu quả không thay đổi.
• C. Hiệu quả giảm sút nhanh chóng.
• D. Hiệu quả chỉ bị ảnh hưởng bởi các hằng số.

Câu 23: Đâu là lợi ích chính của việc phân tích độ phức tạp thời gian của thuật toán?

• A. Xác định thời gian chạy chính xác trên một máy tính cụ thể.
• B. Dự đoán hiệu quả của thuật toán trên dữ liệu lớn và so sánh các thuật toán khác nhau.
• C. Tìm lỗi cú pháp trong mã nguồn.
• D. Giảm số lượng dòng mã của thuật toán.

Câu 24: Cho đoạn mã giả sau:
```
for i from 1 to n:
// Thực hiện một phép toán cơ bản
for j from 1 to m:
// Thực hiện một phép toán cơ bản
```
Với giả định n và m là hai kích thước đầu vào độc lập, độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n * m)
• B. O(n^2)
• C. O(max(n, m))
• D. O(n + m)

Câu 25: Một thuật toán có độ phức tạp O(n log n). Nếu nó mất 0.5 giây để xử lý n=1000, ước tính thời gian xử lý cho n=20000 (tăng 20 lần) là bao nhiêu? (Gợi ý: log₂(1000) ≈ 10, log₂(20000) ≈ 14.3)

• A. 10 giây
• B. 14.3 giây
• C. 20 giây
• D. 5 giây

Câu 26: Đâu là yếu tố không được xem xét trực tiếp khi xác định độ phức tạp thời gian của thuật toán bằng ký hiệu O lớn?

• A. Tốc độ xử lý của máy tính (GHz).
• B. Kích thước dữ liệu đầu vào (n).
• C. Số lượng vòng lặp lồng nhau.
• D. Số lượng phép so sánh hoặc phép toán cơ bản tỷ lệ với n.

Câu 27: Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép hoán đổi (swap) được thực hiện trong trường hợp xấu nhất là bao nhiêu?

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

Câu 28: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to i:
// Thực hiện một phép toán cơ bản
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n^3)

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

• A. Giảm thời gian thực hiện, đặc biệt khi xử lý dữ liệu lớn.
• B. Làm cho mã nguồn dễ đọc và dễ hiểu hơn.
• C. Giảm lượng bộ nhớ sử dụng bởi thuật toán.
• D. Đảm bảo thuật toán luôn tìm ra đáp án chính xác.

Câu 30: Giả sử bạn có một danh sách N tên học sinh cần sắp xếp theo thứ tự bảng chữ cái. Nếu N rất lớn (ví dụ: vài triệu), thuật toán nào sau đây có khả năng là lựa chọn tốt nhất về mặt hiệu quả thời gian?

• A. Bubble Sort (O(n^2))
• B. Selection Sort (O(n^2))
• C. Linear Search (O(n))
• D. Merge Sort (O(n log n))

Câu 1: Xét đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
sum = sum + i
```
Đoạn mã này tính tổng các số từ 1 đến n. Độ phức tạp thời gian của đoạn mã này được biểu diễn bằng kí hiệu Big O nào?

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

Câu 2: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Trong trường hợp xấu nhất, phần tử cần tìm không có trong mảng. Độ phức tạp thời gian trong trường hợp này là bao nhiêu?

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

Câu 3: Một thuật toán có độ phức tạp thời gian là O(n^2). Nếu với đầu vào có kích thước n=1000, thuật toán chạy mất 1 giây, thì ước tính với đầu vào có kích thước n=2000, thuật toán sẽ chạy mất khoảng bao lâu?

• A. 0.5 giây
• B. 1 giây
• C. 2 giây
• D. 4 giây

Câu 4: Thuật toán sắp xếp chọn (Selection Sort) trên một mảng có kích thước n. Độ phức tạp thời gian của thuật toán này là bao nhiêu trong trường hợp trung bình?

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

Câu 5: Xét đoạn mã giả sau:
```
count = 0
for i from 1 to n:
for j from 1 to n:
count = count + 1
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

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

Câu 6: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Trong trường hợp mảng đã được sắp xếp từ trước (trường hợp tốt nhất), độ phức tạp thời gian của thuật toán này là bao nhiêu?

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

Câu 7: Khi phân tích độ phức tạp thời gian của thuật toán, kí hiệu Big O (O) thường được sử dụng để mô tả điều gì?

• A. Thời gian thực hiện chính xác của thuật toán.
• B. Độ phức tạp trong trường hợp tốt nhất.
• C. Giới hạn dưới (lower bound) của tốc độ tăng trưởng thời gian.
• D. Giới hạn trên (upper bound) của tốc độ tăng trưởng thời gian (thường là trường hợp xấu nhất).

Câu 8: Một thuật toán có độ phức tạp O(log n). Điều này có ý nghĩa gì về hiệu suất của thuật toán khi kích thước đầu vào n tăng lên rất lớn?

• A. Thời gian chạy tăng tuyến tính với kích thước đầu vào.
• B. Thời gian chạy tăng rất chậm khi kích thước đầu vào tăng.
• C. Thời gian chạy tăng theo bình phương kích thước đầu vào.
• D. Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào.

Câu 9: Xét đoạn mã giả sau:
```
result = 0
for i from 1 to n:
for j from i to n:
result = result + 1
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n^3)

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

• A. Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào.
• B. Thời gian chạy tăng tuyến tính với kích thước đầu vào.
• C. Thời gian chạy tăng theo logarit của kích thước đầu vào.
• D. Đây là độ phức tạp kém hiệu quả nhất.

Câu 11: Thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có kích thước n. Độ phức tạp thời gian của thuật toán này là bao nhiêu?

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

Câu 12: So sánh hai thuật toán A (độ phức tạp O(n)) và thuật toán B (độ phức tạp O(n^2)). Với kích thước đầu vào n đủ lớn, thuật toán nào sẽ có hiệu suất tốt hơn (chạy nhanh hơn)?

• A. Thuật toán A
• B. Thuật toán B
• C. Hiệu suất như nhau
• D. Không thể so sánh nếu không biết hằng số

Câu 13: Xét đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to 100:
// Thực hiện một phép tính O(1)
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

• A. O(100)
• B. O(n)
• C. O(100n)
• D. O(n^2)

Câu 14: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Trong trường hợp xấu nhất (mảng sắp xếp ngược), độ phức tạp thời gian là bao nhiêu?

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

Câu 15: Khi phân tích độ phức tạp thời gian, tại sao chúng ta thường quan tâm đến trường hợp xấu nhất (worst-case) hơn là trường hợp tốt nhất (best-case)?

• A. Trường hợp tốt nhất hiếm khi xảy ra.
• B. Trường hợp tốt nhất thường có độ phức tạp O(1) nên không cần phân tích.
• C. Trường hợp xấu nhất cung cấp giới hạn trên đáng tin cậy về hiệu suất.
• D. Trường hợp trung bình khó xác định hơn.

Câu 16: Xét đoạn mã giả sau:
```
void process(int n) {
if (n <= 1) return; process(n/2); process(n/2); } ``` Đây là một hàm đệ quy. Độ phức tạp thời gian của hàm này là bao nhiêu?

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

Câu 17: Xét đoạn mã giả sau:
```
void do_something(int n) {
for i from 1 to n:
// Phép tính O(1)
for j from 1 to n:
// Phép tính O(1)
}
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

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

Câu 18: Một thuật toán mất 5ms để xử lý dữ liệu có kích thước n=100. Nếu độ phức tạp của thuật toán là O(n log n), ước tính thời gian xử lý cho dữ liệu có kích thước n=10000 sẽ là bao nhiêu?

• A. 50 ms
• B. 500 ms
• C. 5 s
• D. 1 s

Câu 19: Trong phân tích độ phức tạp, 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?

• A. Vì khi n rất lớn, số hạng bậc cao nhất chi phối tốc độ tăng trưởng.
• B. Vì chúng không ảnh hưởng đến thời gian thực hiện thực tế.
• C. Vì chúng chỉ quan trọng trong trường hợp tốt nhất.
• D. Vì chúng làm cho việc tính toán phức tạp hơn.

Câu 20: Xét đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to i*i:
// Phép tính O(1)
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

• A. O(n)
• B. O(n^2)
• C. O(n^4)
• D. O(n^3)

Câu 21: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Trong trường hợp tốt nhất, phần tử cần tìm nằm ở vị trí đầu tiên. Độ phức tạp thời gian trong trường hợp này là bao nhiêu?

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

Câu 22: Một thuật toán có độ phức tạp O(n log n). Thuật toán này hiệu quả hơn thuật toán O(n^2) và kém hiệu quả hơn thuật toán O(n). Phát biểu này Đúng hay Sai?

• A. Đúng
• B. Sai

Câu 23: Xét một đoạn mã thực hiện việc in tất cả các cặp phần tử khác nhau trong một mảng có kích thước n. Cấu trúc vòng lặp phổ biến để làm việc này là hai vòng lặp lồng nhau, mỗi vòng chạy từ 0 đến n-1, với điều kiện bỏ qua các cặp giống nhau hoặc đã xét. Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(n^3)

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

• A. Đánh giá hiệu quả của thuật toán khi kích thước đầu vào tăng lên.
• B. Xác định thời gian chạy chính xác trên một máy tính cụ thể.
• C. Tìm lỗi trong thuật toán.
• D. Đảm bảo thuật toán luôn cho ra kết quả đúng.

Câu 25: Xét đoạn mã giả sau:
```
void process_data(int n) {
for i from 1 to n:
// Phép tính O(1)
for j from 1 to n*n:
// Phép tính O(1)
}
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

• A. O(n)
• B. O(n^3)
• C. O(n + n^2)
• D. O(n^2)

Câu 26: Thuật toán sắp xếp chèn (Insertion Sort) trên một mảng có kích thước n. Trong trường hợp xấu nhất (mảng sắp xếp ngược), độ phức tạp thời gian của thuật toán này là bao nhiêu?

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

Câu 27: Xét đoạn mã giả sau:
```
void process_recursive(int n) {
if (n <= 0) return; // Phép tính O(1) process_recursive(n - 1); } ``` Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

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

Câu 28: Khi so sánh 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^2), điều gì xảy ra khi kích thước đầu vào n tăng từ nhỏ đến rất lớn?

• A. Thuật toán A nhanh hơn B khi n đủ lớn.
• B. Thuật toán B nhanh hơn A khi n đủ lớn.
• C. Cả hai thuật toán có hiệu suất tương đương khi n rất lớn.
• D. Không thể so sánh hiệu suất chỉ dựa vào độ phức tạp Big O.

Câu 29: Xét đoạn mã giả sau:
```
for i from 1 to 100:
for j from 1 to n:
// Phép tính O(1)
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

• A. O(100)
• B. O(n)
• C. O(100n)
• D. O(n^2)

Câu 30: Một thuật toán xử lý dữ liệu có kích thước n. Người ta đo được thời gian chạy T(n) và vẽ đồ thị T(n) theo n. Nếu đồ thị có dạng một đường thẳng đi qua gốc tọa độ (hoặc gần như vậy khi n lớn), thì độ phức tạp thời gian của thuật toán có khả năng là gì?

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

Câu 1: Cho đoạn mã giả sau:
```
function TinhTong(n):
tong = 0
for i from 1 to n:
tong = tong + i
return tong
```
Độ phức tạp thời gian của hàm `TinhTong(n)` theo ký hiệu O lớn là bao nhiêu?

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

Câu 2: 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 notation) thường mô tả trường hợp nào?

• A. Trường hợp tốt nhất (best case)
• B. Trường hợp trung bình (average case)
• C. Trường hợp xấu nhất (worst case)
• D. Cả ba trường hợp trên

Câu 3: Cho đoạn mã giả sau:
```
function TimPhanTu(mang, gia_tri):
for i from 0 to length(mang) - 1:
if mang[i] == gia_tri:
return i
return -1
```
Nếu mảng `mang` có kích thước `n` và phần tử `gia_tri` nằm ở vị trí cuối cùng của mảng, độ phức tạp thời gian là bao nhiêu?

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

Câu 4: Thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã được sắp xếp có độ phức tạp thời gian trong trường hợp xấu nhất là O(log n). Điều này có ý nghĩa gì khi kích thước dữ liệu `n` tăng lên?

• A. Thời gian thực hiện tăng tuyến tính với `n`.
• B. Thời gian thực hiện tăng theo bình phương của `n`.
• C. Thời gian thực hiện tăng rất nhanh khi `n` lớn.
• D. Thời gian thực hiện tăng rất chậm so với sự tăng của `n`.

Câu 5: Cho đoạn mã giả sau:
```
function XuLyDuLieu(n):
for i from 1 to n:
for j from 1 to n:
print(i * j)
```
Độ phức tạp thời gian của hàm `XuLyDuLieu(n)` là bao nhiêu?

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

Câu 6: Nếu một thuật toán có độ phức tạp thời gian là O(n^2) và mất 1 giây để xử lý 1000 phần tử, ước tính thời gian cần thiết để xử lý 10000 phần tử là bao nhiêu?

• A. 10 giây
• B. 100 giây
• C. 100 giây
• D. 1000 giây

Câu 7: 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à O(n^2). Điều này có nghĩa là gì về hiệu suất của thuật toán này với dữ liệu lớn?

• A. Thời gian thực hiện tăng rất nhanh khi kích thước dữ liệu tăng, không phù hợp với tập dữ liệu rất lớn.
• B. Thời gian thực hiện tăng chậm, phù hợp với mọi kích thước dữ liệu.
• C. Thời gian thực hiện là hằng số, không phụ thuộc vào kích thước dữ liệu.
• D. Thời gian thực hiện chỉ tăng tuyến tính với kích thước dữ liệu.

Câu 8: Cho đoạn mã giả sau:
```
function HamKyBi(n):
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của hàm `HamKyBi(n)` là bao nhiêu?

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

Câu 9: Khi so sánh thuật toán tìm kiếm tuần tự (Linear Search) với tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có kích thước `n`, nhận định nào sau đây là đúng về độ phức tạp thời gian trong trường hợp xấu nhất?

• A. Tìm kiếm tuần tự (O(n)) chậm hơn tìm kiếm nhị phân (O(log n)) đáng kể khi `n` lớn.
• B. Tìm kiếm tuần tự (O(n)) nhanh hơn tìm kiếm nhị phân (O(log n)) khi `n` lớn.
• C. Hai thuật toán có độ phức tạp tương đương nhau khi `n` lớn.
• D. Độ phức tạp của tìm kiếm nhị phân phụ thuộc vào việc mảng có chứa số nguyên hay không.

Câu 10: Một thuật toán thực hiện các bước sau:
1. Duyệt qua toàn bộ mảng kích thước `n` một lần để tìm giá trị lớn nhất (O(n)).
2. Thực hiện 10 phép tính số học cố định (không phụ thuộc vào `n`) (O(1)).
Độ phức tạp thời gian tổng thể của thuật toán này là bao nhiêu?

• A. O(1)
• B. O(n)
• C. O(n + 10)
• D. O(10n)

Câu 11: Cho đoạn mã giả sau:
```
function ProcessData(A, B):
n = length(A)
m = length(B)
for i from 0 to n-1:
for j from 0 to m-1:
print(A[i] + B[j])
```
Nếu `n` rất lớn và `m` rất lớn, độ phức tạp thời gian của hàm `ProcessData(A, B)` là bao nhiêu?

• A. O(n + m)
• B. O(max(n, m))
• C. O(n)
• D. O(n * m)

Câu 12: Khi phân tích độ phức tạp của một thuật toán, hằng số và các hệ số bậc thấp thường bị bỏ qua trong ký hiệu O lớn. Ví dụ, O(2n^2 + 5n + 3) được rút gọn thành O(n^2). Tại sao lại làm như vậy?

• A. Để tập trung vào tốc độ tăng trưởng của thời gian thực hiện khi kích thước đầu vào rất lớn.
• B. Để làm cho việc tính toán đơn giản hơn.
• C. Vì các hằng số và hệ số bậc thấp không ảnh hưởng đến thời gian thực hiện.
• D. Vì chúng chỉ quan trọng trong trường hợp tốt nhất.

Câu 13: 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 tốt nhất (mảng đã sắp xếp) là O(n). Tại sao lại như vậy?

• A. Vì thuật toán chỉ cần một vòng lặp để kiểm tra.
• B. Vì thuật toán có thể phát hiện mảng đã sắp xếp sau một lần duyệt đầy đủ mà không cần đổi chỗ nào.
• C. Vì thuật toán chỉ thực hiện một phép so sánh.
• D. Vì độ phức tạp O(n) là tối ưu cho mọi thuật toán sắp xếp.

Câu 14: Cho đoạn mã giả:
```
function Example(n):
count = 0
for i from 1 to n:
for j from 1 to i:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `Example(n)` là bao nhiêu?

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

Câu 15: Một thuật toán có độ phức tạp O(log n). Nếu với n = 1000, thuật toán chạy mất 10ms, thì ước tính với n = 1,000,000 (gấp 1000 lần), thuật toán sẽ chạy mất khoảng bao lâu? (Biết log2(1000) ≈ 10, log2(1000000) ≈ 20)

• A. Khoảng 20ms
• B. Khoảng 100ms
• C. Khoảng 1000ms
• D. Khoảng 10000ms

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

• A. Tìm kiếm một phần tử trong danh sách liên kết.
• B. Sắp xếp một mảng bằng Bubble Sort.
• C. Truy cập một phần tử tại vị trí bất kỳ trong mảng bằng chỉ số.
• D. Duyệt qua tất cả các phần tử trong một danh sách.

Câu 17: Khi phân tích một thuật toán đệ quy, độ phức tạp thời gian thường được biểu diễn bằng gì?

• A. Hệ thức truy hồi (Recurrence Relation)
• B. Công thức đóng (Closed Form)
• C. Đồ thị hàm số
• D. Ma trận kề

Câu 18: Cho đoạn mã giả sau:
```
function AnotherExample(n):
for i from 1 to n:
j = 1
while j <= n: print(i * j) j = j * 2 ``` Độ phức tạp thời gian của hàm `AnotherExample(n)` là bao nhiêu?

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

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

• A. Tìm kiếm tuần tự (Linear Search)
• B. Sắp xếp chọn (Selection Sort)
• C. Sắp xếp nổi bọt (Bubble Sort)
• D. Sắp xếp trộn (Merge Sort)

Câu 20: Giả sử bạn cần chọn một thuật toán để xử lý một tập dữ liệu có kích thước N rất lớn (ví dụ: N = 1 tỷ). Thuật toán nào có độ phức tạp thời gian ít phù hợp nhất?

• A. O(N^2)
• B. O(N log N)
• C. O(N)
• D. O(log N)

Câu 21: Cho đoạn mã giả sau:
```
function WeirdFunction(n):
if n <= 1: return 1 else: return WeirdFunction(n/2) + WeirdFunction(n/2) ``` Độ phức tạp thời gian của hàm đệ quy `WeirdFunction(n)` là bao nhiêu? (Giả sử phép chia `/` là phép chia nguyên)

• A. O(log n)
• B. O(n)
• C. O(n log n)
• D. O(n)

Câu 22: Khái niệm nào sau đây mô tả tốc độ tăng trưởng của thời gian thực hiện thuật toán khi kích thước đầu vào tăng lên?

• A. Độ chính xác của thuật toán
• B. Độ đo bộ nhớ của thuật toán
• C. Độ phức tạp thời gian của thuật toán
• D. Tính đúng đắn của thuật toán

Câu 23: Cho đoạn mã giả sau:
```
function ProcessMatrix(matrix, n):
# matrix là ma trận vuông n x n
sum = 0
for i from 0 to n-1:
sum = sum + matrix[i][i] # Duyệt đường chéo chính
return sum
```
Độ phức tạp thời gian của hàm `ProcessMatrix(matrix, n)` là bao nhiêu?

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

Câu 24: Trong phân tích độ phức tạp, O(n) được gọi là độ phức tạp gì?

• A. Tuyến tính (Linear)
• B. Logarit (Logarithmic)
• C. Hằng số (Constant)
• D. Bình phương (Quadratic)

Câu 25: Tại sao việc xác định độ phức tạp thời gian của thuật toán lại quan trọng trong thực tế?

• A. Chỉ để biết thuật toán có chạy được hay không.
• B. Để biết chính xác thời gian chạy trên một máy tính cụ thể.
• C. Để làm cho mã nguồn ngắn gọn hơn.
• D. Để dự đoán hiệu suất của thuật toán với các tập dữ liệu lớn và so sánh hiệu quả giữa các thuật toán khác nhau.

Câu 26: Cho đoạn mã giả sau:
```
function AnalyzeData(n):
total = 0
for i from 1 to 100:
total = total + i
for j from 1 to n:
total = total + j*2
return total
```
Độ phức tạp thời gian của hàm `AnalyzeData(n)` là bao nhiêu?

• A. O(100)
• B. O(n + 100)
• C. O(n)
• D. O(n^2)

Câu 27: Trong các độ phức tạp sau, độ phức tạp nào thể hiện hiệu suất tốt nhất (chạy nhanh nhất với `n` đủ lớn)?

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

Câu 28: Khi một thuật toán chứa một vòng lặp `for` chạy từ 1 đến `n` và bên trong vòng lặp đó có một lời gọi hàm khác có độ phức tạp O(log n), thì độ phức tạp tổng thể của thuật toán là bao nhiêu?

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

Câu 29: Cho đoạn mã giả:
```
function CompareArrays(A, B):
n = length(A)
m = length(B)
if n != m:
return False
for i from 0 to n-1:
if A[i] != B[i]:
return False
return True
```
Giả sử `n` và `m` có cùng độ lớn. Độ phức tạp thời gian của hàm `CompareArrays` trong trường hợp xấu nhất (hai mảng giống hệt nhau) là bao nhiêu?

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

Câu 30: Trong các yếu tố sau, yếu tố nào không ảnh hưởng trực tiếp đến độ phức tạp thời gian lý thuyết (Big O) của một thuật toán?

• A. Kích thước của dữ liệu đầu vào (n).
• B. Cấu trúc của các vòng lặp và lời gọi hàm.
• C. Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán.
• D. Số lượng các phép toán cơ bản (so sánh, gán, tính toán) thực hiện trong trường hợp xấu nhất.