11_Lesson_Tìm kiếm

​Lập trình giải bài toán tìm kiếm

Multiple Choice

Khái niệm nào dưới đây mô tả đúng nhất về bài toán tìm kiếm?

• Tìm kiếm dữ liệu từ cơ sở dữ liệu.

• Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu, tìm mục dữ liệu đáp ứng yêu cầu.

• Chỉ tìm kiếm trong mảng số nguyên.

• Không thể tìm thấy một mục dữ liệu nào.

Multiple Choice

Trong Python, phương thức nào được sử dụng để tìm kiếm phần tử trong danh sách?

• search()

• find()

• index()

• locate()

Multiple Choice

Khi nào phương thức index() sẽ trả về lỗi "ValueError"?

• Khi tìm thấy phần tử.

• Khi danh sách rỗng.

• Khi có nhiều phần tử giống nhau.

• Khi không tìm thấy phần tử trong danh sách.

​Lập trình giải bài toán tìm kiếm

​2. Bài toán tìm kiếm trong lập trình

Đề bài: Cho dãy A[0], A[1],..., A[n-1], hãy tìm kiếm phần tử có giá trị là K.

• Đầu vào: Dãy A có n phần tử và giá trị K.

• Đầu ra: Tìm thấy ➜ trả ra vị trí i, ngược lại ➜ trả ra -1.

a. Thuật toán tìm kiếm tuần tự

Duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phần tử bằng K; Ngược lại, thông báo không tìm thấy và trả về giá trị -1.

​Lập trình giải bài toán tìm kiếm

Xét dãy A = [1, 4, 7, 8, 3, 9, 10] và giá trị K = 9. Quá trình thực hiện thuật toán được mô phỏng như sau.

​Lập trình giải bài toán tìm kiếm

Xét dãy A = [1, 4, 7, 8, 3, 9, 10] và giá trị x = 9. Quá trình thực hiện thuật toán được mô phỏng như sau.

​Lập trình giải bài toán tìm kiếm

Chương trình Python

​Lập trình giải bài toán tìm kiếm

Hàm LinearSeach viết theo các khác

​Lập trình giải bài toán tìm kiếm

b. Thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân được áp dụng cho các dãy được sắp xếp theo thứ tự xác định. Sau mỗi bước lặp của thuật toán phạm vi tìm kiếm được thu hẹp dẫn. Ví dụ với dãy tăng dần, nếu giá trị cần tìm nhỏ hơn giá trị của phần tử ở giữa dãy thì phạm vi tìm kiếm thu hẹp vào nửa đầu của dãy, ngược lại, phạm vi tìm kiếm là nửa cuối của dãy. Cứ tiếp tục như vậy cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng.

​Lập trình giải bài toán tìm kiếm

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

​Lập trình giải bài toán tìm kiếm

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

​Lập trình giải bài toán tìm kiếm

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

Multiple Choice

Tìm kiếm tuần tự trong Python là gì?

• Tìm kiếm trong một cơ sở dữ liệu lớn.

• Tìm kiếm bằng cách chia đôi danh sách.

• Tìm kiếm theo thứ tự tăng dần của danh sách.

• Tìm kiếm từng phần tử trong danh sách cho đến khi tìm thấy hoặc đã xét hết danh sách.

Multiple Choice

Thuật toán tìm kiếm nhị phân yêu cầu điều kiện nào trước khi áp dụng?

• Danh sách phải sắp thứ tự.

• Danh sách phải có ít nhất 10 phần tử.

• Danh sách phải không chứa các phần tử trùng lặp.

• Danh sách phải được lưu trữ trong một cơ sở dữ liệu.

Multiple Choice

Trong thuật toán tìm kiếm nhị phân, chỉ số của phần tử ở giữa được tính như thế nào?

• (lo + hi) / 2

• (lo + hi) // 2

• (hi - lo) / 2

• (hi + lo) / 2

Multiple Choice

Trong thuật toán tìm kiếm tuần tự, khi nào bạn thông báo "không tìm thấy"?

• Khi tìm thấy phần tử.

• Khi tìm thấy nhiều phần tử.

• Khi gặp lỗi trong quá trình tìm kiếm.

• Khi đã xét hết dãy số và không tìm thấy phần tử.

Multiple Choice

Khi thực hiện tìm kiếm tuần tự, bạn có thể giới hạn phạm vi tìm kiếm bằng cách nào?

• Xóa các phần tử không liên quan.

• Thay đổi kiểu dữ liệu của danh sách.

• Chỉ tìm kiếm trong các phần tử đầu tiên.

• Sử dụng chỉ số lo và hi trong phương thức index.

Multiple Choice

Một ví dụ thực tế nào dưới đây có thể dẫn đến bài toán tìm kiếm?

• Phát triển một ứng dụng mới.

• Chọn một màu sắc cho đồ họa.

• Thay đổi kích thước của một bức ảnh.

• Tìm kiếm một cuốn sách trong thư viện.

Multiple Choice

Khái niệm bài toán tìm kiếm là gì?

• Tìm một giá trị trong tập hợp dữ liệu.

• Chỉ có thể tìm kiếm trong các dãy số đã sắp xếp.

• Tìm kiếm không bao giờ thất bại.

• Tìm kiếm chỉ áp dụng cho dữ liệu văn bản.

Multiple Choice

Phương thức index() trong Python được sử dụng để làm gì?

• Tìm kiếm một phần tử trong dãy và trả về chỉ số đầu tiên nếu tìm thấy.

• Tìm kiếm một phần tử trong dãy mà không báo lỗi nếu không tìm thấy.

• Chỉ tìm kiếm trong dãy số đã sắp xếp.

• Tìm kiếm tất cả các phần tử giống nhau trong dãy và trả về danh sách các chỉ số.

Fill in the Blank

Phương thức ... thực hiện tìm kiếm một phần tử trong dãy và trả về chỉ số của lần xuất hiện đầu tiên. Nếu không tìm thấy, nó sẽ báo lỗi ValueError.

(

)

Multiple Choice

Bài toán tìm kiếm tuần tự thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy A = [91, 45, 23, 67, 9, 10, 47, 90, 46, 86]?

• 5

• 6

• 7

• 8

Multiple Choice

Trong tìm kiếm tuần tự, khi nào ta có thể tìm thấy kết quả ngay với ít bước nhất?

• Khi phần tử cần tìm ở giữa danh sách

• Khi phần tử cần tìm ở cuối danh sách

• Khi phần tử cần tìm là phần tử đầu tiên

• Khi phần tử cần tìm không có trong danh sách

Multiple Choice

Trong tìm kiếm tuần tự, khi nào cần nhiều bước nhất để tìm ra kết quả?

• Khi phần tử cần tìm ở giữa danh sách

• Khi phần tử cần tìm là phần tử cuối cùng

• Khi phần tử cần tìm không có trong danh sách

• Khi phần tử cần tìm là phần tử đầu tiên 

Multiple Choice

Thuật toán tìm kiếm nhị phân chỉ có thể áp dụng khi danh sách dữ liệu đã được sắp xếp như thế nào?

• Tăng dần

• Giảm dần

• Không cần sắp xếp

• Sắp xếp theo bất kỳ thứ tự nào

Multiple Choice

Với thuật toán tìm kiếm nhị phân, cần bao nhiêu lần duyệt để tìm phần tử có giá trị bằng 34 trong dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67]?

• 2

• 3

• 4

• 5

Multiple Choice

Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần tử có giá trị bằng 34 trong dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67]?

• 10

• 11

• 12

• 13

Multiple Choice

Thuật toán tìm kiếm nhị phân có ưu điểm gì so với tìm kiếm tuần tự?

• Đơn giản hơn trong lập trình

• Có thể áp dụng cho mọi danh sách

• Tốc độ nhanh hơn khi danh sách đã sắp xếp

• Không cần phải sắp xếp danh sách trước khi tìm

Multiple Choice

Cho dãy A = [1, 3, 4, 7, 8, 9, 10]. Cần tìm giá trị K = 9 bằng thuật toán tìm kiếm nhị phân, chỉ số nào sẽ được trả về?

• 3

• 4

• 5

• 6

Multiple Choice

Thuật toán tìm kiếm tuần tự có thể áp dụng trong trường hợp nào?

• Dữ liệu đã được sắp xếp

• Dữ liệu chưa được sắp xếp

• Chỉ cho các dãy số

• Chỉ cho các dãy chữ cái

Multiple Choice

Nếu dãy số đã được sắp xếp giảm dần, thuật toán tìm kiếm nhị phân sẽ hoạt động như thế nào?

• Thuật toán vẫn hoạt động bình thường

• Phải thay đổi thuật toán để so sánh ngược lại

• Không thể áp dụng tìm kiếm nhị phân

• Chỉ áp dụng cho dãy số ngắn

Multiple Choice

Trong bài toán tìm kiếm tuần tự, khi nào thuật toán tìm kiếm có thể tìm thấy ngay kết quả cần tìm?

• Khi phần tử cần tìm nằm ở vị trí đầu tiên của dãy số.

• Khi phần tử cần tìm nằm ở vị trí giữa của dãy số.

• Khi phần tử cần tìm nằm ở vị trí cuối cùng của dãy số

• Khi dãy số có số lượng phần tử lớn hơn 10.

Multiple Choice

Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?

• Vị trí đầu tiên.

• Vị trí cuối cùng.

• Vị trí giữa.

• Bất kì vị trí nào.

Multiple Choice

Khi so sánh giá trị cần tìm với giá trị của vị trí giữa, nếu giá trị cần tìm nhỏ hơn giá trị giữa thì:

• Tìm trong nửa đầu của danh sách.

• Tìm trong nửa sau của danh sách.

• Tìm trong nửa đầu hoặc nửa sau của danh sách.

• Dừng lại.

Multiple Choice

Khi thực hiện tìm kiếm nhị phân số 25 trong dãy số 18, 21, 25, 27, 67, 69, 72, 77, 79, 81 cần thực hiện mấy vòng lặp?

• 2

• 3

• 4

• 5

Multiple Choice

Chọn phát biểu sai về thuật toán tìm kiếm nhị phân?

• Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia (số lượng thẻ của dãy) /2.

• Vòng lặp sẽ kết thúc khi tìm thấy số cần tìm hoặc dãy không còn thẻ số nào nữa.

• Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

• Khi dãy chỉ còn một thẻ số thì nửa trước (hoặc nửa sau) là dãy rỗng (dãy không có thể số nào).

Multiple Choice

 Trong thuật toán tìm kiếm nhị phân, ở mỗi lần lặp ta thực hiện mấy bước?

• 2

• 3

• 4

• 5

Multiple Choice

Chọn phát biểu sai?

• Thuật toán tìm kiếm nhị phân chỉ áp dụng với dãy gia trị đã được sắp xếp.

• Thuật toán tìm kiếm tuần tự chỉ áp dụng với dãy gia trị đã được sắp xếp.

• Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

• Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

Multiple Choice

Thuật toán tìm kiếm nhị phân thực hiện như thế nào?

• Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

• Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm lớn hơn.

• So sánh lần lượt phần tử cuối cùng 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.

• So sánh lần lượt phần tử đầu 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.

Multiple Choice

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:

• Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

• So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

• Sếp xếp dãy số theo thứ tự tăng dần.

• So sánh số cần tìm với số ở giữa dãy số.