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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp vun đống
2. BSắp xếp nổi bọt
3. CQuicksort
4. DSắp xếp trộn

Sắp xếp chọn hoạt động như thế nào?

1. ANó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
2. BNó chia mảng làm đôi rồi trộn lại
3. CNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
4. DNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A12 giây
2. B9 giây
3. C3 giây
4. D6 giây

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

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

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

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

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

1. AO(n)
2. BO(2ⁿ)
3. CO(n log n)
4. DO(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. BThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
3. CKhông thể giải được
4. DNằ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

Đườ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ó luôn giải được trong O(V + E)
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ó là NP-khó