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. BKhoảng n²
3. CKhoảng n / 2
4. DKhoảng log₂ n

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig Omega
2. BBig Theta
3. CLittle omega
4. DBig O

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn không có cấu trúc đệ quy
2. BCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
3. CSắp xếp trộn đã là O(n)
4. DQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BMột cây khung nhỏ nhất trong O(E log V)
3. CĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
4. DMột thứ tự tô-pô trong O(V²)

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

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ACác phép so sánh trên nút danh sách liên kết chậm hơn
2. BTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
3. CĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
4. DDanh sách liên kết không thể được sắp xếp

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n²), nhưng n không phải o(n)
2. B2n = o(n), vì 2n tăng chậm
3. Cn = o(n), vì mọi hàm đều là little-o của chính nó
4. Dn² = o(n)