Người ta xếp ngẫu nhiên 5 lá phiếu có ghi số thứ tự từ 1 đến 5 cạnh nhau. Có bao nhiêu cách xếp để các phiếu phân thành 2 nhóm chẵn lẻ riêng biệt.

Trả lời:

Đáp án đúng: D

Để các phiếu phân thành 2 nhóm chẵn lẻ riêng biệt, ta có 2 trường hợp: * **Trường hợp 1:** Các phiếu lẻ đứng trước, các phiếu chẵn đứng sau. Có 3! cách xếp các phiếu lẻ (1, 3, 5) và 2! cách xếp các phiếu chẵn (2, 4). Vậy có 3! * 2! = 6 * 2 = 12 cách. * **Trường hợp 2:** Các phiếu chẵn đứng trước, các phiếu lẻ đứng sau. Có 2! cách xếp các phiếu chẵn (2, 4) và 3! cách xếp các phiếu lẻ (1, 3, 5). Vậy có 2! * 3! = 2 * 6 = 12 cách. Tổng cộng, có 12 + 12 = 24 cách xếp thỏa mãn yêu cầu. Vậy đáp án đúng là 24.

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 4

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

Một đa giác lồi n cạnh sẽ có bao nhiêu đường chéo? (Một đa giác được gọi là lồi nếu mọi đoạn thẳng nối 2 điểm bên trong hoặc trên biên nằm hoàn toàn trong nó).

Lời giải:

Đáp án đúng: A

Một đa giác lồi n cạnh có n đỉnh. Từ mỗi đỉnh, ta có thể vẽ đường chéo đến n-3 đỉnh còn lại (trừ chính nó và hai đỉnh kề nó). Như vậy, có n(n-3) đường chéo được vẽ. Tuy nhiên, mỗi đường chéo được tính hai lần (ví dụ, đường chéo nối đỉnh A và đỉnh B giống như đường chéo nối đỉnh B và đỉnh A), nên số đường chéo thực tế là n(n-3)/2.

Câu 17:

Thuật toán Dijkstra được áp dụng cho:

Lời giải:

Đáp án đúng: B

Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm. Nó có thể áp dụng cho cả đồ thị vô hướng và đồ thị có hướng, miễn là các cạnh đều có trọng số không âm. Nếu đồ thị có cạnh âm, thuật toán Dijkstra không đảm bảo tìm được đường đi ngắn nhất chính xác. Vì vậy, đáp án phù hợp nhất là đồ thị vô hướng hoặc có hướng có trọng số không âm.

Câu 18:

Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal:

Lời giải:

Đáp án đúng: B

Thuật toán Prim bắt đầu từ một đỉnh và mở rộng cây khung bằng cách thêm các cạnh có trọng số nhỏ nhất, *luôn* kết nối với một đỉnh đã thuộc cây khung. Điều quan trọng là thuật toán này luôn duy trì tính liên thông của cây khung. Trong khi đó, thuật toán Kruskal xem xét tất cả các cạnh theo thứ tự trọng số tăng dần và chọn cạnh nào không tạo thành chu trình, bất kể cạnh đó có liên thông với cây khung hiện tại hay không (cho đến khi tất cả các đỉnh được kết nối). Do đó, đáp án đúng là phương án 2.

Câu 19:

Hãy cho biết đồ thị nào dưới đây là một cây?

Lời giải:

Đáp án đúng: C

Một đồ thị được gọi là cây nếu nó liên thông và không có chu trình. - Hình 1 có chu trình (ví dụ: chu trình đi qua các đỉnh ở giữa). - Hình 2 có chu trình (hình vuông). - Hình 3 không liên thông vì có một đỉnh tách biệt. - Hình 4 liên thông và không có chu trình. Vậy, đáp án đúng là hình 4.

Câu 20:

Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.

Lời giải:

Đáp án đúng: A

Theo định lý Ford-Fulkerson, giá trị luồng cực đại từ điểm phát s đến điểm thu t bằng khả năng thông qua của lát cắt hẹp nhất (min cut) tách điểm s và t. Lát cắt hẹp nhất là lát cắt có tổng khả năng thông qua nhỏ nhất trong số tất cả các lát cắt phân tách s và t.

Câu 21:

Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu:

Lời giải: