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

BÀI 2: TÌM KIẾM NHỊ PHÂN (15 CÂU)

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

Câu 1: 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 là thuật toán tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại

Câu 2: Hãy mô tả thuật toán tìm kiếm nhị phân.

Trả lời:

Bước 1: Phạm vi tìm kiếm là dãy ban đầu.

Bước 2: Lặp khi vẫn còn Phạm vi tìm kiếm

a) Xác định phần tử ở giữa Phạm vi tìm kiếm.

b) Nếu x = phần tử ở giữa:

Thông báo tìm thấy x ở vị trí giữa của dãy.

Kết thúc thuật toán.

Trái lại:

Loại bỏ nửa dãy chắc chắn không chứa x.

Phạm vi tìm kiếm = nửa dãy còn lại.

Hết nhánh.

Hết lặp.

Bước 3: (Đã hết dãy số mà không tìm thấy x): Thông báo không có x trong dãy.

Câu 3: Lưu ý quan trọng và bắt buộc khi sử dụng tìm kiếm nhị phân là gì?

Trả lời:

Lưu ý quan trọng và bắt buộc khi sử dụng tìm kiếm nhị phân là khi dãy đã được sắp xếp theo thứ tự thì mới có thể áp dụng được tìm kiếm nhị phân.

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

Câu 1: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân.

Trả lời:

Bước 1. Sắp xếp dãy theo thứ tự từ nhỏ đến lớn.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy.

Bước 3. Lấy phần tử đứng giữa dãy để so sánh với x.

Nếu phần tử đó chính là x thì kết luận đã tìm thấy x và kết thúc thuật toán.

Ngược lại, ta có thể xác định được x chắc chắn không có trong nửa đầu hay nửa sau của dãy. Từ đó ta xác định được phạm vi tìm kiếm và thực hiện tìm kiếm trong phạm vi nữa dãy còn lại, sẽ được lặp lại theo cách như thế cho đến khi tìm được kết quả.

Câu 2: Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.

Trả lời:

Theo em, chỉ thực hiện tìm kiếm nhị phân ở một số dãy số. Vì khi dãy có thứ tự thì mới áp dụng được tìm kiếm nhị phân.

Câu 3: Hãy chọn những câu đúng và nói rõ tại sao không chọn các câu còn lại:

1) Tìm kiếm nhị phân chia dãy làm hai nửa dài xấp xỉ bằng nhau và chỉ cần tìm kiếm trong một nửa dãy.

2) Tìm kiếm nhị phân chia dãy làm hai nửa dài đúng bằng nhau và chỉ cần tìm kiếm trong một nửa dãy.

3) Tìm kiếm nhị phân lặp lại việc chia đôi dãy cho đến khi dãy chỉ còn một phần tử.

4) Tìm kiếm nhị phân lặp lại việc chia đôi dãy cho đến khi tìm thấy.

5) Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự.

6) Tìm kiếm nhị phân áp dụng chiến lược “chia để trị”

Trả lời:

1) Đúng.

2) Sai khi độ dài dãy là các số lẻ.

3) Đúng.

4) Sai vì khi dãy không có số bằng x thì thuật toán không dừng được, khi dãy chỉ còn một phần tử thì không chia đôi nữa mà kiểm tra trực tiếp.

5) Đúng.

6) Đúng.

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

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

Câu 1: Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.

Trả lời:

Trong thực tế trong quản lý học sinh, danh sách học sinh luôn được sắp xếp theo chữ cái đầu của tên để dễ tìm kiếm.

Câu 2: Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên.

Trả lời:

Tìm kiếm x = 60.

Bước 1. Ta sắp xếp dãy theo thứ tự từ nhỏ đến lớn. (Ở đây dãy số đã được sắp xếp sẵn).

Bước 2. Ta chia đôi dãy số để tìm x trong dãy. Ta sẽ chia ngay số ở vị trí thứ 4 là 39, vì x > 39. Phạm vi tìm kiếm tiếp theo là nửa sau của dãy số.

Bước 3. Ta chia đôi dãy số nửa sau để tìm x trong dãy. Ta sẽ chia ngay số ở vị trí thứ 6 là 52, vì x > 39. Phạm vi tìm kiếm tiếp theo là nửa sau của dãy số.

Bước 4. Khi đó phạm vi tìm kiếm chỉ có số ở vị trí thứ 7 đến thứ 8 và ta thấy không có số nào bằng x. Kết thúc thuật toán không tìm thấy kết quả x.

Câu 3: 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 4: 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 5: Cho danh sách sau:

Em hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên “Hoà” trong danh sách trên.

Trả lời:

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

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

Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3

So sánh “Hòa” và “Hòa”, 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 khách hàng tên “Hoà” nên thuật toán kết thúc.

Câu 6: Cho bảng điểm môn Tin học của học sinh tổ một như sau:

a) Em hãy sắp xếp lại danh sách theo thứ tự tăng dần của Điểm.

b) Em hãy liệt kê các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học. Hãy cho biết tên học sinh đó

Trả lời:

a) Danh sách sau khi đã được sắp xếp theo thứ tự tăng dần của Điểm:

b) Các bước thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học

Vùng tìm kiếm là dãy số: 7,5 8,0 8,5 9,0 9,5 10

Bước 1. Chọn phần tử ở giữa, đó là 8,5.

So sánh ta có 9,5 > 8,5, do đó vùng tìm kiếm thu hẹp chỉ còn nửa sau của danh sách.

Bước 2. Chọn phần tử ở giữa, đó là 9,5.

So sánh ta có 9,5 = 9,5, tìm thấy giá trị cần tìm nên thuật toán dừng lại.

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

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