CHỦ ĐỀ 4. ỨNG DỤNG TIN HỌC

BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

Câu 1: Cho đoạn thông tin:
Thuật toán tìm kiếm nhị phân là một phương pháp hiệu quả để tìm kiếm một giá trị trong một danh sách đã được sắp xếp. Thuật toán này hoạt động bằng cách chia đôi danh sách và so sánh giá trị cần tìm với phần tử giữa. Nếu giá trị cần tìm nhỏ hơn phần tử giữa, thuật toán sẽ tìm kiếm trong nửa bên trái; nếu lớn hơn, nó sẽ tìm trong nửa bên phải.

Hãy đánh giá tính đúng sai của các nhận định sau:
a) Tìm kiếm nhị phân chỉ áp dụng cho danh sách không được sắp xếp.
b) Thuật toán tìm kiếm nhị phân có thể giảm thiểu số lần so sánh cần thiết.
c) Tìm kiếm nhị phân không cần phải biết danh sách đã sắp xếp hay chưa.
d) Thuật toán này có thời gian chạy O(log n).

Câu 2: Cho đoạn thông tin:
Để áp dụng thuật toán tìm kiếm nhị phân, danh sách cần phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Nếu danh sách không được sắp xếp, thuật toán này sẽ không hoạt động chính xác.

Hãy đánh giá tính đúng sai của các nhận định sau:
a) Danh sách không cần phải sắp xếp để áp dụng thuật toán tìm kiếm nhị phân.
b) Tìm kiếm nhị phân có thể tìm thấy giá trị trong danh sách sắp xếp.
c) Thuật toán tìm kiếm nhị phân là phương pháp tìm kiếm chậm nhất.
d) Tìm kiếm nhị phân là một trong những thuật toán tìm kiếm nhanh nhất trên danh sách đã sắp xếp.

Câu 3: Cho đoạn thông tin:
Một trong những ưu điểm của thuật toán tìm kiếm nhị phân là nó có thể tìm kiếm trong các danh sách lớn một cách nhanh chóng, với số lần so sánh ít hơn so với tìm kiếm tuần tự.

Nhận định:
a) Tìm kiếm nhị phân luôn nhanh hơn tìm kiếm tuần tự.
b) Tìm kiếm nhị phân có thể tìm kiếm trong danh sách lớn một cách hiệu quả.
c) Số lần so sánh trong tìm kiếm nhị phân phụ thuộc vào kích thước của danh sách.
d) Tìm kiếm tuần tự không thể tìm kiếm trong danh sách đã sắp xếp.

Câu 4: Cho đoạn thông tin:
Trong thuật toán tìm kiếm nhị phân, nếu giá trị cần tìm không có trong danh sách, thuật toán sẽ trả về giá trị -1 hoặc một thông báo rằng giá trị không tồn tại.

Hãy đánh giá tính đúng sai của các nhận định sau:
a) Nếu giá trị không có trong danh sách, thuật toán sẽ không trả về kết quả gì.
b) Tìm kiếm nhị phân có thể trả về chỉ số của giá trị cần tìm.
c) Thuật toán tìm kiếm nhị phân luôn tìm thấy giá trị, nếu nó tồn tại.
d) Nếu giá trị không tồn tại, thuật toán sẽ trả về một thông báo hoặc giá trị -1.

Câu 5: Cho đoạn thông tin:
Thuật toán tìm kiếm nhị phân có thể được biểu diễn bằng mã giả hoặc ngôn ngữ lập trình. Cấu trúc của thuật toán này thường bao gồm các bước kiểm tra và điều chỉnh các chỉ số bắt đầu và kết thúc của danh sách. (Nguồn: Tài liệu học Tin học)

Hãy đánh giá tính đúng sai của các nhận định sau:
a) Tìm kiếm nhị phân có thể được viết bằng mã giả.
b) Thuật toán này không thể được biểu diễn bằng ngôn ngữ lập trình.
c) Cấu trúc của thuật toán tìm kiếm nhị phân bao gồm các bước điều chỉnh chỉ số.
d) Tìm kiếm nhị phân không cần các bước kiểm tra.