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 nhị phân trên một mảng đã sắp xếp là gì?

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

Thuật toán vét cạn là gì?

1. AThuật toán luôn dùng đệ quy
2. BThuật toán đoán một đáp án ngẫu nhiên
3. CThuật toán chạy trên nhiều bộ xử lý
4. DThuật toán thử mọi lời giải ứng viên có thể

Big O của 3n² + 5n + 2 là gì?

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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BSắp xếp trộn
3. CQuicksort (phiên bản tại chỗ điển hình)
4. DSắp xếp chọn (phiên bản điển hình)

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng log₂ n
2. BKhoảng √n
3. CKhoảng n / 2
4. DKhoảng n

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ACó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
2. BKhông rõ chất lượng so với tối ưu
3. CLuôn là một phủ đỉnh nhỏ nhất
4. DTối đa log n lần giá trị nhỏ 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 × E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V + E)