Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1):
Trả lờ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.
Câu hỏi liên quan
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:
Đáp án đúng: A
Để xác định giá trị của biểu thức logic A = (p→q) ∧ (¬r ∨ ¬q), chúng ta cần xem xét tất cả các trường hợp có thể xảy ra của các biến mệnh đề p, q và r. Vì biểu thức chứa cả phép kéo theo (→), phép phủ định (¬) và phép hội (∧), phép tuyển (∨), nên giá trị của A phụ thuộc vào giá trị của các biến này.
Tuy nhiên, chúng ta không có thông tin cụ thể về giá trị của p, q và r. Do đó, giá trị của A không thể xác định là luôn đúng (1) hoặc luôn sai (0). Giá trị của A thay đổi tùy theo giá trị của p, q, và r.
Ví dụ:
- Nếu p = True, q = True, r = True: A = (True → True) ∧ (¬True ∨ ¬True) = 1 ∧ (0 ∨ 0) = 1 ∧ 0 = 0
- Nếu p = True, q = False, r = True: A = (True → False) ∧ (¬True ∨ ¬False) = 0 ∧ (0 ∨ 1) = 0 ∧ 1 = 0
- Nếu p = False, q = True, r = False: A = (False → True) ∧ (¬False ∨ ¬True) = 1 ∧ (1 ∨ 0) = 1 ∧ 1 = 1
Vì giá trị của A phụ thuộc vào các giá trị của p, q và r mà chúng ta không biết, nên chúng ta không thể xác định được giá trị cụ thể của A.
Tuy nhiên, chúng ta không có thông tin cụ thể về giá trị của p, q và r. Do đó, giá trị của A không thể xác định là luôn đúng (1) hoặc luôn sai (0). Giá trị của A thay đổi tùy theo giá trị của p, q, và r.
Ví dụ:
- Nếu p = True, q = True, r = True: A = (True → True) ∧ (¬True ∨ ¬True) = 1 ∧ (0 ∨ 0) = 1 ∧ 0 = 0
- Nếu p = True, q = False, r = True: A = (True → False) ∧ (¬True ∨ ¬False) = 0 ∧ (0 ∨ 1) = 0 ∧ 1 = 0
- Nếu p = False, q = True, r = False: A = (False → True) ∧ (¬False ∨ ¬True) = 1 ∧ (1 ∨ 0) = 1 ∧ 1 = 1
Vì giá trị của A phụ thuộc vào các giá trị của p, q và r mà chúng ta không biết, nên chúng ta không thể xác định được giá trị cụ thể của A.
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
