Có bao nhiêu cách xếp các chữ a, b, c, d, e sao cho chữ b không đi liền sau chữ a và d không đi liền sau chữ c?

120

Trả lời:

Đáp án đúng: B

Số cách xếp 5 chữ cái a, b, c, d, e là 5! = 120. Số cách xếp sao cho b đi liền sau a là: Xem "ab" là một cụm, ta có 4! = 24 cách xếp. Số cách xếp sao cho d đi liền sau c là: Xem "cd" là một cụm, ta có 4! = 24 cách xếp. Số cách xếp sao cho cả b đi liền sau a và d đi liền sau c là: Xem "ab" và "cd" là các cụm, ta có 3! = 6 cách xếp. Vậy, số cách xếp sao cho hoặc b đi liền sau a hoặc d đi liền sau c là: 24 + 24 - 6 = 42 cách. Số cách xếp sao cho b không đi liền sau a và d không đi liền sau c là: 120 - 42 = 78 cách.

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 16

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

Cho tập nền A = {4, 5, 6, 7, 8}. Có bao nhiêu số có 3 chữ số khác nhau là số chẵn được thành lập từ A.

Lời giải:

Đáp án đúng: B

Để lập một số chẵn có 3 chữ số khác nhau từ tập A = {4, 5, 6, 7, 8}, ta cần xét các trường hợp chữ số cuối cùng là số chẵn. Tập A có 3 số chẵn là 4, 6, 8.

* Bước 1: Chọn chữ số hàng đơn vị.
* Có 3 cách chọn (4, 6 hoặc 8).

* Bước 2: Chọn chữ số hàng trăm.
* Sau khi chọn chữ số hàng đơn vị, còn lại 4 chữ số trong tập A. Vì vậy, có 4 cách chọn chữ số hàng trăm.

* Bước 3: Chọn chữ số hàng chục.
* Sau khi chọn chữ số hàng trăm và hàng đơn vị, còn lại 3 chữ số trong tập A. Vì vậy, có 3 cách chọn chữ số hàng chục.

Vậy, tổng số các số chẵn có 3 chữ số khác nhau được thành lập từ A là: 3 * 4 * 3 = 36.

Câu 18:

Có bao nhiêu xâu nhị phân độ dài 10 bắt đầu bởi 00 hoặc kết thúc bởi 11.

Lời giải:

Đáp án đúng: B

Gọi A là tập các xâu nhị phân độ dài 10 bắt đầu bằng 00, B là tập các xâu nhị phân độ dài 10 kết thúc bằng 11.

Ta cần tính |A ∪ B|.

Theo công thức bù trừ: |A ∪ B| = |A| + |B| - |A ∩ B|.

- |A|: Vì 2 ký tự đầu tiên cố định là 00, nên còn lại 8 vị trí có thể là 0 hoặc 1. Vậy |A| = 2⁸ = 256.

- |B|: Vì 2 ký tự cuối cùng cố định là 11, nên còn lại 8 vị trí có thể là 0 hoặc 1. Vậy |B| = 2⁸ = 256.

- |A ∩ B|: Tập các xâu nhị phân độ dài 10 vừa bắt đầu bằng 00, vừa kết thúc bằng 11. Vậy 2 ký tự đầu là 00, 2 ký tự cuối là 11, còn lại 6 vị trí có thể là 0 hoặc 1. Vậy |A ∩ B| = 2⁶ = 64.

Do đó: |A ∪ B| = 256 + 256 - 64 = 448.

Vậy có 448 xâu nhị phân độ dài 10 bắt đầu bởi 00 hoặc kết thúc bởi 11.

Câu 19:

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 ít nhất 4 trong 5 câu hỏi đầu tiên?

Lời giải:

Đáp án đúng: B

Để giải bài toán này, ta xét các trường hợp học viên trả lời ít nhất 4 trong 5 câu hỏi đầu tiên:

* Trường hợp 1: Học viên trả lời 4 câu trong 5 câu đầu và 4 câu trong 5 câu còn lại. Số cách chọn là C(5, 4) * C(5, 4) = 5 * 5 = 25.
* Trường hợp 2: Học viên trả lời 5 câu trong 5 câu đầu và 3 câu trong 5 câu còn lại. Số cách chọn là C(5, 5) * C(5, 3) = 1 * 10 = 10.

Vậy tổng số cách chọn là 25 + 10 = 35.

Do đó, số lượng sự lựa chọn của học viên là 35.

Câu 20:

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

Lời giải:

Đáp án đúng: D

Thuật toán Dijkstra là một thuật toán tìm kiếm đường đi ngắn nhất trên đồ thị có trọng số không âm. Nó được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn (điểm bắt đầu) đến tất cả các đỉnh còn lại trong đồ thị.

- Phương án 1 không đúng vì thuật toán Dijkstra không trực tiếp tìm đường đi ngắn nhất giữa *tất cả* các cặp đỉnh. Để làm điều đó, có thể sử dụng thuật toán Floyd-Warshall hoặc chạy Dijkstra nhiều lần từ mỗi đỉnh.
- Phương án 3 và 4 không sai hoàn toàn, nhưng chưa đủ. Dijkstra có thể tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích, nhưng nó thực tế tìm đường đi ngắn nhất đến *tất cả* các đỉnh, bao gồm cả đỉnh đích đó.
- Phương án 2 là chính xác nhất vì nó mô tả đúng mục tiêu chính của thuật toán Dijkstra: tìm đường đi ngắn nhất từ một đỉnh xuất phát đến tất cả các đỉnh khác trong đồ thị.

Câu 21:

Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:

Lời giải:

Đáp án đúng: D

Cả thuật toán Prim và Kruskal đều nhằm mục đích xây dựng cây khung ngắn nhất (minimum spanning tree) cho một đồ thị liên thông có trọng số. Cây khung ngắn nhất là một cây bao gồm tất cả các đỉnh của đồ thị, với tổng trọng số các cạnh là nhỏ nhất có thể. Do đó, đáp án chính xác là "Thuật toán xây dựng cây khung ngắn nhất.".

Các đáp án khác không chính xác vì:
- Đáp án 1: Thuật toán dừng khi kết nạp được tất cả các đỉnh, không phải cạnh, vào cây khung. Việc kết nạp tất cả các cạnh sẽ tạo thành đồ thị ban đầu, không phải cây khung.
- Đáp án 2: Cây khung của đồ thị n đỉnh sẽ có n-1 cạnh, không phải n cạnh.
- Đáp án 3: Mô tả này đúng cho thuật toán Prim, nhưng không hoàn toàn chính xác cho thuật toán Kruskal. Kruskal chọn cạnh nhỏ nhất một cách tổng thể, không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung.

Câu 22:

Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

Lời giải: