Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1):

1, 2, 4, 7, 3, 6, 8, 5, 9, 10

1, 7, 6, 3, 9, 8, 5, 10, 4, 2

1, 2, 6, 4, 5, 10, 9, 8, 3, 7

1, 2, 4, 7, 8, 9, 5, 10, 3, 6

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:** Thăm đỉnh 1. 2. **Các đỉnh kề với 1:** Các đỉnh kề với 1 là 2, 4, 7. Thăm các đỉnh này theo thứ tự. 3. **Đỉnh 2:** Thăm đỉnh 2. 4. **Đỉnh 4:** Thăm đỉnh 4. 5. **Đỉnh 7:** Thăm đỉnh 7. 6. **Các đỉnh kề với 2:** Đỉnh kề với 2 là 3, 6. Thăm các đỉnh này theo thứ tự. 7. **Đỉnh 3:** Thăm đỉnh 3. 8. **Đỉnh 6:** Thăm đỉnh 6. 9. **Các đỉnh kề với 4:** Đỉnh kề với 4 là 8, 5. Thăm các đỉnh này theo thứ tự. 10. **Đỉnh 8:** Thăm đỉnh 8. 11. **Đỉnh 5:** Thăm đỉnh 5. 12. **Các đỉnh kề với 7:** Đỉnh kề với 7 là 9, 10. Thăm các đỉnh này theo thứ tự. 13. **Đỉnh 9:** Thăm đỉnh 9. 14. **Đỉnh 10:** Thăm đỉnh 10. Vậy, thứ tự duyệt BFS là: 1, 2, 4, 7, 3, 6, 8, 5, 9, 10.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phầ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

Bắt đầu thi

Câu hỏi liên quan

Câu 28:

Mệnh đề \(P \vee (P \wedge Q)\) tương đương logic với mệnh đề nào sau đây?

Lời giải:

Đáp án đúng: D

Ta có thể dùng luật hấp thụ để đơn giản biểu thức \(P \vee (P \wedge Q)\). Theo luật hấp thụ, \(P \vee (P \wedge Q) \equiv P\). Do đó, mệnh đề \(P \vee (P \wedge Q)\) tương đương logic với mệnh đề P.

Câu 29:

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:

\(\frac{\begin{array}{l} A \to B\\ \overline B \end{array}}{{\therefore \overline A }}\)

Lời giải:

Đáp án đúng: B

Luật suy diễn được đưa ra có dạng: nếu A kéo theo B và B sai, thì A sai. Đây chính là luật phủ định (Modus Tollens). Các luật khác không phù hợp với cấu trúc này.

Câu 30:

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:

\(\frac{\begin{array}{l} A \to B\\ B \to C \end{array}}{{\therefore A \to C}}\)

Lời giải:

Đáp án đúng: D

Luật được sử dụng trong mô hình suy diễn đã cho là luật tam đoạn luận (tiếng Anh: Hypothetical Syllogism). Luật này phát biểu rằng nếu A kéo theo B và B kéo theo C, thì A kéo theo C. Đây là một quy tắc suy luận cơ bản trong logic mệnh đề. Trong các đáp án, chỉ có "Luật tam đoạn luận" mô tả chính xác quy tắc này.

Câu 1:

Cho tập A = {1,2,a}. Hỏi tập nào là tập lũy thừa của tập A?

Lời giải:

Đáp án đúng: C

Tập lũy thừa của một tập hợp A, ký hiệu P(A), là tập hợp chứa tất cả các tập con của A, kể cả tập rỗng và chính tập A. Trong trường hợp này, A = {1, 2, a}. Vậy các tập con của A là: * Tập rỗng: ∅ * Các tập con có 1 phần tử: {1}, {2}, {a} * Các tập con có 2 phần tử: {1, 2}, {1, a}, {2, a} * Tập con có 3 phần tử: {1, 2, a} Do đó, tập lũy thừa của A là: P(A) = {∅, {1}, {2}, {a}, {1, 2}, {1, a}, {2, a}, {1, 2, a}}. Vậy đáp án đúng là phương án 3.

Câu 2:

Cho quy tắc f: ℝ → ℝ thỏa mãn \(f(x) = 2x^2 + 5\). Khi đó f là:

Lời giải:

Đáp án đúng: C

Hàm số \(f(x) = 2x^2 + 5\) là một hàm số bậc hai. Tập xác định của hàm số là tập số thực ℝ và giá trị của hàm số luôn lớn hơn hoặc bằng 5. * **Hàm đơn ánh:** Một hàm được gọi là đơn ánh nếu với mọi \(x_1, x_2\) thuộc tập xác định, nếu \(x_1 ≠ x_2\) thì \(f(x_1) ≠ f(x_2)\). Trong trường hợp này, ta thấy rằng \(f(-1) = 2(-1)^2 + 5 = 7\) và \(f(1) = 2(1)^2 + 5 = 7\). Vì vậy, \(f(-1) = f(1)\) mặc dù \(-1 ≠ 1\), do đó hàm số này không phải là đơn ánh. * **Hàm toàn ánh:** Một hàm được gọi là toàn ánh nếu với mọi \(y\) thuộc tập giá trị, tồn tại một \(x\) thuộc tập xác định sao cho \(f(x) = y\). Vì giá trị của hàm số luôn lớn hơn hoặc bằng 5, nên không có giá trị \(x\) nào thuộc ℝ sao cho \(f(x)\) nhỏ hơn 5 (ví dụ \(f(x) = 0\)). Do đó, hàm số này không phải là toàn ánh (nếu tập giá trị là ℝ). * **Hàm song ánh:** Một hàm được gọi là song ánh nếu nó vừa là đơn ánh, vừa là toàn ánh. Vì hàm số này không phải là đơn ánh và không phải là toàn ánh nên nó không phải là song ánh. * **Hàm số:** Theo định nghĩa, một quy tắc \(f\) từ tập \(A\) vào tập \(B\) được gọi là hàm số nếu với mỗi \(x\) thuộc \(A\), có duy nhất một \(y\) thuộc \(B\) sao cho \(f(x) = y\). Trong trường hợp này, với mỗi giá trị \(x\) thuộc ℝ, ta có một giá trị duy nhất \(f(x)\) thuộc ℝ. Vậy đây là hàm số. Vậy đáp án đúng là "Hàm số".

Câu 3:

Cho tập S = {a, b, c,d} khi đó số phần tử của tập lũy thừa của tập S là:

Lời giải: