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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp trộn
2. BSắp xếp nổi bọt
3. CSắp xếp vun đống
4. DQuicksort

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

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

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ALogarit luôn được làm tròn thành số nguyên
2. BCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
3. CCơ số chỉ quan trọng với n nhỏ
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. AHằng số
2. BHàm mũ
3. CTuyến tính
4. DLogarit

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì n luôn nhỏ
2. BVì nó chỉ hoạt động khi W = 0
3. CVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
4. DW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W