Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Big O của 3n² + 5n + 2 là gì?

1. AO(5n)
2. BO(3n²)
3. CO(n²)
4. DO(n³)

Thuật toán vét cạn là gì?

1. AThuật toán chạy trên nhiều bộ xử lý
2. BThuật toán thử mọi lời giải ứng viên có thể
3. CThuật toán luôn dùng đệ quy
4. DThuật toán đoán một đáp án ngẫu nhiên

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

1. AO(1)
2. BO(log n)
3. CO(n)
4. DO(n log n)

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

1. AO(n)
2. BO(n log n)
3. CO(log n)
4. DO(n²)

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

1. AO(n²)
2. BO(n)
3. CO(n² log n)
4. DO(n³)

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CMột cây khung nhỏ nhất trong O(E log V)
4. DMột thứ tự tô-pô trong O(V²)

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị vô hướng
2. BĐồ thị đầy đủ
3. CĐồ thị có hướng không chu trình
4. DĐồ thị có trọng số âm

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMỗi phép so sánh mất thời gian logarit
2. BTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh
3. CMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
4. DMọi phần tử phải được so sánh ít nhất một lần