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

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

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

Độ phức tạp không gian đo lường:

1. ASố dòng mã
2. BLượng bộ nhớ một thuật toán cần khi đầu vào tăng
3. CKích thước vật lý của máy tính
4. DDung lượng đĩa của tệp chương trình sau khi được biên dịch

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
2. Bf tăng chậm hơn g một cách nghiêm ngặt
3. Cf tăng nhanh hơn g một cách nghiêm ngặt
4. Df luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ACác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
2. BSắp xếp trộn không có cấu trúc đệ quy
3. CSắp xếp trộn đã là O(n)
4. DQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

1. AO(n + k)
2. BO(n log n + k log n)
3. CO(nk)
4. DO(k n log 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 bắt đầu sớm nhất
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 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

Điều gì sẽ xảy ra nếu ai đó tìm được thuật toán thời gian đa thức cho một bài toán NP-đầy đủ?

1. AMọi thuật toán thời gian hàm mũ sẽ lập tức chạy trong thời gian tuyến tính
2. BChỉ bài toán đó chuyển vào P
3. CMọi bài toán trong NP đều giải được trong thời gian đa thức, nên P = NP
4. DBài toán dừng trở nên quyết định được

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AViệc chọn chỉ có thể thực hiện trong O(n²)
2. BViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp
3. CQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
4. DQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất