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. ADòng đầu tiên của hàm
2. BLời gọi dùng nhiều bộ nhớ nhất
3. CTrườ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
4. DTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Đệ quy là gì?

1. AMột vòng lặp không bao giờ kết thúc
2. BMột hàm gọi chính nó trên các đầu vào nhỏ hơn
3. CMột loại cấu trúc dữ liệu
4. DMột phương pháp sắp xếp

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

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n
2. BKhoảng log₂ n
3. CKhoảng n / 2
4. DKhoảng √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)
3. CO(n log n)
4. DO(log n)

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. A3-SAT, trong đó mỗi mệnh đề có đúng ba literal
2. BThỏa mãn mạch
3. C2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
4. DSAT tổng quát trên các công thức dạng chuẩn tắc hội

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức
2. BChứng minh X kiểm chứng được trong thời gian đa thức
3. CQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
4. DChứng minh X không có thuật toán đa thức cho đầu vào nhỏ