JavaScript is required

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.

Trả lời:

Đáp án đúng:


Phân tích từng nhận xét:
  • 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).
Vậy, các nhận xét đúng là a) và c). Nhưng vì đây là multiple choice, nên đáp án chính xác nhất là a).

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