Lý thuyết Tin học 11 Kết nối tri thức bài 19

Bài toán tìm kiếm

Với nội dung bài Lý thuyết Tin học lớp 11 bài 19: Bài toán tìm kiếm hay, chi tiết sách Kết nối tri thức sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt Tin học 11.

Bài: Bài toán tìm kiếm

A. Lý thuyết Tin học 11 bài 19
- 2. Tìm kiếm tuần tự
- 3. Tìm kiếm nhị phân
B. Trắc nghiệm Tin học 11 bài 19

A. Lý thuyết Tin học 11 bài 19

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 họa 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.

B. Trắc nghiệm Tin học 11 bài 19

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.