Trắc nghiệm Cánh diều Tin học 8 Bài 2 Sắp xếp dữ liệu

1. Khi sắp xếp theo thứ tự tăng dần, nếu danh sách đã được sắp xếp sẵn, thuật toán nào có thể hoàn thành nhanh nhất?

A. Selection Sort (Sắp xếp chọn)

B. Bubble Sort (Sắp xếp nổi bọt) với cờ tối ưu hóa

C. Quick Sort (Sắp xếp nhanh)

D. Merge Sort (Sắp xếp trộn)

2. Thuật toán sắp xếp nào có độ phức tạp thời gian là O(n log n) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất)?

A. Bubble Sort (Sắp xếp nổi bọt)

B. Insertion Sort (Sắp xếp chèn)

C. Merge Sort (Sắp xếp trộn)

D. Selection Sort (Sắp xếp chọn)

3. Trong ngữ cảnh sắp xếp dữ liệu, phương pháp nào thường được sử dụng để chia một danh sách thành hai nửa, sắp xếp từng nửa và sau đó kết hợp chúng lại?

A. Bubble Sort (Sắp xếp nổi bọt)

B. Merge Sort (Sắp xếp trộn)

C. Insertion Sort (Sắp xếp chèn)

D. Selection Sort (Sắp xếp chọn)

4. Ưu điểm chính của thuật toán Quick Sort (Sắp xếp nhanh) so với Bubble Sort là gì?

A. Dễ cài đặt hơn

B. Hiệu quả hơn về mặt thời gian với các tập dữ liệu lớn

C. Luôn ổn định (stable)

D. Yêu cầu ít bộ nhớ hơn

5. Khi sắp xếp một danh sách theo thứ tự tăng dần, nếu bạn muốn đảm bảo rằng các phần tử có cùng giá trị giữ nguyên thứ tự ban đầu của chúng, bạn nên chọn thuật toán sắp xếp nào?

A. Selection Sort (Sắp xếp chọn)

B. Heap Sort (Sắp xếp vun đống)

C. Quick Sort (Sắp xếp nhanh)

D. Merge Sort (Sắp xếp trộn)

6. Thuật toán nào sẽ tìm phần tử nhỏ nhất trong phần chưa sắp xếp của danh sách và đặt nó vào vị trí đầu tiên của phần chưa sắp xếp đó?

A. Insertion Sort (Sắp xếp chèn)

B. Bubble Sort (Sắp xếp nổi bọt)

C. Selection Sort (Sắp xếp chọn)

D. Merge Sort (Sắp xếp trộn)

7. Mục đích chính của việc phân hoạch (partitioning) trong thuật toán Quick Sort là gì?

A. Để đổi chỗ các phần tử lớn nhất

B. Để chia mảng thành hai mảng con dựa trên một phần tử chốt

C. Để kiểm tra xem mảng đã sắp xếp chưa

D. Để kết hợp hai mảng con đã sắp xếp

8. Việc sắp xếp dữ liệu có ý nghĩa gì trong việc tìm kiếm thông tin hiệu quả?

A. Làm chậm quá trình tìm kiếm

B. Giúp tìm kiếm nhanh hơn bằng cách loại bỏ các phần không cần thiết

C. Chỉ hữu ích cho việc hiển thị dữ liệu

D. Không có ảnh hưởng đến tìm kiếm

9. Trong trường hợp xấu nhất, độ phức tạp thời gian của Quick Sort là bao nhiêu?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

10. Nếu bạn cần sắp xếp một danh sách rất lớn gồm các số nguyên và ưu tiên hiệu suất, thuật toán nào là lựa chọn tốt nhất?

A. Bubble Sort (Sắp xếp nổi bọt)

B. Insertion Sort (Sắp xếp chèn)

C. Selection Sort (Sắp xếp chọn)

D. Quick Sort (Sắp xếp nhanh)

11. Đâu là một ví dụ về việc sắp xếp dữ liệu trong cuộc sống hàng ngày?

A. Nghe nhạc

B. Sắp xếp sách theo thứ tự bảng chữ cái trên kệ

C. Xem phim

D. Chơi trò chơi điện tử

12. Thuật toán sắp xếp nào thực hiện bằng cách lặp đi lặp lại việc duyệt qua danh sách, so sánh các cặp phần tử liền kề và đổi chỗ chúng nếu chúng sai thứ tự?

A. Quick Sort (Sắp xếp nhanh)

B. Heap Sort (Sắp xếp vun đống)

C. Bubble Sort (Sắp xếp nổi bọt)

D. Selection Sort (Sắp xếp chọn)

13. Khái niệm ổn định (stable) trong sắp xếp dữ liệu có nghĩa là gì?

A. Thuật toán luôn sắp xếp nhanh

B. Thuật toán không làm thay đổi thứ tự tương đối của các phần tử có giá trị bằng nhau

C. Thuật toán yêu cầu ít bộ nhớ phụ trợ

D. Thuật toán luôn đúng trong mọi trường hợp

14. Thuật toán nào có thể được xem là tiệm cận (in-place) nghĩa là nó chỉ yêu cầu một lượng bộ nhớ phụ trợ rất nhỏ, không phụ thuộc vào kích thước dữ liệu?

A. Merge Sort (Sắp xếp trộn)

B. Heap Sort (Vun đống)

C. Quick Sort (Sắp xếp nhanh)

D. Cả B và C

15. Nếu bạn có một danh sách các điểm số của học sinh và muốn tìm ra người có điểm cao nhất, bạn sẽ thực hiện hành động gì?

A. Sắp xếp danh sách theo thứ tự tăng dần và lấy phần tử cuối cùng

B. Sắp xếp danh sách theo thứ tự giảm dần và lấy phần tử đầu tiên

C. Tìm kiếm tuyến tính để xác định điểm cao nhất

D. Cả A và B đều đúng

16. Thuật toán nào thực hiện việc chèn từng phần tử của danh sách vào một danh sách con đã được sắp xếp?

A. Selection Sort (Sắp xếp chọn)

B. Bubble Sort (Sắp xếp nổi bọt)

C. Insertion Sort (Sắp xếp chèn)

D. Merge Sort (Sắp xếp trộn)

17. Khi so sánh Insertion Sort và Selection Sort về mặt hiệu suất trung bình, chúng thường có độ phức tạp thời gian như thế nào?

A. Cả hai đều là O(n log n)

B. Insertion Sort là O(n^2), Selection Sort là O(n log n)

C. Cả hai đều là O(n^2)

D. Insertion Sort là O(n log n), Selection Sort là O(n^2)

18. Thuật toán sắp xếp nào có thể có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất?

A. Merge Sort (Sắp xếp trộn)

B. Heap Sort (Sắp xếp vun đống)

C. Bubble Sort (Sắp xếp nổi bọt)

D. Quick Sort (Sắp xếp nhanh) trong trường hợp tốt nhất

19. Thuật toán nào có thể sử dụng phân chia và thống trị (divide and conquer) để sắp xếp dữ liệu?

A. Bubble Sort (Sắp xếp nổi bọt)

B. Insertion Sort (Sắp xếp chèn)

C. Quick Sort (Sắp xếp nhanh) và Merge Sort (Sắp xếp trộn)

D. Selection Sort (Sắp xếp chọn)

20. Khi sắp xếp một danh sách các chuỗi ký tự theo thứ tự từ điển (alphabetical order), apple sẽ đứng trước hay sau banana?

A. Sau banana

B. Trước banana

C. Phụ thuộc vào độ dài chuỗi

D. Ngẫu nhiên

21. Việc sắp xếp dữ liệu theo ngày tháng năm sinh từ cũ nhất đến mới nhất sẽ đặt người nào ở vị trí đầu tiên?

A. Người có ngày sinh gần đây nhất

B. Người có ngày sinh xa xưa nhất

C. Người có ngày sinh vào giữa năm

D. Người có tên bắt đầu bằng chữ A

22. Thuật toán Insertion Sort (Sắp xếp chèn) hiệu quả nhất khi nào?

A. Khi danh sách rất lớn và ngẫu nhiên

B. Khi danh sách gần như đã được sắp xếp hoặc có kích thước nhỏ

C. Khi cần một thuật toán đơn giản nhất

D. Khi cần sắp xếp theo thứ tự giảm dần

23. Trong Quick Sort, pivot (phần tử chốt) đóng vai trò gì?

A. Là phần tử lớn nhất trong danh sách

B. Là phần tử nhỏ nhất trong danh sách

C. Là phần tử dùng để phân chia danh sách thành hai phần nhỏ hơn

D. Là phần tử trung bình của danh sách

24. Khi sắp xếp một danh sách theo thứ tự giảm dần, phần tử lớn nhất sẽ nằm ở đâu sau khi quá trình sắp xếp hoàn tất?

A. Ở giữa danh sách

B. Cuối danh sách

C. Đầu danh sách

D. Phụ thuộc vào thuật toán sắp xếp

25. Trong thuật toán Heap Sort, cấu trúc dữ liệu heap (cây vun đống) được sử dụng để làm gì?

A. Để lưu trữ tạm thời các phần tử đã sắp xếp

B. Để đảm bảo phần tử lớn nhất (hoặc nhỏ nhất) luôn ở nút gốc

C. Để chia danh sách thành các phần nhỏ

D. Để thực hiện so sánh các phần tử liền kề