Chọn một trong hai ngôn ngữ Python hoặc C++… – Đáp án Câu 4 Phần II, Tin học 2025

Câu 4.(Khoa học máy tính)

Chọn một trong hai ngôn ngữ Python hoặc C++ để tìm hiểu một hàm cho dưới đây:

Hàm viết bằng ngôn ngữ Python:

def find(x, a, n):
    found = False
    i = 0
    while (i<n) and not found:
        if a[i] == x:
            found = True
        i = i + 1
    return found

Hàm viết bằng ngôn ngữ C++:

bool find(int x, int a[], int n) {
    bool found = false;
    int i = 0;
    while (i<n && !found) {
        if (a[i] == x)
            found = true;
        i = i + 1; }
return found; }

Một số bạn học sinh nhận xét về hàm trên như sau:

a)
Hàm thể hiện một thuật toán đệ quy.
Sai
b)
Các thao tác với mảng a trong hàm không phải là thao tác trên kiểu dữ liệu ngăn xếp.
Đúng
c)
Thuật toán của hàm có độ phức tạp thời gian là hằng số, kí hiệu là O(1).
Sai
d)
Nếu mảng a = {2, 6, 3, 8} và x = 9 thì hàm trả về giá trị logic sai.
Đúng

Lời giải

a) Sai: hàm không tự gọi lại chính nó; đây là thuật toán tìm kiếm tuần tự dùng vòng lặp while.

b) Đúng: hàm truy cập phần tử bất kì a[i] theo chỉ số, đó là thao tác trên mảng; ngăn xếp chỉ cho thêm và lấy phần tử ở đỉnh.

c) Sai: trong trường hợp xấu nhất (không tìm thấy x), vòng lặp chạy $n$ lần nên độ phức tạp thời gian là $O(n)$ , không phải $O(1)$ .

d) Đúng: 9 không có trong mảng {2, 6, 3, 8}, vòng lặp duyệt hết 4 phần tử mà found vẫn là sai, hàm trả về False (false trong C++).

Câu 4 Phần II · Đề tham khảo Tin học 2025 (Bộ GD&ĐT)