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

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

1. ANó 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
2. BNó chia mảng làm đôi rồi trộn lại
3. CNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
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

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V + E)
2. BO(V × E)
3. CO(E log V)
4. DO(V²)

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng log₂ n
2. BKhoảng n
3. CKhoảng n / 2
4. DKhoảng n²

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

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BCác bài toán con chồng lặp và cấu trúc con tối ưu
3. CChỉ các đầu vào ngẫu nhiên
4. DHoàn toàn không có bài toán con, nên có thể giải trong một bước

Độ 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(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó bất khả quyết định
2. BNó là NP-khó
3. CNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
4. DNó luôn giải được trong O(V + E)

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. AHàm băm chậm
2. BMảng có truy cập O(n)
3. CCác khóa phải được sắp xếp trước
4. DNhiều khóa có thể va chạm vào cùng một ngăn