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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. AHằng số
2. BLogarit
3. CBậc hai
4. DTuyến tính

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

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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BVét cạn
3. CLựa chọn tham lam
4. DChia để trị

Thuật toán sắp xếp nào là ổn định?

1. AQuicksort (phiên bản tại chỗ điển hình)
2. BSắp xếp trộn
3. CSắp xếp vun đống
4. DSắp xếp chọn (phiên bản điển hình)

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp

Đườ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ó là NP-khó
2. BNó luôn giải được trong O(V + E)
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

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. A2ⁿ tăng nhanh hơn n!
2. Bn! là O(n²)
3. CChúng tăng với cùng tốc độ
4. Dn! tăng nhanh hơn 2ⁿ