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. AQuicksort
2. BSắp xếp nổi bọt
3. CSắp xếp trộn
4. DSắp xếp vun đống

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

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

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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
2. BNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
3. CNó xóa cạnh đắt nhất cho đến khi không còn chu trình
4. DNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 100
2. BKhoảng 20
3. CKhoảng 500,000
4. DKhoảng 1,000

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(2ⁿ) và không gian O(1)
3. CThời gian O(log n) và không gian O(n)
4. DThời gian O(n) và không gian O(1)

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó luôn giải được trong O(V + E)
2. BNó là NP-khó
3. CNó bất khả quyết định
4. DNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu