JavaScript is required

Trong các giải thuật sắp xếp, giải thuật nào sau đây áp dụng phương pháp Chia để trị?

A.

Quick sort, Heap sort

B.

Quick sort, Merge sort

C.

Quick sort, Bubble sort

D.

Quick sort, Insert sort

Trả lời:

Đáp án đúng: B


Phương pháp Chia để trị (Divide and Conquer) là một kỹ thuật thiết kế thuật toán bằng cách chia nhỏ bài toán thành các bài toán con tương tự nhưng nhỏ hơn, giải quyết các bài toán con này một cách đệ quy, và sau đó kết hợp các kết quả để có được lời giải cho bài toán ban đầu.

Quick Sort:

  • Chia: Chọn một phần tử làm chốt (pivot) và chia mảng thành hai mảng con: một mảng chứa các phần tử nhỏ hơn chốt và một mảng chứa các phần tử lớn hơn chốt.
  • Trị: Sắp xếp đệ quy hai mảng con này.
  • Kết hợp: Không cần kết hợp vì quá trình chia đã đảm bảo vị trí đúng của các phần tử.

Merge Sort:

  • Chia: Chia mảng thành hai nửa bằng nhau.
  • Trị: Sắp xếp đệ quy hai nửa này.
  • Kết hợp: Trộn hai nửa đã sắp xếp để tạo thành một mảng đã sắp xếp hoàn chỉnh.

Heap Sort, Bubble Sort, Insert Sort: Các thuật toán này không sử dụng phương pháp chia để trị.

Vậy, đáp án đúng là Quick sort và Merge sort.

Đề cương ôn thi với 220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án được chọn lọc và chia sẻ dưới đây, nhằm giúp bạn sinh viên hệ thống kiến thức chuẩn bị cho kì thi sắp diễn ra.


50 câu hỏi 60 phút

Câu hỏi liên quan