Đồ thị G vô hướng n đỉnh là một cây nếu:

Nếu liên thông và có n-1 cạnh

Nếu không liên thông và có n-1 cạnh

Nếu liên thông và có n cạnh

Nếu không liên thông và có n cạnh

Trả lời:

Đáp án đúng: A

Một đồ thị vô hướng G có n đỉnh được gọi là cây nếu nó liên thông và có n-1 cạnh. Tính liên thông đảm bảo giữa hai đỉnh bất kỳ có một đường đi, và n-1 cạnh là số cạnh tối thiểu để đảm bảo điều này mà không tạo thành chu trình.

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 16

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

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

Lời giải:

Đáp án đúng: B

Thuật toán BFS (Breadth-First Search - Tìm kiếm theo chiều rộng) duyệt đồ thị bắt đầu từ một đỉnh (trong trường hợp này là đỉnh H), sau đó duyệt tất cả các đỉnh kề với nó, rồi đến các đỉnh kề với các đỉnh vừa duyệt, cứ tiếp tục như vậy cho đến khi tất cả các đỉnh có thể đến được đều đã được duyệt. Thứ tự duyệt các đỉnh kề thường theo thứ tự bảng chữ cái nếu không có quy tắc nào khác. Bắt đầu từ H, các đỉnh kề là G, F, E. Tiếp theo, duyệt các đỉnh kề với G (đã duyệt G): B, D, K. Tiếp theo, duyệt các đỉnh kề với F (đã duyệt F): A, C. Tiếp theo, duyệt các đỉnh kề với E (đã duyệt E): I. Vậy thứ tự duyệt sẽ là: H, G, F, E, B, D, K, A, C, I. Đáp án phù hợp nhất là: H, G, F, B, D, E, K, A, C, I (do E đứng trước vì xét theo thứ tự duyệt các đỉnh kề H là G, F, E).

Câu 25:

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

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) bắt đầu từ đỉnh 1, duyệt theo chiều sâu. 1. Bắt đầu từ đỉnh 1. 2. Duyệt đỉnh kề chưa được thăm của 1, ví dụ đỉnh 2. 3. Duyệt đỉnh kề chưa được thăm của 2, ví dụ đỉnh 7. 4. Duyệt đỉnh kề chưa được thăm của 7, ví dụ đỉnh 4. 5. Duyệt đỉnh kề chưa được thăm của 4, ví dụ đỉnh 5. 6. Duyệt đỉnh kề chưa được thăm của 5, ví dụ đỉnh 10. 7. Quay lui lại 4, không còn đỉnh kề chưa thăm. Quay lui lại 7, không còn đỉnh kề chưa thăm. Quay lui lại 2. 8. Duyệt đỉnh kề chưa được thăm của 2, ví dụ đỉnh 3. 9. Duyệt đỉnh kề chưa được thăm của 3, ví dụ đỉnh 6. 10. Duyệt đỉnh kề chưa được thăm của 6, ví dụ đỉnh 9. 11. Duyệt đỉnh kề chưa được thăm của 9, ví dụ đỉnh 8. Vậy, thứ tự duyệt các đỉnh là: 1, 2, 7, 4, 5, 10, 3, 6, 9, 8.

Câu 26:

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

Lời giải:

Đáp án đúng: B

Một công thức logic mệnh đề được gọi là có dạng chuẩn tắc hội (CNF - Conjunctive Normal Form) nếu nó là hội (AND) của các mệnh đề, trong đó mỗi mệnh đề là một tuyển (OR) của các literal (biến mệnh đề hoặc phủ định của biến mệnh đề). Do đó, đáp án chính xác là "Nó là hội của các biểu thức tuyển cơ bản". Biểu thức tuyển cơ bản ở đây tương ứng với một mệnh đề (clause).

Câu 27:

Quy tắc suy luận nào sau đây là quy tắc tam đoạn luận?

Lời giải:

Đáp án đúng: D

Quy tắc tam đoạn luận là một quy tắc suy luận trong logic mệnh đề, cho phép suy ra một kết luận từ hai tiền đề có dạng "Nếu P thì Q" và "Nếu Q thì R". Kết luận suy ra được là "Nếu P thì R". Như vậy, quy tắc tam đoạn luận có dạng: ((P→Q) ∧ (Q→R)) → (P→R). Các đáp án khác không tuân theo cấu trúc này. Đáp án 1: \((P \wedge (P \to Q)) \to Q\) là Modus Ponens (khẳng định). Nếu P đúng và P kéo theo Q, thì Q đúng. Đáp án 2 và 3 không đúng vì chúng sử dụng phép tuyển (\(\vee\)) và cho ra một kết luận không chính xác theo quy tắc tam đoạn luận.

Câu 28:

Qui tắc suy luận nào là cơ sở của suy diễn sau: "Nếu hôm nay trời mưa thì cô ta không đến, Nếu cô ta không đến thì ngày mai cô ta đến, Vậy thì, nếu hôm nay trời mưa thì ngày mai cô ta đến."

Lời giải:

Đáp án đúng: C

Đoạn suy diễn trên có dạng:

Nếu P thì Q
Nếu Q thì R
Vậy, nếu P thì R

Đây chính là cấu trúc của tam đoạn luận (hay còn gọi là quy tắc bắc cầu). Trong trường hợp này:

P: Hôm nay trời mưa
Q: Cô ta không đến
R: Ngày mai cô ta đến

Do đó, quy tắc suy luận được sử dụng ở đây là tam đoạn luận.

Câu 29:

Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Nếu An học giỏi thì An sẽ được khen thưởng. Và nếu An nhiệt tình tham gia các hoạt động Đoàn thì An cũng được khen thưởng. Vậy Nếu An học giỏi hoặc tham gia nhiệt tình các hoạt động Đoàn thì An sẽ được khen thưởng.

Lời giải: