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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B12
3. C10
4. D512

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian tối đa nó mất trên mọi đầu vào kích thước n
2. BThời gian nó mất trên một máy tính chậm
3. CThời gian nó mất trên đầu vào nhỏ nhất
4. DThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. AHằng số
2. BLogarit
3. CTuyến tính
4. DBậc hai

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
4. DCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử

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(log n)
3. CO(n log n)
4. DO(n)

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Công thức truy hồi T(n) = 2T(n/2) + n log n có nghiệm là gì?

1. AΘ(n²)
2. BΘ(n log² n)
3. CΘ(n)
4. DΘ(n log n)

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó bất khả quyết định
2. BNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
3. CNó là NP-khó
4. DNó luôn giải được trong O(V + E)