BÀI 14: THUẬT TOÁN TÌM KIẾM TUẦN TỰ (15 CÂU)

I. NHẬN BIẾT (2 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 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 2: Hãy mô tả thuật toán tìm kiếm tuần tự.

Trả lời:

Bước 1: Xét vị trí đầu tiên của danh sách.

Bước 2: Nếu giá trị của phần tử ở vị trí đang xét bằng giá trị cần tìm thì chuyển sang Bước 4. Nếu không thì chuyển đến vị trí tiếp theo.

Bước 3: Kiểm tra đã hết danh sách chưa. Nếu đã hết danh sách thì chuyển sang Bước 5. Nếu chưa thì lặp lại từ Bước 2.

Bước 4: Thông báo “Tìm thấy” và chỉ ra vị trí phần tử tìm được. Kết thúc.

Bước 5: Thông báo “Không tìm thấy”. Kết thúc.

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

Câu 1: Thuật toán tìm kiếm tuần tự yêu cầu danh sách cần tìm phải được sắp xếp không?

Trả lời:

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

Câu 2: Đ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 3: Chọn câu diễn đạt đúng hoạt động của thuật toán tìm kiếm tuần tự.

1. Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
2. Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
3. Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
4. Tìm trên danh sách bất kì, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

Trả lời:

Đáp án đúng là D.

Câu 4: Em hãy ghép mỗi nội dung ở cột A với những nội dung phù hợp ở cột B để xác định chính xác đầu vào và đầu ra của thuật toán tìm kiếm tuần tự.

Trả lời:

1-a 1-c 2-b 2-d

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

[đã hết, “Không tìm thấy”, bằng, vị trí đầu tiên, “Tìm thấy”]

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 tuần tự.

1. a) Bước 1: Xét phần tử … của danh sách.
2. b) Bước 2: Nếu giá trị của phần tử ở vị trí đang xét … giá trị cần tìm thì chuyển sang Bước 4, nếu không thì chuyển đến vị trí tiếp theo.
3. c) Bước 3: Kiểm tra đã hết danh sách chưa. Nếu … danh sách thì chuyển sang Bước 5, nếu chưa thì lặp lại từ Bước 2.
4. d) Bước 4: Trả lời … và chỉ ra vị trí phần tử tìm được; Kết thúc.
5. e) Bước 5: Trả lời …; Kết thúc.
   Trả lời:
6. a) vị trí đầu tiên
7. b) “Tìm thấy”
8. c) đã hết
9. d) bằng
10. e) “Không tìm thấy”

Câu 6: 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ị.

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

Câu 1: 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:

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:

Bước 1: Thấy số 1.

Bước 2: Thấy số 4.

Bước 3: Thấy số 6.

Bước 4: Thấy số 7.

Câu 2: 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 3: Thực hiện thuật toán tìm kiếm tuần tự để tìm số 10 trong danh sách các số [2, 6, 8, 4, 10, 12]. Đầu ra của thuật toán là ?

Trả lời:

Thực hiện thuật toán tìm kiếm tuần tự để tìm số 10:

Bước 1: Tìm thấy số 2 ở vị trí đầu tiên.

Bước 2: Tìm thấy số 6 ở vị trí thứ hai.

Bước 3: Tìm thấy số 8 ở vị trí thứ ba.

Bước 4: Tìm thấy số 4 ở vị trí thứ tư.

Bước 5: Tìm thấy số 10 ở vị trí thứ năm.

Bước 6: Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ năm của danh sách.

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à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 6: 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 đó.

Trả lời:

- Danh sách tên các sách: Toán, Ngữ Văn, Tiếng Anh, Lịch Sử, Địa Lý, Sinh Học, Vật Lý.

- Sử dụng thuật toán tuần tự tìm sách Địa Lý.

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.