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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Độ phức tạp không gian đo lường:

1. ALượng bộ nhớ một thuật toán cần khi đầu vào tăng
2. BKích thước vật lý của máy tính
3. CDung lượng đĩa của tệp chương trình sau khi được biên dịch
4. DSố dòng mã

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(log n)
2. BO(n)
3. CO(n²)
4. DO(n log n)

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
2. BKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn
3. CCó, vì cả hai đều là hàm mũ
4. DCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. ANó rơi vào vòng lặp vô hạn ở mọi cạnh âm
2. BSố âm không thể lưu trong hàng đợi ưu tiên
3. CMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn
4. DNó chỉ hoạt động trên đồ thị vô hướng