CHỦ ĐỀ 6: KĨ THUẬT LẬP TRÌNH

BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

A. TRẮC NGHIỆM

1. NHẬN BIẾT

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

1. Sắp xếp chọn.
2. Sắp xếp nổi bọt.
3. Sắp xếp chèn.
4. Sắp xếp nhanh.

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

1. Thực hiện việc đổi chỗ 2 số liền kế trong một dãy số.
2. 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.
3. 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.
4. Chia nhỏ dãy số ra và sắp xếp từng phần.

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

1. Di chuyển số nhỏ nhất về cuối dãy số.
2. Đổ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.
3. Di chuyển số lớn nhất về đầu dãy số.
4. Cả A và C.

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

1. Đổ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.
2. Di chuyển số nhỏ nhất về cuối danh sách.
3. Di chuyển số lớn nhất về đầu danh sách.
4. Cả ba đáp án trên đều sai.

Câu 5: Ý tưởng của thuật toán sắp xếp chèn là:

1. thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy.
2. thực hiện vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n – 2 (phần tử gần cuối).
3. thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ.
4. Cả 3 đáp án trên đều sai

Câu 6: Thuật toán sắp xếp chọn là:

1. thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy.
2. thực hiện vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n – 2 (phần tử gần cuối).
3. thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ.
4. Cả 3 đáp án trên đều sai

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

1. thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy.
2. thực hiện vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n – 2 (phần tử gần cuối).
3. thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ.
4. Cả 3 đáp án trên đều sai

2. THÔNG HIỂU

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

18. 19, 16, 15, 18.
19. 16, 19, 15, 18.
20. 19, 15, 18, 16.
21. 15, 19, 16, 18.

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

3. 3.
4. 4.
5. 5.
6. 6.

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

3. 14, 6, 8, 19, 3.
4. 3, 14, 6, 8, 19.
5. 3, 6, 19, 14, 8.
6. 3, 6, 14, 8, 19.

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

1. 1.
2. 2.
3. 3.
4. 4.

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

1. 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.
2. Đư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.
3. 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ử.
4. Thực hiện sắp xếp dãy phần tử không giảm (hoặc không tăng).

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

8. 19, 16, 25, 8.
9. 16, 19, 25, 8.
10. 19, 25, 8, 16.
11. 8, 16, 19, 25.

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

1. Giúp công việc đơn giản hơn.
2. Giúp công việc dễ giải quyết hơn.
3. Làm cho công việc trở nên phức tạp hơn.
4. Giúp bài toán trở nên dễ hiểu hơn.

Câu 8: Nêu ý nghĩa thực tế của thuật toán sắp xếp chọn:

1. sắp xếp xử lý chèn phần tử đang xét vào vị trí thích hợp của dãy số đã sắp xếp phía trước sao cho dãy số vẫn là dãy sắp xếp có thứ tự.
2. so sánh hai phần tử từ đầu tới cuối
3. so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau.
4. thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Câu 9: Nêu ý nghĩa thực tế của thuật toán sắp xếp nổi bọt:

1. sắp xếp xử lý chèn phần tử đang xét vào vị trí thích hợp của dãy số đã sắp xếp phía trước sao cho dãy số vẫn là dãy sắp xếp có thứ tự.
2. so sánh hai phần tử từ đầu tới cuối
3. so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau.
4. thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Câu 10: Nêu ý nghĩa thực tế của thuật toán sắp xếp chèn:

1. sắp xếp xử lý chèn phần tử đang xét vào vị trí thích hợp của dãy số đã sắp xếp phía trước sao cho dãy số vẫn là dãy sắp xếp có thứ tự.
2. so sánh hai phần tử từ đầu tới cuối
3. so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau.
4. thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

3. VẬN DỤNG

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

4. 3, 4.
5. 4, 9.
6. 4.
7. 3.

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

1. c.
2. g.
3. q.
4. a.

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

64. 11, 25, 12, 22, 64.
65. 11, 12, 25, 22, 64.
66. 11, 12, 22, 25, 64.
67. 12, 22, 11, 25, 64.

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

19. 17, 20, 21, 19.
20. 17, 21, 20, 19.
21. 17, 19, 20, 21.
22. 17, 19, 21, 20.

Câu 5: Theo thuật toán sắp xếp chọn, sau mỗi bước thứ i thì các phần tử A[0]. A[1]..... A[i] đã được sắp xếp đúng. Đúng hay sai?

1. Đúng
2. Sai

4. VẬN DỤNG CAO

Câu 1: Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có 4 phần tử

1. Đảo giá trị 2 biến
2. Sắp xếp hoặc chèn 2 biến
3. Cả A,B đều đúng
4. Cả A,B đều sai

Câu 2: Mô phỏng chi tiết các bước lặp sắp xếp chèn dãy A = [5, 0, 4, 2, 3]

Bước 1: i = 1;//giả sử có đoạn a[0] đã được sắp xếp

Bước 2: x = a[i];

Bước 3:

Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn a[i] vào danh sách.

Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].

Bước 4: a[pos] = x;//chèn x, có đoạn a[0],…,a[i] đã được sắp.

Bước 5: i = i+1; nếu i < n -> lặp lại bước 2, ngược lại -> Dừng.

Em có nhận xét gì về các bước mô phỏng trên:

1. Hoàn tàn đồng ý
2. Bước 2 sai
3. Bước 4, 5 đúng
4. Các bước 1,2,5 là sai

 --------------- Còn tiếp ---------------