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 + E)
3. CO(V²)
4. DO(E log V)

Truy cập một phần tử theo chỉ số trong một mảng mất:

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(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. AQuicksort
2. BSắp xếp vun đống
3. CSắp xếp trộn
4. DSắp xếp nổi bọt

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 2 đồng; tối ưu là 2
2. BTham lam dùng 4 đồng; tối ưu là 3
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 3 đồng; tối ưu là 3

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng mà các phần tử đều khác nhau
2. BMột mảng có thứ tự ngẫu nhiên
3. CMột mảng đã được sắp xếp
4. DMột mảng có độ dài 2

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n^{log₂ 7}), khoảng n^2,81
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n² log n)

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX thuộc P, và X quy dẫn về SAT
2. BX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
3. CX không có thuật toán đa thức, và X quyết định được
4. DX quy dẫn về một bài toán trong P, và X thuộc NP