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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Độ 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(1)
2. BO(n log n)
3. CO(n)
4. DO(log 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 vun đống
2. BSắp xếp nổi bọt
3. CQuicksort
4. DSắp xếp trộn

Công thức truy hồi T(n) = T(n − 1) + O(1) có nghiệm là gì?

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

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
2. BNó chạy trong thời gian O(1)
3. CNó tự động trả về 0
4. DTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
2. BNó xóa cạnh đắt nhất cho đến khi không còn chu trình
3. CNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
4. DNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây

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 + E) log V)
3. CO(V + E)
4. DO(V³)

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. AKhông rõ chất lượng so với tối ưu
2. BLuôn là một phủ đỉnh nhỏ nhất
3. CCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
4. DTối đa log n lần giá trị nhỏ nhất