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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
2. BThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n
3. CThời gian cho một đầu vào có độ dài trung bình
4. DThời gian trên loại máy tính phổ biến nhất

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. AThời gian chạy của nó không tăng theo kích thước đầu vào
2. BNó xử lý đúng một phần tử mỗi giây thời gian chạy
3. CNó chỉ có thể chạy một lần
4. DNó luôn mất đúng một giây

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ó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
3. CNó chạy trong thời gian O(1)
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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
2. BNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
3. CNó xóa cạnh đắt nhất cho đến khi không còn chu trình
4. DNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS

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

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. A2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
2. B3-SAT, trong đó mỗi mệnh đề có đúng ba literal
3. CSAT tổng quát trên các công thức dạng chuẩn tắc hội
4. DThỏa mãn mạch

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ATìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
2. BĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
3. CDanh sách liên kết không thể được sắp xếp
4. DCác phép so sánh trên nút danh sách liên kết chậm hơn