Có bao nhiêu chuỗi bít độ dài bằng 8 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11.

112

128

124

Trả lời:

Đáp án đúng: A

Gọi A là tập hợp các chuỗi bit độ dài 8.

Gọi B là tập hợp các chuỗi bit độ dài 8 bắt đầu bởi 00.

Gọi C là tập hợp các chuỗi bit độ dài 8 kết thúc bởi 11.

Ta cần tìm |B ∪ C| = |B| + |C| - |B ∩ C|

|A| = 2⁸ = 256

|B| = 2⁶ = 64 (vì 2 bit đầu cố định là 00, 6 bit còn lại có thể là 0 hoặc 1)

|C| = 2⁶ = 64 (vì 2 bit cuối cố định là 11, 6 bit còn lại có thể là 0 hoặc 1)

|B ∩ C| = 2⁴ = 16 (vì 2 bit đầu cố định là 00, 2 bit cuối cố định là 11, 4 bit còn lại có thể là 0 hoặc 1)

Vậy, |B ∪ C| = 64 + 64 - 16 = 112

Vậy số chuỗi bit độ dài bằng 8 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11 là 112.

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 1

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 34:

Trong cách biểu diễn đồ thị bằng danh sách cạnh chúng ta lưu trữ:

Lời giải:

Đáp án đúng: A

Trong biểu diễn đồ thị bằng danh sách cạnh, chúng ta lưu trữ danh sách tất cả các cạnh của đồ thị. Mỗi cạnh thường được biểu diễn bằng cặp đỉnh mà nó kết nối. Do đó, đáp án A là đáp án chính xác.

Câu 35:

Đồ thị dưới dạng ma trận kề:

Là đồ thị:

Lời giải:

Đáp án đúng: C

Đồ thị Hamilton là đồ thị có chu trình Hamilton (chu trình đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần, rồi quay về đỉnh xuất phát).
Đồ thị Euler là đồ thị có chu trình Euler (chu trình đi qua tất cả các cạnh, mỗi cạnh đúng một lần, rồi quay về đỉnh xuất phát).

Phân tích đồ thị:
* Đồ thị liên thông: Đồ thị đã cho là liên thông.
* Đồ thị Hamilton: Đồ thị này có chu trình Hamilton, ví dụ: 1-2-3-4-5-6-1. Vậy nó là đồ thị Hamilton.
* Đồ thị Euler: Để kiểm tra xem đồ thị có phải là đồ thị Euler hay không, ta kiểm tra bậc của các đỉnh. Một đồ thị vô hướng liên thông là đồ thị Euler khi và chỉ khi tất cả các đỉnh của nó đều có bậc chẵn. Đỉnh 1, 2, 3, 4, 5, 6 đều có bậc 3 (lẻ). Vậy đồ thị không phải là đồ thị Euler.

Kết luận:
Đồ thị đã cho là đồ thị Hamilton nhưng không phải là đồ thị Euler. Đáp án phù hợp nhất là C. Hamilton.

Câu 36:

Thuật toán Floy được dùng để:

Lời giải:

Đáp án đúng: A

Thuật toán Floyd-Warshall (thường gọi tắt là thuật toán Floyd) là một thuật toán để tìm đường đi ngắn nhất giữa *tất cả* các cặp đỉnh trong một đồ thị có trọng số (có hướng hoặc vô hướng). Thuật toán này có thể xử lý đồ thị có trọng số âm, nhưng không thể xử lý đồ thị có chu trình âm (vì đường đi ngắn nhất sẽ không xác định).

* Phương án A đúng: Thuật toán Floyd được thiết kế để tìm đường đi ngắn nhất giữa mọi cặp đỉnh.
* Phương án B sai: Thuật toán Dijkstra được dùng để tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại.
* Phương án C sai: Mặc dù Floyd có thể tìm đường đi ngắn nhất giữa hai cặp đỉnh cụ thể, nhưng nó thực chất tính toán cho tất cả các cặp.
* Phương án D sai: Dijkstra hoặc các thuật toán tìm kiếm đường đi A* hiệu quả hơn cho trường hợp tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích.

Câu 37:

Giá trị của luồng cực đại trong mạng:

Lời giải:

Đáp án đúng: C

Giá trị của luồng cực đại trong mạng bị giới hạn bởi lát cắt hẹp nhất. Lát cắt hẹp nhất (min cut) là lát cắt có khả năng thông qua nhỏ nhất. Luồng cực đại không thể vượt quá khả năng thông qua của lát cắt hẹp nhất này, vì nó tạo thành nút thắt cổ chai cho luồng đi qua mạng. Do đó, đáp án C là chính xác.

Câu 38:

Nếu G = (V, E) là một đa đồ thị vô hướng thì:

Lời giải:

Đáp án đúng: B

Đa đồ thị vô hướng cho phép có cả khuyên (cạnh nối một đỉnh với chính nó) và cạnh bội (nhiều cạnh nối cùng một cặp đỉnh). Do đó, các phát biểu A và C sai. Phát biểu D sai vì đồ thị vô hướng không thể có cạnh có hướng.

Vậy đáp án đúng là B: G chứa cạnh bội.

Câu 39:

Số màu của một đồ thị phẳng là:

Lời giải: