Câu hỏi tự luận tin học 7 cánh diều Chủ đề F Bài 1: Tìm kiếm tuần tự

BÀI 1: TÌM KIẾM TUẦN TỰ (15 CÂU)

I. NHẬN BIẾT (3 CÂU)

Câu 1: 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 xuất phát tìm kiếm từ đầu dãy, nếu số ở đầu dãy không phải là số cần tìm thì chuyển sang số tiếp theo trong dãy xem có phải số cần tìm không. Cứ như thế cho đến khi tìm thấy hoặc đã xét hết dãy.

Câu 2: Hãy mô tả thuật toán tìm kiếm tuần tự.

Trả lời:

Bước 1: Số đang xét là số ở đầu dãy.

Bước 2: Lặp khi (chưa xét hết dãy số)

Nếu Số đang xét khác x: Chuyển đến xét số tiếp theo trong dãy.

Trái lại: Thông báo vị trí tìm thấy x và kết thúc thuật toán.

Hết nhánh.

Hết lặp.

Bước 3: Thông báo không tìm thấy x và kết thúc thuật toán.

Câu 3: Bài toán tìm kiếm chia thành mấy loại? Hãy nêu rõ.

Trả lời:

Bài toán tìm kiếm chia làm 2 loại:

- Tìm kiếm trong dãy không sắp thứ tự.

- Tìm kiếm trong dãy đã sắp thứ tự.

II. THÔNG HIỂU (6 CÂU)

Câu 1: Thuật toán tìm kiếm tuần tự có yêu cầu dãy cần tìm phải được sắp xếp thứ tự thì mới có thể thực hiện được không?

Trả lời:

Thuật toán tìm kiếm tuần tự không yêu cầu dãy cần tìm phải được sắp xếp thứ tự. Thuật toán sẽ tìm kiếm lần lượt từ đầu dãy đến khi tìm được hoặc là đến cuối dãy nên không cần dãy phải sắp xếp theo trình tự.

Câu 2: Em có cách nào khác để giải bài toán tìm kiếm trong dãy không sắp thứ tự không? Tại sao?

Trả lời:

Em có cách tìm kiếm tuần tự trong dãy không sắp thứ tự. Vì khi dãy không có thứ tự thì phải tìm kiếm tuần tự để đảm bảo không bỏ sót, cho đến khi tìm thấy hoặc hết dãy và không tìm thấy.

Câu 3: Có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp thứ tự không? Tại sao?

Trả lời:

Ta vẫn có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp thứ tự. Vì khi đã sắp xếp tuần tự ta sẽ nhanh chóng tìm thấy kết quả khi áp dụng thuật toán tìm kiếm tuần tự.

Câu 4: Hai khả năng xảy ra khi kết thúc tìm kiếm tuần tự là gì?

Trả lời:

Khả năng thứ 1: Tìm thấy kết quả.

Khả năng thứ 2: Không tìm thấy kết quả.

Câu 5: Trả lời các câu sau:

1, Khi nào thì việc tìm kiếm tuần tự kết thúc ở giữa chừng của dãy?

2, Khi nào thì việc tìm kiếm tuần tự dò tìm đến phần từ cuối dãy?

Trả lời:

1, Khi đã tìm thấy kết quả thì tìm kiếm tuần tự kết thúc ở giữa.

2, Khi chưa tìm thấy kết quả thì tìm tuần tự sẽ dò tìm đến phần tử cuối dãy. Nếu đến cuối dãy mà vẫn chưa tìm được kết quả thì sẽ trả về không tìm thấy. Còn ngược lại nếu tìm thấy kết quả ở cuối dãy sẽ trả về kết quả.

Câu 6: Hãy cho biết mỗi khẳng định sau đây là đúng hay sai và giải thích lí do:

Nếu trong dãy có nhiều số bằng x thì thuật toán tìm kiếm tuần tự:

1) Tìm thấy tất cả các số đó.

2) Tìm thấy số đầu tiên trong dãy bằng x.

3) Tìm thấy số cuối cùng trong dãy bằng x.

Trả lời:

1) Sai. Vì thuật toán dừng ngay khi tìm thấy một số bằng x mà không tiếp tục kiểm tra thêm.

2) Đúng. Thuật toán dừng ngay khi tìm thấy một số bằng x nên đó là số đầu tiên trong dãy bằng x.

3) Sai. Vì 2) và 3) không thể cùng đúng nếu như có nhiều hơn một số trong dãy bằng x.

III, VẬN DỤNG (5 CÂU)

Câu 1: Thực hiện các yêu cầu sau:

1) Nêu một bài toán thực tế dẫn đến bài toán tìm kiếm.

2) Nêu một bài toán thực tế dẫn đến bài toán tìm kiếm trong dãy đã sắp thứ tự.

Trả lời:

1) Nhân viên lễ tân khách sạn tìm một chìa khóa phòng của một phòng trong khách sạn để đưa cho khách.

2) Trong bảng kết quả một cuộc thi, tìm họ tên và kết quả thi của một thí sinh khi biết số báo danh của thí sinh đó.

Câu 2: Cho danh sách các số [1, 4, 6, 7, 8, 10].

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 số 7.

Trả lời:

Gọi số phải tìm là x (x = 7):

- Bước 1. So sánh số ở vị trí thứ nhất trong dãy với x, vì 1 ≠ x nên chuyển sang xét số tiếp theo trong dãy.

- Bước 2. So sánh số ở vị trí thứ hai trong dãy với x, vì 4 ≠ x nên chuyển sang xét số tiếp theo trong dãy.

- Bước 3. So sánh số ở vị trí thứ ba trong dãy với x, vì 6 ≠ x nên chuyển sang xét số tiếp theo trong dãy.

- Bước 4. So sánh số ở vị trí thứ tư trong dãy với x, vì 7 = x nên kết luận: Tìm thấy x ở vị trí thứ tư trong dãy. Kết thúc thuật toán.

=> Thuật toán tìm kiếm tuần tự cần thực hiện 4 bước để tìm thấy số 7.

Câu 3: Cho dãy số:

Em hãy thể hiện từng bước của thuật toán giải bài toán “Tìm xem số 45 có trong dãy này không? Nếu có thì nằm ở vị trí nào?”.

Trả lời:

Gọi số phải tìm là x (x = 45):

- Bước 1. So sánh số ở đầu dãy với x, vì a1 = 27 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy.

- Bước 2. So sánh số đang xét với x, vì a2 = 63 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy.

- Bước 3. So sánh số đang xét với x, vì a3 = 12 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy.

- Bước 4. So sánh số đang xét với x, vì a4 = 59 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy.

- Bước 5. So sánh số đang xét với x, vì a5 = 67 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy.

- Bước 6. So sánh số đang xét với x, vì a6 = 45 = x. Kết luận: Tìm thấy x ở vị trí a6 trong dãy. Kết thúc thuật toán.

Nếu trong dãy vẫn còn số 45 thì ta thực hiện tìm kiếm tương tự để lấy số 45 ở vị trí tiếp theo. Nếu hết thì ta sẽ dừng thuật toán.

Vậy số 45 có nằm trong dãy cho trước. Số 45 nằm ở vị trí a6.

Câu 4: 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 5: 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à đ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.

IV. VẬN DỤNG CAO (1 CÂU)

Câu 1: Bài tập 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 mặt hàng và đơn giá của mỗi mặt hàng. Sau đó thực hiện mặt hàng mà em thích nhất và thuật toán tìm kiếm tuần tự để tìm kiếm một mặt hàng đó.

Trả lời:

- Gợi ý cách làm:

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

Bước 2: Chỉ ra tên một mặt hàng mà em thích nhất.

Bước 3: Lập 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 tên mặt hàng mà em thích nhất trong danh sách

Ví dụ em thích Bàn cờ vua.

=> Lập bảng liệt kê các bước.