Câu hỏi:
Chọn một trong hai ngôn ngữ Python hoặc C++ để tìm hiểu một hàm tìm kiếm dưới đây:
Hàm viết bằng ngôn ngữ Python: |
Hàm viết bằng ngôn ngữ C++: |
def search(x, a, n): found = False i = 0 while i < n and not found: if a[i] == x: found = True i += 1 return found |
bool search(int x, int a[], int n) { bool found = false; int i = 0; while (i < n && !found) { if (a[i] == x) found = true; i++; } return found; } |
Một số nhận xét về hàm trên như sau:
a) Hàm thực hiện một thuật toán tìm kiếm tuyến tính.
b) Các thao tác trong hàm chỉ áp dụng cho danh sách đã được sắp xếp.
c) Hàm có độ phức tạp thuật toán là O(n).
d) Nếu mảng a = {4, 5, 7} và x = 3 thì hàm trả về giá trị logic đúng.
Đáp án đúng:
- a) Đúng. Hàm `search` duyệt qua từng phần tử của mảng để tìm giá trị `x`, đây là thuật toán tìm kiếm tuyến tính.
- b) Sai. Thuật toán tìm kiếm tuyến tính không yêu cầu danh sách phải được sắp xếp. Nó hoạt động trên cả danh sách đã sắp xếp và chưa sắp xếp.
- c) Đúng. Trong trường hợp xấu nhất (giá trị `x` không có trong mảng hoặc nằm ở cuối mảng), hàm `search` phải duyệt qua tất cả `n` phần tử của mảng. Do đó, độ phức tạp thuật toán là $O(n)$.
- d) Sai. Nếu `a = {4, 5, 7}` và `x = 3`, hàm `search` sẽ duyệt qua mảng và không tìm thấy `x`. Do đó, hàm sẽ trả về `False` (sai), chứ không phải `True` (đúng).
Câu hỏi này thuộc đề thi trắc nghiệm dưới đây, bấm vào Bắt đầu thi để làm toàn bài
Câu hỏi liên quan

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Giáo Dục Kinh Tế Và Pháp Luật Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Lịch Sử Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Công Nghệ Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Hóa Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Sinh Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT
