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 - Đề 02
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 - Đề 02 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: Để tính tổng các số chẵn từ 0 đến n (n là số nguyên dương chẵn), bạn viết một chương trình duyệt qua từng số từ 0 đến n và kiểm tra tính chẵn lẻ. Nếu n tăng gấp đôi, thời gian thực hiện chương trình sẽ thay đổi như thế nào?
- A. Thời gian thực hiện không đổi.
- B. Thời gian thực hiện tăng lên xấp xỉ gấp đôi.
- C. Thời gian thực hiện tăng lên xấp xỉ gấp bốn lần.
- D. Thời gian thực hiện giảm đi một nửa.
Câu 2: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to n:
thực hiện phép toán X
```
Độ phức tạp thời gian của đoạn mã trên là:
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(n log n)
Câu 3: Thuật toán tìm kiếm nhị phân (Binary Search) hoạt động hiệu quả nhất trên dữ liệu nào sau đây?
- A. Mảng số nguyên ngẫu nhiên.
- B. Danh sách liên kết chưa sắp xếp.
- C. Cây nhị phân tìm kiếm không cân bằng.
- D. Mảng số nguyên đã được sắp xếp tăng dần.
Câu 4: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), sau khi thực hiện xong vòng lặp ngoài đầu tiên, điều gì được đảm bảo?
- A. Mảng đã được sắp xếp hoàn toàn.
- B. Phần tử lớn nhất đã được đặt vào vị trí cuối cùng của mảng.
- C. Phần tử nhỏ nhất đã được đặt vào vị trí đầu tiên của mảng.
- D. Mảng đã được sắp xếp một nửa.
Câu 5: Độ phức tạp thời gian O(log n) thường gặp ở loại thuật toán nào?
- A. Thuật toán duyệt toàn bộ danh sách.
- B. Thuật toán có vòng lặp lồng nhau.
- C. Thuật toán chia bài toán thành các bài toán con nhỏ hơn và giải quyết đệ quy.
- D. Thuật toán thực hiện một số lượng phép toán cố định, không đổi theo kích thước đầu vào.
Câu 6: Cho hàm tính giai thừa số tự nhiên như sau:
```
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
```
Độ phức tạp thời gian của hàm `factorial(n)` là:
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(1)
Câu 7: Trong các độ phức tạp thời gian sau, độ phức tạp nào thể hiện thuật toán có hiệu quả nhất khi kích thước dữ liệu đầu vào tăng lên?
- A. O(n^2)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 8: Xét thuật toán sắp xếp chọn (Selection Sort). Số lượng phép so sánh trong trường hợp xấu nhất khi sắp xếp một mảng n phần tử là bao nhiêu?
- A. n - 1
- B. log n
- C. n(n - 1) / 2
- D. n log n
Câu 9: Một thuật toán có độ phức tạp thời gian O(n log n). Nếu thời gian chạy của thuật toán là 1 giây khi n = 1000, thời gian chạy dự kiến sẽ là bao nhiêu khi n = 10000?
- A. 10 giây
- B. 100 giây
- C. 1 giây
- D. Khoảng 13 giây
Câu 10: Trong thuật toán tìm kiếm tuần tự (Linear Search), trường hợp tốt nhất xảy ra khi nào?
- A. Phần tử cần tìm nằm ở vị trí đầu tiên của mảng.
- B. Phần tử cần tìm nằm ở vị trí cuối cùng của mảng.
- C. Mảng đã được sắp xếp.
- D. Phần tử cần tìm không có trong mảng.
Câu 11: Độ phức tạp không gian (space complexity) của một thuật toán đề cập đến điều gì?
- A. Thời gian thực hiện thuật toán.
- B. Số lượng phép toán mà thuật toán thực hiện.
- C. Lượng bộ nhớ máy tính mà thuật toán cần sử dụng.
- D. Độ dài mã nguồn của thuật toán.
Câu 12: Cho đoạn mã giả sau:
```
for i from 1 to n:
print(i)
```
Độ phức tạp thời gian của đoạn mã này là:
- A. O(n)
- B. O(1)
- C. O(log n)
- D. O(n^2)
Câu 13: Trong thuật toán sắp xếp chèn (Insertion Sort), trường hợp tốt nhất xảy ra khi nào?
- A. Mảng đầu vào chứa các phần tử giống nhau.
- B. Mảng đầu vào đã được sắp xếp.
- C. Mảng đầu vào sắp xếp ngược.
- D. Kích thước mảng đầu vào nhỏ.
Câu 14: Độ phức tạp thời gian O(1) còn được gọi là độ phức tạp gì?
- A. Độ phức tạp tuyến tính.
- B. Độ phức tạp logarit.
- C. Độ phức tạp hằng số.
- D. Độ phức tạp đa thức.
Câu 15: Để kiểm tra xem một số n có phải là số nguyên tố hay không bằng cách thử chia cho tất cả các số từ 2 đến căn bậc hai của n, độ phức tạp thời gian của thuật toán này là:
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(√n)
Câu 16: Trong thuật toán Bubble Sort, trường hợp xấu nhất xảy ra khi nào?
- A. Mảng đã được sắp xếp.
- B. Mảng chứa các phần tử giống nhau.
- C. Mảng sắp xếp theo thứ tự ngược lại.
- D. Kích thước mảng nhỏ.
Câu 17: Độ phức tạp thời gian O(n log n) thường liên quan đến loại thuật toán nào?
- A. Thuật toán tìm kiếm tuần tự.
- B. Thuật toán sắp xếp hiệu quả (ví dụ: Merge Sort, Quick Sort).
- C. Thuật toán duyệt đồ thị theo chiều rộng (BFS).
- D. Thuật toán tính tổng các phần tử trong mảng.
Câu 18: So sánh độ phức tạp thời gian của thuật toán tìm kiếm tuần tự (Linear Search) và tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp. Thuật toán nào hiệu quả hơn khi kích thước mảng lớn?
- A. Tìm kiếm tuần tự hiệu quả hơn.
- B. Cả hai thuật toán có hiệu quả tương đương.
- C. Tìm kiếm nhị phân hiệu quả hơn.
- D. Hiệu quả phụ thuộc vào giá trị cần tìm.
Câu 19: Cho đoạn mã giả sau:
```
function Mystery(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 `Mystery(n)` là:
- A. O(n)
- B. O(n log n)
- C. O(n^2)
- D. O(log n)
Câu 20: Một thuật toán có độ phức tạp O(n^3). Nếu thời gian chạy là 2 giây khi n = 100, thời gian chạy dự kiến là bao nhiêu khi n = 200?
- A. 4 giây
- B. 16 giây
- C. 8 giây
- D. 24 giây
Câu 21: Trong thuật toán sắp xếp nổi bọt (Bubble Sort) cải tiến, nếu trong một vòng lặp không có bất kỳ phép đổi chỗ nào xảy ra, điều đó có nghĩa là gì?
- A. Thuật toán đã chạy sai.
- B. Cần thêm một vòng lặp nữa.
- C. Vẫn cần tiếp tục các vòng lặp tiếp theo để đảm bảo chắc chắn.
- D. Mảng đã được sắp xếp hoàn toàn và thuật toán có thể kết thúc.
Câu 22: Độ phức tạp thời gian của phép toán truy cập một phần tử trong mảng (ví dụ: `array[index]`) là:
- A. O(n)
- B. O(1)
- C. O(log n)
- D. O(n log n)
Câu 23: Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép đổi chỗ (swap) trong trường hợp xấu nhất khi sắp xếp mảng n phần tử là:
- A. n - 1
- B. log n
- C. n(n - 1) / 2
- D. n log n
Câu 24: Để tìm phần tử lớn nhất trong một mảng chưa sắp xếp gồm n phần tử, độ phức tạp thời gian tối thiểu là:
- A. O(1)
- B. O(log n)
- C. O(n)
- D. O(n log n)
Câu 25: Cho đoạn mã giả sau:
```
function RecursiveFunction(n):
if n <= 1:
return
else:
RecursiveFunction(n/2)
```
Độ phức tạp thời gian của hàm `RecursiveFunction(n)` là:
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(1)
Câu 26: Trong các thuật toán sắp xếp, thuật toán nào có độ phức tạp thời gian trung bình là O(n log n) và thường được coi là một trong những thuật toán sắp xếp nhanh nhất?
- A. Sắp xếp nổi bọt (Bubble Sort)
- B. Sắp xếp chèn (Insertion Sort)
- C. Sắp xếp chọn (Selection Sort)
- D. Sắp xếp nhanh (Quick Sort)
Câu 27: Khi nói về độ phức tạp thời gian của thuật toán, chúng ta thường quan tâm đến trường hợp nào nhất?
- 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 28: Để tìm kiếm một cuốn sách trong thư viện không được sắp xếp theo bất kỳ thứ tự nào, phương pháp tìm kiếm nào sẽ phù hợp và có độ phức tạp thời gian là bao nhiêu?
- A. Tìm kiếm tuần tự (Linear Search), độ phức tạp O(n).
- B. Tìm kiếm nhị phân (Binary Search), độ phức tạp O(log n).
- C. Tìm kiếm theo chiều rộng (BFS), độ phức tạp O(n).
- D. Tìm kiếm theo chiều sâu (DFS), độ phức tạp O(n).
Câu 29: 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^2) và thuật toán B có độ phức tạp O(n log n). Với kích thước đầu vào lớn, thuật toán nào sẽ chạy nhanh hơn?
- A. Thuật toán A (O(n^2))
- B. Thuật toán B (O(n log n))
- C. Cả hai thuật toán có tốc độ tương đương.
- D. Không thể xác định nếu không biết kích thước đầu vào cụ thể.
Câu 30: Trong phân tích độ phức tạp thuật toán, ký hiệu "O" lớn (Big O notation) tập trung vào điều gì?
- A. Thời gian thực hiện chính xác của thuật toán trên một máy tính cụ thể.
- B. Số lượng phép toán cụ thể mà thuật toán thực hiện.
- C. Lượng bộ nhớ chính xác mà thuật toán sử dụng.
- D. Tốc độ tăng trưởng của thời gian thực hiện hoặc không gian bộ nhớ khi kích thước đầu vào tăng lên.
