Trắc nghiệm Tin học 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
Trắc nghiệm Tin học 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 bao gồm nhiều câu hỏi hay, bám sát chương trình. Cùng làm bài tập trắc nghiệm ngay.
Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, yếu tố nào sau đây được xem xét là đơn vị thời gian cơ bản?
- A. Thời gian thực thi tuyệt đối trên một máy tính cụ thể
- B. Số lượng các phép toán cơ bản mà thuật toán thực hiện
- C. Tổng thời gian CPU sử dụng để chạy chương trình
- D. Kích thước bộ nhớ mà chương trình sử dụng
Câu 2: Cho đoạn chương trình sau:
```
for i in range(n):
print(i)
```
Độ phức tạp thời gian của đoạn chương trình này là bao nhiêu?
- A. O(1)
- B. O(n)
- C. O(log n)
- D. O(n^2)
Câu 3: Quy tắc nào sau đây được sử dụng để xác định độ phức tạp thời gian của một chuỗi các lệnh tuần tự trong một chương trình?
- A. Quy tắc cộng (Summation Rule)
- B. Quy tắc nhân (Multiplication Rule)
- C. Quy tắc chia (Division Rule)
- D. Quy tắc lũy thừa (Exponentiation Rule)
Câu 4: Xét đoạn chương trình:
```
for i in range(n):
for j in range(m):
print(i + j)
```
Nếu `m` tỉ lệ thuận với `n` (ví dụ, m = 2n), độ phức tạp thời gian của đoạn chương trình này là:
- A. O(n + m)
- B. O(max(n, m))
- C. O(min(n, m))
- D. O(n * m)
Câu 5: Độ phức tạp thời gian O(log n) thường xuất hiện trong loại thuật toán nào?
- A. Thuật toán duyệt tuần tự
- B. Thuật toán có vòng lặp tuyến tính
- C. Thuật toán chia để trị (Divide and Conquer)
- D. Thuật toán sắp xếp nổi bọt (Bubble Sort)
Câu 6: 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 khi kích thước đầu vào `n` tăng lên rất lớn?
- A. O(1)
- B. O(n)
- C. O(n log n)
- D. O(n^2)
Câu 7: Thuật toán tìm kiếm tuyến tính (Linear Search) trong mảng có độ phức tạp thời gian trung bình là bao nhiêu?
- A. O(1)
- B. O(n)
- C. O(log n)
- D. O(n log n)
Câu 8: Độ phức tạp thời gian O(n!) thường liên quan đến loại bài toán nào?
- A. Bài toán sắp xếp mảng
- B. Bài toán tìm kiếm trong cây nhị phân cân bằng
- C. Bài toán quy hoạch động
- D. Bài toán liệt kê tất cả các hoán vị
Câu 9: Để tính độ phức tạp thời gian của hai vòng lặp lồng nhau, trong đó vòng ngoài chạy `n` lần và vòng trong chạy `log n` lần, ta sử dụng quy tắc nào?
- A. Quy tắc cộng
- B. Quy tắc nhân
- C. Quy tắc lặp
- D. Quy tắc tuyến tính
Câu 10: 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 tốt nhất, trung bình và xấu nhất là bao nhiêu?
- A. O(n^2)
- B. O(n)
- C. O(n log n)
- D. O(log n)
Câu 11: Cho hàm sau:
```python
def tinh_tong(arr):
tong = 0
for x in arr:
tong += x
return tong
```
Nếu `arr` là một danh sách có `n` phần tử, độ phức tạp thời gian của hàm `tinh_tong` là:
- A. O(1)
- B. O(n)
- C. O(log n)
- D. O(n^2)
Câu 12: Độ phức tạp thời gian nào sau đây là chấp nhận được cho một thuật toán xử lý dữ liệu lớn trong thời gian thực?
- A. O(n^2)
- B. O(log n)
- C. O(2^n)
- D. O(n!)
Câu 13: Trong 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 nhất để đánh giá giới hạn hiệu suất của thuật toá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. Trường hợp điển hình (Typical-case)
Câu 14: Nếu 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à khi kích thước đầu vào `n` tăng gấp đôi, thời gian thực hiện sẽ tăng lên khoảng bao nhiêu lần?
- A. Gấp đôi
- B. Gấp bốn
- C. Hơn gấp đôi nhưng ít hơn gấp bốn
- D. Không thay đổi
Câu 15: Cho đoạn mã giả:
```
function TimKiem(arr, target):
for each element in arr:
if element == target:
return true
return false
```
Độ phức tạp thời gian của thuật toán `TimKiem` là:
- A. O(1)
- B. O(n)
- C. O(log n)
- D. O(n log n)
Câu 16: Độ phức tạp thời gian O(2^n) thường được gọi là độ phức tạp gì?
- A. Độ phức tạp tuyến tính
- B. Độ phức tạp đa thức
- C. Độ phức tạp mũ
- D. Độ phức tạp logarit
Câu 17: Trong các thuật toán sắp xếp sau, thuật toán nào có độ phức tạp thời gian trung bình là O(n log n)?
- A. Sắp xếp chèn (Insertion Sort)
- B. Sắp xếp nhanh (Quick Sort)
- C. Sắp xếp chọn (Selection Sort)
- D. Sắp xếp nổi bọt (Bubble Sort)
Câu 18: Để so sánh hiệu quả của hai thuật toán, một có độ phức tạp O(n) và một có độ phức tạp O(n^2), thuật toán nào sẽ hiệu quả hơn cho dữ liệu đầu vào lớn?
- A. Thuật toán O(n)
- B. Thuật toán O(n^2)
- C. Cả hai hiệu quả như nhau
- D. Không thể xác định
Câu 19: Cho đoạn mã Python:
```python
def mystery_function(n):
count = 0
i = 1
while i < n:
count += 1
i *= 2
return count
```
Độ phức tạp thời gian của `mystery_function` là:
- A. O(n)
- B. O(n^2)
- C. O(log n)
- D. O(1)
Câu 20: Phát biểu nào sau đây là đúng về ký hiệu Big O?
- A. Đo lường thời gian thực thi chính xác của thuật toán
- B. Phụ thuộc vào ngôn ngữ lập trình và phần cứng
- C. Chỉ áp dụng cho trường hợp tốt nhất của thuật toán
- D. Mô tả tốc độ tăng trưởng tiệm cận của thời gian thực hiện theo kích thước đầu vào
Câu 21: Một thuật toán có độ phức tạp O(n^3). Nếu thời gian chạy của nó là 1 giây với n = 1000, thời gian chạy ước tính với n = 2000 sẽ là bao nhiêu?
- A. 2 giây
- B. 4 giây
- C. 8 giây
- D. 16 giây
Câu 22: Độ phức tạp thời gian O(n log n) tốt hơn độ phức tạp nào trong các lựa chọn sau đây khi `n` lớn?
- A. O(n)
- B. O(log n)
- C. O(n)
- D. O(n^2)
Câu 23: Cho đoạn mã giả:
```
function process(n):
if n <= 1:
return
for i from 1 to n:
print(i)
process(n/2)
process(n/2)
```
Độ phức tạp thời gian của `process(n)` là:
- A. O(n^2)
- B. O(n log n)
- C. O(log n)
- D. O(n)
Câu 24: Khi nào độ phức tạp thời gian của thuật toán sắp xếp chèn (Insertion Sort) đạt trường hợp tốt nhất?
- A. Khi mảng đã được sắp xếp
- B. Khi mảng sắp xếp ngược
- C. Khi mảng chứa các phần tử giống nhau
- D. Độ phức tạp không phụ thuộc vào đầu vào
Câu 25: Trong phân tích độ phức tạp thuật toán, hằng số và các hệ số bậc thấp thường bị bỏ qua. Tại sao?
- A. Để đơn giản hóa việc tính toán
- B. Vì chúng không ảnh hưởng đến hiệu suất thực tế
- C. Vì chúng trở nên không đáng kể khi kích thước đầu vào lớn
- D. Để làm cho thuật toán trông hiệu quả hơn
Câu 26: Cho đoạn mã giả:
```
function calculate(n):
sum = 0
for i from 1 to n*n:
sum += i
return sum
```
Độ phức tạp thời gian của `calculate(n)` là:
- A. O(n)
- B. O(log n)
- C. O(n log n)
- D. O(n^2)
Câu 27: Độ phức tạp thời gian nào sau đây là kém hiệu quả nhất khi `n` rất lớn?
- A. O(n log n)
- B. O(n^2)
- C. O(2^n)
- D. O(n)
Câu 28: Thuật toán tìm kiếm nhị phân (Binary Search) yêu cầu dữ liệu đầu vào phải có đặc điểm gì để đạt được độ phức tạp O(log n)?
- A. Dữ liệu phải là số nguyên
- B. Dữ liệu phải được sắp xếp
- C. Dữ liệu phải là duy nhất
- D. Không có yêu cầu đặc biệt
Câu 29: Nếu bạn có hai đoạn chương trình chạy tuần tự, đoạn thứ nhất có độ phức tạp O(n) và đoạn thứ hai có độ phức tạp O(n log n), độ phức tạp thời gian tổng cộng của cả chương trình là bao nhiêu?
- A. O(n)
- B. O(n + log n)
- C. O(n log n)
- D. O(n^2)
Câu 30: Trong bối cảnh tối ưu hóa hiệu suất chương trình, hiểu biết về độ phức tạp thời gian giúp lập trình viên đưa ra quyết định nào?
- A. Chọn ngôn ngữ lập trình phù hợp
- B. Tăng tốc độ CPU của máy tính
- C. Giảm dung lượng bộ nhớ sử dụng
- D. Lựa chọn thuật toán và cấu trúc dữ liệu hiệu quả hơn
