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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian tối đa nó mất trên mọi đầu vào kích thước n
2. BThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
3. CThời gian nó mất trên một máy tính chậm
4. DThời gian nó mất trên đầu vào nhỏ nhất

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 dãy hữu hạn các bước được xác định rõ để giải một bài toán
4. DMột cấu trúc dữ liệu lưu trữ các số

Độ 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(n)
3. CO(log n)
4. DO(n²)

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

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 Dijkstra
2. BThuật toán Kruskal
3. CThuật toán Prim bắt đầu từ một nút
4. DFloyd–Warshall

Một bài toán là NP-đầy đủ nếu nó:

1. ANằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng
2. BThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
3. CGiải được trong thời gian đa thức
4. DKhông thể giải được