Trắc Nghiệm Tin Học 11 Cánh Diều Khoa Học Máy Tính Chủ đề FCS Bài 9: Lập trình sắp xếp nhanh là nội dung thuộc môn Tin học, được biên soạn dưới dạng đề ôn tập tham khảo cho học sinh lớp 11 theo chương trình sách giáo khoa Cánh Diều. Bộ đề tập trung vào thuật toán sắp xếp nhanh (Quick Sort) – một trong những thuật toán quan trọng và hiệu quả nhất trong xử lý dữ liệu, giúp học sinh hiểu rõ cơ chế chia để trị, cách chọn chốt và quá trình phân hoạch mảng. Trong đoạn mở đầu có sử dụng định dạng trắc nghiệm Tin học 11 Khoa học máy tính Cánh Diều, tài liệu được biên soạn năm 2024 bởi thầy Phạm Đức Hoàng – giáo viên Tin học Trường THPT Nguyễn Thượng Hiền (TP. Hồ Chí Minh). Bộ đề được đăng tải trên detracnghiem.edu.vn nhằm hỗ trợ học sinh luyện tập sâu và hệ thống.
Trắc nghiệm môn Tin học 11 ở bài học này bao gồm hệ thống câu hỏi từ nhận biết đến vận dụng cao, giúp học sinh nắm vững cách hoạt động của Quick Sort, phân tích độ phức tạp, so sánh với các thuật toán sắp xếp khác và vận dụng thuật toán vào lập trình thực tế. Khi luyện tập trên detracnghiem.edu.vn, học sinh được xem lời giải chi tiết, đánh giá mức độ tiến bộ và rèn luyện tư duy thuật toán hiệu quả. Đây là tài liệu thiết thực giúp học sinh chuẩn bị tốt cho các bài kiểm tra định kỳ Trắc nghiệm lớp 11.
Trắc Nghiệm Tin Học 11 Cánh Diều Khoa Học Máy Tính
Chủ đề FCS: Giải quyết vấn đề với sự trợ giúp của máy tính
Bài 9: Lập trình sắp xếp nhanh
Câu 1: Thuật toán sắp xếp nhanh (QuickSort) dựa trên kĩ thuật thiết kế thuật toán nào sau đây?
A. Quy hoạch động.
B. Tham lam (Greedy).
C. Chia để trị.
D. Quay lui (Backtracking).
Câu 2: Trong thuật toán QuickSort, phần tử được chọn để làm mốc so sánh và phân chia dãy số được gọi là gì?
A. Phần tử khóa (key).
B. Phần tử lính canh.
C. Phần tử chốt (pivot).
D. Phần tử trung vị.
Câu 3: Độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh là bao nhiêu?
A. O(n).
B. O(n log n).
C. O(n²).
D. O(log n).
Câu 4: Mục đích chính của thao tác “phân đoạn” (partition) trong QuickSort là gì?
A. Tìm phần tử nhỏ nhất và đưa về đầu dãy.
B. Chia đôi dãy số thành hai nửa bằng nhau.
C. Đưa phần tử chốt về đúng vị trí đã sắp xếp.
D. Sao chép dữ liệu sang một mảng phụ khác.
Câu 5: Sau khi thực hiện xong việc phân đoạn với chốt là p, tính chất nào sau đây luôn đúng?
A. Mảng được sắp xếp hoàn toàn tăng dần.
B. Các số bên trái ≤ p, các số bên phải ≥ p.
C. Phần tử chốt p nằm ở vị trí cuối cùng.
D. Phần tử chốt p nằm ở vị trí đầu tiên.
Câu 6: Trong phân đoạn Lomuto (thường chọn chốt ở cuối), biến i dùng để quản lý điều gì?
A. Duyệt qua tất cả các phần tử của dãy.
B. Lưu trữ giá trị của phần tử chốt.
C. Đếm số lần hoán đổi vị trí.
D. Đánh dấu ranh giới các phần tử nhỏ hơn chốt.
Câu 7: Điều kiện dừng của đệ quy trong hàm quickSort(A, low, high) là gì?
A. low == high
B. low < high
C. low >= high
D. high == len(A)
Câu 8: Trường hợp xấu nhất (Worst Case) của QuickSort xảy ra khi nào (với cách chọn chốt đơn giản ở đầu hoặc cuối)?
A. Khi dãy số có kích thước rất nhỏ.
B. Khi các phần tử trong dãy bằng nhau hết.
C. Khi dãy số hoàn toàn ngẫu nhiên.
D. Khi dãy đã được sắp xếp tăng hoặc giảm dần.
Câu 9: Độ phức tạp thời gian của QuickSort trong trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n!)
D. O(n²)
Câu 10: Cho dãy A = [5, 1, 4, 2, 8]. Nếu chọn chốt là 5 và thực hiện phân đoạn, dãy có thể trở thành:
A. [1, 2, 4, 5, 8]
B. [2, 1, 4, 5, 8]
C. [8, 5, 1, 4, 2]
D. [5, 1, 4, 2, 8]
Câu 11: So với Sắp xếp trộn (Merge Sort), QuickSort có ưu điểm gì về mặt không gian bộ nhớ?
A. Luôn chạy nhanh hơn trong mọi trường hợp.
B. Không sử dụng đệ quy nên ít tốn stack.
C. Sắp xếp tại chỗ, không cần mảng phụ lớn.
D. Mã nguồn ngắn gọn và dễ hiểu hơn.
Câu 12: Trong phân đoạn Hoare, người ta sử dụng hai con trỏ di chuyển như thế nào?
A. Từ hai đầu dãy di chuyển lại gần nhau.
B. Cùng xuất phát từ đầu dãy đi về cuối.
C. Cùng xuất phát từ cuối dãy đi về đầu.
D. Xuất phát từ giữa dãy đi ra hai bên.
Câu 13: Hàm partitionLomuto(A, low, high) trong sách giáo khoa trả về giá trị gì?
A. Giá trị của phần tử chốt.
B. Danh sách đã được sắp xếp.
C. Số lượng phần tử của mảng.
D. Chỉ số (vị trí) của phần tử chốt.
Câu 14: Để giảm thiểu nguy cơ rơi vào trường hợp xấu nhất của QuickSort, ta nên chọn chốt như thế nào?
A. Luôn chọn phần tử đầu tiên.
B. Luôn chọn phần tử cuối cùng.
C. Chọn ngẫu nhiên hoặc chọn trung vị.
D. Chọn phần tử lớn nhất trong dãy.
Câu 15: Câu lệnh quickSort(A, low, k – 1) và quickSort(A, k + 1, high) thực hiện điều gì?
A. Sắp xếp toàn bộ mảng A hai lần.
B. Sắp xếp phần tử chốt tại vị trí k.
C. Bỏ qua không sắp xếp phần tử k.
D. Gọi đệ quy sắp xếp hai nửa trái và phải.
Câu 16: Trong Python, giới hạn độ sâu đệ quy mặc định có thể gây lỗi gì nếu dùng QuickSort cho mảng rất lớn?
A. MemoryError
B. TypeError
C. RecursionError
D. IndexError
Câu 17: Cho đoạn mã Lomuto: if A[j] <= pivot: … Hành động tiếp theo thường là gì?
A. Tăng i lên 1 và đổi chỗ A[i] với A[j].
B. Giảm j đi 1 và đổi chỗ A[i] với A[j].
C. Chỉ cần tăng biến chạy j lên 1.
D. Đổi chỗ A[j] với phần tử chốt ngay.
Câu 18: Tại sao QuickSort không được coi là thuật toán sắp xếp “ổn định” (stable)?
A. Vì thời gian chạy của nó không cố định.
B. Vì nó phụ thuộc vào phần cứng máy tính.
C. Vì nó có thể đổi chỗ các phần tử bằng nhau.
D. Vì nó không sắp xếp được số âm.
Câu 19: Nếu mảng đầu vào có nhiều phần tử giống nhau, hiệu suất của QuickSort (bản chuẩn) sẽ:
A. Tăng lên rất nhanh.
B. Không bị ảnh hưởng gì.
C. Luôn đạt mức tốt nhất.
D. Có thể bị giảm (gần với trường hợp xấu).
Câu 20: Trong phân đoạn Hoare, vòng lặp dừng lại khi nào?
A. Khi tìm thấy phần tử lớn hơn chốt.
B. Khi con trỏ trái chạm vào chốt.
C. Khi hai con trỏ trái và phải vượt qua nhau.
D. Khi duyệt hết đúng n lần lặp.
Câu 21: Giả sử hàm partition trả về vị trí k. Sau bước này, ta biết chắc chắn điều gì về A[k]?
A. A[k] là phần tử nhỏ nhất mảng.
B. A[k] là phần tử lớn nhất mảng.
C. A[k] bằng trung bình cộng của mảng.
D. A[k] đang đứng đúng vị trí sắp xếp.
Câu 22: Để sắp xếp giảm dần bằng QuickSort, ta cần thay đổi điều gì trong hàm phân đoạn?
A. Thay đổi cách chọn phần tử chốt.
B. Đổi phép so sánh =.
C. Đổi thứ tự gọi đệ quy trái phải.
D. Không thể dùng QuickSort để xếp giảm.
Câu 23: Cho dãy A = [2, 8, 7, 1, 3, 5, 6, 4]. Chọn chốt là 4 (cuối cùng). Theo phân đoạn Lomuto, phần tử 4 sẽ đổi chỗ với số nào cuối cùng?
A. Số 2.
B. Số 1.
C. Số 8.
D. Số 6.
Câu 24: Khi cài đặt QuickSort trên Python, để hoán đổi giá trị hai phần tử A[i] và A[j], ta viết:
A. swap(A[i], A[j])
B. A[i] = A[j]
C. A[i], A[j] = A[j], A[i]
D. A[i] A[j]
Câu 25: Trong các thư viện chuẩn của các ngôn ngữ lập trình (như C++, Java, Python), thuật toán sắp xếp mặc định thường là:
A. Bubble Sort thuần túy.
B. Selection Sort vì dễ cài đặt.
C. QuickSort hoặc biến thể lai (như Timsort).
D. Insertion Sort vì ít tốn bộ nhớ.
Câu 26: Kỹ thuật “chọn chốt là phần tử ở giữa” (mid = (low + high) // 2) giúp QuickSort giải quyết tốt vấn đề gì?
A. Vấn đề tràn bộ nhớ stack.
B. Tránh trường hợp xấu nhất khi mảng đã sắp xếp.
C. Giảm bớt số lượng biến cần khai báo.
D. Làm cho mã nguồn ngắn gọn hơn.
Câu 27: Một biến thể của QuickSort dùng để tìm phần tử lớn thứ K trong mảng mà không cần sắp xếp hết gọi là gì?
A. MergeSelect.
B. BinarySearch.
C. BubbleSelect.
D. QuickSelect.
Câu 28: Nếu kích thước mảng con trở nên rất nhỏ (ví dụ < 10 phần tử), chiến lược tối ưu thường được áp dụng kết hợp với QuickSort là gì?
A. Dùng Bubble Sort để sắp xếp mảng con.
B. Dừng đệ quy và không sắp xếp nữa.
C. Chuyển sang dùng Insertion Sort.
D. Tăng thêm bộ nhớ cho mảng con.
Câu 29: Đoạn mã:
import sys
sys.setrecursionlimit(2000)
có ý nghĩa gì khi chạy QuickSort?
A. Tăng tốc độ xử lý của CPU.
B. Giới hạn số phần tử của mảng là 2000.
C. Tăng giới hạn số lần gọi đệ quy.
D. Tự động chọn chốt tối ưu.
Câu 30: Trong phân đoạn Lomuto, nếu tất cả các phần tử trong mảng đều nhỏ hơn chốt (trừ chốt), thì sau khi phân đoạn, chốt sẽ nằm ở đâu?
A. Vị trí đầu tiên của mảng.
B. Vị trí giữa mảng.
C. Vị trí ngẫu nhiên.
D. Vị trí cuối cùng của mảng.
