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

Độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp trộn là gì?

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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

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 là O(n log n) trong trường hợp xấu nhất
2. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắ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
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

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. BKhông rõ chất lượng so với tối ưu
3. CLuôn là một phủ đỉnh nhỏ nhất
4. DTối đa log n lần giá trị nhỏ nhất

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. ANó chỉ hoạt động trên đồ thị vô hướng
2. BSố âm không thể lưu trong hàng đợi ưu tiên
3. CNó rơi vào vòng lặp vô hạn ở mọi cạnh âm
4. DMộ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