Câu hỏi tự luận tin học 7 cánh diều Chủ đề F Bài 4: Sắp xếp nổi bọt

BÀI 4: SẮP XẾP NỔI BỌT (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 nhiều lượt so sánh và đổi chỗ các cặp phần tử liền kề cho đến khi không còn bất kì cặp phần tử liền kề nào trái thứ tự mong muốn.

Câu 2: 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:

Lặp với i từ 1 đến n – 1:

          Nếu số ở vị trí thứ nhất = số ở vị trí thứ hai: giữ nguyên vị trí.

          Nếu số ở vị trí thứ nhất > số ở vị trí thứ hai: đổi chỗ 2 số với nhau.

Hết nhánh

Hết lặp.

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

Câu 1: 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.

Câu 2: Thuật toán sắp xếp nổi bọt kết thúc khi nào?

Trả lời:

Thuật toán kết thúc khi tất cả phần tử được sắp xếp theo thứ tự tăng dần hoặc giảm dần.

Câu 3: Theo em, vì sao thuật toán sắp xếp trên lại có tên là sắp xếp nổi bọt?

Trả lời:

Vì thuật toán nổi bọt hay còn gọi là sắp xếp nổi bọt hoạt động của nó giống như việc "nổi bọt" các phần tử lên trên mặt nước: các phần tử nhẹ hơn (nhỏ hơn) sẽ "nổi lên" dần dần vị trí đúng của chúng, trong khi các phần tử nặng hơn (lớn hơn) sẽ chuyển dần về vị trí phù hợp hơn trong danh sách.

Câu 4: 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 5: Dùng thuật toán sắp xếp nổi bọt để sắp xếp một dãy số tăng dần. Mỗi vòng lặp sẽ duyệt các phần tử từ cuối danh sách đến đầu danh sách. Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị là gì?

Trả lời:

Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị nhỏ nhất trong dãy số.

Câu 6: Trong thuật toán sắp xếp nổi bọt thì dấu hiệu để biết dãy chưa sắp xếp xong là gì?

Trả lời:

Dấu hiệu nhận biết dãy chưa sắp xếp xong là:

Nếu dãy chưa được sắp xếp đúng thứ tự thì trong dãy sẽ còn cặp phần tử liền kề không đúng thứ tự tăng dần hoặc giảm dần.

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

Câu 1: Em hãy chọn thuật toán sắp xếp hợp lý cho từng trường hợp sau:

a) Hoán đổi vị trí hai phần tử liên tiếp khi chúng không đúng thứ tự là thuật toán nào?

b) Tìm phần tử nhỏ nhất trong dãy và đổi chỗ phần tử này với phần tử đầu tiên của dãy chưa được sắp xếp là thuật toán nào?

Trả lời:

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

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

Câu 2: 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 3: Cho dãy số sau: 15, 20, 10, 18.
Em hãy sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số tăng dần. Mỗi vòng lặp sẽ duyệt từ phần tử cuối đến phần tử đầu tiên.

Trả lời:

| 15 | 20 | 10 | 18 | → | 10 | 15 | 20 | 18 | → | 10 | 15 | 18 | 20 |

Tổng số lần đổi vị trí phần tử là 3 lần.

Câu 4: Cho dãy số:

Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo thứ tự giảm dần (không tăng).

Trả lời:

Câu 5: Hãy trình bày diễn biến từng bước của thuật toán sắp xếp nổi bọt áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} để được dãy số tăng dần.

Trả lời:

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

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.