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

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

Thuật toán vét cạn là gì?

1. AThuật toán thử mọi lời giải ứng viên có thể
2. BThuật toán luôn dùng đệ quy
3. CThuật toán đoán một đáp án ngẫu nhiên
4. DThuật toán chạy trên nhiều bộ xử lý

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó tự động trả về 0
2. BNó chạy trong thời gian O(1)
3. CNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
4. DTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toà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(log n)
2. BO(n²)
3. CO(n)
4. DO(n log n)

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(d(n + k))
2. BO(dn log k)
3. CO(n²)
4. DO(n log n)

Phát biểu nào về P và NP là đúng?

1. ANP có nghĩa là "không đa thức"
2. BCác bài toán NP không thể được kiểm chứng nhanh
3. CMọi bài toán trong P cũng thuộc NP
4. DĐã được chứng minh rằng P ≠ NP

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