10 câu hỏi
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 được xác định bởi yếu tố nào?
Kích thước dữ liệu đầu vào
Ngôn ngữ lập trình
Kỹ năng lập trình viên
Thời gian thực hiện cụ thể của thuật toán
Độ phức tạp thời gian tuyến tính được ký hiệu là gì?
O(1)
O(log n)
O(n)
O(n^2)
Phép toán nào được coi là phép toán sơ cấp?
Phép cộng hai số
Phép lặp
Phép lựa chọn
Phép khai căn
Thuật toán nào sau đây có độ phức tạp thời gian hằng số?
Tìm kiếm một phần tử trong danh sách
Tính tổng dãy số từ 1 đến n bằng công thức
Sắp xếp một danh sách số
Tính giai thừa của n
Khi ước lượng độ phức tạp thời gian của thuật toán, quy tắc nào được áp dụng?
Chỉ giữ lại các phép toán có bậc thấp nhất
Bỏ qua các hằng số nhân
Chỉ xem xét các phép toán không sơ cấp
Tính tổng tất cả các phép toán thực hiện
Trong trường hợp nào thuật toán có thể có độ phức tạp thời gian tuyến tính?
Tìm số lớn nhất trong một dãy số không tăng
Sắp xếp một danh sách số ngẫu nhiên
Tìm kiếm một phần tử cụ thể trong danh sách
Tính giai thừa của một số
Phép toán nào không được coi là sơ cấp?
Phép nhân hai số
Phép lặp qua một dãy số
Phép so sánh hai giá trị
Phép khai thác giá trị tuyệt đối
Cách nào được coi là ước lượng làm giả thêm?
Tính toán độ phức tạp thực tế của một thuật toán
Tìm số phép toán tối thiểu và tối đa cần thiết cho một thuật toán
Xác định ước lượng trung bình cho tất cả các trường hợp
Lựa chọn phương pháp ước lượng đảm bảo không vượt quá giá trị ước tính
Khi nào độ phức tạp thời gian của thuật toán là O(n^2)?
Khi thực hiện một lần lặp qua n phần tử
Khi thực hiện hai lần lặp lồng nhau qua n phần tử
Khi thực hiện tìm kiếm nhị phân
Khi thực hiện phép cộng n số
Đặc điểm nào sau đây không thuộc về độ phức tạp thời gian hằng số?
T(n) = C với C là một hằng số
Số phép toán thực hiện không phụ thuộc vào kích thước n
Được ký hiệu là O(1)
Số phép toán tăng theo kích thước n