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

Đệ quy là gì?

1. AMột vòng lặp không bao giờ kết thúc
2. BMột phương pháp sắp xếp
3. CMột loại cấu trúc dữ liệu
4. DMột hàm gọi chính nó trên các đầu vào nhỏ hơn

Thuật toán là gì?

1. AMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
2. BBất kỳ chương trình máy tính nào có giao diện đồ họa
3. CMột cấu trúc dữ liệu lưu trữ các số
4. DMột dãy hữu hạn các bước được xác định rõ để giải một bài toán

Độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp trộn là gì?

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

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng có thứ tự ngẫu nhiên
2. BMột mảng mà các phần tử đều khác nhau
3. CMột mảng đã được sắp xếp
4. DMột mảng có độ dài 2

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 Dijkstra
4. DThuật toán Kruskal

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 20
2. BKhoảng 100
3. CKhoảng 500,000
4. DKhoảng 1,000

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. AMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn
2. BSố âm không thể lưu trong hàng đợi ưu tiên
3. CNó chỉ hoạt động trên đồ thị vô hướng
4. DNó rơi vào vòng lặp vô hạn ở mọi cạnh âm

Cận nào là đúng cho log(n!)?

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