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

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó có thể được giải trong thời gian hằng số
2. BNó không có lời giải
3. CNó có thể được giải trong thời gian đa thức
4. DNó chỉ có thể được giải bằng cách thử mọi khả năng

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

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

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 nó mất trên một máy tính chậm
2. BThời gian nó mất trên đầu vào nhỏ nhất
3. CThời gian tối đa nó mất trên mọi đầu vào kích thước n
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

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

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

Độ 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² log n)
2. BO(n)
3. CO(n³)
4. DO(n²)

Phân tích khấu hao đo lường điều gì?

1. AChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
2. BChi phí của một thuật toán trên đầu vào tốt nhất
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí kỳ vọng trên các đầu vào ngẫu nhiên

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
2. BVì nó chỉ hoạt động khi W = 0
3. CVì n luôn nhỏ
4. DVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào

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