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

Thuật toán là gì?

1. AMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
2. BMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
3. CBất kỳ chương trình máy tính nào có giao diện đồ họa
4. DMột cấu trúc dữ liệu lưu trữ các số

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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AĐộ dài mảng phải là lũy thừa của hai
2. BMảng phải được sắp xếp
3. CMảng không được có quá 1000 phần tử
4. DMảng chỉ được chứa số dương

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

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

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

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 ngắn nhất trước
2. BChọ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
3. CChọ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
4. DChọn hoạt động bắt đầu sớm nhất

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

1. AChứng minh X kiểm chứng được 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. CQuy dẫn X về một bài toán NP-khó đã biết 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

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ALuôn chọn phần tử đầu tiên
2. BChọn pivot đồng đều ngẫu nhiên
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DChỉ dùng đệ quy ở phía bên trái