ÔN TẬP CHỦ ĐỀ 5: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH (PHẦN 2 - 20 CÂU)

Câu 1: Điều gì xảy ra khi thuật toán tìm kiếm tuần tự không tìm thấy giá trị cần tìm trong danh sách?

Trả lời:

Khi thuật toán tìm kiếm tuần tự không tìm thấy giá trị tìm trong danh sách nó sẽ thông báo “Không tìm thấy” và kết thúc thuật toán.

Câu 2: Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là gì?

Trả lời:

Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là: Thuật toán tuần tự sẽ không yêu cầu danh sách cần phải được sắp xếp nhưng thuật toán tìm kiếm nhị phân cần danh sách phải được sắp xếp thì mới có thể thực hiện được.

Câu 3: 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 xét từng vị trí từ đầu đến cuối dãy, so sánh trực tiếp phần tử ở vị trí được xét với những phần tử ở phía sau nó và hoán đổi nếu chúng chưa đúng thứ tự.

Câu 4: Thuật toán tìm kiếm tuần tự là gì.

Trả lời:

Thuật toán tìm kiếm tuần tự là thuật toán thực hiện tìm lần lượt từ đầu đến cuối danh sách, chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.

Câu 5: Hãy mô tả thuật toán tìm kiếm nhị phân.

Trả lời:

Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thấy và thuật toán kết thúc.

Bước 2: Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

Bước 3: Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận “giá trị cần tìm xuất hiện tại vị trí giữa” và kết thúc.

Bước 4: Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa trước của dãy. Ngược lại, nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa sau của dãy.

Bước 5: Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1).

Câu 6: Dùng thuật toán sắp xếp nổi bọt để sắp xếp một dãy số tăng dần. Mỗi vòng lặp sẽ duyệt các phần tử từ cuối danh sách đến đầu danh sách. Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị là gì?

Trả lời:

Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị nhỏ nhất trong dãy số.

Câu 7: Em hãy nêu lợi ích của việc sử dụng thuật toán tìm kiếm tuần tự khi trong việc tìm kiếm.

Trả lời:

Lợi ích của việc sử dụng thuật toán tìm kiếm tuần tự khi trong việc tìm kiếm là:

- Thuật toán tìm kiếm tuần tự rất đơn giản và dễ hiểu. Nó dễ dàng triển khai khi sử dụng.

- Áp dụng được cho dữ liệu không được sắp xếp, nó không đòi hỏi dữ liệu phải được sắp xếp trước khi tìm kiếm.

- Trên các tập dữ liệu nhỏ, thuật toán tìm kiếm tuần tự có thể hiệu quả và nhanh chóng.

- Nếu muốn tìm kiếm một phần tử duy nhất trong tập dữ liệu và dừng lại ngay khi phần tử đó được tìm thấy thì thuật toán tìm kiếm tuần tự là rất phù hợp.

- Sử dụng thuật toán tìm kiếm tuần tự sẽ không bị lỡ những chi tiết nhỏ vì nó sẽ tìm kiếm từ đầu đến cuối trong dãy giá trị.

Câu 8: Em hãy điền các cụm từ:

[giá trị cần tìm xuất hiện ở vị trí giữa, nửa sau, “Không tìm thấy”, nửa trước]

vào chỗ chấm (...) trong các câu sau để được mô tả chính xác về thuật toán tìm kiếm nhị phân:

a) Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận … và thuật toán kết thúc.

b) Bước 2: Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

c) Bước 3: Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận … và kết thúc.

d) Bước 4: Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn … của dãy.

Ngược lại, nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn … của dãy.

e) Bước 5: Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1).

Trả lời:

a) “Không tìm thấy”

b) giá trị cần tìm xuất hiện ở vị trí giữa

c) nửa trước - nửa sau

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

Câu 10: Cho danh sách tên các thành phố [Hà Nội, Hải Phòng, Nam Định, Huế, Hồ Chí Minh].

Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu bước để tìm thấy Thành phố Nam Định.

Trả lời:

Thuật toán tìm kiếm tuần tự cần thực hiện 3 bước để tìm thấy thành phố Nam Định:

Bước 1: Tìm thấy Thành phố Hà Nội.

Bước 2: Tìm thấy Thành phố Hải Phòng.

Bước 3: Tìm thấy Thành Phố Nam Định.

Câu 11: Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.

Trả lời:

Trong thực tế trong quản lý học sinh, danh sách học sinh luôn được sắp xếp theo chữ cái đầu của tên để dễ tìm kiếm.

Câu 12: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt để sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.

Trả lời:

Câu 13: Cho danh sách học sinh sau đây:

Em hãy tạo bảng liệt kê các bước thực hiện thuật toán tìm kiếm tuần tự để tìm học sinh đầu tiên sinh vào tháng Một.

Trả lời:

Vậy Hà Minh Đức là học sinh đầu tiên trong danh sách sinh vào tháng Một. Đã tìm thấy sau 3 lần lặp.

Câu 14: Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu bước lặp để thông báo không tìm thấy số 15 trong danh sách [3, 5, 7, 11, 12, 25]?
Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí của số 11.

So sánh số 11 và số 15. Vì số 11 bé hơn số 15 nên bỏ đi nửa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí của số 12.

So sánh số 12 và số 15. Vì số 12 bé hơn số 15 nên bỏ đi nửa đầu danh sách.

Bước 3: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí của số 25.

So sánh số 25 và số 15. Vì số 25 lớn hơn số 15 nên bỏ đi nửa sau danh sách.

Bước 4: Vì danh sách đã hết giá trị nên thông báo không tìm thấy số 15 trong danh sách. Thuật toán tìm kiếm kết thúc.

Cần thực hiện 4 bước lặp để thông báo không tìm thấy số 15 trong danh sách.

Câu 15: 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 16: Cho danh sách tên các nước sau đây:

Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany

Em hãy kẻ bên dưới vào vở và điền các bước thực hiện thuật toán tìm kiếm tuần tự để tìm tên nước Vietnam trong danh sách trên (dòng 1 là ví dụ minh hoạ).

Trả lời:

Thông báo “Tìm thấy” Vietnam sau 5 lần lặp.

Câu 17: Cho danh sách tên các nước sau đây:

Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany

a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.

b) Em hãy liệt kê các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân.

Trả lời:

a) Danh sách tên các nước theo thứ tự trong bảng chữ cái: Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.

b) Các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí thứ 5

So sánh “Greenland” và “Iceland” vì “G” đứng trước “I” trong bảng chữ cái nên bỏ đi nữa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nửa sau của dãy, đó là vị trí thứ 7

So sánh Portugal và “Iceland” vì “P” đứng sau “I” trong bảng chữ cái nên bỏ đi nữa sau danh sách.

Bước 3: Xét vị trí ở giữa của dãy, đó là vị trí thứ 6

So sánh “Iceland” và “Iceland” vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 3 bước đã tìm thấy tên nước “Iceland” nên thuật toán kết thúc.

Câu 18: Hãy mô tả thuật toán sắp xếp chọn.

Trả lời:

1. Với vị trí đầu tiên, thực hiện vòng lặp như sau:

1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên.

1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên.

1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên.

2. Với vị trí thứ hai, thực hiện một vòng lặp tương tự như trên.

2.1. So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai.

2.2. Nếu phần tử được xét nhỏ hơn phần tử thứ hai thì hoán đổi nó với phần tử tại vị trí thứ hai.

2.3 Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhì được đưa về vị trí thứ hai.

3. Tương tự như trên với các vị trí thứ ba, thứ tư,… đến vị trí được vị trí cuối cùng.

4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Câu 19: Thực hành: Em hãy tìm kiếm thông tin trên internet để lập bảng danh sách khoảng 10 cuốn sách mà em yêu thích và đơn giá của mỗi cuốn sách. Sau đó thực hiện thuật toán tìm kiếm nhị phân để tìm cuốn sách mà em thích nhất trong danh sách vừa tìm được và cho biết đơn giá của cuốn sách đó.

Trả lời:

Hướng dẫn:

Bước 1. Tìm kiếm thông tin trên Internet, lập bảng danh sách khoảng 10 cuốn sách và đơn giá của mỗi cuốn sách.

Bước 2. Sắp xếp tên sách theo thứ tự của bảng chữ cái.

Bước 3. Chỉ ra tên một cuốn sách mà em thích nhất.

Bước 4. Liệt kê các bước thực hiện thuật toán tìm kiếm nhị phân đề tìm tên cuốn sách mà em thích nhất trong danh sách ở Bước 2.

Bước 5. Ghi ra đơn giá của cuốn sách tìm thấy ở Bước 4.

Câu 20: m hãy quan sát dãy gồm các số: 10, 7, 3, 13, 2, 8, 5 được thay đổi vị trí theo từng bước như hình dưới đây:

a) Em hãy cho biết dãy số được sắp xếp theo thuật toán nào?

b) Em hãy sắp xếp dãy số ban đầu theo thuật toán khác mà em đã được học. So sánh các sắp xếp của thuật toán nào nhanh hơn?

Trả lời:

a) Dãy số đã được sắp xếp theo thuật toán sắp xếp chọn.

b) Dãy số có thể sắp xếp theo thuật toán nổi bọt như sau:

Vòng lặp thứ nhất:

Vòng lặp thứ hai:

Vòng lặp thứ ba:

Vòng lặp thứ tư:

Vòng lặp thứ năm:

Vậy thuật toán sắp xếp nổi bọt sẽ cần 5 vòng lặp, trong khi đó sắp xếp theo theo thuật toán chọn sẽ cần 8 vòng lặp. Vậy thuật toán nổi bọt trong trường hợp này nhanh hơn.