Cho đồ thị G = (V, E), |V| = n đỉnh, |E| = m cạnh. Khi đó đường đi Hamilton trong G có:

n đỉnh

n+1 đỉnh

1 đỉnh

2 đỉnh

Trả lời:

Đáp án đúng: A

Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị đúng một lần. Vì vậy, nếu đồ thị có n đỉnh thì đường đi Hamilton sẽ có n đỉnh.

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 2

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 1:

Dãy nhị phân độ dài 5 hiện tại là 01011 dãy liền sau dãy này theo thuật toán sinh là:

Lời giải:

Đáp án đúng: D

Thuật toán sinh dãy nhị phân kế tiếp thực hiện như sau:

1. Tìm vị trí bit 0 từ phải sang trái: Bắt đầu từ cuối dãy, tìm bit '0' đầu tiên.
2. Đảo bit: Đảo bit '0' này thành '1'.
3. Đặt lại các bit sau: Tất cả các bit từ vị trí vừa đảo trở về cuối dãy được đặt lại thành '0'.

Áp dụng vào dãy `01011`:

1. Duyệt từ phải sang, bit '0' đầu tiên xuất hiện ở vị trí thứ hai từ phải sang (tức là bit thứ hai từ phải qua là 1, bit thứ nhất từ phải qua là 1, đến bit thứ hai thì dừng lại, bit này bằng 0).
2. Đảo bit này thành '1': `01111`
3. Đặt lại tất cả các bit sau bit vừa đảo thành '0': `01100`

Vậy dãy nhị phân kế tiếp là `01100`.

Câu 2:

Một nhóm có 9 bạn sinh viên gồm 4 nữ và 5 nam. Hỏi có bao nhiêu cách chọn 3 bạn đi dự hội thảo? Biết rằng trong số 3 bạn đi dự có ít nhất một nữ.

Lời giải:

Đáp án đúng: B

Số cách chọn 3 bạn bất kỳ từ 9 bạn là C(9,3) = 84.
Số cách chọn 3 bạn nam từ 5 bạn nam là C(5,3) = 10.
Số cách chọn 3 bạn sao cho có ít nhất một nữ là: C(9,3) - C(5,3) = 84 - 10 = 74.
Vậy đáp án đúng là 74.

Câu 3:

Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8} và tập cạnh E = {(1,2), (1,3), (1,6), (2,3), (2,5)}. Hỏi số cạnh (nối giữa các đỉnh trong V) ít nhất cần bổ sung thêm vào G là bao nhiêu để G trở thành đồ thị Euler?

Lời giải:

Đáp án đúng: C

Để một đồ thị vô hướng trở thành đồ thị Euler, tất cả các đỉnh của nó phải có bậc chẵn. Ta kiểm tra bậc của các đỉnh trong đồ thị đã cho:

- Đỉnh 1 có bậc 3 (kết nối với 2, 3, 6)
- Đỉnh 2 có bậc 3 (kết nối với 1, 3, 5)
- Đỉnh 3 có bậc 2 (kết nối với 1, 2)
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 1 (kết nối với 2)
- Đỉnh 6 có bậc 1 (kết nối với 1)
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Các đỉnh có bậc lẻ là 1, 2, 5, 6. Để biến đồ thị thành đồ thị Euler, ta cần thêm cạnh để biến các đỉnh có bậc lẻ thành bậc chẵn. Số lượng cạnh ít nhất cần thêm bằng một nửa số đỉnh bậc lẻ. Ở đây, ta có 4 đỉnh bậc lẻ, nên ta cần ít nhất 4/2 = 2 cạnh.

Ví dụ, ta có thể thêm cạnh (1,5) và (2,6). Khi đó:

- Đỉnh 1 có bậc 4
- Đỉnh 2 có bậc 4
- Đỉnh 3 có bậc 2
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 2
- Đỉnh 6 có bậc 2
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Hoặc ta có thể thêm cạnh (1,2) và (5,6). Khi đó:

- Đỉnh 1 có bậc 4
- Đỉnh 2 có bậc 4
- Đỉnh 3 có bậc 2
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 2
- Đỉnh 6 có bậc 2
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Như vậy, cần thêm ít nhất 2 cạnh.

Câu 4:

Phát biểu nào sau đây là đúng?

Lời giải:

Đáp án đúng: A

Đáp án đúng là A.

Chu trình Hamilton trên đồ thị vô hướng G là một chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần (trừ đỉnh xuất phát, đỉnh này xuất hiện hai lần: đầu và cuối chu trình). Phương án B sai vì nó mô tả chu trình Euler, không phải chu trình Hamilton.

Câu 5:

Có bao nhiêu xâu nhị phân độ dài 5 không chứa 2 bít 1 đứng cạnh nhau?

Lời giải:

Đáp án đúng: C

Để giải bài toán này, ta có thể sử dụng phương pháp đệ quy hoặc quy hoạch động. Gọi $a_n$ là số xâu nhị phân độ dài $n$ không chứa hai bit 1 đứng cạnh nhau.

- Với $n = 1$, ta có 2 xâu là "0" và "1", vậy $a_1 = 2$.
- Với $n = 2$, ta có 3 xâu là "00", "01" và "10", vậy $a_2 = 3$.

Ta có thể xây dựng xâu độ dài $n$ từ xâu độ dài $n-1$ và $n-2$ như sau:

- Nếu xâu độ dài $n-1$ kết thúc bằng 0, ta có thể thêm 0 hoặc 1 vào cuối.
- Nếu xâu độ dài $n-1$ kết thúc bằng 1, ta chỉ có thể thêm 0 vào cuối.

Vậy, số xâu độ dài $n$ sẽ bằng số xâu độ dài $n-1$ kết thúc bằng 0 cộng với số xâu độ dài $n-1$ kết thúc bằng 1 cộng với số xâu độ dài $n-2$ kết thúc bằng 0 khi ta thêm '10' vào. Điều này dẫn đến công thức truy hồi: $a_n = a_{n-1} + a_{n-2}$.

Áp dụng công thức này:
- $a_3 = a_2 + a_1 = 3 + 2 = 5$
- $a_4 = a_3 + a_2 = 5 + 3 = 8$
- $a_5 = a_4 + a_3 = 8 + 5 = 13$

Vậy, có 13 xâu nhị phân độ dài 5 không chứa 2 bít 1 đứng cạnh nhau.

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 đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?

Lời giải: