Cho đồ thị G có 9 đỉnh có bậc lần lượt là 1, 2, 2, 3, 3, 4, 4, 4, 5. Số cạnh của đồ thị G là:

Trả lời:

Đáp án đúng: D

Tổng bậc của tất cả các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị đó. Gọi số cạnh của đồ thị G là m. Ta có: 2m = 1 + 2 + 2 + 3 + 3 + 4 + 4 + 4 + 5 = 28 => m = 14. Vậy số cạnh của đồ thị G là 14.

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 10

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 50:

Trong các phát biểu sau đây phát biểu nào không là mệnh đề.

Lời giải:

Đáp án đúng: D

Mệnh đề là một câu khẳng định có tính đúng hoặc sai. Các phát biểu A, B, C, D đều là các câu khẳng định có thể xác định được tính đúng sai của chúng.

Tuy nhiên, không có phương án nào trong các lựa chọn là một câu không phải là mệnh đề. Có thể câu hỏi hoặc các phương án có lỗi, hoặc có thể câu hỏi đang kiểm tra một khía cạnh khác về mệnh đề (ví dụ như mệnh đề chứa biến), nhưng với thông tin hiện tại, không thể xác định một đáp án "không là mệnh đề" một cách chắc chắn.

Vì không có đáp án đúng trong các lựa chọn đã cho, nên câu hỏi này có thể cần được xem xét lại.

Câu 1:

Một nhóm có 7 bạn sinh viên gồm 3 nữ và 4 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ỹ? Biết rằng: thủ quỹ phải là nữ và không ai trong số các bạn được bầu, được giữ chức danh kiêm nhiệm.

Lời giải:

Đáp án đúng: B

Để giải bài toán này, ta thực hiện các bước sau:

1. Chọn thủ quỹ: Vì thủ quỹ phải là nữ và có 3 bạn nữ, nên có 3 cách chọn thủ quỹ.
2. Chọn trưởng nhóm: Sau khi chọn thủ quỹ, còn lại 6 người (3 nam và 2 nữ). Vậy có 6 cách chọn trưởng nhóm.
3. Chọn phó nhóm: Sau khi chọn thủ quỹ và trưởng nhóm, còn lại 5 người. Vậy có 5 cách chọn phó nhóm.

Vậy, tổng số cách bầu là: 3 * 6 * 5 = 90 cách.

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

Câu 2:

Dãy 1 2 5 6 là tổ hợp chập 4 của 6 phần tử, cấu hình đứng liền sau của dãy này theo thuật toán sinh là:

Lời giải:

Đáp án đúng: B

Câu hỏi này kiểm tra kiến thức về thuật toán sinh tổ hợp. Cho một tổ hợp chập k của n phần tử, thuật toán sinh sẽ tạo ra tổ hợp kế tiếp theo thứ tự từ điển.

Để tìm cấu hình kế tiếp của dãy 1 2 5 6, ta thực hiện như sau:

1. Bắt đầu từ phần tử cuối cùng (6), tìm phần tử đầu tiên từ phải sang trái mà có thể tăng lên được. Trong trường hợp này, đó là 2. Vì 2 có thể tăng lên (để tạo ra một tổ hợp hợp lệ), ta tăng 2 lên thành 3.

2. Các phần tử đứng sau 3 (trong trường hợp này là các vị trí thứ 3 và thứ 4 của dãy mới) sẽ được điền các giá trị nhỏ nhất có thể, lớn hơn phần tử trước đó. Do đó, sau 3 sẽ là 4 và 5.

Vậy, cấu hình kế tiếp của dãy 1 2 5 6 là 1 3 4 5.

Do đó, đáp án đúng là C.

Câu 3:

Có bao nhiêu cách mua 7 quả trái cây từ 3 loại cam, xoài, quít. Mỗi loại hiện có không ít hơn 7 quả.

Lời giải:

Đáp án đúng: B

Đây là bài toán chia kẹo Euler. Ta cần tìm số nghiệm nguyên không âm của phương trình x + y + z = 7, trong đó x, y, z lần lượt là số cam, xoài, quít được mua.

Số nghiệm của phương trình này là tổ hợp chập 7 của (3 + 7 - 1), tức là C(7, 3+7-1) = C(7, 9) = C(2, 9) = (9!)/(7!2!) = (9*8)/2 = 36.

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

Câu 4:

Dãy bit tiếp sau của dãy 10010011 trong thuật toán liệt kê tất cả các xâu nhị phân có độ dài 8 bằng phương pháp sinh.

Lời giải:

Đáp án đúng: D

Thuật toán sinh xâu nhị phân độ dài n hoạt động bằng cách bắt đầu từ xâu "00...0" (n số 0) và lặp lại các bước sau cho đến khi đạt đến xâu "11...1" (n số 1):

1. Tìm vị trí bit 0 cuối cùng: Duyệt xâu từ phải sang trái, tìm vị trí `i` đầu tiên mà bit tại vị trí đó là 0.
2. Đổi bit 0 thành 1: Đặt bit tại vị trí `i` thành 1.
3. Đặt các bit sau vị trí i thành 0: Tất cả các bit từ vị trí `i+1` đến cuối xâu đều được đặt thành 0.

Áp dụng vào bài toán:
Dãy bit hiện tại là 10010011.

1. Tìm vị trí bit 0 cuối cùng: Duyệt từ phải sang trái, ta thấy vị trí bit 0 cuối cùng là vị trí thứ 2 từ phải sang (tức là vị trí thứ 7 từ trái sang).
2. Đổi bit 0 thành 1: Dãy bit trở thành 10010111.
3. Đặt các bit sau vị trí i thành 0: Không có bit nào sau vị trí i.

Vậy, dãy bit tiếp theo là 10010100 (A).

Câu 5:

Có bao nhiêu xâu nhị phân độ dài 5?

Lời giải: