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

BÀI 3: SẮP XẾP CHỌN (15 CÂU)

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

Câu 1: Em hãy nêu mô hình chung của các bài toán sắp xếp.

Trả lời:

Các 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 (không giảm) hoặc giảm dần (không tăng).

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à một vòng lặp. Mỗi bước lặp nhằm đưa một số của dãy vào đúng vị trí mong muốn (tức là vị trí của nó trong dãy kết quả). Để làm được điều đó, ở mỗi bước lặp cần thực hiện chọn số lớn nhất trong dãy số còn lại chưa sắp xếp và đưa nó về đầu dãy này bằng cách đổi chỗ nó với số đứng ở đầu dãy.

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

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

a) Tìm số lớn nhất trong dãy số cần sắp xếp.

b) Đổi chỗ số lớn nhất và số ở vị trí đầu tiên cho nhau.

Hết lặp.

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

Câu 1: Hãy nêu vài ví dụ bài toán sắp xếp trong thực tế và nói rõ tiêu chi sắp xếp.

Trả lời:

Trong thực tế ta thường dùng thuật toán sắp xếp trong “Xếp hàng”, ta sẽ sắp xếp theo thứ tự tăng dần (không giảm).

Câu 2: Hãy tóm tắt bằng một câu trả lời cho câu hỏi: Thế nào là sắp xếp chọn?

Trả lời:

Sắp xếp chọn dần là một thuật toán mô phỏng cách sắp xếp: 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 3: 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 4: Trong thuật toán sắp xếp chọn, nếu thay “Tìm giá trị lớn nhất” bằng “Tìm giá trị nhỏ nhất” thì kết quả nhận được là dãy số có thứ tự ra sao?

Trả lời:

Nếu thay tìm giá trị lớn nhất bằng tìm giá trị nhỏ nhất thì dãy sẽ có thứ tự tăng dần (không giảm).

Câu 5: Sau vòng lặp thứ nhất của thuật toán sắp xếp chọn, ta sẽ nhận được dãy số mới có dạng như thế nào?

Trả lời:

Phần tử có giá trị nhỏ nhất (nếu sắp xếp theo thứ tự tăng dần) hoặc lớn nhất (nếu sắp xếp theo thứ tự giảm dần) trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.

Câu 6: Tác dụng của việc chia bài toán thành những bài toán nhỏ hơn là gì?

Trả lời:

Việc chia 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.

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

Câu 1: Trình bày diễn biến từng bước của thuật toán sắp xếp chọn cho dãy số 11, 70, 18, 39, 63, 52, 41, 5

Trả lời:

Bước 1. Số lớn nhất trong dãy số (70) cần được chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗ 70 với 11. Sau bước này, vì 94 đã ở đúng vị trí mong muốn nên tiếp theo chỉ cần quan tâm đến dãy số còn lại: 11,18, 39, 63, 52, 41, 5.

Bước 2. Số lớn nhất trong dãy số còn lại (63) cần được chuyển về đầu dãy này, do đó đổi chỗ 63 với 11. Sau bước này có thêm số 63 đã ở đúng vị trí mong muốn, dãy số còn lại chưa được sắp xếp là 18, 39, 11, 52, 41, 5.

Tiếp tục lặp lại việc “Chọn lấy số lớn nhất trong dãy số còn lại và đổi chỗ nó với số đứng đầu dãy này” cho đến khi hết dãy ban đầu.

Câu 2: 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 3: Cho dãy số sau: 15, 20, 10, 18.
Em hãy sử dụng thuật toán sắp xếp chọn để 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 | 20 | 15 | 18 | → | 10 | 15 | 20 | 18 | → | 10 | 15 | 18 | 20 |

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

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

Câu 1: Trong thuật toán sắp xếp bằng cách chọn dần, dãy đích hình thành ở đầu trái, dài thêm dần và dãy nguồn còn lại ở bên phải, ngắn đi dần. Nếu yêu cầu ngược lại, dãy đích hình thành ở đầu bên phải và dãy nguồn còn lại ở bên trái thì cần sửa lại thao tác ở các bước như thế nào.

Trả lời:

- Để dãy đích hình thành ở đầu trái thì phải đổi chỗ cho phần tử cuối dãy nguồn còn lại. Ở bước i, cuối dãy nguồn là vị trí n + 1 – i.

- Ở mỗi bước, nếu ta chọn số lớn nhất trong dãy nguồn còn lại thì kết quả sẽ là dãy tăng dần (không giảm). Nếu vẫn muốn sắp dãy giảm dần thì chọn số nhỏ nhất để đổi chỗ.

Sửa lại thao tác trong vòng lặp như sau:

a) Tìm số nhỏ nhất trong dãy nguồn còn lại {a1, a2, ……, an+1-i} gọi là amin.

b) Đổi chỗ amin cho an+1-i.