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 trộn
3. CSắp xếp nổi bọt
4. DQuicksort

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ABậc hai
2. BTuyến tính
3. CHằng số
4. DLogarit

log₂ 1024 bằng bao nhiêu?

1. A10
2. B512
3. C32
4. D12

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. AThuật toán Dijkstra
2. BBắt buộc phải dùng Bellman–Ford trong mọi trường hợp
3. CThuật toán Kruskal
4. DTìm kiếm theo chiều sâu

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp chọn (phiên bản điển hình)
2. BSắp xếp trộn
3. CQuicksort (phiên bản tại chỗ điển hình)
4. DSắp xếp vun đống

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMọi phần tử phải được so sánh ít nhất một lần
2. BMỗi phép so sánh mất thời gian logarit
3. CTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh
4. DMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(n) và không gian O(n)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(log n) và không gian O(n)
4. DThời gian O(2ⁿ) và không gian O(1)