Giải Tin Học 7 trang 72
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 72–73
Bài 14: Thuật toán tìm kiếm tuần tự
Hoạt động 1: Tìm địa chỉ
Đề bài: Em hãy kẻ Bảng 14.2 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 ra địa chỉ của khách hàng có họ tên là "Thanh Trúc".
Danh sách khách hàng (Bảng 14.1):
| TT | Họ tên | Địa chỉ |
|---|---|---|
| 1 | Nguyễn An | Xóm 1, Nghĩa Lộ, Võng Xuyên |
| 2 | Trần Bình | Xóm 3, Thư Trai |
| 3 | Hoàng Mai | Số 3, tổ 7, Phúc Hoà |
| 4 | Thanh Trúc | Xóm 2, Lục Xuân, Hoà Hưng |
| 5 | Nguyễn Hoà | Số 69 đường Ngô Quyền |
Cách giải
Bước 1: Hiểu thuật toán tìm kiếm tuần tự
- Bắt đầu từ phần tử đầu tiên trong danh sách
- So sánh lần lượt từng phần tử với giá trị cần tìm
- Nếu tìm thấy → ghi ra kết quả và kết thúc
- Nếu hết danh sách mà chưa tìm thấy → thông báo "Không tìm thấy"
Bước 2: Điền bảng theo từng lần lặp
Bảng 14.2. Các bước tìm địa chỉ khách hàng "Thanh Trúc":
| Lần lặp | Tên khách hàng | Có đúng khách hàng cần tìm không? | Có đúng là đã hết danh sách không? |
|---|---|---|---|
| 1 | Nguyễn An | Sai | Sai |
| 2 | Trần Bình | Sai | Sai |
| 3 | Hoàng Mai | Sai | Sai |
| 4 | Thanh Trúc | Đúng | — |
Bước 3: Kết luận
Đáp án: Tìm thấy khách hàng "Thanh Trúc" ở lần lặp thứ 4. Địa chỉ: Xóm 2, Lục Xuân, Hoà Hưng
Giải thích:
- Lần 1: So sánh "Nguyễn An" với "Thanh Trúc" → Sai → Chưa hết danh sách → Tiếp tục
- Lần 2: So sánh "Trần Bình" với "Thanh Trúc" → Sai → Chưa hết danh sách → Tiếp tục
- Lần 3: So sánh "Hoàng Mai" với "Thanh Trúc" → Sai → Chưa hết danh sách → Tiếp tục
- Lần 4: So sánh "Thanh Trúc" với "Thanh Trúc" → Đúng → Ghi ra địa chỉ → Kết thúc
Câu hỏi 1
Đề bài: Thuật toán tìm kiếm tuần tự thực hiện công việc gì?
A. Lưu trữ dữ liệu.
B. Sắp xếp dữ liệu theo chiều tăng dần.
C. Xử lí dữ liệu.
D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho.
Cách giải
Phân tích từng đáp án:
- A. Lưu trữ dữ liệu → Sai (đây là chức năng của bộ nhớ, không phải thuật toán tìm kiếm)
- B. Sắp xếp dữ liệu → Sai (đây là thuật toán sắp xếp, không phải tìm kiếm)
- C. Xử lí dữ liệu → Sai (quá chung chung, không đúng mục đích chính)
- D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho → Đúng
Đáp án: D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho.
Câu hỏi 2
Đề bài: Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào?
A. Sắp xếp lại dữ liệu theo thứ tự của bảng chữ cái.
B. Xem xét mục dữ liệu đầu tiên, sau đó xem xét lần lượt từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.
C. Chia nhỏ dữ liệu thành từng phần để tìm kiếm.
D. Bắt đầu tìm từ vị trí bất kì của danh sách.
Cách giải
Phân tích từng đáp án:
- A. Sắp xếp theo bảng chữ cái → Sai (tìm kiếm tuần tự không cần sắp xếp)
- B. Xem xét từ đầu, lần lượt từng mục cho đến khi tìm thấy hoặc hết danh sách → Đúng (đây chính là cách hoạt động của tìm kiếm tuần tự)
- C. Chia nhỏ dữ liệu → Sai (đây là đặc điểm của tìm kiếm nhị phân)
- D. Bắt đầu từ vị trí bất kì → Sai (tìm kiếm tuần tự luôn bắt đầu từ đầu danh sách)
Đáp án: B. Xem xét mục dữ liệu đầu tiên, sau đó xem xét lần lượt từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.
💡 Mẹo nhớ: "Tuần tự" = "Lần lượt từ đầu đến cuối" - giống như đọc sách từ trang 1!
Luyện tập
Đề bài: 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ảng 14.3 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 Iceland trong danh sách trên.
Cách giải
Bước 1: Xác định danh sách và giá trị cần tìm
- Danh sách: Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany
- Giá trị cần tìm: Iceland
- Iceland nằm ở vị trí thứ 6 trong danh sách
Bước 2: Thực hiện thuật toán tìm kiếm tuần tự
Bảng 14.3. Các bước tìm kiếm tuần tự:
| Lần lặp | Tên nước | Có đúng tên nước cần tìm không? | Có đúng là đã hết danh sách không? | Đầu ra |
|---|---|---|---|---|
| 1 | Bolivia | Sai | Sai | |
| 2 | Albania | Sai | Sai | |
| 3 | Scotland | Sai | Sai | |
| 4 | Canada | Sai | Sai | |
| 5 | Vietnam | Sai | Sai | |
| 6 | Iceland | Đúng | — | Tìm thấy Iceland ở vị trí 6 |
Giải thích chi tiết:
- Lần 1: "Bolivia" ≠ "Iceland" → Sai → Chưa hết → Tiếp tục
- Lần 2: "Albania" ≠ "Iceland" → Sai → Chưa hết → Tiếp tục
- Lần 3: "Scotland" ≠ "Iceland" → Sai → Chưa hết → Tiếp tục
- Lần 4: "Canada" ≠ "Iceland" → Sai → Chưa hết → Tiếp tục
- Lần 5: "Vietnam" ≠ "Iceland" → Sai → Chưa hết → Tiếp tục
- Lần 6: "Iceland" = "Iceland" → Đúng → Kết thúc
Đáp án: Tìm thấy "Iceland" sau 6 lần lặp, ở vị trí thứ 6 trong danh sách.
Vận dụng
Đề bài: Em hãy lập danh sách những cuốn sách mà em có. Sau đó sử dụng thuật toán tìm kiếm tuần tự để tìm một cuốn sách trong danh sách đó.
Cách giải
Bước 1: Lập danh sách sách (ví dụ minh họa)
| TT | Tên sách |
|---|---|
| 1 | Toán 7 |
| 2 | Ngữ văn 7 |
| 3 | Tiếng Anh 7 |
| 4 | Tin học 7 |
| 5 | Lịch sử 7 |
| 6 | Địa lí 7 |
Bước 2: Chọn sách cần tìm
- Giả sử cần tìm: "Tin học 7"
Bước 3: Thực hiện thuật toán tìm kiếm tuần tự
| Lần lặp | Tên sách | Có đúng sách cần tìm không? | Có đúng là đã hết danh sách không? | Kết quả |
|---|---|---|---|---|
| 1 | Toán 7 | Sai | Sai | |
| 2 | Ngữ văn 7 | Sai | Sai | |
| 3 | Tiếng Anh 7 | Sai | Sai | |
| 4 | Tin học 7 | Đúng | — | Tìm thấy ở vị trí 4 |
Kết luận: Tìm thấy sách "Tin học 7" sau 4 lần lặp, ở vị trí thứ 4 trong danh sách.
Lưu ý cho học sinh: Em hãy tự lập danh sách sách của riêng mình và chọn một cuốn sách bất kỳ để thực hành thuật toán tìm kiếm tuần tự nhé!
🎯 Ghi nhớ: - Thuật toán tìm kiếm tuần tự duyệt lần lượt từ phần tử đầu tiên đến cuối danh sách - Dừng lại khi: (1) Tìm thấy giá trị cần tìm, hoặc (2) Đã hết danh sách - Ưu điểm: Đơn giản, dễ hiểu, không cần sắp xếp danh sách trước - Nhược điểm: Chậm với danh sách dài (phải duyệt nhiều phần tử)