Bài 22: Thực hành bài toán sắp xếp

Chủ đề 6. Kĩ thuật lập trình – Bài 22: Thực hành bài toán sắp xếp – sách bài tập trang 70 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 22: Thực hành bài toán sắp xếp

Câu 22.1

Áp dụng thuật toán sắp xếp chọn cho dãy số sau:

A [4, 6, 1, 3, 10, 7]

Thứ tự các phần tử trong dãy như thế nào sau vòng lặp đầu tiên?

A. 3, 1, 4, 6, 10, 7.

C. 1, 3, 4, 6, 7, 10.

B. 1, 4, 6, 3, 10, 7.

D. 1, 6, 4, 3, 10, 7.

Trả lời:

Đáp án D. Trong thuật toán sắp xếp chọn, ở mỗi vòng lặp chúng ta sẽ chọn ra số nhỏ nhất để đưa lên đầu phần dãy chưa sắp xếp. Ở vòng lặp đầu tiên, số nhỏ nhất trong dãy là số “1”, ta đổi chỗ số “1” với phần tử đầu tiên là số “4”. Do đó, sau vòng lặp đầu tiên, thứ tự các phần tử trong dãy số là 1, 6, 4, 3, 10, 7.

Câu 22.2

Trong một số ứng dụng, chúng ta phải sắp xếp dữ liệu ngay khi chúng được thêm vào một dãy số. Ví dụ, giả sử đã có một danh sách dữ liệu đã sắp xếp và thường xuyên phải bổ sung thêm các dữ liệu mới vào danh sách. Theo em, thuật toán sắp xếp nào là phù hợp nhất với ứng dụng ở trên?

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

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

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

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Trả lời:

Đáp án B. Trong các thuật toán trên thì thuật toán sắp xếp chèn là phù hợp nhất vì ý tưởng của thuật toán là với mỗi phần tử chưa được sắp xếp, tìm và xếp phần tử đó vào đúng vị trí của nó. Với thuật toán sắp xếp chèn, ta chỉ cần tìm đúng vị trí của phần tử mới được đưa vào dãy mà không phải sắp xếp lại toàn bộ dãy như thuật toán sắp xếp chọn hoặc sắp xếp nổi bọt.

Câu 22.3

Mô tả “Thuật toán lần lượt duyệt từng cặp phần tử trong danh sách, đổi chỗ các cặp phần tử chưa đúng thứ tự” là đúng nhất với thuật toán sắp xếp nào sau đây?

A. Thuật toán sắp xếp chèn.

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

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

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Trả lời:

Đáp án C. Mô tả trên là đúng nhất với thuật toán sắp xếp nổi bọt.

Câu 22.4

Mô tả “Ở mỗi bước thuật toán lấy một phần tử ở phần chưa được sắp xếp và đưa vào đúng vị trí của nó trong phần dãy số đã được duyệt” là đúng nhất với thuật toán sắp xếp nào sau đây?

A. Thuật toán sắp xếp chèn.

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

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

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Trả lời:

Đáp án C. Mô tả trên đúng nhất với thuật toán sắp xếp chèn.

Câu 22.5

Mô tả “Ở mỗi bước lặp, thuật toán tìm kiếm phần tử lớn nhất/ nhỏ nhất trong dãy để đưa về đúng vị trí của nó” là đúng nhất với thuật toán sắp xếp nào sau đây?

A. Thuật toán sắp xếp chèn.

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

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

D. Các thuật toán ở phương án A, B, C đều không phù hợp.

Trả lời:

Đáp án B. Mô tả trên đúng nhất với thuật toán sắp xếp chọn.

Câu 22.6

Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của một thuật toán sắp xếp được mô tả như sau:

1, 4, 10, 9, 3, 7, 12, 20

1, 3, 10, 9, 4, 7, 12, 20

1, 3, 4, 9, 10, 7, 12, 20

Thuật toán sắp xếp được sử dụng là:

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

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

B. Thuật toán sắp xếp chèn.

Trả lời:

Đáp án A. Thuật toán sắp xếp chọn. Ở vòng lặp đầu tiên, ta thấy phần tử nhỏ nhất của dãy số đã ở vị trí đầu dãy. Ở vòng lặp thứ hai, trong phần dãy chưa được sắp xếp (4, 10, 9, 3, 7, 12, 20), 3 là phần tử nhỏ nhất và được đổi chỗ với phần tử đầu tiên trong phần chưa được sắp xếp (số 4). Ở vòng lặp thứ ba, 4 là phần tử nhỏ nhất trong phần chưa được sắp xếp (10, 9, 4, 7, 12, 20) và 4 được đổi chỗ với 10.

Câu 22.7

Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của thuật toán sắp xếp được mô tả như sau:

5, 8, 1, 4, 7, 10

5, 1, 8, 4, 7, 10

5, 1, 4, 8, 7, 10

Thuật toán sắp xếp được sử dụng là:

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

B. Thuật toán sắp xếp chèn.

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

Trả lời:

Đáp án C. Thuật toán sắp xếp nổi bọt. Ở vòng lặp thứ hai, ta có thể thấy phần tử thứ hai và thứ ba được đổi chỗ cho nhau (8 và 1). Ở vòng lặp thứ ba, phần tử thứ ba và thứ tư được đổi chỗ cho nhau (4 và 8). Như vậy, thuật toán tiến hành xét từng cặp số liền kề và đổi chỗ chúng nếu cần. Đây là ý tưởng của thuật toán sắp xếp nổi bọt.

Câu 22.8

Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của thuật toán sắp xếp được mô tả như sau:

5, 7, 4, 6, 9, 20, 8

4, 5, 7, 6, 9, 20, 8

4, 5, 6, 7, 9, 20, 8

Thuật toán sắp xếp được sử dụng là:

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

B. Thuật toán sắp xếp chèn.

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

Trả lời:

Đáp án B. Thuật toán sắp xếp chèn. Chúng ta có thể thấy ở vòng lặp thứ hai, phần tử thứ ba của dãy (số 4) đã được chèn vào đúng vị trí của nó (trước số 5). Tiếp theo, ở vòng lặp thứ ba, phần tử thứ tư của dãy (số 6) được chèn vào đúng vị trí của nó (giữa số 5 và số 7). Như vậy, thuật toán sắp xếp được sử dụng ở đây là thuật toán sắp xếp chèn.

Câu 22.9

Chúng ta thường thấy danh sách lớp thường được sắp xếp theo thứ tự bảng chữ cái. Cho trước một danh sách lớp chưa được sắp xếp như sau: Nam, An Cường, Sơn, Trung, Bình.

Hãy cho biết kết quả sau mỗi bước lặp với mỗi thuật toán sắp xếp nổi bọt, sắp xếp chèn và sắp xếp chọn cho đến khi danh sách được sắp xếp xong.

Trả lời:

Kết quả danh sách lớp sau hai bước lặp với các thuật toán sắp xếp như sau:

– Thuật toán sắp xếp chèn:

B1: An, Nam, Cường, Sơn, Trung, Bình

B2: An, Cường, Nam, Sơn, Trung, Bình

B3: An, Cường, Nam, Sơn, Trung, Bình

B4: An, Cường, Nam, Sơn, Trung, Bình

B5: An, Bình, Cường. Nam, Sơn, Trung

– Thuật toán sắp xếp chọn:

B1: An, Nam, Cường, Sơn, Trung, Bình

B2: An, Bình, Cường. Sơn, Trung, Nam

B3: An, Bình, Cường, Sơn, Trung, Nam
B4: An, Bình, Cường, Nam, Sơn, Trung

B5: An, Bình, Cường, Nam, Sơn, Trung

– Thuật toán sắp xếp nổi bọt:

B1:
- An, Nam, Cường, Sơn, Trung, Bình
- An, Nam, Cường, Sơn, Bình, Trung

B2: An, Nam, Cường, Bình, Sơn, Trung

B3: An, Nam, Bình, Cường, Sơn, Trung

B4: An, Bình, Nam, Cường, Sơn, Trung
B5: An, Bình, Cường, Nam, Sơn, Trung

Câu 22.10

Viết chương trình cho phép người dùng nhập các số nguyên từ bàn phím, sắp xếp các số đã được nhập theo thứ tự tăng dần và in ra màn hình dãy số đã được sắp xếp, nhập vào từ khoá ‘end’ để kết thúc chương trình. Yêu cầu ngay khi nhập xong dữ liệu thì dãy số cũng sắp xếp xong (chúng ta có thể thực hiện bằng cách mỗi khi nhập một phần tử mới, sắp xếp vào đúng vị trí của nó trong dãy số).

Trả lời:

Như đã phân tích ở Câu 22.2, thuật toán sắp xếp phù hợp nhất cho bài toán này là thuật toán sắp xếp chèn. Bài toán này có thể giải như sau:

A = []
while (True):
    tmp = input ("Hãy thêm một số: ");
    if (tmp == "end"):
        break
    else:
        tmp = int(tmp)
        A.append(tmp) #đưa số vừa nhập vào cuối dãy
        i = len(A) - 2 #bắt đầu xét số ngay trước số vừa nhập
        while i >= 0 and A[i] > tmp:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = tmp
    print("Dãy số sau khi đã sắp xếp là:", A)

Câu 22.11*

Khi sử dụng dịch vụ tìm kiếm phòng nghỉ của một số trang cung cấp dịch vụ đặt phòng trực tuyến (Agoda/Booking,…). Các hệ thống đó thường cho phép sắp xếp theo giá tăng dần hoặc giá giảm dần để người dùng tiện lựa chọn. Để thực hiện theo yêu cầu của người dùng, chương trình có thể tiến hành theo một trong các cách sau:

Cách 1: Nếu chọn “tăng dần” thi thực hiện đoạn chương trinh sắp xếp tăng dần; nếu chọn “giảm dần” thi thực hiện chương trình sắp xếp giảm dần.

Cách 2: Sử dụng kết hợp câu lệnh IF trước khi thực hiện so sánh “lớn hơn” hay “nhỏ hơn” trong vòng lặp sắp xếp.

Trả lời:

Một số ưu điểm/nhược điểm của ba cách sắp xếp như sau:

Cách 1:

Nếu khách chọn “tăng dần” thì thực hiện đoạn chương trình sắp xếp tăng dần; nếu chọn “giảm dần” thì thực hiện chương trình sắp xếp giảm dần.

Ưu điểm của phương án này là không làm gia tăng số lượng các phép toán cần thực hiện, tuy nhiên người dùng phải viết riêng hai chương trình, một cho lựa chọn “tăng dần”, một cho lựa chọn “giảm dần”.

Cách 2:

Sử dụng kết hợp câu lệnh IF trước khi thực hiện so sánh “lớn hơn” hay “nhỏ hơn” trong vòng lặp sắp xếp.

Ưu điểm của phương án này là không cần phải viết riêng hai chương trình cho hai lựa chọn sắp xếp. Tuy nhiên, phương pháp này chúng ta cần phải thực hiện khá nhiều lệnh kiểm tra điều kiện IF trước khi thực hiện lệnh so sánh “lớn hơn” hay “nhỏ hơn”.

Cách 3:

Nếu khách hàng lựa chọn sắp xếp “giảm dần” thì lấy toàn bộ các phần tử của dãy nhân với -1, sau đó vẫn áp dụng thuật toán sắp xếp tăng dần.

Ưu điểm của phương án này là không phải thay đổi chương trình sắp xếp, tuy nhiên sẽ làm gia tăng số lượng phép toán do phải nhân toàn bộ dữ liệu với -1.

Ngoài 3 cách trên, chúng ta còn có thể sử dụng một cách khác là vẫn sắp xếp dữ liệu theo thứ tự tăng dần như bình thường. Nếu người dùng chọn “tăng dần” thì khi hiển thị dữ liệu ra theo thứ tự từ đầu dãy đến cuối dãy, nếu người dùng chọn “giảm dần” thì hiển thị dữ liệu theo thứ tự từ cuối dãy đến đầu dãy.

Xem các bài giải khác: Giải Sách Bài Tập Lớp 11 Khoa Học Máy Tính Kết Nối Tri Thức Với Cuộc Sống

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech