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

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

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

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

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

Trả lời:

Đáp án đúng: A

The BFS algorithm explores the graph level by level. Starting from node I, it visits its neighbors A and B. Then, it visits the neighbors of A (E, C) and B (D). Next, it visits the neighbors of E (G), C (F), and D (H). Finally, it visits the neighbor of G (K). The correct traversal order is I, A, B, E, C, D, G, F, H, K. However, based on the provided options, none of them match this order. So no choice is correct.

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Phần 11

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 42:

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

Lời giải:

Đáp án đúng: B

Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) bắt đầu tại một đỉnh (trong trường hợp này là đỉnh C), sau đó thăm các đỉnh kề của nó theo chiều sâu trước khi quay lui.

1. Bắt đầu tại C: Thuật toán bắt đầu từ đỉnh C.
2. Thăm A: Từ C, thuật toán thăm đỉnh A.
3. Thăm E: Từ A, thuật toán thăm đỉnh E (vì E đứng trước B theo thứ tự bảng chữ cái).
4. Thăm G: Từ E, thuật toán thăm đỉnh G.
5. Quay lui và thăm B: Từ G, không có đỉnh nào để đi tiếp, quay lại E rồi đến A. Từ A, thuật toán thăm đỉnh B.
6. Thăm D: Từ B, thuật toán thăm đỉnh D.
7. Thăm F: Từ D, thuật toán thăm đỉnh F.
8. Thăm H: Từ F, thuật toán thăm đỉnh H.
9. Thăm K: Từ H, thuật toán thăm đỉnh K.
10. Thăm I: Từ K, thuật toán thăm đỉnh I.
11. Thăm N: Từ I, thuật toán thăm đỉnh N.

Vậy thứ tự duyệt đúng là: C, A, E, G, B, D, F, H, K, I, N

Câu 43:

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

Công thức có dạng chuẩn tắc hội (CNF - Conjunctive Normal Form) là một công thức logic mệnh đề được biểu diễn dưới dạng hội của các mệnh đề tuyển. Mỗi mệnh đề tuyển là một tuyển của các literal (biến hoặc phủ định của biến). Biểu thức hội cơ bản còn được gọi là mệnh đề tuyển (clause). Như vậy, một công thức được gọi là có dạng chuẩn tắc hội nếu nó là hội của các biểu thức tuyển cơ bản.

Câu 44:

Biết chân trị của mệnh đề P → Q là 0, thì chân trị của các mệnh đề P Λ Q và Q → P tương ứng là?

Lời giải:

Đáp án đúng: A

Ta có P → Q sai khi và chỉ khi P đúng và Q sai.

Khi đó, P Λ Q sai (vì Q sai) và Q → P đúng (vì Q sai).

Vậy, chân trị của P Λ Q là 0 và của Q → P là 1.

Câu 45:

Phương pháp phản chứng là phương pháp?

Lời giải:

Đáp án đúng: B

Phương pháp phản chứng là một phương pháp chứng minh toán học, trong đó ta giả sử điều cần chứng minh là sai (phản định của mệnh đề cần chứng minh) rồi từ giả thiết đó suy ra một điều mâu thuẫn với giả thiết hoặc một tiên đề đã được công nhận. Từ đó kết luận điều giả sử là sai, suy ra điều cần chứng minh là đúng.

* Đáp án A: Quy bài toán ban đầu về bài toán con đơn giản hơn là phương pháp chia để trị hoặc quy nạp.
* Đáp án B: Giả sử điều cần chứng minh là sai để từ đó suy ra mâu thuẫn là định nghĩa chính xác của phương pháp phản chứng.
* Đáp án C: Liệt kê tất cả các khả năng để từ đó đưa ra quyết định là phương pháp vét cạn hoặc duyệt.
* Đáp án D: Biểu diễn nghiệm của bài toán bằng các dữ kiện ban đầu là một cách giải bài toán, nhưng không phải là phương pháp phản chứng.

Câu 46:

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 toán học, cho phép suy ra một kết luận từ hai mệnh đề cho trước. Cụ thể, nếu có hai mệnh đề "P suy ra Q" và "Q suy ra R" đều đúng, thì có thể suy ra mệnh đề "P suy ra R" cũng đúng.

Phương án A: (P∧(P→Q)) → Q là quy tắc Modus Ponens (khẳng định). Nếu P đúng và P suy ra Q đúng, thì Q đúng.
Phương án B: ((P→Q) ∨ (Q→R)) → (P→R) không phải là quy tắc tam đoạn luận. Vế trái sử dụng phép "hoặc", và kết luận không chắc chắn.
Phương án C: ((P→Q) ∨ (Q→R)) → (Q→R) cũng không phải là quy tắc tam đoạn luận. Tương tự như phương án B, vế trái sử dụng phép "hoặc" và kết luận không hợp lý.
Phương án D: ((P→Q) ∧ (Q→R)) → (P→R) chính là quy tắc tam đoạn luận. Nếu "P suy ra Q" và "Q suy ra R" đồng thời đúng (phép "và"), thì có thể suy ra "P suy ra R".

Vậy đáp án đúng là D.

Câu 47:

Quy tắc (luật) suy luận nào là cơ sở của suy diễn sau: Nếu là sinh viên CNTT của trường DHCN Việt Hung thì phải học Toán rời rạc. An không học Toán rời rạc nên An không phải là sinh viên CNTT của trường ĐHCN Việt Hung.

Lời giải: