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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ATrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
2. BDòng đầu tiên của hàm
3. CLời gọi dùng nhiều bộ nhớ nhất
4. DTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

1. AO(n)
2. BO(1)
3. CO(log 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²)

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

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

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BCác bài toán con chồng lặp và cấu trúc con tối ưu
3. CChỉ các đầu vào ngẫu nhiên
4. DHoàn toàn không có bài toán con, nên có thể giải trong một bước

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

Cận nào là đúng cho log(n!)?

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