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 trung bình mô tả điều gì?

1. AThời gian cho một đầu vào có độ dài trung bình
2. BThời gian trên loại máy tính phổ biến nhất
3. CGiá 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
4. DThờ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

Sắp xếp chọn hoạt động như thế nào?

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
3. CNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
4. DNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu

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

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

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

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

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

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

1. ANó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
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ó 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

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

1. AGiải được trong thời gian đa thức
2. BKhông thể giải được
3. CThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
4. DNằ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

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. AChỉ dùng đệ quy ở phía bên trái
2. BSắp xếp đầu vào trước khi chạy quicksort
3. CChọn pivot đồng đều ngẫu nhiên
4. DLuôn chọn phần tử đầu tiên