Cấu trúc dữ liệu và giải thuật: gói ôn nước rú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ì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn 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(log n) và không gian O(n)
2. BThời gian O(n) và không gian O(n)
3. CThời gian O(n) và không gian O(1)
4. DThời gian O(2ⁿ) và không gian O(1)

Duyệt thứ tự giữa (in-order) của cây tìm kiếm nhị phân thăm các khóa theo:

1. AThứ tự tăng dần đã sắp xếp
2. BLuôn luôn thứ tự giảm dần
3. CThứ tự theo mức
4. DThứ tự chèn

Bạn phải giữ k giá trị nhỏ nhất từ một luồng n số bằng bộ nhớ O(k). Cách nào chạy trong thời gian O(n log k)?

1. AMột đống max kích thước k, thay gốc của nó khi có giá trị nhỏ hơn đến
2. BMột đống min chứa tất cả n giá trị, từ đó k giá trị nhỏ nhất được lấy ra ở cuối
3. CMột mảng đã sắp xếp chứa tất cả n giá trị
4. DMột hàng đợi FIFO gồm k giá trị cuối

Đồ thị đầy đủ K₅ có bao nhiêu chu trình Hamilton khác nhau H? Các chu trình chỉ khác nhau ở đỉnh xuất phát hoặc chiều đi được tính là một.

Thuật toán Prim xây dựng một cây khung nhỏ nhất bắt đầu từ đỉnh A. Hãy nhấp vào cạnh mà nó thêm vào là cạnh số 4.

1. 1cạnh AB
2. 2cạnh AC
3. 3cạnh BC
4. 4cạnh BD
5. 5cạnh CE
6. 6cạnh DE
7. 7cạnh DF
8. 8cạnh EF