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 theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

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

Độ phức tạp không gian đo lường:

1. ADung lượng đĩa của tệp chương trình sau khi được biên dịch
2. BKích thước vật lý của máy tính
3. CLượng bộ nhớ một thuật toán cần khi đầu vào tăng
4. DSố dòng 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. BLogarit
3. CBậc hai
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ó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó 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
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ó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ADanh sách liên kết không thể được sắp xếp
2. BĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
3. CCác phép so sánh trên nút danh sách liên kết chậm hơn
4. DTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ

Điều gì sẽ xảy ra nếu ai đó tìm được thuật toán thời gian đa thức cho một bài toán NP-đầy đủ?

1. AMọi thuật toán thời gian hàm mũ sẽ lập tức chạy trong thời gian tuyến tính
2. BChỉ bài toán đó chuyển vào P
3. CMọi bài toán trong NP đều giải được trong thời gian đa thức, nên P = NP
4. DBài toán dừng trở nên quyết định được