Trắc Nghiệm Tin Học 11 KHMT Kết Nối Tri Thức Chủ Đề 6 Bài 19: Bài Toán Tìm Kiếm là bộ câu hỏi thuộc môn Tin học, tập trung giúp học sinh lớp 11 hiểu rõ các phương pháp tìm kiếm cơ bản trong lập trình. Đây là đề ôn tập của Trường THPT Chu Văn An (Hà Nội), được biên soạn năm 2024 bởi thầy Nguyễn Hoàng Tú – giáo viên Tin học của trường. Bộ tài liệu được trình bày theo dạng trắc nghiệm Tin học 11 KHMT, hỗ trợ học sinh luyện tập có hệ thống và dễ dàng tiếp cận thông qua nền tảng detracnghiem.edu.vn, nơi cung cấp kho đề phong phú và giao diện học tập trực quan.

Trắc nghiệm Tin học 11 ở chủ đề này tập trung vào các kỹ thuật tìm kiếm như tìm kiếm tuần tự và tìm kiếm nhị phân, giúp học sinh rèn luyện tư duy phân tích dữ liệu và đánh giá hiệu quả của từng thuật toán. Mỗi câu hỏi đều có đáp án và lời giải chi tiết, hỗ trợ việc tự học, tự kiểm tra và củng cố kỹ năng lập trình theo chương trình KHMT. Bộ đề là tài liệu cần thiết cho học sinh trong quá trình chuẩn bị kiểm tra và ôn luyện cuối chương. Trắc nghiệm ôn tập lớp 11

Trắc nghiệm Tin học 11 KHMT Kết nối tri thức

Chủ đề 6: Kỹ thuật lập trình

Bài 19: Bài toán tìm kiếm

Câu 1: Mục đích chính của bài toán tìm kiếm là gì?
A. Sắp xếp lại dãy số theo thứ tự tăng dần.
B. Tính tổng các phần tử trong dãy số.
C. Tìm vị trí của một phần tử có giá trị bằng K cho trước trong dãy.
D. Xóa tất cả các phần tử trùng lặp trong dãy.

Câu 2: Để áp dụng thuật toán Tìm kiếm nhị phân (Binary Search), dãy số đầu vào bắt buộc phải thỏa mãn điều kiện gì?
A. Dãy số phải bao gồm các số nguyên dương.
B. Dãy số không được có phần tử trùng nhau.
C. Dãy số đã được sắp xếp thứ tự (tăng hoặc giảm).
D. Dãy số phải có số lượng phần tử là số chẵn.

Câu 3: Thuật toán Tìm kiếm tuần tự (Linear Search) thực hiện công việc như thế nào?
A. So sánh giá trị cần tìm với phần tử ở giữa dãy.
B. Duyệt lần lượt từng phần tử từ đầu đến cuối dãy và so sánh với giá trị cần tìm.
C. Chia dãy số thành các phần nhỏ và tìm kiếm song song.
D. Sắp xếp dãy số trước rồi mới tìm kiếm.

Câu 4: Cho dãy số A = [3, 8, 1, 5, 9]. Nếu sử dụng tìm kiếm tuần tự để tìm số K = 5, thuật toán sẽ thực hiện bao nhiêu phép so sánh?
A. 2 lần.
B. 3 lần.
C. 4 lần.
D. 5 lần.

Câu 5: Trong thuật toán tìm kiếm tuần tự, trường hợp nào được coi là trường hợp xấu nhất (tốn nhiều thời gian nhất)?
A. Phần tử cần tìm nằm ở vị trí đầu tiên.
B. Phần tử cần tìm nằm ở vị trí chính giữa.
C. Dãy số đã được sắp xếp tăng dần.
D. Phần tử cần tìm nằm ở cuối dãy hoặc không tồn tại trong dãy.

Câu 6: Công thức tính chỉ số giữa (mid) trong thuật toán tìm kiếm nhị phân với left là biên trái và right là biên phải là gì?
A. mid = (left – right) // 2
B. mid = left + right
C. mid = (left + right) // 2
D. mid = (left + right) % 2

Câu 7: Cho dãy số đã sắp xếp A = [2, 4, 6, 8, 10, 12, 14]. Tìm K = 10 bằng tìm kiếm nhị phân. Ở bước 1, mid là chỉ số 3 (giá trị 8). Bước tiếp theo, ta sẽ tìm kiếm trong khoảng nào?
A. Nửa bên trái (từ 2 đến 8).
B. Nửa bên phải (từ 10 đến 14).
C. Tìm ở cả hai bên.
D. Dừng lại vì đã tìm thấy.

Câu 8: Xét đoạn mã Python sau cho tìm kiếm tuần tự:
code
Python
def search(A, K):
for i in range(len(A)):
if A[i] == K:
return i
return -1
Nếu hàm trả về giá trị -1, điều đó có nghĩa là gì?
A. Tìm thấy K tại vị trí cuối cùng.
B. Dãy số A bị rỗng.
C. Không tìm thấy giá trị K trong dãy A.
D. Có lỗi cú pháp trong chương trình.

Câu 9: Tại sao thuật toán Tìm kiếm nhị phân lại nhanh hơn Tìm kiếm tuần tự trên dãy đã sắp xếp?
A. Vì nó dùng ít bộ nhớ hơn.
B. Vì sau mỗi lần so sánh, phạm vi tìm kiếm giảm đi một nửa.
C. Vì nó không sử dụng vòng lặp for.
D. Vì nó được viết bằng ngôn ngữ máy.

Câu 10: Cho dãy A = [10, 20, 30, 40, 50]. Cần tìm K = 25. Thuật toán tìm kiếm nhị phân sẽ kết thúc như thế nào?
A. Trả về chỉ số 1 (giá trị 20).
B. Trả về chỉ số 2 (giá trị 30).
C. Trả về giá trị trung bình là 25.
D. Thông báo không tìm thấy sau khi đã thu hẹp phạm vi hết mức.

Câu 11: Trong thuật toán tìm kiếm nhị phân, nếu A[mid] < K (dãy tăng dần), ta cần cập nhật biến left như thế nào?
A. left = mid
B. left = mid + 1
C. left = mid – 1
D. right = mid + 1

Câu 12: Cho dãy A = [1, 3, 5, 7, 9, 11, 13, 15]. Tìm K = 13 bằng tìm kiếm nhị phân. Các giá trị của mid lần lượt qua các bước là:
A. 3, 5, 6.
B. 3, 5, 6. (Giải thích: Lần 1 mid=3(7)<13; Lần 2 đoạn [9..15] mid=5(11)<13; Lần 3 đoạn [13..15] mid=6(13)=13)
C. 4, 6, 7.
D. 0, 7, 6.

Câu 13: Một danh sách tên học sinh chưa được sắp xếp: [“Lan”, “Mai”, “Cúc”, “Trúc”]. Để tìm xem bạn “Hoa” có trong danh sách không, ta phải dùng thuật toán nào?
A. Tìm kiếm nhị phân.
B. Tìm kiếm tuần tự.
C. Sắp xếp chèn.
D. Không thể tìm kiếm được.

Câu 14: Đoạn mã sau bị sai ở đâu (Tìm kiếm nhị phân)?
code
Python
while left <= right:
mid = (left + right) // 2
if A[mid] == K: return mid
if A[mid] < K:
right = mid – 1 # Sai ở đây nếu dãy tăng
else:
left = mid + 1
A. Sai công thức tính mid.
B. Sai điều kiện vòng lặp.
C. Sai logic cập nhật left/right (bị ngược chiều so với dãy tăng dần).
D. Không có dòng return -1.

Câu 15: Số lần so sánh tối đa của thuật toán Tìm kiếm tuần tự với dãy n phần tử là:
A. n/2
B. log₂n
C. n
D. n²

Câu 16: Số lần so sánh tối đa của thuật toán Tìm kiếm nhị phân với dãy n phần tử (xấp xỉ) là:
A. n
B. log₂n
C. n/2
D. 1

Câu 17: Nếu danh sách có 1.000.000 phần tử đã sắp xếp. Tìm kiếm tuần tự có thể mất tới 1 triệu bước. Tìm kiếm nhị phân chỉ mất khoảng bao nhiêu bước?
A. 500.000 bước.
B. 1.000 bước.
C. 100 bước.
D. 20 bước. (2²⁰≈10⁶)

Câu 18: Trong trò chơi “Đoán số” từ 1 đến 100. Bạn A chọn một số bí mật. Bạn B đoán. Mỗi lần đoán A chỉ trả lời “Lớn hơn”, “Nhỏ hơn” hoặc “Đúng”. Chiến thuật tối ưu nhất của B chính là áp dụng tư tưởng của thuật toán nào?
A. Tìm kiếm tuần tự (đoán 1, 2, 3…).
B. Tìm kiếm nhị phân (đoán 50, rồi 25 hoặc 75…).
C. Tìm kiếm ngẫu nhiên.
D. Sắp xếp nổi bọt.

Câu 19: Biến mid trong tìm kiếm nhị phân có vai trò gì?
A. Lưu trữ giá trị cần tìm.
B. Đếm số bước lặp.
C. Xác định vị trí phần tử ở giữa phạm vi tìm kiếm hiện tại.
D. Lưu trữ kết quả trả về.

Câu 20: Khi cài đặt tìm kiếm nhị phân, điều kiện dừng của vòng lặp while (khi không tìm thấy) thường là:
A. left == right
B. left != right
C. left > right
D. mid == K

Câu 21: Cho dãy A = [5, 8, 8, 8, 10]. Tìm kiếm nhị phân tiêu chuẩn có thể trả về chỉ số nào khi tìm K = 8?
A. Chắc chắn là chỉ số 1 (đầu tiên).
B. Chắc chắn là chỉ số 3 (cuối cùng).
C. Có thể là chỉ số 2 (ở giữa), tùy thuộc vào cách làm tròn mid.
D. Không tìm thấy vì có nhiều số 8.

Câu 22: Nếu dãy số chưa sắp xếp, muốn dùng tìm kiếm nhị phân thì ta phải làm gì?
A. Dùng ngay lập tức, kết quả có thể sai.
B. Sắp xếp dãy số trước, sau đó mới tìm kiếm (tuy nhiên cần cân nhắc chi phí sắp xếp).
C. Chuyển sang tìm kiếm tuần tự thì tốt hơn.
D. Xóa các phần tử không cần thiết.

Câu 23: Vận dụng cao: Bài toán tìm kiếm nhị phân có thể áp dụng cho hàm số đơn điệu (đồng biến hoặc nghịch biến) không?
A. Không, chỉ áp dụng cho mảng số nguyên.
B. Có, có thể dùng để tìm nghiệm gần đúng của phương trình hoặc tìm giá trị thỏa mãn điều kiện trên miền giá trị liên tục.
C. Chỉ áp dụng nếu hàm số là đường thẳng.
D. Không, vì hàm số không có chỉ số index.

Câu 24: Vận dụng cao: Cho bài toán: “Tìm vị trí xuất hiện đầu tiên của số K trong dãy đã sắp xếp (có thể có nhiều số K)”. Ta cần sửa thuật toán nhị phân như thế nào?
A. Khi gặp A[mid] == K, trả về mid ngay lập tức.
B. Dùng tìm kiếm tuần tự cho chắc ăn.
C. Khi gặp A[mid] == K, không dừng lại mà lưu vị trí đó, rồi tiếp tục tìm ở nửa bên trái (right = mid – 1) để xem còn số K nào trước đó không.
D. Khi gặp A[mid] == K, tiếp tục tìm ở nửa bên phải.

Câu 25: Vận dụng cao: Giả sử bạn có một cuốn từ điển dày 2000 trang. Bạn muốn tìm từ “Computer”. Cách lật sách nào mô phỏng tìm kiếm tuần tự?
A. Mở trang giữa, xem vần C ở trước hay sau, rồi chia đôi tiếp.
B. Mở trang 1, trang 2, trang 3… cho đến khi thấy từ “Computer”.
C. Mở ngẫu nhiên một trang bất kỳ.
D. Mở trang mục lục.