Với tóm tắt lý thuyết Tin học lớp 7 Bài 14: Thuật toán sắp xếp sách Chân trời sáng tạo hay, chi tiết cùng với bài tập trắc nghiệm chọn lọc có đáp án giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học7.

Tin học lớp 7 Bài 14: Thuật toán sắp xếp

Video giải Tin học lớp 7 Bài 14: Thuật toán sắp xếp - Chân trời sáng tạo

A. Lý thuyết Tin học 7 Bài 14: Thuật toán sắp xếp

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

- Thuật toán sắp xếp nổi bọt 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ự.

- Mô tả thuật toán sắp xếp nổi bọt (áp dụng cho bài toán sắp xếp dãy tổng quá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.

+ 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.

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

+ 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.

+ 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.

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

+ 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ố đã được sắp xếp theo thứ tự tăng dần.

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

- Thuật toán sắp xếp chọ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 dãy đó.

Ví dụ:

Hình 2. Minh họa thuật toán sắp xếp nổi bọt

B. Bài tập trắc nghiệm Tin học 7 Bài 14: Thuật toán sắp xếp

Câu 1. Sau khi kết thúc vòng lặp thứ hai của thuật toán nổi bọt để sắp xếp dãy số sau theo thứ tự tăng dần, thu được dãy số là?

Dãy số ban đầu: 14, 6, 8, 3, 19

A. 14, 6, 8, 19, 3.

B. 3, 14, 6, 8, 19.

C. 3, 6, 19, 14, 8.

D. 3, 6, 14, 8, 19.

Đáp án: D

Giải thích:

Sau khi kết thúc vòng lặp thứ 2, số nhỏ nhất và số nhỏ thứ hai được sắp xếp đúng vị trí.

Câu 2. Dãy số sau là kết quả khi thực hiện vòng lặp thứ mấy khi sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số 5, 3, 8, 2, 5 theo thứ tự tăng dần?

Kết quả: 2, 5, 3, 8, 5.

A. 1.

B. 2.

C. 3.

D. 4.

Đáp án: A

Giải thích:

Sau khi kết thúc vòng lặp thứ 1, số nhỏ nhất được sắp xếp đúng vị trí.

Câu 3. Phát biểu nào không đúng khi nói về thuật toán sắp xếp chọn?

A. Thuật toán thực hiện việc chọn số lớn nhất trong dãy chưa được sắp xếp.

B. Đưa số nhỏ nhất chưa được sắp xếp về vị trí đầu tiên của dãy chưa được sắp xếp.

C. Lặp lại quá trình chọn số nhỏ nhất chưa sắp xếp và đưa về vị trí đầu tiên của dãy cho đến khi dãy chỉ còn một phần tử.

D. Thực hiện sắp xếp dãy phần tử không giảm (hoặc không tăng).

Đáp án: A

Giải thích:

- Dùng thuật toán sắp xếp chọn để sắp xếp dãy tăng dần: Thuật toán thực hiện việc chọn số nhỏ nhất trong dãy chưa được sắp xếp và đưa số này về vị trí đầu tiên của dãy chưa được sắp xếp. Lặp lại quá trình này cho đến khi dãy chưa sắp xếp chỉ còn một phần tử.

Câu 4. Dùng thuật toán sắp xếp chọn để sắp xếp dãy sau tăng dần, sau khi thực hiện bước thứ 2 ta thu được dãy số nào?

Dãy số ban đầu: 19, 16, 8, 25

A. 19, 16, 25, 8.

B. 16, 19, 25, 8.

C. 19, 25, 8, 16.

D. 8, 16, 19, 25.

Đáp án: D

Giải thích:

Sau khi kết thúc bước 2, hai số nhỏ nhất đúng vị trí, do đó chọn đáp án D.

Câu 5. Chỉ ra phương án sai:

Ý nghĩa của việc chi bài toán thành bài toán nhỏ hơn là:

A. Giúp công việc đơn giản hơn.

B. Giúp công việc dễ giải quyết hơn.

C. Làm cho công việc trở nên phức tạp hơn.

D. Giúp bài toán trở nên dễ hiểu hơn.

Đáp án: C

Giải thích:

Ý C không phải là ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn.

Câu 6. Định nghĩa sau là của thuật toán sắp xếp nào?

“Thuật toán thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp”.

A. Sắp xếp chọn.

B. Sắp xếp nổi bọt.

C. Sắp xếp chèn.

D. Sắp xếp nhanh.

Đáp án: B

Giải thích:

Thuật toán sắp xếp nổi bọt thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

Câu 7. Sau khi thực hiện vòng lặp thứ nhất của thuật toán sắp xếp nổi bọt cho dãy số sau theo thứ tự tăng dần ta thu được dãy số nào?

Dãy số ban đầu: 19, 16, 18, 15

A. 19, 16, 15, 18.

B. 16, 19, 15, 18.

C. 19, 15, 18, 16.

D. 15, 19, 16, 18.

Đáp án: D

Giải thích:

- So sánh số thứ tư với số thứ ba, vì 15 < 18, sai thứ tự nên ta đổi chỗ 2 thẻ (thẻ ghi số 15 về vị trí thứ 3)

- So sánh số thứ ba với số thứ hai, vì 15 < 16, sai thứ tự ta đổi chỗ 2 thẻ (thẻ ghi số 15 về vị trí thứ hai)

- So sánh số thứ hai với số thứ nhất, vì 15 < 19, sai thứ tự, ta đổi chỗ 2 thẻ (thẻ ghi số 15 về vị trí thứ nhất)

- Kết thúc vòng lặp số 1, số nhỏ nhất (15) đã đúng thứ tự là vị trí thứ nhất trong dãy.

Câu 8. Dãy số sau thực hiện mấy vòng lặp khi thực hiện sắp xếp nổi bọt để sắp xếp dãy theo thứ tự tăng dần?

Dãy ban đầu: 13, 14, 8, 9, 4, 5

A. 3.

B. 4.

C. 5.

D. 6.

Đáp án: B

Giải thích:

Kết thúc vòng lặp 1: 4, 13, 14, 8, 9, 5.

Kết thúc vòng lặp 2: 4, 5, 13, 14, 8, 9.

Kết thúc vòng lặp 3: 4, 5, 8, 13, 14, 9.

Kết thúc vòng lặp 4: 3, 4, 5, 8, 9, 13, 14.

Câu 9. Tìm đáp án đúng nhất khi nói về thuật toán sắp xếp nổi bọt

A. Thực hiện việc đổi chỗ 2 số liền kế trong một dãy số.

B. Thực hiện lặp lại việc đổi chỗ 2 số liền kế trong một dãy số nếu chúng bị sai thứ tự cho đến khi được sắp xếp.

C. Thực hiện so sánh số thứ nhất với các số còn lại trong dãy rồi đổi chỗ, các số còn lại tương tự cho đến khi dãy số được sắp xếp.

D. Chia nhỏ dãy số ra và sắp xếp từng phần.

Đáp án: B

Giải thích:

Thuật toán thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

Câu 10. Thuật toán sếp xếp nổi bọt thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?

A. Di chuyển số nhỏ nhất về cuối dãy số.

B. Đổi chỗ 2 số liền kề nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

C. Di chuyển số lớn nhất về đầu dãy số.

D. Cả A và C.

Đáp án: B

Giải thích:

Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử không giảm bằng cách thực hiện đổi chỗ 2 số liền kề nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

Câu 11. Cho dãy số sau: 3, 8, 4, 9, 6. Ở bước thứ nhất và thứ hai khi dùng thuật toán sắp xếp chọn cho dãy số trên theo thứ tự tăng dần, ta thực hiện đổi vị trí của số nào?

A. 3, 4.

B. 4, 9.

C. 4.

D. 3.

Đáp án: C

Giải thích:

Ở bước 1, số 3 nhỏ nhất đã đúng vị trí nên không cần đổi.

Ở bước 2, số 4 nhỏ thứ hai chưa đúng vị trí nên ta cần đổi chỗ số 4.

Câu 12. Bạn An thực hiện thuật toán sắp xếp chọn để sắp xếp dãy chữ cái “c, g, q, a, h, m” theo thứ tự tăng dần. Ở vòng lặp đầu tiên ta sẽ đổi vị trí của chữ cái nào?

A. c.

B. g.

C. q.

D. a.

Đáp án: D

Giải thích:

Ở vòng lặp đầu tiên ta sẽ đổi vị trí của chữ cái nhỏ nhất trong dãy là chữ cái a.

Câu 13. Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?

A. Đổi chỗ 2 số liền kề nhau nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

B. Di chuyển số nhỏ nhất về cuối danh sách.

C. Di chuyển số lớn nhất về đầu danh sách.

D. Cả ba đáp án trên đều sai.

Đáp án: A

Giải thích:

Thuật toán sắp xếp nổi bọt thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự số sau bé hơn số trước cho đến khi dãy thẻ số được sắp xếp theo thứ tự tăng dần.

Câu 14. Bạn An thực hiện thuật toán sắp xếp chọn để sắp xếp dãy số sau theo thứ tự tăng dần, kết thúc bước thứ 3 ta thu được dãy số nào?

Dãy số ban đầu: 64, 25, 12, 22, 11

A. 11, 25, 12, 22, 64.

B. 11, 12, 25, 22, 64.

C. 11, 12, 22, 25, 64.

D. 12, 22, 11, 25, 64.

Đáp án: C

Giải thích:

Sau khi kết thúc vòng lặp số 3, 3 số đầu tiên đúng vị trí: 11, 12, 22, 25, 64.

Câu 15. Cho dãy chưa sắp xếp sau: 20, 21, 17, 19. Kết quả sau vòng lặp 1 khi sử dụng thuật toán sắp xếp chọn để sắp xếp dãy trên theo thứ tự tăng dần?

A. 17, 20, 21, 19.

B. 17, 21, 20, 19.

C. 17, 19, 20, 21.

D. 17, 19, 21, 20.

D. Sắp xếp nhanh.

Đáp án: B

Giải thích:

Kết quả sau vòng lặp 1: 17, 21, 20, 19.

Xem thêm các bài tóm tắt lý thuyết Tin học 7 Chân trời sáng tạo hay, chi tiết khác:

Bài 10: Sử dụng hàm để tính toán

Bài 11: Tạo bài trình chiếu

Bài 12: Sử dụng ảnh minh hoạ, hiệu ứng động trong bài trình chiếu

Bài 13: Thuật toán tìm kiếm