PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch(A, K) là:
AĐáp án A: O(1)
BĐáp án B: O(n)
CĐáp án C: O(log n)
DĐáp án D: O(n^2)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:B
Đáp án: B
Giải thích: Trong trường hợp xấu nhất, thuật toán tìm kiếm tuần tự phải duyệt qua toàn bộ mảng để tìm phần tử, do đó độ phức tạp là O(n).
Câu 2
1 điểm
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort(A) là:
AĐáp án A: O(n)
BĐáp án B: O(log n)
CĐáp án C: O(n^2)
DĐáp án D: O(n log n)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:C
Đáp án: C
Giải thích: Thuật toán sắp xếp chọn có độ phức tạp thời gian là O(n^2) do cần thực hiện các vòng lặp lồng nhau để tìm phần tử nhỏ nhất và đổi chỗ ở mỗi lần duyệt.
Câu 3
1 điểm
Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt BubbleSort(A) là:
AĐáp án A: O(n)
BĐáp án B: O(n^2)
CĐáp án C: O(n log n)
DĐáp án D: O(log n)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:B
Đáp án: B
Giải thích: Trong trường hợp xấu nhất, thuật toán sắp xếp nổi bọt sẽ có độ phức tạp O(n^2) vì có hai vòng lặp lồng nhau chạy qua các phần tử.
Câu 4
1 điểm
Đối với thuật toán LinearSearch(A, K), thời gian tính toán trong trường hợp tốt nhất là:
AĐáp án A: O(n)
BĐáp án B: O(log n)
CĐáp án C: O(1)
DĐáp án D: O(n^2)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:C
Đáp án: C
Giải thích: Trong trường hợp tốt nhất, phần tử cần tìm có thể nằm ngay ở vị trí đầu tiên của mảng, và thuật toán chỉ cần thực hiện một lần so sánh để trả về kết quả, do đó độ phức tạp là O(1).
Câu 5
1 điểm
Độ phức tạp thời gian của hàm Mystery(n) với các vòng lặp lồng nhau từ i đến j và j đến k là:
AĐáp án A: O(n)
BĐáp án B: O(n^2)
CĐáp án C: O(n^3)
DĐáp án D: O(log n)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:C
Đáp án: C
Giải thích: Hàm Mystery(n) có ba vòng lặp lồng nhau, do đó độ phức tạp thời gian của nó là O(n^3).
Câu 6
1 điểm
Nếu thời gian thực hiện thuật toán sắp xếp chọn là 1 giây, giá trị lớn nhất của n sẽ là: