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

Độ 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)
4. DO(n log n)

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

1. ALời gọi dùng nhiều bộ nhớ nhất
2. BTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
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. DDòng đầu tiên của hàm

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(E log V)
2. BO(V + E)
3. CO(V²)
4. DO(V × E)

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

1. AO(n)
2. BO(n²)
3. CO(n³)
4. DO(n log 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 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
2. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắ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
4. DSắp xếp chèn là O(n log n) trong trường hợp xấu nhất

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. ACây khung nhỏ nhất
2. BThứ tự tô-pô trong mọi đồ thị
3. CĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
4. DĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

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

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