Câu hỏi tự luận tin học 7 chân trời Bài 14: Thuật toán sắp xếp

BÀI 14: THUẬT TOÁN SẮP XẾP (15 CÂU)

I. NHẬN BIẾT (2 CÂU)

Câu 1: Thuật toán sắp xếp nổi bọt là gì?

Trả lời:

Thuật toán sắp xếp nổi bọt là thuật toán thực hiện sắp xếp dãy phần tử (tăng dần hay giảm dần) bằng cách thực hiện lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nếu chúng sai thứ tự.

Câu 2: Thuật toán sắp xếp chọn là gì?

Trả lời:

Thuật toán sắp xếp chọn là thuật toán thực hiện lặp lại quá trình chọn phần tử nhỏ nhất trong dãy chưa sắp xếp và đưa phần tử này về vị trí đầu tiên của nó.

II. THÔNG HIỂU (5 CÂU)

Câu 1: Em hãy mô tả thuật toán sắp xếp nổi bọt.

Trả lời:

Thuật toán sắp xếp nổi bọt.

Đầu vào: Dãy chưa được sắp xếp.

Đầu ra: Dãy được sắp xếp không giảm.

1. Chuyển phần tử nhỏ nhất về vị trí đầu tiên.

1.1 So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử đầu tiên.

1.2 Nếu nhỏ hơn thì đổi chỗ hai phần tử.

1.3 Kết thúc vòng lặp, phần tử nhỏ nhất “nổi lên” vị trí đầu tiên của dãy.

2. Chuyển phần tử nhỏ thứ hai về vị trí thứ hai.

2.1 So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử thứ hai.

2.2 Nếu nhỏ hơn thì đổi chỗ hai phần tử.

2.3 Kết thúc vòng, phần tử nhỏ thứ hai “nổi lên” vị trí thứ hai của dãy.

3. Thực hiện tương tự như trên với phần tử nhỏ thứ ba, thứ tư,… cho đến phần tử liền trước phần tử cuối cùng.
4. Kết thúc thuật toán, ta sẽ nhận được dãy số đã dược sắp xếp theo thứ tự tăng dần.

Câu 2: Em hãy mô tả thuật toán sắp xếp chọn.

Trả lời:

Thuật toán sắp xếp chọn.

Đầu vào: Dãy chưa được sắp xếp.

Đầu ra: Dãy được sắp xếp không giảm.

1. Với vị trí đầu tiên, thực hiện vòng lặp như sau:

1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên.

1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên.

1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên.

2. Với vị trí thứ hai, thực hiện một vòng lặp tương tự như trên.

2.1. So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai.

2.2. Nếu phần tử được xét nhỏ hơn phần tử thứ hai thì hoán đổi nó với phần tử tại vị trí thứ hai.

2.3 Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhì được đưa về vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ ba, thứ tư,… đến vị trí được vị trí cuối cùng.
4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo tăng dần.

Câu 3: Em hãy nêu sự khác nhau giữa thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chọn?
Trả lời:

Sự khác nhau giữa thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chọn là:

- Cách thức hoạt động :

+ Thuật toán sắp xếp nổi bọt di chuyển lần lượt qua danh sách, so sánh cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Quá trình này lặp lại cho đến khi không còn phần tử nào cần phải hoán đổi.

+ Thuật toán sắp xếp chọn lựa chọn phần tử nhỏ nhất từ danh sách và đặt nó ở vị trí đầu tiên. Sau đó, nó chọn phần tử nhỏ nhất thứ hai và đặt nó ở vị trí thứ hai, và tiếp tục như vậy cho đến khi danh sách được sắp xếp hoàn toàn.

- Hiệu suất: Thuật toán sắp xếp nổi bọt thường sẽ hiệu quả hơn thuật toán sắp xếp chọn đối với danh sách nhỏ hoặc đã gần sắp xếp. Tuy nhiên thì cả 2 đều không thể hoạt động tốt với danh sách lớn vì phải thực hiện nhiều lần lặp.

Câu 4: Trong thuật toán sắp xếp chọn, khi nào không cần thực hiện thao tác “Đổi chỗ số lớn nhất tìm được cho số đầu tiên” mà kết quả sắp xếp vẫn đúng?

Trả lời:

Ta không cần thay đổi vị trí khi vị trí đó đã là số lớn nhất hoặc bé nhất trong dãy còn lại thì không cần phải thay đổi vị trí.

Câu 5: Trong thuật toán sắp xếp nổi bọt, khi nào hai phần từ liền kề được đổi chổ?

Trả lời:

Nếu số ở vị trí thứ nhất > số ở vị trí thứ hai, thì đổi chỗ 2 số với nhau đối với sắp xếp tăng dần.

Nếu số ở vị trí thứ nhất < số ở vị trí thứ hai, thì đổi chỗ 2 số với nhau đối với sắp xếp giảm dần.

III, VẬN DỤNG (6 CÂU)

Câu 1: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

Trả lời:

Câu 2: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

Trả lời:

Câu 3: Nếu sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số 8, 22, 7, 19, 5 theo thứ tự tăng dần thì số lần thực hiện thao tác hoán đổi giá trị trong vòng lặp thứ nhất là bao nhiêu?

Trả lời:

Đáp án là 2.

Vòng lặp 1:

| 8 | 22 | 7 | 19 | 5 | → lần 1: | 7 | 22 | 8 | 19 | 5 | → lần 2: | 5 | 22 | 7 | 19 | 8 |

Câu 4: Danh sách tên của các bạn trong tổ gồm Tiến, Vân, Phương, Bình, Anh, Hùng hiện đang được sắp xếp theo thứ tự chỗ ngồi. Hãy sắp xếp lại danh sách theo vần a, b, c các chữ cái bắt đầu của tên các bạn bằng thuật toán sắp xếp chọn. Ghi kết quả của các vòng lặp vào bảng sau đây (ví dụ như dòng 1).

Trả lời:

Câu 5: Em hãy sử dụng thuật toán sắp xếp chọn để sắp xếp bốn thành viên trong gia đình bạn Hải (bao gồm: bố, mẹ, Hải và em gái) (như hình minh họa dưới) theo thứ tự tăng dẫn của chiều cao.

Trả lời:

Vòng lặp thứ nhất: Em gái là người thấp nhất nên đổi chỗ em gái với bố. Thứ tự mới bây giờ là em gái, bố, mẹ, Hải.

Vòng lặp thứ hai: Hải là người thấp nhất trong dãy còn lại nên Hải đổi chỗ với bố. Thứ tự mới bây giờ là em gái, Hải, mẹ, bố.

Vòng lặp thứ ba: Mẹ ở đúng vị trí nên thứ tự sắp xếp đã đúng.

Câu 6: Hãy sử dụng các thuật toán sắp xếp đã học để thực hiện sắp xếp danh sách các thành viên trong gia đình em theo thứ tự tháng sinh không giảm rồi tiếp tục sắp xếp theo ngày sinh không giảm đối với những người cùng tháng sinh (theo mẫu dưới đây).

Trả lời:

*Hướng dẫn: Lựa chọn 2 thuật toán sắp xếp khác nhau cho việc sắp xếp danh sách theo ngày sinh và theo tháng sinh. Sau khi sắp xếp theo tháng sinh, toàn bộ danh sách sẽ hình thành các đoạn danh sách con các thành viên có cùng trong tháng sinh. Tiếp tục sắp xếp các danh sách con đó theo ngày sinh để hoàn thành công việc được giao.

IV. VẬN DỤNG CAO (2 CÂU)

Câu 1: Bài tập thực hành:

Em hãy ghi lại kết quả điểm học tập môn Tin học của các bạn trong tổ. Thực hiện thuật toán sắp xếp chọn hoặc sắp xếp nổi bọt để sắp xếp điểm theo thứ tự giảm dần. Dựa trên kết quả sắp xếp, hãy cho biết danh sách tên các bạn tương ứng theo kết quả sắp xếp đó.

Trả lời:

- Gợi ý cách làm:

- 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:

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

Câu 2: Hãy mô phỏng thuật toán sắp xếp nổi bọt cho một dãy số nguyên tùy chọn, không ít hơn 5 phần tử. Sau bao nhiêu lượt đi từ đầu đến cuối dãy để so sánh và đổi chỗ thì thuật toán kết thúc? Tổng số có bao nhiêu lần đổi chỗ hai phần tử liền kề?

Trả lời:

Ta có dãy số: 5, 2, 4, 1, 3. Sắp xếp giảm dần.

Bước 1. So sánh số 5 và 2. Ta thấy số 5 lớn hơn 2. Nên ta giữ nguyên kết quả. Dãy số sau khi đổi: 5, 2, 4, 1, 3.

Bước 2. So sánh số 2 và 4. Ta thấy số 4 lớn hơn 2 và ta tiến hành đổi chỗ số 4 và 2. Dãy số sau khi đổi: 5, 4, 2, 1, 3.

Bước 3. So sánh số 2 và 1. Ta thấy số 2 lớn hơn 1, ta giữ nguyên dãy số: 5, 4, 2, 1, 3.

Bước 4. So sánh số 1 và 3, ta thấy số 3 lớn hơn số 1, ta tiến hành đổi chỗ số 3 và số 1. Dãy số sau khi đổi: 5, 4, 2, 3, 1.

Bước 5. Tiến hành duyệt dãy số một lần nữa để chắc chắn dãy số đã được sắp xếp giảm dần. So sánh số 5 và 4, số 5 lớn hơn 4 giữ nguyên, dãy thu được: 5, 4, 2, 3, 1.

Bước 6. So sánh số 4 và 2, số 4 lớn hơn 2 giữ nguyên.

Bước 7. So sánh số 2 và 3, số 3 lớn hơn số 2, ta tiến hành đổi vị trí số 2 và 3. Dãy số thu được: 5, 4, 3, 2, 1.

Bước 8. So sánh số 2 và 1, số 2 lớn hơn số 1, nên ta giữ nguyên.

Ta sẽ đi tám lượt đi thì thuật toán mới kết thúc.