Cho cây nhị phân: A B C D E F. Cho biết thứ tự các phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự sau?

Phương pháp sắp xếp lựa chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của dãy, và đổi chỗ nó với phần tử đầu tiên của phần chưa được sắp xếp đó. Lặp lại quá trình này cho đến khi toàn bộ dãy được sắp xếp.

Dãy ban đầu: {6 1 3 0 5 7 9 2 8 4}

Sau lần lặp 1: {0 1 3 6 5 7 9 2 8 4} (Số 0 được đưa về đầu)

Sau lần lặp 2: {0 1 3 6 5 7 9 2 8 4} (Số 1 đã đúng vị trí)

Sau lần lặp 3: {0 1 2 6 5 7 9 3 8 4} (Số 2 được đưa về vị trí thứ 3)

Sau lần lặp 4: {0 1 2 3 5 7 9 6 8 4} (Số 3 được đưa về vị trí thứ 4)

Sau lần lặp 5: {0 1 2 3 4 7 9 6 8 5} (Số 4 được đưa về vị trí thứ 5)

Vậy, dãy số thu được sau lần lặp thứ năm là {0 1 2 3 4 7 9 6 8 5}.

Sắp xếp lựa chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của dãy số và hoán đổi nó với phần tử đầu tiên của phần chưa được sắp xếp đó. Sau mỗi lần lặp, một phần tử sẽ được đặt đúng vị trí cuối cùng của nó trong dãy số đã sắp xếp.

Cho dãy số ban đầu: {6 1 3 0 5 7 9 2 8 4}

Sau lần lặp đầu tiên: {0 1 3 6 5 7 9 2 8 4}. Số 0 được đưa về vị trí đầu tiên.

Các bước tiếp theo:

- Lần lặp 2: Tìm min từ vị trí thứ 2 trở đi (tức từ 1 đến hết dãy). Ta có số 1 đã đúng vị trí.

- Lần lặp 3: Tìm min từ vị trí thứ 3 trở đi (tức từ 3 đến hết dãy). Ta có số 2, và hoán đổi nó với số 3. Dãy trở thành: {0 1 2 6 5 7 9 3 8 4}

- Lần lặp 4: Tìm min từ vị trí thứ 4 trở đi (tức từ 6 đến hết dãy). Ta có số 3, và hoán đổi nó với số 6. Dãy trở thành: {0 1 2 3 5 7 9 6 8 4}

- Lần lặp 5: Tìm min từ vị trí thứ 5 trở đi (tức từ 5 đến hết dãy). Ta có số 4, và hoán đổi nó với số 5. Dãy trở thành: {0 1 2 3 4 7 9 6 8 5}

- Lần lặp 6: Tìm min từ vị trí thứ 6 trở đi (tức từ 7 đến hết dãy). Ta có số 5, và hoán đổi nó với số 7. Dãy trở thành: {0 1 2 3 4 5 9 6 8 7}

Vậy, sau lần lặp thứ sáu, dãy số thu được là: {0 1 2 3 4 5 9 6 8 7}

Phương pháp sắp xếp hòa nhập (Merge Sort) là một thuật toán sắp xếp chia để trị. Trong lượt đầu tiên (lượt 1), thuật toán chia dãy số thành các cặp phần tử liền kề và sắp xếp từng cặp đó.

Dãy số ban đầu: 40 25 75 15 65 55 90 30 95 85

Sau lượt 1, các cặp được sắp xếp như sau:

• Cặp 1: 40 và 25 -> 25 40
• Cặp 2: 75 và 15 -> 15 75
• Cặp 3: 65 và 55 -> 55 65
• Cặp 4: 90 và 30 -> 30 90
• Cặp 5: 95 và 85 -> 85 95

Vậy dãy số sau lượt 1 sẽ là: [25 40] [15 75] [55 65] [30 90] [85 95]

Đáp án phù hợp nhất là phương án 4.