Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là:
Trả lời:
Đáp án đúng: B
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 từng nhánh của đồ thị cho đến khi không còn đỉnh kề chưa được thăm, sau đó quay lui (backtrack) để khám phá các nhánh khác.
Trong trường hợp này, bắt đầu từ đỉnh G, ta có thể duyệt theo thứ tự sau:
1. **G:** Bắt đầu từ đỉnh G.
2. **H:** Duyệt đến đỉnh H kề với G.
3. **N:** Duyệt đến đỉnh N kề với H.
4. **K:** Duyệt đến đỉnh K kề với N.
5. **B:** Duyệt đến đỉnh B kề với K.
6. **A:** Duyệt đến đỉnh A kề với B.
7. **C:** Duyệt đến đỉnh C kề với A.
8. **D:** Duyệt đến đỉnh D kề với C.
9. **E:** Duyệt đến đỉnh E kề với D.
10. **I:** Duyệt đến đỉnh I kề với K.
11. **F:** Duyệt đến đỉnh F kề với E.
Vậy, thứ tự duyệt đúng là: G, H, N, K, B, A, C, D, E, I, F
Câu hỏi liên quan
Lời giải:
Đáp án đúng: A
Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh 1:
1. Đỉnh 1: Bắt đầu từ đỉnh 1.
2. Các đỉnh kề của 1: Duyệt các đỉnh kề của 1 là 2, 4, 7.
3. Đỉnh 2:
4. Đỉnh 4:
5. Đỉnh 7:
6. Các đỉnh kề của 2: Duyệt các đỉnh kề của 2 là 3, 6.
7. Đỉnh 3:
8. Đỉnh 6:
9. Các đỉnh kề của 4: Duyệt các đỉnh kề của 4 là 8, 5, 9.
10. Đỉnh 8:
11. Đỉnh 5:
12. Đỉnh 9:
13. Các đỉnh kề của 7: Duyệt các đỉnh kề của 7 là 10.
14. Đỉnh 10:
Vậy thứ tự duyệt các đỉnh là: 1, 2, 4, 7, 3, 6, 8, 5, 9, 10.
1. Đỉnh 1: Bắt đầu từ đỉnh 1.
2. Các đỉnh kề của 1: Duyệt các đỉnh kề của 1 là 2, 4, 7.
3. Đỉnh 2:
4. Đỉnh 4:
5. Đỉnh 7:
6. Các đỉnh kề của 2: Duyệt các đỉnh kề của 2 là 3, 6.
7. Đỉnh 3:
8. Đỉnh 6:
9. Các đỉnh kề của 4: Duyệt các đỉnh kề của 4 là 8, 5, 9.
10. Đỉnh 8:
11. Đỉnh 5:
12. Đỉnh 9:
13. Các đỉnh kề của 7: Duyệt các đỉnh kề của 7 là 10.
14. Đỉnh 10:
Vậy thứ tự duyệt các đỉnh là: 1, 2, 4, 7, 3, 6, 8, 5, 9, 10.
Lời giải:
Đáp án đúng: B
Thuật toán DFS (Depth-First Search) hay còn gọi là tìm kiếm theo chiều sâu, là một thuật toán duyệt hoặc tìm kiếm trên các cấu trúc dữ liệu đồ thị. Thuật toán bắt đầu tại một đỉnh gốc (trong trường hợp này là đỉnh 10) và khám phá sâu nhất có thể dọc theo mỗi nhánh trước khi quay lui.
Trong đồ thị đã cho, bắt đầu từ đỉnh 10, ta có thể duyệt theo các bước sau:
1. 10: Bắt đầu từ đỉnh 10.
2. 4: Từ 10, duyệt đến 4 (hoặc 5, thứ tự duyệt có thể khác nhau tùy thuộc vào cách cài đặt, nhưng kết quả cuối cùng phải tuân theo DFS).
3. 5: Từ 4, có thể duyệt đến 5.
4. 1: Từ 5, có thể duyệt đến 1.
5. 2: Từ 1, duyệt đến 2.
6. 3: Từ 2, duyệt đến 3.
7. 6: Từ 3, duyệt đến 6.
8. 9: Từ 6, duyệt đến 9.
9. 8: Từ 9, duyệt đến 8.
10. 7: Từ 8, duyệt đến 7.
Như vậy, kết quả của thuật toán DFS(10) là: 10, 4, 5, 1, 2, 3, 6, 9, 8, 7
Trong đồ thị đã cho, bắt đầu từ đỉnh 10, ta có thể duyệt theo các bước sau:
1. 10: Bắt đầu từ đỉnh 10.
2. 4: Từ 10, duyệt đến 4 (hoặc 5, thứ tự duyệt có thể khác nhau tùy thuộc vào cách cài đặt, nhưng kết quả cuối cùng phải tuân theo DFS).
3. 5: Từ 4, có thể duyệt đến 5.
4. 1: Từ 5, có thể duyệt đến 1.
5. 2: Từ 1, duyệt đến 2.
6. 3: Từ 2, duyệt đến 3.
7. 6: Từ 3, duyệt đến 6.
8. 9: Từ 6, duyệt đến 9.
9. 8: Từ 9, duyệt đến 8.
10. 7: Từ 8, duyệt đến 7.
Như vậy, kết quả của thuật toán DFS(10) là: 10, 4, 5, 1, 2, 3, 6, 9, 8, 7
Lời giải:
Đáp án đúng: C
Biểu thức (P ∧ Q) → (P ∨ Q) tương đương logic với ¬(P ∧ Q) ∨ (P ∨ Q). Ta có thể viết lại như sau: (¬P ∨ ¬Q) ∨ (P ∨ Q). Sau đó, sắp xếp lại thành (¬P ∨ P) ∨ (¬Q ∨ Q), biểu thức này luôn đúng (True).
Phương án C: ¬(P ∧ Q) ∨ (P ∨ Q) tương đương với (¬P ∨ ¬Q) ∨ (P ∨ Q) tương đương với (¬P ∨ P) ∨ (¬Q ∨ Q) tương đương với True.
Phương án C: ¬(P ∧ Q) ∨ (P ∨ Q) tương đương với (¬P ∨ ¬Q) ∨ (P ∨ Q) tương đương với (¬P ∨ P) ∨ (¬Q ∨ Q) tương đương với True.
tương đương logic với mệnh đề nào sau đây?Lời giải:
Đáp án đúng: C
Ta có mệnh đề gốc là P → Q. Mệnh đề tương đương với P → Q là ¬P ∨ Q. Phân tích các đáp án:
* Đáp án A: P ∧ Q không tương đương với P → Q.
* Đáp án B: ¬P ∨ Q tương đương với P → Q.
* Đáp án C: P ∨ Q không tương đương với P → Q.
* Đáp án D: P ∧ ¬Q không tương đương với P → Q.
* Đáp án A: P ∧ Q không tương đương với P → Q.
* Đáp án B: ¬P ∨ Q tương đương với P → Q.
* Đáp án C: P ∨ Q không tương đương với P → Q.
* Đáp án D: P ∧ ¬Q không tương đương với P → Q.
Lời giải:
Đáp án đúng: A
Bảng chân trị của một biểu thức logic E(q1, q2, ..., qn) là một bảng liệt kê tất cả các giá trị (chân trị) của biểu thức E tương ứng với mọi trường hợp có thể về chân trị của các biến mệnh đề q1, q2, ..., qn. Ví dụ, nếu có hai biến mệnh đề (n=2), ta sẽ có 22 = 4 trường hợp về chân trị của các biến này, và bảng chân trị sẽ chỉ ra giá trị của biểu thức E cho mỗi trường hợp đó.
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
