Có bao nhiêu xâu nhị phân có độ dài nhỏ hơn hoặc bằng 6 kết thúc là bít 0?

1+2¹ + 2² + 2³+ 2⁴ + 2⁵

2¹ + 2² + 2³ + 2⁴ + 2⁵

1+2¹ + 2² + 2³+ 2⁴ + 2⁵ + 2⁶

2¹ . 2² . 2³ . 2⁴ .2⁵

Trả lời:

Đáp án đúng: A

Đề bài yêu cầu đếm số xâu nhị phân có độ dài nhỏ hơn hoặc bằng 6 và kết thúc bằng bít 0.

Xét các trường hợp:

Độ dài 1: xâu "0" (1 xâu)
Độ dài 2: xâu có dạng "x0", x có thể là 0 hoặc 1 (2¹ xâu)
Độ dài 3: xâu có dạng "xx0", mỗi x có thể là 0 hoặc 1 (2² xâu)
Độ dài 4: xâu có dạng "xxx0" (2³ xâu)
Độ dài 5: xâu có dạng "xxxx0" (2⁴ xâu)
Độ dài 6: xâu có dạng "xxxxx0" (2⁵ xâu)

Vậy tổng số xâu là: 1 + 2¹ + 2² + 2³ + 2⁴ + 2⁵

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

Một thương nhân đi bán hàng tại n thành phố. Chị ta có thể bắt đầu hành trình của mình tại một thành phố nào đó nhưng phải qua (n-1) thành phố kia theo bất kỳ thứ tự nào mà chị muốn. Hỏi có bao nhiêu lộ trình khác nhau chị ta có thể đi?

Lời giải:

Đáp án đúng: D

Vì người thương nhân có thể bắt đầu ở bất kỳ thành phố nào trong n thành phố, và sau đó phải đi qua n-1 thành phố còn lại theo bất kỳ thứ tự nào, đây là một bài toán về hoán vị. Khi đã chọn thành phố bắt đầu, ta có (n-1) lựa chọn cho thành phố thứ hai, (n-2) lựa chọn cho thành phố thứ ba, và cứ tiếp tục như vậy cho đến thành phố cuối cùng. Do đó, số lượng lộ trình khác nhau là (n-1)!.

Câu 20:

Một học viên phải trả lời 8 trong số 10 câu hỏi cho một kỳ thi. Học viên này có bao nhiêu sự lựa chọn nếu học viên phải trả lời 3 câu hỏi đầu tiên?

Lời giải:

Đáp án đúng: A

Học viên phải trả lời 8 câu hỏi, trong đó 3 câu hỏi đầu tiên là bắt buộc. Vậy học viên cần chọn thêm 5 câu hỏi từ 7 câu hỏi còn lại (10 - 3 = 7). Số cách chọn 5 câu hỏi từ 7 câu hỏi là tổ hợp chập 5 của 7, ký hiệu là C(7,5) hay 7C5. Ta có công thức tính tổ hợp: C(n, k) = n! / (k! * (n-k)!). Trong trường hợp này, C(7,5) = 7! / (5! * 2!) = (7 * 6) / (2 * 1) = 21.

Câu 21:

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.

Lời giả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.

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: