Lời giải bài tập Tin học lớp 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 sách Cánh diều hay, ngắn gọn sẽ giúp học sinh dễ dàng trả lời câu hỏi Tin học 7 Bài 5 từ đó học tốt môn Tin 7.

Giải bài tập Tin học lớp 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

Luyện tập 1 trang 90 Tin học lớp 7: Cho dãy số ban đầu

Hãy mô phỏng thuật toán tìm kiếm tuần tự một số trong dãy số bằng cách trình bày diễn biến các bước thực hiện dưới dạng bảng.

1) Tìm x = 5.

2) Tìm x = 6.

Trả lời:

1) Đối với bài này ta sẽ sử dụng thuật toán tìm kiếm tuần tự để trình bày.

Bước 1. So sánh số ở đầu dãy với x. Vì a₁ = 8 khác x nên chuyển sang xét số tiếp theo a₂ trong dãy.

Bước 2. So sánh số ở đầu dãy với x. Vì a₂ = 17 khác x nên chuyển sang xét số tiếp theo a₃ trong dãy.

Bước 3. So sánh số ở đầu dãy với x. Vì a₃ = 23 khác x nên chuyển sang xét số tiếp theo a₄ trong dãy.

Bước 4. So sánh số ở đầu dãy với x. Vì a₄ = 1 khác x nên chuyển sang xét số tiếp theo a₅ trong dãy.

Bước 5. So sánh số ở đầu dãy với x. Vì a₅ = 12 khác x nên chuyển sang xét số tiếp theo a₆ trong dãy.

Bước 6. So sánh số ở đầu dãy với x. Vì a₆ = 7 khác x nên chuyển sang xét số tiếp theo a₇ trong dãy.

Bước 7. So sánh số ở đầu dãy với x. Vì a₇ = 5 bằng x. Kết luận tìm thấy x ở vị trí thứ 7 trong dãy, kết thúc thuật toán.

2) Đối với bài này ta sẽ sử dụng thuật toán tìm kiếm tuần tự để trình bày.

Bước 1. So sánh số ở đầu dãy với x. Vì a₁ = 8 khác x nên chuyển sang xét số tiếp theo a₂ trong dãy.

Bước 2. So sánh số ở đầu dãy với x. Vì a₂ = 17 khác x nên chuyển sang xét số tiếp theo a₃ trong dãy.

Bước 3. So sánh số ở đầu dãy với x. Vì a₃ = 23 khác x nên chuyển sang xét số tiếp theo a₄ trong dãy.

Bước 4. So sánh số ở đầu dãy với x. Vì a₄ = 1 khác x nên chuyển sang xét số tiếp theo a₅ trong dãy.

Bước 5. So sánh số ở đầu dãy với x. Vì a₅ = 12 khác x nên chuyển sang xét số tiếp theo a₆ trong dãy.

Bước 6. So sánh số ở đầu dãy với x. Vì a₆ = 7 khác x nên chuyển sang xét số tiếp theo a₇ trong dãy.

Bước 7. So sánh số ở đầu dãy với x. Vì a₇ = 5 khác x nên chuyển sang xét số tiếp theo a₈ trong dãy.

Bước 8. So sánh số ở đầu dãy với x. Vì a₈ = 1 khác x nên chuyển sang xét số tiếp theo a₉ trong dãy.

Bước 9. So sánh số ở đầu dãy với x. Vì a₉ = 13 khác x nên chuyển sang xét số tiếp theo a₁₀ trong dãy.

Bước 10. So sánh số ở đầu dãy với x. Vì a₁₀ = 10 khác x, ta đã duyệt đến cuối dãy những không tìm thấy x = 6.

Kết luận: Không tìm thấy phần tử x = 6.

Luyện tập 2 trang 90 Tin học lớp 7: Cho dãy số ban đầu như trong Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp chọn để sắp xếp dãy số theo chiều không tăng

Trả lời:

Luyện tập 3 trang 90 Tin học lớp 7: Cho dãy số ban đầu như trong Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng

Trả lời:

Luyện tập 4 trang 90 Tin học lớp 7: Hãy mô phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự là kết quả của Bài 2 và Bài 3

1) Tìm x = 5.

2) Tìm x = 6.

Trả lời:

1) x = 5

Bước 1. Chia đôi phạm vi tìm kiếm từ đầu dãy a₁ đến a₁₀.

Bước 2. Lấy a₅ là vị trí cần chia đôi. Vì a₅ > x. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a₁ đến a₅ chắc chắn sẽ không chứa x cần tìm. Kết quả: Tìm thấy số x tại vị trí a₈.

Bước 3. Lấy a₈ là vị trí cần chia đôi. Khi ta chia đôi ở a₈ ta thấy vị trí số x.

2) x = 6

Bước 1. Chia đôi phạm vi tìm kiếm từ đầu dãy a₁ đến a₁₀.

Bước 2. Lấy a₅ là vị trí cần chia đôi. Vì a₅ > x. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a₁ đến a₅ chắc chắn sẽ không chứa x cần tìm.

Bước 3. Lấy a₈ là vị trí cần chia đôi. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a₈ đến a₁₀ chắc chắn sẽ không chứa x cần tìm. Khi đó chỉ còn vị trí a₆ và a₇, thì ta kiểm tra không có số x cần tìm. Kết quả: Không tìm thấy số x.

Vận dụng trang 90 Tin học lớp 7: Nếu được yêu cầu sắp xếp một dãy số, em lựa chọn thuật toán sắp xếp chọn hay sắp xếp nổi bọt? Giải thích tại sao

Trả lời:

Em sẽ lựa chọn thuật toán sắp xếp nổi bọt vì sắp xếp chọn hay nổi bọt đều như nhau, đều dùng phép so sánh để đưa ra kết quả lớn nhất và đổi chỗ vị trí với nhau. Nhưng khi dùng sắp xếp nổi bọt thì em thấy bước cuối cùng sẽ duyệt mảng lần nữa sẽ chắc chắn là mảng đó đã được sắp xếp theo thứ tự tăng hoặc giảm.

Xem thêm các bài giải SGK Tin học lớp 7 Cánh diều hay, chi tiết khác:

Bài 1: Tìm kiếm tuần tự

Bài 2: Tìm kiếm nhị phân

Bài 3: Sắp xếp chọn

Bài 4: Sắp xếp nổi bọt

Bài 5 : Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp