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

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
2. BGiải phóng bộ nhớ sau khi một hàm trả về
3. CTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
4. DLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A12 giây
2. B6 giây
3. C3 giây
4. D9 giây

Độ 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)

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

1. AO(2ⁿ)
2. BO(n 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³)
2. BO(n² log n)
3. CO(n²)
4. DO(n)

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Bài toán dừng cho thấy rằng:

1. AMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng
2. BNên tránh các vòng lặp
3. CKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không
4. DMọi chương trình cuối cùng đều dừng

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Kruskal
2. BThuật toán Prim bắt đầu từ một nút
3. CFloyd–Warshall
4. DThuật toán Dijkstra