Lý thuyết Tin học 11 Bài 19 (Kết nối tri thức): Bài toán tìm kiếm

Lý thuyết Tin học 11 Bài 19: Bài toán tìm kiếm

A. Lý thuyết Bài toán tìm kiếm

1. Bài toán tìm kiếm trên thực tế

- Bài toán 1: Miền dữ liệu là tất cả ảnh trên mạng Internet, kết quả là các ảnh hoa hồng.

- Bài toán 2: Miền dữ liệu là các tệp văn bản trên đĩa cứng, kết quả là tệp bai-hoc-1.docx.

- Bài toán 3: Miền dữ liệu là danh sách học sinh và điểm thi, kết quả là danh sách 5 bạn có điểm trung bình cao nhất.

2. Tìm kiếm tuần tự

- Cách An lật thẻ từ đầu đến cuối là tìm kiếm tuần tự trong dãy đối tượng.

- Bài toán tìm kiếm trên một dãy số: cho dãy A[0], A[1],..., A[n-1] và giá trị K, cần tìm chỉ số i mà A[i] = K, trả về -1 nếu không tìm thấy.

3. Tìm kiếm nhị phân

a. Phân tích bài toán

- Tìm kiếm nhị phân: tìm kiếm với dãy số đã được sắp xếp.

- Duyệt phần tử bất kì, xác định phần tử cần tìm ở bên trái hay bên phải.

- Quyết định tìm tiếp theo hướng nào mà không cần duyệt tất cả các phần tử của dãy số.

b. Thuật toán tìm kiếm nhị phân

- Thuật toán tìm kiếm nhị phân thu hẹp phạm vi tìm kiếm liên tục.

- Nếu giá trị của phần tử ở giữa bằng K thì thông báo tìm thấy.

- Nếu K nhỏ hơn giá trị ở giữa, thu hẹp phạm vi tìm kiếm nửa đầu dãy tăng A (ngược lại thì phạm vi tìm kiếm nửa sau).

- Thiết lập left, right là chỉ số phần tử đầu và cuối của dãy cần tìm. Cần tìm K trong A[left..right].

- So sánh K với phần tử giữa dãy A[mid], có 3 trường hợp có thể xảy ra:

+ Nếu K = A[mid] thì trả về chỉ số mid và kết thúc.

+ Nếu K < A[mid] thì phần tử cần tìm ở dãy con bên trái của A[mid], cập nhật right = mid - 1, giữ nguyên left.

+ Nếu K > A[mid] thì phần tử cần tìm ở dãy con bên phải của A[mid], cập nhật left = mid + 1, giữ nguyên right.

- Lặp lại cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng (right < left).

c. Minh hoạ các bước của thuật toán tìm kiếm nhị phân

- Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì số phần tử cần duyệt giảm một nửa sau mỗi vòng lặp.

- Với cùng dãy số A và giá trị tìm kiếm K, thuật toán tìm kiếm tuần tự cần 6 bước, nhưng thuật toán tìm kiếm nhị phân chỉ cần 2 bước.

- Thuật toán tìm kiếm nhị phân trên dãy số đã sắp xếp tăng dần, hàm BinarySearch(A,K) trả lại chỉ số i nếu tìm thấy A[i] = K và -1 nếu không tìm thấy K trong dãy A.

Sơ đồ tư duy Bài toán tìm kiếm

B. Bài tập Bài toán tìm kiếm

Câu 1: Đâu là phát biểu đúng khi nói đến thuật toán tìm kiếm tuần tự?

A. Thực hiện tìm lần lượt từ đầu đến cuối danh sách.

B. Khi chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.

C. Cả A, B đúng.

D. Cả A, B sai.

Câu 2: Thuật toán tìm kiếm tuần tự thực hiện công việc gì?

A. Lưu trữ dữ liệu.

B. Sắp xếp dữ liệu theo chiều tăng dần.

C. Xử lí dữ liệu.

D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho.

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

A. Đúng.

B. Sai.

Câu 4: Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào?

A. Sắp xếp lại dữ liệu theo thứ tự bảng chữ cái.

B. Xem xét mục dữ liệu đầu tiên, sau đó xem xét từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.

C. Cho nhỏ dữ liệu thành từng phần để tìm kiếm.

D. Bất đầu tìm từ vị trí bất kì trong danh sách.

Câu 5: Trong tìm kiếm tuần tự thì có mấy điều kiện cần kiểm tra để dừng vòng lặp?

A. 1

B. 2

C. 3

D. Không

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

A. Thông báo “Không tìm thấy”.

B. Thông báo “Tìm thấy”.

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

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

Câu 7: Cho sơ đồ khối dùng để mô tả thuật toán tìm kiếm tuần tự tên sách như hình bên dưới:

Thông tin đầu vào tại vị trí X (phía dưới bắt đầu) là?

A. Tên sách cần tìm

B. Danh sách tên sách

C. Danh sách họ tên học sinh

D. Đáp án khác

Câu 8: Cho sơ đồ khối như sau, đầu ra của thuật toán dưới là gì?

A. Số lượng tên học sinh.

B. Tên học sinh bị trùng.

C. Có tìm thấy tên học sinh cần tìm không.

D. Danh sách tên học sinh.

Câu 9: Chọn câu diễn đạt đúng hoạt động của thuật toán tìm kiếm tuần tự.

A. 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.

B. 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.

C. 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.

D. 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.

Câu 10: Cho sơ đồ khối như sau mô tả thuật toán?

A. Thuật toán tìm kiếm tên khác hàng

B. Thuật toán tìm kiếm địa chỉ khách hàng

C. Thuật toán tìm kiếm tên học sinh

D. Thuật toán tìm kiếm địa chỉ học sinh

Xem thêm các bài lý thuyết Tin học 11 sách Kết nối tri thức hay, chi tiết tại:

Lý thuyết Bài 21: Các thuật toán sắp xếp đơn giản

Lý thuyết Bài 23: Kiểm thử và đánh giá chương trình

Lý thuyết Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Lý thuyết Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Lý thuyết Bài 28: Thiết kế chương trình theo Mô đun