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 tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. AThời gian chạy của nó không tăng theo kích thước đầu vào
2. BNó xử lý đúng một phần tử mỗi giây thời gian chạy
3. CNó luôn mất đúng một giây
4. DNó chỉ có thể chạy một lần

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ó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
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ó tự động trả về 0
4. DNó chạy trong thời gian O(1)

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
2. BChọn hoạt động bắt đầu sớm nhất
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích

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

1. ABà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 đó
2. BMộ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
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

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

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

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. ANó rơi vào vòng lặp vô hạn ở mọi cạnh âm
2. BNó chỉ hoạt động trên đồ thị vô hướng
3. CSố âm không thể lưu trong hàng đợi ưu tiên
4. DMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn