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 nhị phân trên một mảng đã sắp xếp là gì?

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

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

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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ALời gọi dùng nhiều bộ nhớ nhất
2. BDòng đầu tiên của hàm
3. CTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
4. DTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BSắp xếp chọn (phiên bản điển hình)
3. CSắp xếp trộn
4. DQuicksort (phiên bản tại chỗ điển hình)

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn 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. AThuật toán Kruskal
2. BThuật toán Dijkstra
3. CTìm kiếm theo chiều sâu
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

Điều gì sẽ xảy ra nếu ai đó tìm được thuật toán thời gian đa thức cho một bài toán NP-đầy đủ?

1. AMọi thuật toán thời gian hàm mũ sẽ lập tức chạy trong thời gian tuyến tính
2. BChỉ bài toán đó chuyển vào P
3. CBài toán dừng trở nên quyết định được
4. DMọi bài toán trong NP đều giải được trong thời gian đa thức, nên P = NP

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMọi phần tử phải được so sánh ít nhất một lần
2. BTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh
3. CMỗi phép so sánh mất thời gian logarit
4. DMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n