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

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

1. ADòng đầu tiên của hàm
2. BTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
3. CLời gọi dùng nhiều bộ nhớ nhất
4. DTrườ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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BLựa chọn tham lam
3. CChia để trị
4. DVét cạn

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn log n)
4. DO(mn)

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. ATuyến tính
2. BHàm mũ
3. CLogarit
4. DHằng số

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ó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
3. CNó 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
4. DNó xóa cạnh đắt nhất cho đến khi không còn chu trình

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ọn pivot đồng đều ngẫu nhiên
2. BChỉ dùng đệ quy ở phía bên trái
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DLuôn chọn phần tử đầu tiên

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ABài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ
2. BBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
3. CBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
4. DCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán