Câu hỏi tự luận tin học 7 chân trời Bài 13: Thuật toán tìm kiếm

BÀI 13: THUẬT TOÁN TÌM KIẾM (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 so sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

Câu 2: Thuật toán tìm kiếm nhị phân là gì?

Trả lời:

- Thuật toán tìm kiếm nhị phân chỉ áp dụng cho dãy giá trị đã được sắp xếp.

- Thuật toán tìm kiếm nhị phân là một vòng lặp, ở mỗi lần lặp ta thực hiện:

+ Bước 1: So sánh giá trị cần tìm với giá trí của phần tử giữa dãy đang xét.

+ Bước 2: Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.

+ Bước 3: Nếu nhỏ hơn thì xét dãy ở nửa trước và ngược lại.

+ Bước 4: Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, nếu không thì lặp lại từ bước 1.

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

Câu 1: Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là gì?

Trả lời:

Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là: Thuật toán tuần tự sẽ không yêu cầu danh sách cần phải được sắp xếp nhưng thuật toán tìm kiếm nhị phân cần danh sách phải được sắp xếp thì mới có thể thực hiện được.

Câu 2: 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 đầ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 3: 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 đầu vào và đầu ra của thuật toán tìm kiếm nhị phân.

Trả lời:

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

Câu 4: Nêu các bước để tạo hiệu ứng động cho đối tượng trong phần mềm trình chiếu.

Trả lời:

Các bước để tạo hiệu ứng động cho đối tượng trong phần mềm trình chiếu là:

- Bước 1: Chọn đối tượng muốn áp hiệu ứng bằng cách bôi đen đối tượng đó.

- Bước 2: Chọn Animations.

- Bước 3: Chọn hiệu ứng.

- Bước 4: Chọn thời điểm xuất hiện thời lượng thực hiện hiệu ứng.

- Bước 5: Thay đổi thứ tự xuất hiện của hiệu ứng.

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

[giá trị cần tìm xuất hiện ở vị trí giữa, nửa sau, “Không tìm thấy”, nửa trước]

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 nhị phân:

1. a) Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận … và thuật toán kết thúc.
2. b) Bước 2: Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.
3. c) Bước 3: Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận … và kết thúc.
4. d) Bước 4: Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn … của dãy.

Ngược lại, nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn … của dãy.

1. e) Bước 5: Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1).

Trả lời:

1. a) “Không tìm thấy”
2. b) giá trị cần tìm xuất hiện ở vị trí giữa
3. c) nửa trước - nửa sau

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

III, VẬN DỤNG (5 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:

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 2: Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy “Mai" trong danh sách ["Hoa”, ”Lan”, "Ly”, ”Mai”, ”Phong”, ”Vi]?

Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 3.

So sánh “Ly” và “Mai”. Vì “L” đứng trước “M” trong bảng chữ cái nên bỏ đi nửa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí số 5.

So sánh “Phong” và “Mai”. Vì “P” đứng sau “M” trong bảng chữ cái nên bỏ đi nửa sau danh sách.

Bước 3: Xét vị trí ở giữa của dãy giữa sau danh sách, đó là vị trí số 4.

So sánh “Mai” và “Mai”. Vì hai giá trị bằng nhau nên thuật toán kết thúc

=> Sau 3 bước đã tìm thấy “Mai” trong danh sách.

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: Theo em, thuật toán tìm kiếm nào trong 2 thuật toán đã học là phù hợp nhất để tìm một số trong dãy số 14, 17, 21, 25, 30, 52, 66? Vì sao em không chọn thuật toán còn lại?

Hãy mô phỏng thuật toán phù hợp nhất đã chọn để tìm số 30 trong dãy số trên bằng cách điền thông tin mỗi lần lặp vào bảng dưới đây.

Trả lời:

Sử dụng thuật toán tìm kiếm nhị phân là phù hợp nhất để tìm một số trong dãy số này vì đây là dãy số sắp xếp tăng dần, số lần lặp phải thực hiện ít hơn hẳn khi sử dụng thuật toán tìm kiếm tuần tự (ta sẽ thấy rõ khi dãy có nhiều phần tử và phần tử này cần tìm cách xa phần tử đầu tiên).

Câu 5: Bạn em có một bộ 20 thẻ số, mỗi thẻ ghi một số khác nhau, được đặt úp trên bàn theo thứ tự giá trị các số tăng dần từ trái sang phải. Bạn đố em lật tìm được đúng một số trong 20 thẻ số đó chỉ với tối đa 5 lần lật. Em có thực hiện được không? Vì sao?

Trả lời:

Thực hiện được, vì: Áp dụng thuật toán tìm kiếm nhị phân.

Theo công thức phần nguyên, ta xác định và lật thẻ ở giữa như sau (giả định trường hợp xấu nhất là lần lật cuối cùng mới đúng số cần tìm):

- Lần 1: lật 1 thẻ trong 20 thẻ, ta lật thẻ thứ 10.

- Lần 2: lật 1 thẻ trong 9 thẻ bên trái hoặc trong 10 thẻ bên phải thẻ thứ 10, ta lật thẻ thứ 5 hoặc lật thẻ thứ 15.

Cứ tiếp tục chọn và lật như vậy thì đến lần 5, sẽ chỉ còn 1 số để lật và chắc chắn tìm được một số theo yêu cầu.

IV. VẬN DỤNG CAO (2 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.

Câu 2: Bài tập thực hành:

Em hay tìm kiếm thông tin trên internet để lập bảng danh sách khoảng 10 cuốn sách mà em yêu thích và đơn giá của mỗi cuốn sách. Sau đó thực hiện thuật toán tìm kiếm nhị phân để tìm cuốn sách mà em thích nhất trong danh sách vừa tìm được và cho biết đơn giá của cuốn sách đó.

 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 cuốn sách đơn sách.

Bước 2. Sắp xếp tên sách theo thứ tự của bằng chữ cái.

Bước 3. Chỉ ra tên một cuốn sách mà em thích nhất.

Bước 4. Liệt kê các bước thực hiện thuật toán tìm kiếm nhị phân để tìm tên cuốn sách mà em thích nhất trong danh sách ở Bước 2.

Bước 5. Ghi ra đơn giá của cuốn sách tìm thấy ở Bước 4.

Các bước tìm kiếm tên sách “Tôi tự học” trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí thứ 5

So sánh “Hoàng tử bé” và “Tôi tự học” vì “H” đứng trước “T” trong bảng chữ cái nên bỏ đi nửa đầu danh sách

Bước 2: Xét vị trí ở giữa của nửa sau dãy, đó là vị trí thứ 8

So sánh “Tôi tự học” và “Tôi tự học” vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 2 bước đã tìm thấy tên sách “Tôi tự học” với đơn giá sách là 80.000đ.