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?
Đáp án đúng: B
Tổng số cách xếp 5 chữ a, b, c, d, e là 5! = 120 cách.
Số cách xếp mà chữ b đi liền sau chữ a là: coi ab là một khối, vậy ta có 4! = 24 cách.
Số cách xếp mà chữ d đi liền sau chữ c là: coi cd là một khối, vậy ta có 4! = 24 cách.
Số cách xếp mà cả chữ b đi liền sau chữ a và chữ d đi liền sau chữ c là: coi ab và cd là một khối, vậy ta có 3! = 6 cách.
Vậy số cách xếp mà chữ b không đi liền sau chữ a và d không đi liền sau chữ c là:
120 - 24 - 24 + 6 = 78 cách.
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!
Câu hỏi liên quan
* 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.
Gọi B là tập các xâu nhị phân độ dài 10 kết thúc bởi 11.
Ta cần tìm |A ∪ B|.
Theo nguyên lý bao hàm và loại trừ, ta có:
|A ∪ B| = |A| + |B| - |A ∩ B|
Tính |A|:
Vì 2 ký tự đầu tiên cố định là 00, còn lại 8 ký tự có thể là 0 hoặc 1. Vậy có 2^8 = 256 xâu.
Tính |B|:
Vì 2 ký tự cuối cùng cố định là 11, còn lại 8 ký tự có thể là 0 hoặc 1. Vậy có 2^8 = 256 xâu.
Tính |A ∩ B|:
Vì 2 ký tự đầu tiên là 00 và 2 ký tự cuối cùng là 11, còn lại 6 ký tự có thể là 0 hoặc 1. Vậy có 2^6 = 64 xâu.
Vậy |A ∪ B| = 256 + 256 - 64 = 448.
Gọi số câu hỏi học sinh phải trả lời từ 5 câu đầu là x. Theo đề bài, x ≥ 4.
Vậy x có thể là 4 hoặc 5.
Trường hợp 1: x = 4, tức là học sinh phải chọn 4 câu từ 5 câu đầu và 4 câu còn lại từ 5 câu sau. Số cách chọn là C(5,4) * C(5,4) = 5 * 5 = 25.
Trường hợp 2: x = 5, tức là học sinh phải chọn 5 câu từ 5 câu đầu và 3 câu còn lại từ 5 câu sau. Số cách chọn là C(5,5) * C(5,3) = 1 * 10 = 10.
Tổng số cách chọn là 25 + 10 = 35.
Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất trong đồ thị có trọng số không âm. Thuật toán này tìm đường đi ngắn nhất từ một đỉnh nguồn đã chọn đến tất cả các đỉnh còn lại trong đồ thị.
Tại sao các phương án khác không đúng:
- Phương án 1: Tìm đường đi ngắn nhất giữa *các cặp đỉnh bất kì* của đồ thị thường được giải quyết bằng thuật toán Floyd-Warshall.
- Phương án 3: Dijkstra có thể tìm đường đi ngắn nhất giữa hai đỉnh, nhưng nó thực tế tìm đường đi ngắn nhất từ đỉnh nguồn đến *tất cả* các đỉnh khác, rồi mới có thể xác định đường đi ngắn nhất đến đỉnh đích cụ thể. Phương án 2 chính xác hơn vì nó bao quát toàn bộ quá trình hoạt động của thuật toán.
- Phương án 4: Tương tự phương án 3, Dijkstra có thể được sử dụng để tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích. Tuy nhiên, trong quá trình đó, nó sẽ tìm ra đường đi ngắn nhất đến tất cả các đỉnh khác. Do đó, phương án 2 mô tả chính xác và đầy đủ hơn mục đích của thuật toán Dijkstra.
Cả thuật toán Prim và Kruskal đều là các thuật toán tham lam được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số. Điểm giống nhau cốt lõi giữa hai thuật toán này là cả hai đều cố gắng xây dựng cây khung bằng cách chọn các cạnh có trọng số nhỏ nhất một cách tham lam, đồng thời đảm bảo không tạo ra chu trình (cycle) trong cây khung đang xây dựng.
Phân tích các đáp án:
- Đáp án 1: Dừng khi kết nạp được tất cả các cạnh vào cây khung. - Sai. Cây khung chỉ chứa n-1 cạnh (với n là số đỉnh của đồ thị).
- Đáp án 2: Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung - Sai. Cây khung có n đỉnh và n-1 cạnh.
- Đáp án 3: Thuật toán chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây khung và không tạo ra chu trình. - Gần đúng. Mô tả đúng việc chọn cạnh nhỏ nhất và không tạo chu trình, nhưng "liên thuộc với các đỉnh đã thuộc cây khung" đúng hơn với Prim, còn Kruskal chọn cạnh nhỏ nhất bất kì không quan trọng là liên thuộc đỉnh nào đã có.
- Đáp án 4: Thuật toán xây dựng cây khung ngắn nhất. - Đúng. Đây là mục tiêu chung của cả hai thuật toán. Cả Prim và Kruskal đều tìm cách xây dựng cây khung có tổng trọng số các cạnh là nhỏ nhất có thể.
Vậy, đáp án chính xác nhất là 4, vì nó thể hiện mục tiêu chung của cả hai thuật toán.
.jpg)
