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 các chuỗi bit độ dài 8, |A| = 2⁸ = 256.
Gọi B là tập các chuỗi bit độ dài 8 bắt đầu bằng 00.
Gọi C là tập các chuỗi bit độ dài 8 kết thúc bằng 11.
Ta cần tìm |B ∪ C| = |B| + |C| - |B ∩ C|.
|B| = 2⁶ = 64 (vì 2 bit đầu tiên cố định là 00, còn lại 6 bit tự do).
|C| = 2⁶ = 64 (vì 2 bit cuối cùng cố định là 11, còn lại 6 bit tự do).
B ∩ C là tập các chuỗi bit độ dài 8 vừa bắt đầu bằng 00 vừa kết thúc bằng 11. Vậy 4 bit giữa là tự do.
|B ∩ C| = 2⁴ = 16.
Do đó, |B ∪ C| = 64 + 64 - 16 = 112.

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 22:

Cho đồ thị vô hướng G = (V,E), khẳng định nào dưới đây là đúng?

Lời giải:

Đáp án đúng: C

Thuật toán BFS (Breadth-First Search) bắt đầu từ một đỉnh u và duyệt tất cả các đỉnh có thể đến được từ u theo kiểu duyệt rộng. Điều này có nghĩa là BFS(u) sẽ duyệt tất cả các đỉnh trong cùng thành phần liên thông với đỉnh u. Các lựa chọn khác không đúng vì BFS(u) không duyệt toàn bộ đồ thị nếu đồ thị không liên thông (lựa chọn 1), không phải lúc nào cũng tìm được đường đi giữa hai đỉnh bất kì (chỉ tìm được nếu chúng cùng thuộc một thành phần liên thông), và mặc dù mỗi đỉnh trong thành phần liên thông được duyệt đúng một lần, nhưng lựa chọn này không nhấn mạnh đến tính 'thành phần liên thông' vốn là mấu chốt của thuật toán.

Câu 23:

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

Lời giải:

Đáp án đúng: B

Đa đồ thị (multigraph) là một đồ thị mà giữa hai đỉnh có thể có nhiều cạnh nối (cạnh bội). Đồ thị có khuyên (loop) là đồ thị có cạnh nối một đỉnh với chính nó. Đa đồ thị vô hướng không có cạnh có hướng. Vì vậy, nếu G là một đa đồ thị vô hướng, G chắc chắn chứa cạnh bội (có thể có). Các đáp án còn lại đều sai.

Câu 24:

Đỉnh cô lập trên đồ thị G là:

Lời giải:

Đáp án đúng: C

Đỉnh cô lập là đỉnh không có cạnh nào nối tới nó, tức là bậc của đỉnh bằng 0.

Câu 25:

Cho đồ thị G = (V,E) vô hướng. Bậc của các đỉnh 1, 2, 3, 4, 5 tương ứng là:

Lời giải:

Đáp án đúng: B

Đỉnh 1 có bậc 3 (kết nối với 3 đỉnh khác).
Đỉnh 2 có bậc 4 (kết nối với 4 đỉnh khác).
Đỉnh 3 có bậc 6 (kết nối với 6 đỉnh khác).
Đỉnh 4 có bậc 4 (kết nối với 4 đỉnh khác).
Đỉnh 5 có bậc 4 (kết nối với 4 đỉnh khác).
Vậy, đáp án đúng là 3, 4, 6, 4, 4.

Câu 26:

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

Lời giải:

Đáp án đúng: D

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh I, ta duyệt các đỉnh kề với I là A, C, E, G. Sau đó duyệt các đỉnh kề với A, C, E, G chưa được duyệt, lần lượt là B, D, F, H. Cuối cùng duyệt đỉnh K kề với H. Vậy thứ tự duyệt là: I, A, C, E, G, B, D, F, H, K.

Câu 27:

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