Trắc nghiệm Tin học 11 bài 19: Bài toán tìm kiếm

Chọn đáp án đúng

Khi dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thư tự không giảm), sau bước Kiểm tra: dãy rỗng? nếu nhận kết quả Sai, ta thực hiện bước nào?

Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần 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?

Thuật toán tìm kiếm tuần tự có thể giúp em:

Chọn đáp án đúng

Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}. Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

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

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?

Chọn phát biểu sai?

Chọn đáp án đúng

Dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thư tự không giảm), sau bước Kiểm tra: số cần tìm nhỏ hơn giá trị trên thẻ? nếu nhận kết quả Sai, ta thực hiện bước nào?

Chọn đáp án đúng

Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần như sau:

def binary_search(arr, x):

left = 0

right = len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == x:

return mid

elif arr[mid] < x:

right = mid - 1

else:

left = mid + 1

return -1

# Sử dụng hàm để tìm kiếm giá trị 5 trong dãy sắp xếp giảm dần [9, 8, 6, 5, 3, 1]

arr = [9, 8, 6, 5, 3, 1]

x = 5

result = binary_search(arr, x)

if result != -1:

print("Element is present at index", str(result))

else:

print("Element is not present in array")

Em hãy nhận xét về cách viết chương trình này:

Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần nhiều bước nhất?

Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}. 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?

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

Thuật toán tìm kiếm nhị phân áp dụng với bài toán tìm kiếm kiểu nào?

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