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

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

Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia nào?

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

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 nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?

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:

Trong thuật toán tìm kiếm tuần tự để tìm một số trong dãy thẻ số, sau bước Kiểm tra: Số thẻ có đúng là số cần tìm không? Mà nhận được kết quả Đúng thì ta sẽ thực hiện bước nào?

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?

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?

Chọn phát biểu sai?

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ự có thể giúp em:

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?

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

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?

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?