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

Sắp xếp chọn hoạt động như thế nào?

1. ANó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
2. BNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
3. CNó chia mảng làm đôi rồi trộn lại
4. DNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BVét cạn
3. CChia để trị
4. DLựa chọn tham lam

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²)

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BTìm kiếm theo chiều sâu
3. CThuật toán Kruskal
4. DThuật toán Dijkstra

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ó chạy trong thời gian O(1)
2. BTrì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
3. CNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
4. DNó tự động trả về 0

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
2. BThứ tự tô-pô trong mọi đồ thị
3. CĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
4. DCây khung nhỏ nhất

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. ATối đa log n lần giá trị nhỏ nhất
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. DKhông rõ chất lượng so với tối ưu

Phát biểu nào về ký hiệu little-o là đúng?

1. An² = o(n)
2. B2n = o(n), vì 2n tăng chậm
3. Cn = o(n), vì mọi hàm đều là little-o của chính nó
4. Dn = o(n²), nhưng n không phải o(n)