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

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

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

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A6 giây
2. B9 giây
3. C3 giây
4. D12 giây

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

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

1. ASắp xếp chọn (phiên bản điển hình)
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 vun đống

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n² log n)
4. DΘ(n²)

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Dijkstra
2. BThuật toán Prim bắt đầu từ một nút
3. CThuật toán Kruskal
4. DFloyd–Warshall