Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K):

K, B, D, F, H, A, C, E, G, I

K, B, A, C, D, F, E, G, H, I

K, B, F, H, A, C, D, E, G, I

K, E, F, G, H, A, B, C, D, I

Trả lời:

Đáp án đúng: C

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh K, ta duyệt các đỉnh kề với K (B, F, H). Sau đó, duyệt các đỉnh kề với B (A, C), rồi các đỉnh kề với F (D, E), và cuối cùng các đỉnh kề với H (G, I). Như vậy, thứ tự duyệt sẽ là: K, B, F, H, A, C, D, E, G, I.

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 6

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 26:

Một công thức được gọi là có dạng chuẩn tắc tuyển nếu …?

Lời giải:

Đáp án đúng: C

Công thức ở dạng chuẩn tắc tuyển (Disjunctive Normal Form - DNF) là một tuyển (OR) của các mệnh đề hội (AND). Mỗi mệnh đề hội này được gọi là một biểu thức hội cơ bản. Vì vậy, đáp án đúng là "Nó là tuyển của các biểu thức hội cơ bản".

Câu 27:

Xác định chân trị của biểu thức (\(\neg \)X→ \(\neg \)Y ) v (\(\neg \)Y → \(\neg \)Z ) và (\(\neg \)X → \(\neg \)Z) khi X = Y=0, Z= 1?

Lời giải:

Đáp án đúng: C

Để xác định chân trị của biểu thức logic, ta thay các giá trị X = 0, Y = 0, và Z = 1 vào biểu thức và tính toán:

(¬X → ¬Y) v (¬Y → ¬Z) và (¬X → ¬Z)

Với X = 0, Y = 0, Z = 1:

¬X = ¬0 = 1

¬Y = ¬0 = 1

¬Z = ¬1 = 0

Thay vào biểu thức thứ nhất: (¬X → ¬Y) v (¬Y → ¬Z) = (1 → 1) v (1 → 0) = 1 v 0 = 1

Thay vào biểu thức thứ hai: (¬X → ¬Z) = (1 → 0) = 0

Vậy, chân trị của biểu thức lần lượt là 1 và 0.

Câu 28:

Câu nào sau đây KHÔNG phải là một mệnh đề:

Lời giải:

Đáp án đúng: A

Mệnh đề là một câu khẳng định có tính đúng hoặc sai. Trong các phương án trên, "Có ai ở nhà không?" là một câu hỏi, không phải là một khẳng định và do đó không phải là một mệnh đề.

Câu 29:

Có bao nhiêu cạnh trong đồ thị có 8 đỉnh, mỗi đỉnh có bậc là 10?

Lời giải:

Đáp án đúng: D

Tổng bậc của đồ thị bằng 2 lần số cạnh. Gọi số cạnh là m. Ta có công thức: Tổng bậc = 2 * m. Trong trường hợp này, có 8 đỉnh, mỗi đỉnh có bậc là 10, vậy tổng bậc là 8 * 10 = 80. Suy ra, 80 = 2 * m, vậy m = 80 / 2 = 40. Vậy số cạnh là 40.

Câu 30:

Cho biết bậc của đồ thị G có n đỉnh, m cạnh?

Lời giải:

Đáp án đúng: A

Trong lý thuyết đồ thị, bậc của một đỉnh là số cạnh liên thuộc với đỉnh đó. Tổng bậc của tất cả các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị đó. Vì vậy, bậc của đồ thị G có n đỉnh và m cạnh là 2.m.

Câu 1:

Cho biết số phần tử của \(A \cap (B \cup C)\) nếu mỗi tập có 100 phần tử và nếu có 50 phần tử chung của mỗi cặp 2 tập và có 10 phần tử chung của cả 3 tập.

Lời giải: