Đáp án và lời giải

Bài tập Thuật toán sắp xếp có đáp án

Câu 1

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Các bước thực hiện:

- Đổ nước trong cốc A (hoặc cốc B) sang cốc C.

- Đổ nước trong cốc B (hoặc A) còn lại sang cốc trống.

- Đổ nước trong cốc C vào cốc còn trống.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Vòng lặp thứ nhất	3 5 4 1 2 2 > 1 ⇒ KHÔNG hoán đổi 3 5 4 1 2 1 < 4 ⇒ hoán đổi 3 5 1 4 2 1 < 5 ⇒ hoán đổi 3 1 5 4 2 1 < 3 ⇒ hoán đổi Kết quả vòng lặp thứ nhất 1 3 5 4 2
Vòng lặp thứ hai	1 3 5 4 2 2 < 4 ⇒ hoán đổi 1 3 5 2 4 2 < 5 ⇒ hoán đổi 1 3 2 5 4 2 < 3 ⇒ hoán đổi Kết quả vòng lặp thứ hai 1 2 3 5 4
Vòng lặp thứ ba	1 2 3 5 4 4 < 5 ⇒ hoán đổi 1 2 3 4 5 4 > 3 ⇒ KHÔNG hoán đổi 1 2 3 4 5 3 > 2 ⇒ KHÔNG hoán đổi 1 2 3 4 5 2 > 1 ⇒ KHÔNG hoán đổi Kết quả vòng lặp thứ ba 1 2 3 4 5

Lời giải do TopStudy biên soạn

Đáp án: C

Đáp án đúng là: C

Thuật toán sắp xếp nổi bọt sắp xếp danh sách được thực hiện bằng cách hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Vòng lặp thứ nhất	41 15 17 32 18 15 < 41 ⇒ hoán đổi 15 41 17 32 18 17 > 15 ⇒ KHÔNG hoán đổi 15 41 17 32 18 32 > 15 ⇒ KHÔNG hoán đổi 15 41 17 32 18 18 > 15 ⇒ KHÔNG hoán đổi Kết quả vòng lặp thứ nhất 15 41 17 32 18
Vòng lặp thứ hai	15 41 17 32 18 17 < 41 ⇒ hoán đổi 15 17 41 32 18 32 > 17 ⇒ KHÔNG hoán đổi 15 17 41 32 18 18 > 17 ⇒ KHÔNG hoán đổi Kết quả vòng lặp thứ hai 15 17 41 32 18
Vòng lặp thứ ba	15 17 41 32 18 32 < 41 ⇒ hoán đổi 15 17 32 41 18 18 < 32 ⇒ hoán đổi 15 17 18 41 32 Kết quả vòng lặp thứ ba 15 17 18 41 32
Vòng lặp thứ tư	15 17 18 41 32 32 < 41 ⇒ hoán đổi Kết quả vòng lặp thứ tư 15 17 18 32 41

Đầu ra dãy các phần tử đã sắp xếp tăng dần:

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Vòng lặp thứ hai	1 4 3 5 2 3 < 4 ⇒ hoán đổi 1 3 4 5 2 KHÔNG hoán đổi 1 3 4 5 2 2 < 3 ⇒ hoán đổi Kết quả vòng lặp thứ hai 1 2 4 5 3
Vòng lặp thứ ba	1 2 4 5 3 5 > 4 ⇒ KHÔNG hoán đổi 1 2 4 5 3 3 < 4 ⇒ hoán đổi 1 2 3 5 4 Kết quả vòng lặp thứ ba
Vòng lặp thứ tư	1 2 3 5 4 4 < 5 ⇒ hoán đổi 1 2 3 4 5 Kết quả vòng lặp thứ tư

Lời giải do TopStudy biên soạn

Đáp án: C

Đáp án đúng là: C

Chia một bài toán thành những bài toán nhỏ hơn giúp thuật toán dễ hiểu và dễ thực hiện hơn.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Vòng lặp thứ nhất	3 2 4 1 5 5 > 1 ⇒ KHÔNG hoán đổi 3 2 4 1 5 1 < 4 ⇒ hoán đổi 3 2 1 4 5 1 < 2 ⇒ hoán đổi Kết quả vòng lặp thứ nhất 3 1 2 4 5 1 < 3 ⇒ hoán đổi 1 3 2 4 5 Kết quả vòng lặp thứ nhất
Vòng lặp thứ hai	1 3 2 4 5 5 > 4 ⇒ KHÔNG hoán đổi 1 3 2 4 5 4 < 2 ⇒ KHÔNG hoán đổi 1 3 2 4 5 2 < 3 ⇒ hoán đổi 1 2 3 4 5 Kết quả vòng lặp thứ hai

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Vòng lặp thứ nhất	3 2 4 1 5 2 < 3 ⇒ hoán đổi 2 3 4 1 5 KHÔNG hoán đổi 2 3 4 1 5 1 < 2 ⇒ hoán đổi Kết quả vòng lặp thứ nhất 1 3 4 2 5
Vòng lặp thứ hai	1 3 4 2 5 KHÔNG hoán đổi 1 3 4 2 5 2 < 3 ⇒ hoán đổi 1 2 4 3 5 Kết quả vòng lặp thứ hai
Vòng lặp thứ ba	1 2 4 3 5 3 < 4 ⇒ hoán đổi 1 2 3 4 5 Kết quả vòng lặp thứ ba
Vòng lặp thứ tư	1 2 3 4 5 KHÔNG hoán đổi 1 2 3 4 5 Kết quả vòng lặp thứ tư

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

- Bảng điểm môn Tin học

- Thực hiện thuật toán sắp xếp nổi bọt:

Vòng lặp thứ nhất	7 4 9 5 6 6 > 5 ⇒ hoán đổi 7 4 9 6 5 6 < 9 ⇒ KHÔNG hoán đổi 7 4 9 6 5 9 > 4 ⇒ hoán đổi 7 9 4 6 5 9 > 7 ⇒ hoán đổi 9 7 4 6 5 Kết quả vòng lặp thứ nhất
Vòng lặp thứ hai	9 7 4 6 5 5 < 6 ⇒ KHÔNG hoán đổi 9 7 4 6 5 6 > 4 ⇒ hoán đổi 9 7 6 4 5 7 < 9 ⇒ KHÔNG hoán đổi 9 7 6 4 5 Kết quả vòng lặp thứ hai
Vòng lặp thứ ba	9 7 6 4 5 5 > 4 ⇒ hoán đổi 9 7 6 5 4 5 < 6 ⇒ KHÔNG hoán đổi 9 7 6 5 4 7 < 9 ⇒ KHÔNG hoán đổi 9 7 6 5 4 7 < 9 ⇒ KHÔNG hoán đổi 9 7 6 5 4 Kết quả vòng lặp thứ hai

- Bảng điểm môn Tin học sau khi sắp xếp: