Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n / 2
2. BKhoảng n²
3. CKhoảng n
4. DKhoảng log₂ 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 nổi bọt
2. BQuicksort
3. CSắp xếp chèn
4. DSắp xếp trộn

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ATrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
2. BDòng đầu tiên của hàm
3. CTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
4. DLời gọi dùng nhiều bộ nhớ nhất

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

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

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

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
2. BCác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
3. CCác bài toán cần thời gian hàm mũ trên mọi máy tính
4. DCác bài toán có thể giải song song

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. AMộ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
2. BNó rơi vào vòng lặp vô hạn ở mọi cạnh âm
3. CSố âm không thể lưu trong hàng đợi ưu tiên
4. DNó chỉ hoạt động trên đồ thị vô hướng