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

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

1. AChia để trị
2. BLựa chọn tham lam
3. CVét cạn
4. DQuy hoạch động

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
2. BBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
3. CBài toán có thể giải trong thời gian hằng số
4. DMọi bài toán con đều có cùng kích thước

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó tự động trả về 0
2. BTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn
3. CNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
4. DNó chạy trong thời gian O(1)

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

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

Bài toán dừng cho thấy rằng:

1. AKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không
2. BMọi chương trình cuối cùng đều dừng
3. CMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng
4. DNên tránh các vòng lặp

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

1. AΘ(n)
2. BΘ(n²)
3. CΘ(n log² n)
4. DΘ(n log n)