Có bao nhiêu xâu nhị phân độ dài bằng 8 bắt đầu bởi 00 và kết thúc bởi 11?

128

Trả lời:

Đáp án đúng: B

Xâu nhị phân có độ dài 8 bắt đầu bởi 00 và kết thúc bởi 11 có dạng 00xxxx11, trong đó x có thể là 0 hoặc 1.

Có 4 vị trí x cần điền, mỗi vị trí có 2 lựa chọn (0 hoặc 1). Vì vậy, số lượng xâu nhị phân thỏa mãn là 2 * 2 * 2 * 2 = 2⁴ = 16.

Tuy nhiên, không có đáp án nào là 16. Có lẽ có một sự nhầm lẫn trong các lựa chọn đáp án. Vì vậy, ta cần kiểm tra lại.

Nếu yêu cầu là xâu nhị phân độ dài *ít nhất* bằng 8 thì bài toán sẽ khác. Tuy nhiên, với yêu cầu hiện tại, ta phải giả định là không có đáp án đúng ở đây.

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 10

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 32:

Đồ thị liên thông nào trong các đồ thị dưới đây là đồ thị Euler nếu số bậc của các đỉnh lần lượt là:

Lời giải:

Đáp án đúng: C

Một đồ thị liên thông là đồ thị Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn.

- Phương án A: Các bậc là 2, 4, 1, 2, 6. Có đỉnh bậc 1 nên không phải đồ thị Euler.

- Phương án B: Các bậc là 3, 4, 4, 2, 4. Có đỉnh bậc 3 nên không phải đồ thị Euler.

- Phương án C: Các bậc là 1, 4, 2, 5, 2. Có đỉnh bậc 1 và bậc 5 nên không phải đồ thị Euler.

- Phương án D: Các bậc là 4, 4, 6, 5, 3. Có đỉnh bậc 5 và bậc 3 nên không phải đồ thị Euler.

Vậy không có đáp án nào đúng.

Câu 33:

Đồ thị K₄ có số đỉnh và số cạnh tương ứng là?

Lời giải:

Đáp án đúng: A

Đồ thị K₄ là đồ thị đầy đủ với 4 đỉnh. Trong đồ thị đầy đủ, mỗi đỉnh được nối với tất cả các đỉnh còn lại. Vì vậy:

Số đỉnh của K₄ là 4.
Số cạnh của K₄ có thể được tính bằng công thức n(n-1)/2, trong đó n là số đỉnh. Trong trường hợp này, số cạnh là 4(4-1)/2 = 4(3)/2 = 12/2 = 6.

Vậy đồ thị K₄ có 4 đỉnh và 6 cạnh.

Câu 34:

Đồ thị phân đôi đầy đủ K_n,m có số màu bằng:

Lời giải:

Đáp án đúng: C

Đồ thị phân đôi đầy đủ K_n,m là đồ thị mà tập đỉnh của nó có thể chia thành hai tập rời nhau X và Y, sao cho |X| = n và |Y| = m, và mọi đỉnh trong X đều kề với mọi đỉnh trong Y. Để tô màu cho đồ thị này, ta có thể sử dụng hai màu. Một màu cho tất cả các đỉnh trong X và một màu khác cho tất cả các đỉnh trong Y. Vì không có cạnh nào nối giữa hai đỉnh trong cùng một tập (X hoặc Y), nên không có hai đỉnh kề nhau nào có cùng màu. Do đó, số màu cần thiết là 2.

Câu 35:

Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.

Lời giải:

Đáp án đúng: A

Định lý Ford-Fulkerson phát biểu rằng giá trị luồng cực đại từ điểm phát s đến điểm thu t bằng khả năng thông qua (capacity) của lát cắt hẹp nhất (minimum cut) tách điểm s và t. Lát cắt hẹp nhất là lát cắt có tổng khả năng thông qua nhỏ nhất trong tất cả các lát cắt tách s và t. Vì vậy, đáp án A là đáp án chính xác.

Câu 36:

Nếu G = (V, E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)

Lời giải:

Đáp án đúng: A

Trong một đơn đồ thị vô hướng G = (V, E), ma trận kề biểu diễn mối quan hệ giữa các đỉnh. Vì đồ thị là vô hướng, nên nếu có một cạnh nối đỉnh i và đỉnh j, thì cũng có một cạnh nối đỉnh j và đỉnh i. Điều này có nghĩa là phần tử ở hàng i, cột j của ma trận kề sẽ bằng phần tử ở hàng j, cột i. Do đó, ma trận kề của một đơn đồ thị vô hướng là một ma trận đối xứng qua đường chéo chính.

Phương án A đúng vì nó phản ánh tính chất đối xứng của ma trận kề trong đồ thị vô hướng.

Phương án B sai vì nó khẳng định ma trận kề không đối xứng.

Phương án C sai vì các phần tử trên đường chéo chính của ma trận kề bằng 1 khi có một vòng lặp (cạnh nối một đỉnh với chính nó), nhưng trong một đơn đồ thị (không có vòng lặp), các phần tử này thường bằng 0.

Phương án D sai vì không có quy tắc nào quy định các phần tử trên đường chéo phụ phải bằng 1.

Câu 37:

Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:

Lời giải: