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

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?

Để 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:

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

Chọn khẳng định sai trong các khẳng định sau:

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?

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

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

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?

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?

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 nhị phân áp dụng với bài toán tìm kiếm kiểu nào?

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?

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:

Chọn phát biểu sai?

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