Trắc nghiệm Tin học 11 Cánh diều KHMT bài 9 Lập trình thuật toán sắp xếp nhanh

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

A A. Chọn một phần tử chốt có khả năng gần với giá trị trung vị thực sự của mảng con, giảm thiểu khả năng chia mảng không cân bằng. B B. Sắp xếp ba phần tử đầu tiên của mảng con. C C. Tăng tốc độ của bước phân hoạch bằng cách xử lý ba phần tử cùng lúc. D D. Giảm số lần hoán vị trong quá trình sắp xếp.

A A. Chuyển sang sử dụng một thuật toán sắp xếp khác hiệu quả hơn cho mảng nhỏ, như Insertion Sort. B B. Tiếp tục sử dụng Quick Sort với các mảng con rất nhỏ. C C. Dừng quá trình sắp xếp và báo cáo kết quả. D D. Sử dụng thuật toán Heap Sort cho các mảng nhỏ.

A A. Thuật toán thực hiện sắp xếp trực tiếp trên mảng dữ liệu gốc mà không cần mảng phụ lớn. B B. Thuật toán chỉ sắp xếp các phần tử tại vị trí ban đầu của chúng. C C. Thuật toán cần một bản sao của mảng để thực hiện sắp xếp. D D. Thuật toán chỉ làm việc với các phần tử đã được đánh dấu là tại chỗ.

A A. Quick Sort thường yêu cầu ít bộ nhớ phụ hơn vì nó có thể sắp xếp tại chỗ (in-place). B B. Merge Sort yêu cầu ít bộ nhớ phụ hơn vì nó chia mảng thành các phần tử nhỏ. C C. Cả hai thuật toán đều yêu cầu lượng bộ nhớ phụ tương đương nhau. D D. Quick Sort luôn yêu cầu bộ nhớ phụ lớn hơn Merge Sort.

A A. Phần tử cuối cùng của mảng con. B B. Phần tử đầu tiên của mảng con. C C. Phần tử có giá trị nhỏ nhất trong mảng con. D D. Phần tử có giá trị lớn nhất trong mảng con.

A A. Tốc độ trung bình nhanh và hiệu quả trên nhiều loại dữ liệu. B B. Độ phức tạp thời gian luôn là O(n log n) bất kể trường hợp nào. C C. Dễ dàng cài đặt và hiểu rõ hơn Merge Sort. D D. Sử dụng ít bộ nhớ phụ hơn Bubble Sort.

A A. Thuật toán sẽ rơi vào trường hợp xấu nhất với độ phức tạp O(n^2). B B. Thuật toán sẽ hoạt động hiệu quả nhất với độ phức tạp O(n log n). C C. Thuật toán sẽ bị lỗi và không hoàn thành việc sắp xếp. D D. Thuật toán sẽ chuyển sang sử dụng một phương pháp sắp xếp khác.

A A. Mảng con đã được sắp xếp hoặc sắp xếp ngược. B B. Mảng con chứa các phần tử ngẫu nhiên. C C. Mảng con chứa các phần tử giống nhau. D D. Mảng con có kích thước nhỏ.

A A. Khi phần tử chốt luôn là phần tử nhỏ nhất hoặc lớn nhất trong mảng con, dẫn đến việc chia mảng không cân bằng. B B. Khi phần tử chốt luôn là phần tử trung vị của mảng con. C C. Khi mảng đã được sắp xếp hoặc sắp xếp ngược. D D. Khi tất cả các phần tử trong mảng là giống nhau.

A A. Giảm khả năng xảy ra trường hợp xấu nhất (O(n^2)). B B. Tăng tốc độ sắp xếp trong mọi trường hợp lên O(n). C C. Giảm lượng bộ nhớ sử dụng. D D. Đảm bảo độ phức tạp O(n log n) cho mọi trường hợp.

A A. Thứ tự tương đối của các phần tử bằng nhau có thể bị thay đổi sau quá trình phân hoạch. B B. Thuật toán không thể sắp xếp các phần tử bằng nhau. C C. Phần tử chốt luôn được đặt ở vị trí chính xác giữa mảng. D D. Thuật toán chỉ hoạt động với các phần tử duy nhất.

A A. Phần tử chốt được đặt vào đúng vị trí cuối cùng của nó trong mảng đã sắp xếp, và các phần tử được chia thành hai mảng con độc lập. B B. Mảng được chia thành hai nửa với kích thước gần bằng nhau. C C. Phần tử nhỏ nhất được đưa về đầu mảng. D D. Hai phần tử liền kề sai thứ tự được hoán đổi.

A A. Khi bộ nhớ có hạn và cần sắp xếp tại chỗ. B B. Khi cần đảm bảo tính ổn định của thuật toán. C C. Khi dữ liệu có kích thước rất lớn và cần độ phức tạp O(n log n) nghiêm ngặt. D D. Khi cần một thuật toán có độ phức tạp xấu nhất là O(n log n).

A A. Thuật toán chia để trị. B B. Thuật toán tham lam. C C. Thuật toán quay lui. D D. Thuật toán duyệt theo chiều rộng.

A A. Thường thực hiện ít phép hoán đổi hơn và hiệu quả hơn trên dữ liệu có nhiều phần tử trùng lặp. B B. Luôn nhanh hơn Lomuto trong mọi trường hợp. C C. Dễ cài đặt hơn Lomuto. D D. Yêu cầu ít bộ nhớ phụ hơn Lomuto.

A A. Có thể là phần tử đầu tiên, cuối cùng, giữa hoặc một phần tử ngẫu nhiên. B B. Luôn là phần tử có giá trị nhỏ nhất trong mảng. C C. Luôn là phần tử có giá trị lớn nhất trong mảng. D D. Luôn là phần tử có giá trị trung vị của mảng.

A A. Chia để trị. B B. Quy hoạch động. C C. Duyệt đồ thị. D D. Tìm kiếm nhị phân.

A A. Giảm độ phức tạp không gian của ngăn xếp đệ quy xuống O(log n) ngay cả trong trường hợp xấu nhất. B B. Tăng tốc độ xử lý của thuật toán. C C. Giảm số lượng phép so sánh. D D. Làm cho thuật toán trở nên ổn định.

A A. Chọn một phần tử làm chốt (pivot) và sắp xếp lại các phần tử sao cho các phần tử nhỏ hơn chốt nằm trước chốt, các phần tử lớn hơn nằm sau chốt. B B. Hoán đổi vị trí của hai phần tử liền kề nếu chúng sai thứ tự. C C. Tìm phần tử nhỏ nhất trong mảng và đưa nó về vị trí đầu tiên. D D. Chia mảng thành hai nửa và sắp xếp từng nửa một cách độc lập.

A A. O(log n) trong trường hợp trung bình và O(n) trong trường hợp xấu nhất. B B. O(n) trong mọi trường hợp. C C. O(1) trong mọi trường hợp. D D. O(n log n) trong trường hợp trung bình.

A A. Khi mảng con có 0 hoặc 1 phần tử. B B. Khi mảng con có 2 phần tử. C C. Khi mảng con có 10 phần tử. D D. Khi mảng con đã được sắp xếp hoàn toàn.

A A. Hai con trỏ, một từ đầu và một từ cuối mảng con, tiến về phía nhau. B B. Một con trỏ bắt đầu từ đầu mảng con và một con trỏ cố định ở cuối. C C. Hai con trỏ cùng bắt đầu từ giữa mảng con và di chuyển ra hai bên. D D. Một con trỏ duy nhất di chuyển từ đầu đến cuối mảng con.

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

A A. Chỉ số của phần tử chốt sau khi phân hoạch. B B. Số lượng phần tử nhỏ hơn chốt. C C. Số lượng phần tử lớn hơn chốt. D D. Tổng giá trị của các phần tử trong mảng con.