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 chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp chèn
2. BSắp xếp trộn
3. CSắp xếp nổi bọt
4. DQuicksort

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó chỉ có thể chạy một lần
2. BNó luôn mất đúng một giây
3. CNó xử lý đúng một phần tử mỗi giây thời gian chạy
4. DThời gian chạy của nó không tăng theo kích thước đầu vào

Ghi nhớ (memoisation) là gì?

1. ATự độ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
2. BLư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ớ
3. CGiải phóng bộ nhớ sau khi một hàm trả về
4. DViết chú thích bên cạnh từng dòng mã

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ACác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
2. BQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
3. CSắp xếp trộn đã là O(n)
4. DSắp xếp trộn không có cấu trúc đệ quy

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

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

1. AO(n + k)
2. BO(nk)
3. CO(n log n + k log n)
4. DO(k n log n)

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

1. AO(V × E)
2. BO(V + E)
3. CO(V³)
4. DO((V + E) log V)

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Kruskal
2. BThuật toán Prim bắt đầu từ một nút
3. CFloyd–Warshall
4. DThuật toán Dijkstra