Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(I) là:
Trả lời:
Đáp án đúng: D
Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) duyệt đồ thị bằng cách đi sâu vào một nhánh đến khi không còn đỉnh kề chưa thăm, sau đó quay lui để duyệt các nhánh khác. Bắt đầu từ đỉnh I, ta có các bước như sau:
1. **I:** Bắt đầu từ đỉnh I.
2. **G:** Từ I, ta chọn một đỉnh kề chưa thăm, ví dụ G.
3. **H:** Từ G, ta chọn đỉnh kề chưa thăm, ví dụ H.
4. **N:** Từ H, ta chọn đỉnh kề chưa thăm, ví dụ N.
5. **K:** Từ N, ta chọn đỉnh kề chưa thăm, ví dụ K.
6. **B:** Từ K, ta chọn đỉnh kề chưa thăm, ví dụ B.
7. **A:** Từ B, ta chọn đỉnh kề chưa thăm, ví dụ A.
8. **C:** Từ A, ta chọn đỉnh kề chưa thăm, ví dụ C.
9. **E:** Từ C, ta chọn đỉnh kề chưa thăm, ví dụ E.
10. **F:** Từ E, ta chọn đỉnh kề chưa thăm, ví dụ F.
11. **D:** Từ F, ta chọn đỉnh kề chưa thăm, ví dụ D.
Vậy, thứ tự duyệt theo DFS(I) là: I, G, H, N, K, B, A, C, E, F, D.
So sánh với các đáp án, ta thấy đáp án 4 phù hợp nhất: I, G, H, N, K, B, A, C, E, F, D
Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!
30 câu hỏi 60 phút
