Một nhóm có 8 bạn sinh viên gồm 3 nữ và 5 nam. Hỏi có bao nhiêu cách bầu một trưởng nhóm, một phó nhóm và một thủ quỹ? Không ai trong các bạn được bầu giữ chức danh kiêm nhiệm.

336

312

432

286

Trả lời:

Đáp án đúng: C

Đây là bài toán về hoán vị. Ta cần chọn 3 người từ 8 người vào 3 vị trí khác nhau (trưởng nhóm, phó nhóm, thủ quỹ). Số cách chọn trưởng nhóm là 8. Sau khi chọn trưởng nhóm, số cách chọn phó nhóm là 7. Sau khi chọn trưởng nhóm và phó nhóm, số cách chọn thủ quỹ là 6. Vậy tổng số cách chọn là 8 * 7 * 6 = 336. Đáp án đúng là A.

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Phần 7

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 3:

Cho đồ thị vô hướng G= (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,2), (1,3), (1,6), (2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Hỏi G có phải là đồ thị đầy đủ không?

Lời giải:

Đáp án đúng: A

Đồ thị đầy đủ là đồ thị mà giữa hai đỉnh bất kỳ đều có cạnh nối.

Trong đồ thị G đã cho, ta thấy đỉnh 1 không kề với đỉnh 4 và đỉnh 3 không kề với đỉnh 4 và đỉnh 3 không kề với đỉnh 5. Như vậy, đồ thị G không phải là đồ thị đầy đủ.

Câu 4:

Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Thực hiện phép duyệt đồ thị G theo chiều sâu (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi thứ tự các đỉnh được thăm trong phép duyệt theo chiều sâu là thứ tự nào dưới đây?

Lời giải:

Đáp án đúng: B

Duyệt đồ thị theo chiều sâu (DFS - Depth First Search) bắt đầu từ đỉnh 1. Theo thứ tự từ điển, ta chọn đỉnh kề nhỏ nhất chưa được thăm.

1. Bắt đầu từ đỉnh 1, các đỉnh kề là 2, 3, 6. Chọn đỉnh 2.
2. Từ đỉnh 2, các đỉnh kề chưa thăm là 3, 5, 6. Chọn đỉnh 3.
3. Từ đỉnh 3, các đỉnh kề chưa thăm là 6. Chọn đỉnh 6.
4. Từ đỉnh 6, các đỉnh kề chưa thăm là 4, 5. Chọn đỉnh 4.
5. Từ đỉnh 4, đỉnh kề chưa thăm là 5. Chọn đỉnh 5.

Vậy thứ tự duyệt là: 1, 2, 3, 6, 4, 5.

Câu 5:

Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6),(1,5)}. Hỏi chu trình nào dưới đây là chu trình Hamilton?

Lời giải:

Đáp án đúng: A

Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần, trừ đỉnh đầu tiên (cũng là đỉnh cuối cùng).

Xét từng phương án:

Phương án A: 1 – 3 – 2 – 5 – 4 – 6 – 1. Chu trình này đi qua tất cả các đỉnh {1, 2, 3, 4, 5, 6} mỗi đỉnh đúng một lần (trừ đỉnh 1 lặp lại ở cuối). Đây là một chu trình Hamilton.
Phương án B: 1 – 2 – 3 – 1 – 5 – 4 – 6 – 1. Đỉnh 1 xuất hiện 3 lần, đỉnh 5, 4, 6 mỗi đỉnh xuất hiện 1 lần, đỉnh 2, 3 xuất hiện 1 lần, không phải chu trình Hamilton.
Phương án C: 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1. Các đỉnh 2, 5, 6 xuất hiện nhiều hơn 1 lần. Không phải chu trình Hamilton.

Vậy, phương án A là đáp án đúng.

Câu 6:

Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi thứ tự các đỉnh được thăm trong phép duyệt theo chiều rộng là thứ tự nào dưới đây?

Lời giải:

Đáp án đúng: B

Ta sẽ thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 1 (do không có đỉnh nào được chỉ định trước). Khi duyệt, ta sẽ ưu tiên thăm các đỉnh theo thứ tự từ điển (tức là số nhỏ hơn được thăm trước).

1. Bắt đầu từ đỉnh 1: Đưa 1 vào hàng đợi và đánh dấu đã thăm.
2. Các đỉnh kề của 1: Các đỉnh kề của 1 là 2, 3, và 6. Theo thứ tự từ điển, ta thăm 2, sau đó 3, sau đó 6. Đưa 2, 3, 6 vào hàng đợi.
3. Thăm đỉnh 2: Các đỉnh kề của 2 là 1, 3, 5, và 6. 1 đã thăm. 3 và 6 đã được đưa vào hàng đợi. Vậy ta chỉ cần đưa 5 vào hàng đợi.
4. Thăm đỉnh 3: Các đỉnh kề của 3 là 1 và 2, cả hai đều đã thăm.
5. Thăm đỉnh 6: Các đỉnh kề của 6 là 1, 2, 4, 5. 1 và 2 đã thăm. 5 đã được đưa vào hàng đợi. Ta đưa 4 vào hàng đợi.
6. Thăm đỉnh 5: Các đỉnh kề của 5 là 2, 4, 6. Cả 3 đều đã thăm.
7. Thăm đỉnh 4: Các đỉnh kề của 4 là 5, 6. Cả 2 đều đã thăm

Như vậy, thứ tự các đỉnh được thăm là: 1, 2, 3, 6, 5, 4.

Câu 7:

Xác định tập lũy thừa của tập A = {ôtô, Lan}

Lời giải:

Đáp án đúng: D

Tập lũy thừa của một tập A, ký hiệu P(A), là tập hợp tất cả các tập con của A, kể cả tập rỗng (∅) và chính tập A. Trong trường hợp này, A = {ôtô, Lan}.

Vậy, các tập con của A bao gồm:

- Tập rỗng: ∅
- Tập chứa một phần tử: {ôtô}, {Lan}
- Tập chứa hai phần tử: {ôtô, Lan}

Do đó, tập lũy thừa của A là P(A) = {∅, {ôtô}, {Lan}, {ôtô, Lan}}.

So sánh với các phương án:

- Phương án A thiếu tập rỗng và có chứa phần tử "táo" không thuộc tập A.
- Phương án B thiếu tập rỗng.
- Phương án C thiếu tập {ôtô, Lan}.
- Phương án D đầy đủ tất cả các tập con của A, bao gồm cả tập rỗng và chính tập A.

Vậy đáp án đúng là D.

Câu 8:

Cho 2 tập A, B với |A|=100, |B|=200, A⊆B.|A∪B| là.

Lời giải: