Tuần 23 — Tìm kiếm tuyến tính (Linear search)
Tin học Lớp 8 · 5 câu hỏi có lời giải
Câu 1.Linear search hoạt động bằng?
- A.Duyệt tuần tự từng phần tử, so sánh với x cần tìm
- B.Băm khoá rồi tra bảng
- C.Nhảy bước
- D.Chia đôi
Xem đáp án
Đáp án: A. Duyệt tuần tự từng phần tử, so sánh với x cần tìm
Linear search: kiểm tra từng phần tử cho đến khi tìm thấy hoặc hết dãy.
Câu 2.Độ phức tạp linear search xấu nhất?
- A.O(1) — luôn tìm thấy ngay
- B.O(n)
- C.O(log n)
- D.O(n²) — hai vòng lồng
Xem đáp án
Đáp án: B. O(n)
Xấu nhất: phải duyệt toàn bộ n phần tử → O(n).
Câu 3.Khi nào linear search là cách duy nhất?
- A.Mảng đã sắp tăng dần
- B.Dãy đã sắp
- C.Liên kết
- D.Dãy chưa sắp xếp
Xem đáp án
Đáp án: D. Dãy chưa sắp xếp
Dãy chưa sắp → chỉ có thể duyệt tuần tự (không thể binary search).
Câu 4.Trong Python, kiểm tra x in list dùng?
- A.Cơ chế tương đương linear search
- B.Hash O(1) như set/dict
- C.Không có cách
- D.Binary search
Xem đáp án
Đáp án: A. Cơ chế tương đương linear search
Toán tử in trên list = linear search; trên set/dict mới là hash O(1).
Câu 5.Linear search trả về gì khi không tìm thấy?
- A.Crash chương trình
- B.Tự thêm
- C.0
- D.-1 (hoặc None — tuỳ quy ước)
Xem đáp án
Đáp án: D. -1 (hoặc None — tuỳ quy ước)
Quy ước phổ biến: trả -1 hoặc None để báo không tìm thấy.