Tin học lớp 7 Bài 3: Sắp xếp chọn
A. Lý thuyết Tin học 7 Bài 3: Sắp xếp chọn
1. Ý tưởng sắp xếp bằng cách chọn dần
Ý tưởng giải quyết bài toán được thể hiện qua ví dụ sau:
Ví dụ: Giả sử cần đổi chỗ các số hạng trong dãy số 55, 19, 42, 94, 18, 67 để tạo ra được dãy có thứ tự giảm dần.
Bước 1. Số lớn nhất trong dãy số (94) cần được chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗ 94 và 55, dãy còn lại là: 19, 42, 55, 18, 67.
Bước 2. Số lớn nhất trong dãy là 67 chuyển về đầu dãy này, do đó đổi chỗ 67 với 19, dãy còn lại chưa được sắp xếp là 42, 55, 18, 19.
Tiếp tục lặp lại việc “Chọn số lớn nhất và đổi chỗ cho nói với số đứng đầu dãy”, cho đến khi hết dãy ban đầu.
Hình 3.1: Minh họa ý tưởng sắp xếp bằng cách chọn dần
2. Thuật toán sắp xếp chọn
Bài toán sắp xếp đặt ra như sau:
Đầu vào: Dãy số a1, a2, …, an gọi là dãy (a).
Đầu ra: Dãy số gồm các dãy số (a) những thứ tự giảm dần.
Thuật toán gồm một vòng lặp n – 1 lần, mỗi lần lặp nhằm đưa số của dãy vào đúng vị trí mong muốn.
Hình 3.2: Một mô tả thuật toán sắp xếp chọn
Trong các bước trên có yêu cầu tìm số lớn nhất trong dãy số cho trước (a).
Các bước để tìm được số lớn nhất của một dãy số nằm ở vị trí nào:
Bước 1. Tạm ghi nhận vị trí của số lớn nhất là 1.
Hình 3.3: Minh họa cách tìm số lớn nhất trong dãy số
Bước 2. So sánh a2 với số lớn nhất, nếu a2 lớn hơn số lớn nhất thì ghi nhận lại vị trị số lớn nhất là 2.
Cứ tiếp tục như vậy, đến khi so sánh xong an với số lớn nhất và ghi nhận lại vị trí của số lớn nhất thì số lớn nhất chính là số lớn nhất trong toàn bộ dãy và tìm được vị trí m của số lớn nhất trong dãy.
3. Bài toán sắp xếp
Sắp xếp là bài toán cơ sở trong tin học. Duy trì dữ liệu được sắp xếp đúng thứ tự sẽ làm giảm đáng kể thời gian tìm kiếm dữ liệu.
Khi phát biểu bài toán cần xác định rõ:
– Dãy đầu vào: Sắp xếp những gì?
– Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng dần hay giảm dần?
Ví dụ: Sắp xếp danh sách kết quả điểm kiểm tra môn Tin học theo thứ tự từ cao xuống thấp là bài toán sắp xếp. Tiêu chí là điểm kiểm tra theo thứ tự giảm dần.
B. Bài tập trắc nghiệm Tin học 7 Bài 3: Sắp xếp chọn
Câu 1. Cho dãy số 2,5,4,9,3,7. Sắp xếp dãy số theo thứ tự giảm dần theo cách chọn dần thì sau bước thứ nhất ta được dãy số:
A. 9,5,4,2,3,7
B. 9,7,5,4,3,2
C. 9,5,4,2,3,7
D. 2,5,4,9,3,7
Hướng dẫn giải
Đáp án đúng là: A
Bước 1: Số lớn nhất trong dãy là số 9 được chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗi số 9 với số 2.
→ Sau bước này ta có dãy 9,5,4,2,3,7
Câu 2. Cho dãy số 2,5,4,9,3,7. Sắp xếp dãy số theo thứ tự giảm dần theo cách chọn dần thì sau khi sắp xếp ta được dãy số:
A. 9,5,4,2,3,7
B. 9,7,5,4,3,2
C. 9,5,4,2,3,7
D. 2,5,4,9,3,7
Hướng dẫn giải
Đáp án đúng là: B
Sau khi sắp xếp theo chiều giảm dần ta có dãy số: 9,7,5,4,3,2
Câu 3. Cho dãy số 3,5,2,8. Sắp xếp dãy theo chiều giảm dần bằng cách chọn dần được minh họa theo bảng:
A. 
B. 
C. 
D. 
Hướng dẫn giải
Đáp án đúng là: B
Cho dãy số 3,5,2,8. Sắp xếp dãy theo chiều giảm dần bằng cách chọn dần được minh họa theo bảng:
Câu 4. Cho dãy số 3, 5, 2, 8, 9. Sắp xếp dãy theo chiều giảm dần bằng cách chọn dần gồm một vòng lặp có số lần lặp là:
A.4
B.5
C.3
D.2
Hướng dẫn giải
Đáp án đúng là:A
Cho dãy số 3,5,2,8,9. Sắp xếp dãy theo chiều giảm dần bằng cách chọn dần gồm một vòng lặp có n–1=5–1=4 lần lặp.
Câu 5. Để tìm số lớn nhất của dãy 3,7, 9,2,1, nằm ở vị trí nào ở bước 1 tạm thời ghi nhận vị trí của số lớn nhất là vị trí của số:
A. 9
B. 7
C. 3
D. 1
Hướng dẫn giải
Đáp án đúng là: C
Để tìm số lớn nhất của dãy 3,7,9,2 nằm ở vị trí nào ở bước 1 tạm thời ghi nhận vị trí của số lớn nhất là 1- là vị trí của số 3.
Câu 6. Sắp xếp chọn dần là:
A. Chọn ra những phần tử chưa sắp xếp còn lại và xếp vào đầu dãy đó.
B.Chọn phần tử lớn nhất trong dãy chưa sắp xếp còn lại và xếp vào đầu dãy đó.
C. Chọn ra các phần tử dương.
D. Chọn ra các phần tử âm.
Hướng dẫn giải
Đáp án đúng là: B
Sắp xếp chọn dần là: Chọn phần tử lớn nhất trong dãy chưa sắp xếp còn lại và xếp vào đầu dãy đó.
Câu 7. Trong bài toán sắp xếp giảm dần dãy số 11, 70, 20, 39, 80, 52, 41, 5. Ở bước đầu tiên của sắp xếp chọn ta cần đổi chỗ phần tử 80 cho phần tử:
A. 11
B. 70
C. 5
D. 39
Hướng dẫn giải
Đáp án đúng là: A
Số lớn nhất trong dãy số (80) cần đươc chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗ 80 với 11.
Câu 8. Trong mỗi bước của thuật toán sắp xếp chọn theo thứ tự giảm dần ta cần tìm:
A. Phần tử âm lớn nhất.
B. Phần tử nhỏ nhất.
C. Phần tử lớn nhất.
D. Phần tử bằng 0.
Hướng dẫn giải
Đáp án đúng là: C
Trong mỗi bước của thuật toán sắp xếp chọn theo thứ tự giảm dần ta cần tìm phần tử lớn nhất.
Câu 9. Trong mỗi bước của thuật toán sắp xếp chọn theo thứ tự tăng dần ta cần tìm:
A. Phần tử âm lớn nhất.
B. Phần tử nhỏ nhất
C. Phần tử lớn nhất.
D. Phần tử bằng 0.
Hướng dẫn giải
Đáp án đúng là: B
Trong mỗi bước của thuật toán sắp xếp chọn theo thứ tự tăng dần ta cần tìm phần tử nhỏ nhất.
Câu 10. Cho một dãy số a1,a2, …, an. Các bước để tìm được số lớn nhất của một dãy số nằm ở vị trí nào là:
A. So sánh a2 với số lớn nhất, nếu a2 lớn hơn số lớn nhất thì ghi nhận lại vị trí số lớn nhất là 2. Cứ tiếp tục như vậy cho đến khi so sánh xong an với số lớn nhất và ghi nhận lại vị trí của số lớn nhất.
B. Ghi nhận vị trí cuối cùng là vị trí lớn nhất.
C. Vị trí đầu tiên chính là vị trí của số lớn nhất.
D. Bước 1: Tạm thời ghi nhận vị trí của số lớn nhất là 1.
Bước 2: So sánh a2 với số lớn nhất, nếu a2 lớn hơn số lớn nhất thì ghi nhận lại vị trí số lớn nhất là 2. Cứ tiếp tục như vậy cho đến khi so sánh xong an với số lớn nhất và ghi nhận lại vị trí của số lớn nhất.
Hướng dẫn giải
Đáp án đúng là: D
Các bước để tìm được số lớn nhất của một dãy số nằm ở vị trí nào là:
Bước 1: Tạm thời ghi nhận vị trí của số lớn nhất là 1.
Bước 2: So sánh a2 với số lớn nhất, nếu a2 lớn hơn số lớn nhất thì ghi nhận lại vị trí số lớn nhất là 2. Cứ tiếp tục như vậy cho đến khi so sánh xong an với số lớn nhất và ghi nhận lại vị trí của số lớn nhất.
Câu 11. Các bước để tìm vị trí số lớn nhất của dãy 3,7,9,2 là:
A. 
B. 
C. 
D. 
Hướng dẫn giải
Đáp án đúng là: B
Các bước để tìm vị trí số lớn nhất của dãy 3,7,9,2 là:
Câu 12. Để tìm vị trí số lớn nhất của dãy 3, 7, 9, 2 ta có … bước so sánh:
A.2
B.3
C.4
D.5
Hướng dẫn giải
Đáp án đúng là: B
Ta có 3 lần so sánh
Câu 13. Trong các bài toán sau, đâu là bài toán sắp xếp:
A. Sắp xếp bảng điểm môn tin của lớp 7A theo thứ tự tăng dần.
B. Tìm ra bạn có điểm cao nhất trong bảng điểm môn tin của lớp 7A.
C. Sắp xếp bảng điểm môn tin của lớp 7A theo thứ tự giảm dần.
D.Cả A và C
Hướng dẫn giải
Đáp án đúng là: D
Sắp xếp bảng điểm môn tin theo chiều tăng dần hay giảm dần đều là bài toán sắp xếp.
Câu 14. Khẳng định nào sau đây là đúng khi nói về bài toán sắp xếp?
A. Bài toán sắp xếp có mô hình chung là: Đổi chỗ các phần tử trong dãy để dãy có thứ tự tăng dần hoặc giảm dần.
B. Bài toán sắp xếp có mô hình chung là: Tìm ra phần tử lớn nhất trong dãy.
C. Bài toán sắp xếp có mô hình chung là: Tìm ra phần tử nhỏ nhất trong dãy.
D. Bài toán sắp xếp có mô hình chung là: Đổi chỗ phần tử lớn nhất với phần tử nhỏ nhất.
Hướng dẫn giải
Đáp án đúng là: A
Bài toán sắp xếp có mô hình chung là: Đổi chỗ các phần tử trong dãy để dãy có thứ tự tăng dần hoặc giảm dần.
Câu 15. Khi phát biểu bài toán sắp xếp cần xác định rõ:
A. Thứ tự tăng dần hay giảm dần?
B. Sắp xếp những gì?
C. Dãy đầu vào. Sắp xếp những gì?
Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng dần hay giảm dần?
D. Dãy đầu vào là gì?
Hướng dẫn giải
Đáp án đúng là: C
Khi phát biểu bài toán sắp xếp cần xác định rõ:
– Dãy đầu vào. Sắp xếp những gì?
– Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng dần hay giảm dần?
Xem thêm các bài tóm tắt lý thuyết Tin học 7 Cánh diều hay, chi tiết khác:
Lý thuyết Tin học 7 Bài 1: Tìm kiếm tuần tự
Lý thuyết Tin học 7 Bài 2: Tìm kiếm nhị phân
Lý thuyết Tin học 7 Bài 3: Sắp xếp chọn
Lý thuyết Tin học 7 Bài 4: Sắp xếp nổi bọt
Lý thuyết Tin học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp