Phiếu bài tập Thuật toán và độ phức tạp có đáp á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²)

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 đầu vào nhỏ nhất
4. DThời gian nó mất trên một máy tính chậm

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ATuyến tính
2. BHằng số
3. CLogarit
4. DBậc hai

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
2. BSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 100
2. BKhoảng 500,000
3. CKhoảng 20
4. DKhoảng 1,000

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

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. ASố âm không thể lưu trong hàng đợi ưu tiên
2. BNó rơi vào vòng lặp vô hạn ở mọi cạnh âm
3. CMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn
4. DNó chỉ hoạt động trên đồ thị vô hướng

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ACó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
2. BLuôn là một phủ đỉnh nhỏ nhất
3. CKhông rõ chất lượng so với tối ưu
4. DTối đa log n lần giá trị nhỏ nhất