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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

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

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

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AThứ tự tô-pô trong mọi đồ thị
2. BĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
3. CĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
4. DCây khung nhỏ nhất

Đệ 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 log₂ n
2. BKhoảng √n
3. CKhoảng n / 2
4. DKhoảng n

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ó độ dài 2
4. DMột mảng đã được sắp xếp

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ANó đếm các chu trình bằng tìm kiếm theo chiều sâu
2. BSau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không
3. CNó kiểm tra xem có cạnh nào có trọng số âm không
4. DNó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách

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²)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n² log n)
4. DΘ(n³)