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

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

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

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

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

Trả lời:

Đáp án đúng: D

Thuật toán DFS (Depth-First Search) duyệt đồ thị theo chiều sâu. Bắt đầu từ đỉnh I, ta duyệt theo các nhánh sâu nhất có thể trước khi quay lui. 1. Bắt đầu từ I. 2. Chọn một đỉnh kề với I, ví dụ G. Duyệt G. 3. Chọn một đỉnh kề với G, ví dụ H. Duyệt H. 4. Chọn một đỉnh kề với H, là N. Duyệt N. 5. Chọn một đỉnh kề với N, là K. Duyệt K. 6. Quay lui về G, chọn một đỉnh kề khác, là B. Duyệt B. 7. Chọn một đỉnh kề với B, là F. Duyệt F. 8. Quay lui về I, chọn một đỉnh kề khác, là A. Duyệt A. 9. Chọn một đỉnh kề với A, là C. Duyệt C. 10. Chọn một đỉnh kề với C, là E. Duyệt E. 11. Quay lui về C và A, sau đó quay lui về I. 12. Quay lui về B, chọn một đỉnh kề khác, là D. Duyệt D. Vậy thứ tự duyệt là I, G, H, N, K, B, A, C, E, F, D. Phương án 4 là đáp án đúng

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 17

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:

Xác định chân trị của biểu thức ( P → Q ) Λ ( Q → R ) và (P → R) khi P = Q = 1, R=0?

Lời giải:

Đáp án đúng: B

Ta có P = 1, Q = 1, R = 0.
Khi đó:
- P → Q = 1 → 1 = 1
- Q → R = 1 → 0 = 0
- P → R = 1 → 0 = 0
Vậy ( P → Q ) Λ ( Q → R ) = 1 Λ 0 = 0.
Do đó, giá trị của biểu thức ( P → Q ) Λ ( Q → R ) là 0 và (P → R) là 0.

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{A}{{\therefore (A \vee B)}}\)

Lời giải:

Đáp án đúng: B

Luật cộng (Addition) phát biểu rằng nếu A là đúng, thì (A ∨ B) cũng đúng, bất kể giá trị của B là gì. Mô hình suy diễn \(\frac{A}{{\therefore (A \vee B)}}\) thể hiện chính xác quy tắc này.

Câu 30:

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

Lời giải:

Đáp án đúng: C

Tổng bậc của đồ thị bằng hai lần số cạnh. Gọi số cạnh của đồ thị là m. Ta có tổng bậc của đồ thị là 10 đỉnh * 4 bậc/đỉnh = 40. Vậy 2m = 40, suy ra m = 20. Vậy số cạnh của đồ thị là 20.

Câu 1:

Cho X={1,2,3,4,5,6,7,8,9} A={1,2,3,8}, B={2,4,8,9}, C={6,7,8,9}

Tìm xâu bit biểu diễn tập: \((A \cup B) \cap C\)

Lời giải:

Đáp án đúng: A

Đầu tiên, ta tìm \(A \cup B\): \(A \cup B = \{1, 2, 3, 4, 8, 9\}\). Tiếp theo, ta tìm \((A \cup B) \cap C\): \((A \cup B) \cap C = \{8, 9\}\). Vì X = {1, 2, 3, 4, 5, 6, 7, 8, 9}, xâu bit biểu diễn tập \((A \cup B) \cap C\) sẽ có độ dài 9. Các phần tử 8 và 9 thuộc tập \((A \cup B) \cap C\) nên bit thứ 8 và thứ 9 sẽ là 1, các bit còn lại là 0. Vậy xâu bit là 000000011.

Câu 2:

Cho 2 tập hợp:

A = {1,2,3,4,5,a, hoa, xe máy, dog, táo, mận}

B = {hoa, 3,4 , táo}

Tập nào trong các tập dưới đây là tập con của tập AxB:

Lời giải:

Đáp án đúng: C

Tập A x B là tập hợp các cặp có thứ tự (a, b) sao cho a thuộc A và b thuộc B. Xét các phương án: - Phương án 1: {(1, táo), (a, 3), (3,3), (táo, a)}. Ta thấy: 1 thuộc A, táo thuộc B; a thuộc A, 3 thuộc B; 3 thuộc A, 3 thuộc B. Tuy nhiên, táo thuộc A nhưng a không thuộc B. Do đó, phương án này sai. - Phương án 2: {(hoa, hoa), (táo, mận), (5, 4)}. Ta thấy: hoa thuộc A, hoa thuộc B; táo thuộc A, mận không thuộc B; 5 thuộc A, 4 thuộc B. Do đó, phương án này sai. - Phương án 3: {(1,táo), (táo, táo), (xe máy, 3)}. Ta thấy: 1 thuộc A, táo thuộc B; táo thuộc A, táo thuộc B; xe máy thuộc A, 3 thuộc B. Vậy tất cả các phần tử đều thỏa mãn. Do đó, tập này là tập con của A x B. - Phương án 4: Vì phương án 3 đúng nên phương án này sai. Vậy, tập {(1,táo), (táo, táo), (xe máy, 3)} là tập con của A x B.

Câu 3:

Kết quả của một cuộc điều tra ở Hà Nội cho thấy 96% các gia đình có máy thu hình, 98% có điện thoại và 95% có điện thoại và máy thu hình. Tính tỷ lệ % các gia đình ở Hà Nội không có thiết bị nào là). ( Tỷ lệ % các gia đình có điện thoại hoặc máy thu hình là 98%+96%-95%=99%. Tỷ lệ % các gia đình không có điện thoại và không có máy thu hình là 1%)

Lời giải: