Cho đồ thị vô hướng G = (V,E), khẳng định nào dưới đây là đúng?
A.
Thuật toán BFS(u) duyệt tất cả các thành phần liên thông của đồ thị
B.
Thuật toán BFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị
C.
Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u
D.
Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần
Trả lời:
Đáp án đúng: C
Phân tích câu hỏi:
Câu hỏi này kiểm tra kiến thức về thuật toán BFS (Breadth-First Search) trên đồ thị vô hướng, đặc biệt là khả năng của nó trong việc duyệt các thành phần liên thông.
Đánh giá các phương án:
- Phương án 1: "Thuật toán BFS(u) duyệt tất cả các thành phần liên thông của đồ thị" - Sai. BFS(u) chỉ duyệt thành phần liên thông chứa đỉnh u. Nếu đồ thị có nhiều thành phần liên thông, BFS(u) sẽ không duyệt hết.
- Phương án 2: "Thuật toán BFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị" - Sai. BFS(u) chỉ tìm được đường đi giữa hai đỉnh nếu chúng thuộc cùng một thành phần liên thông. Nếu không, đường đi sẽ không tồn tại.
- Phương án 3: "Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u" - Đúng. Đây là đặc điểm cơ bản của thuật toán BFS. BFS bắt đầu từ đỉnh u và duyệt tất cả các đỉnh có thể đạt được từ u, tức là các đỉnh trong cùng thành phần liên thông với u.
- Phương án 4: "Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần" - Sai. Điều này chỉ đúng nếu đồ thị liên thông và ta bắt đầu BFS từ một đỉnh bất kỳ. Nếu đồ thị không liên thông, BFS(u) sẽ chỉ duyệt thành phần liên thông chứa u.
Kết luận:
Phương án đúng nhất là phương án 3.
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
Câu hỏi liên quan
Lời giải:
Đáp án đúng: B
Đa đồ thị vô hướng là đồ thị có thể chứa cạnh bội (nhiều cạnh nối cùng một cặp đỉnh). Nó có thể hoặc không có khuyên (cạnh nối một đỉnh với chính nó). Do đó, khẳng định chắc chắn đúng là G chứa cạnh bội.
Lời giải:
Đáp án đúng: C
Đỉnh cô lập là đỉnh không có cạnh nào nối tới nó, tức là bậc của đỉnh bằng 0.
Lời giải:
Đáp án đúng: B
Đỉnh 1 có bậc 3 (kết nối với 3 đỉnh khác).
Đỉnh 2 có bậc 4 (kết nối với 4 đỉnh khác).
Đỉnh 3 có bậc 6 (kết nối với 6 đỉnh khác).
Đỉnh 4 có bậc 4 (kết nối với 4 đỉnh khác).
Đỉnh 5 có bậc 4 (kết nối với 4 đỉnh khác).
Vậy, đáp án đúng là 3, 4, 6, 4, 4.
Đỉnh 2 có bậc 4 (kết nối với 4 đỉnh khác).
Đỉnh 3 có bậc 6 (kết nối với 6 đỉnh khác).
Đỉnh 4 có bậc 4 (kết nối với 4 đỉnh khác).
Đỉnh 5 có bậc 4 (kết nối với 4 đỉnh khác).
Vậy, đáp án đúng là 3, 4, 6, 4, 4.
Lời giải:
Đáp án đúng: D
Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh I, ta duyệt các đỉnh kề với I là A, C, E, G. Tiếp theo, duyệt các đỉnh kề với A là B, D. Sau đó, duyệt các đỉnh kề với C là F. Tiếp tục duyệt các đỉnh kề với E là H. Duyệt đỉnh kề với G là K. Như vậy, thứ tự duyệt là I, A, C, E, G, B, D, F, H, K.
Lời giả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
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
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
