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

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V × E)
2. BO(V²)
3. CO(V + E)
4. DO(E log V)

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

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

Độ phức tạp không gian đo lường:

1. ASố dòng mã
2. BDung lượng đĩa của tệp chương trình sau khi được biên dịch
3. CLượng bộ nhớ một thuật toán cần khi đầu vào tăng
4. DKích thước vật lý của máy tính

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BSắp xếp chọn (phiên bản điển hình)
3. CSắp xếp trộn
4. DQuicksort (phiên bản tại chỗ điển hình)

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 4 đồng; tối ưu là 3
2. BTham lam dùng 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 3 đồng; tối ưu là 3

Một thuật toán tham lam:

1. ALuôn cho lời giải tối ưu
2. BĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
3. CThử mọi lời giải có thể
4. DChỉ dùng đệ quy

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACái túi phân số, trong đó các món có thể bị chia nhỏ
2. BKhông biến thể nào
3. CCả hai biến thể
4. DBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên

Một bài toán là NP-đầy đủ nếu nó:

1. AGiải được trong thời gian đa thức
2. BKhông thể giải được
3. CNằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng
4. DThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức