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 tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó chỉ có thể được giải bằng cách thử mọi khả năng
2. BNó có thể được giải trong thời gian đa thức
3. CNó có thể được giải trong thời gian hằng số
4. DNó không có lời giải

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

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. AQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
2. BCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
3. CSắp xếp trộn không có cấu trúc đệ quy
4. DSắp xếp trộn đã là O(n)

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ALogarit luôn được làm tròn thành số nguyên
2. BMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DCơ số chỉ quan trọng với n nhỏ

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. AThuật toán Kruskal
2. BTìm kiếm theo chiều sâu
3. CThuật toán Dijkstra
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

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

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

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ASắp xếp đầu vào trước khi chạy quicksort
2. BLuôn chọn phần tử đầu tiên
3. CChọn pivot đồng đều ngẫu nhiên
4. DChỉ dùng đệ quy ở phía bên trái