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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Ghi nhớ (memoisation) là gì?

1. AGiải phóng bộ nhớ sau khi một hàm trả về
2. BViết chú thích bên cạnh từng dòng mã
3. CTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
4. DLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắp xếp chèn là O(n log n) trong trường hợp xấu nhất

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì n³ nhỏ hơn n² khi n lớn
2. BKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. AChọn pivot đồng đều ngẫu nhiên
2. BChỉ dùng đệ quy ở phía bên trái
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DLuôn chọn phần tử đầu tiên

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ó kiểm tra xem có cạnh nào có trọng số âm không
2. BNó đếm các chu trình bằng tìm kiếm theo chiều sâu
3. CSau 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
4. DNó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách