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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp trộn
2. BQuicksort
3. CSắp xếp chèn
4. DSắp xếp nổi bọt

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

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

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

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

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

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

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

Một thuật toán tham lam:

1. AThử mọi lời giải có thể
2. BLuôn cho lời giải tối ưu
3. CĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
4. DChỉ dùng đệ quy

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. BChọn pivot đồng đều ngẫu nhiên
3. CLuôn chọn phần tử đầu tiên
4. DChỉ dùng đệ quy ở phía bên trái

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ASau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không
2. BNó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách
3. CNó kiểm tra xem có cạnh nào có trọng số âm không
4. DNó đếm các chu trình bằng tìm kiếm theo chiều sâu