Đáp án đúng: C
Để giải bài toán này, ta cần tìm số xâu nhị phân độ dài 8 thỏa mãn hai điều kiện: chứa ít nhất 3 số 0 và ít nhất 3 số 1.
Ta sẽ tính tổng số xâu nhị phân độ dài 8, sau đó trừ đi các trường hợp không thỏa mãn điều kiện.
Tổng số xâu nhị phân độ dài 8 là 28 = 256.
Các trường hợp không thỏa mãn:
- Chứa ít hơn 3 số 0: Tức là chứa 0, 1 hoặc 2 số 0.
- 0 số 0: Có C(8,0) = 1 xâu (toàn số 1).
- 1 số 0: Có C(8,1) = 8 xâu.
- 2 số 0: Có C(8,2) = 8! / (2! * 6!) = (8 * 7) / 2 = 28 xâu.
- Chứa ít hơn 3 số 1: Tức là chứa 0, 1 hoặc 2 số 1.
- 0 số 1: Có C(8,0) = 1 xâu (toàn số 0).
- 1 số 1: Có C(8,1) = 8 xâu.
- 2 số 1: Có C(8,2) = 8! / (2! * 6!) = (8 * 7) / 2 = 28 xâu.
Vậy, số xâu thỏa mãn là: 256 - 37 - 37 = 182.
Vậy đáp án là 182.
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!
Câu hỏi liên quan
Số các số tự nhiên có 5 chữ số được lấy từ tập {1, 2, 3, 4, 5, 6, 7} và tận cùng bằng chữ số 5 là 7^4 = 2401.
Số các số tự nhiên có 5 chữ số được lấy từ tập {1, 2, 3, 4, 5, 6, 7} và không tận cùng bằng chữ số 5 là 16807 - 2401 = 14406.
Đường đi Euler trên đồ thị vô hướng tồn tại khi và chỉ khi đồ thị liên thông và có đúng 0 hoặc 2 đỉnh bậc lẻ.
- Nếu có 0 đỉnh bậc lẻ (tất cả các đỉnh đều bậc chẵn), đường đi Euler là chu trình Euler, đỉnh đầu và đỉnh cuối trùng nhau.
- Nếu có 2 đỉnh bậc lẻ, đường đi Euler bắt đầu từ một trong hai đỉnh bậc lẻ và kết thúc ở đỉnh bậc lẻ còn lại, do đó đỉnh đầu và đỉnh cuối khác nhau.
Vậy, đáp án đúng nhất là khi đỉnh đầu và đỉnh cuối khác nhau, đồ thị có đường đi Euler.
Đồ thị vô hướng G được gọi là liên thông nếu giữa mọi cặp đỉnh u, v bất kỳ đều tồn tại một đường đi vô hướng nối u đến v. Điều này có nghĩa là ta có thể di chuyển từ đỉnh u đến đỉnh v (và ngược lại) dọc theo các cạnh của đồ thị.
- Phương án 1 sai vì chỉ cần một đường đi, không nhất thiết phải là cạnh nối trực tiếp.
- Phương án 2 sai vì đồ thị là vô hướng, nên đường đi không có hướng.
- Phương án 4 sai vì không nhất thiết phải có hai cạnh nối.
Trong lý thuyết đồ thị, một chu trình là một đường đi khép kín, bắt đầu và kết thúc tại cùng một đỉnh và đi qua các đỉnh và cạnh khác nhau. Độ dài của một chu trình được định nghĩa là số cạnh mà nó chứa. Ví dụ, một chu trình đơn giản tạo bởi các đỉnh A, B, và C (A-B-C-A) có độ dài là 3, vì nó chứa ba cạnh: AB, BC, và CA. Do đó, đáp án chính xác là số cạnh tạo thành chu trình.
Đường đi đơn trong đồ thị G là đường đi mà trên đó mỗi đỉnh chỉ xuất hiện một lần, ngoại trừ trường hợp đường đi là chu trình thì đỉnh đầu và đỉnh cuối có thể trùng nhau. Do đó, phương án 2 là đáp án đúng nhất.
