Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ

Giải Tin học 11 Bài 19: Bài toán tìm kiếm - Kết nối tri thức

Câu hỏi 3 trang 91 Tin học 11: Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.

Lời giải:

Thuật toán tìm kiếm tuần tự sẽ cần nhiều bước nhất khi phải duyệt qua toàn bộ dãy số để tìm kiếm phần tử cần tìm, tức là phần tử đó nằm ở cuối dãy hoặc không có trong dãy. Đây là trường hợp xấu nhất của thuật toán tìm kiếm tuần tự.

Ví dụ: Giả sử chúng ta cần tìm phần tử có giá trị là 100 trong dãy A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Phần tử này không có trong dãy, và thuật toán tìm kiếm tuần tự sẽ phải duyệt qua toàn bộ dãy 10 phần tử để xác nhận rằng phần tử này không có trong dãy.

Vậy, trong trường hợp xấu nhất, số lần duyệt cần thực hiện là đúng bằng số phần tử trong dãy. Trong ví dụ trên, số lần duyệt cần thực hiện là 10 lần để tìm kiếm phần tử không có trong dãy.

Lời giải bài tập Tin học 11 Bài 19: Bài toán tìm kiếm hay khác:

• Khởi động trang 89 Tin học 11: Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần ....

• Hoạt động 1 trang 89 Tin học 11: Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả năng các kết quả có thể tìm được của bài toán ....

• Câu hỏi 1 trang 90 Tin học 11: Bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số ....

• Câu hỏi 2 trang 90 Tin học 11: Bài toán tìm tất cả các trường trung học phổ thông (tên trường, địa chỉ) ở quận (huyện) em đang cư trú ....

• Hoạt động 2 trang 90 Tin học 11: Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau ....

• Câu hỏi 1 trang 91 Tin học 11: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt ....

• Câu hỏi 2 trang 91 Tin học 11: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất? ....

• Hoạt động 3 trang 91 Tin học 11: Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây ....

• Câu hỏi 1 trang 93 Tin học 11: Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34? ....

• Câu hỏi 2 trang 93 Tin học 11: Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34? ....

• Câu hỏi 3 trang 93 Tin học 11: Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa ....

• Luyện tập 1 trang 93 Tin học 11: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm ....

• Luyện tập 2 trang 93 Tin học 11: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần ....

• Vận dụng 1 trang 93 Tin học 11: Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn ....

• Vận dụng 2 trang 93 Tin học 11: Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái ....

Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay nhất, ngắn gọn khác:

• Tin học 11 Bài 20: Thực hành bài toán tìm kiếm

• Tin học 11 Bài 21: Các thuật toán sắp xếp đơn giản

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

• Tin học 11 Bài 23: Kiểm thử và đánh giá chương trình

• Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải sgk Tin học 11 Kết nối tri thức
• Giải Chuyên đề Tin học 11 Kết nối tri thức
• Giải SBT Tin học 11 Kết nối tri thức
• Giải lớp 11 Kết nối tri thức (các môn học)
• Giải lớp 11 Chân trời sáng tạo (các môn học)
• Giải lớp 11 Cánh diều (các môn học)

---