50 câu hỏi 60 phút
Giả sử dãy 1 4 5 6 là cấu hình hiện tại tổ hợp chập 4 của 6 phần tử. Cấu hình nào sau đây sinh ra cấu hình này theo thuật toán sinh:
2135
1246
1356
50 câu hỏi 60 phút
45 câu hỏi 60 phút
50 câu hỏi 60 phút
22 câu hỏi 60 phút
50 câu hỏi 60 phút
50 câu hỏi 60 phút
50 câu hỏi 60 phút
50 câu hỏi 60 phút
50 câu hỏi 60 phút
50 câu hỏi 60 phút
Câu hỏi này kiểm tra kiến thức về chu trình Euler trong lý thuyết đồ thị.
Phương án A: Sai. Phát biểu này mô tả chu trình Hamilton, không phải chu trình Euler.
Phương án B: Đúng. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.
Phân tích bài toán:
Đề bài yêu cầu tìm số xâu nhị phân có độ dài 5 thỏa mãn điều kiện bít đầu và bít cuối bằng nhau.
Cách giải:
Ta chia bài toán thành 2 trường hợp:
- Trường hợp 1: Bít đầu và bít cuối đều là 0. Khi đó, ta có xâu dạng 0 _ _ _ 0. Có 3 vị trí ở giữa, mỗi vị trí có 2 lựa chọn (0 hoặc 1). Vậy có 2*2*2 = 8 xâu.
- Trường hợp 2: Bít đầu và bít cuối đều là 1. Khi đó, ta có xâu dạng 1 _ _ _ 1. Tương tự trường hợp 1, có 3 vị trí ở giữa, mỗi vị trí có 2 lựa chọn (0 hoặc 1). Vậy có 2*2*2 = 8 xâu.
Tổng cộng, có 8 + 8 = 16 xâu thỏa mãn.