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 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(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E log V)

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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian tối đa nó mất trên mọi đầu vào kích thước n
2. BThời gian nó mất trên đầu vào nhỏ nhất
3. CThời gian nó mất trên một máy tính chậm
4. DThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n

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

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

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức
2. BChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
3. CChứng minh X kiểm chứng được trong thời gian đa thức
4. DQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức

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

1. ACá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
2. BCác bài toán có thể giải song song
3. CCá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
4. DCác bài toán cần thời gian hàm mũ trên mọi máy tính