Hàm Boole f = x + xy tương đương với hàm nào sau đây?

f = xy

f = y

f = x+y

f = x

Trả lời:

Đáp án đúng: D

Để tìm hàm Boole tương đương với f = x + xy, ta có thể sử dụng các định luật đại số Boole để đơn giản hóa biểu thức.

Ta có: f = x + xy = x(1 + y)

Vì (1 + y) luôn bằng 1 trong đại số Boole (do y chỉ có thể là 0 hoặc 1), nên:

f = x(1) = x

Vậy, hàm Boole f = x + xy tương đương với hàm f = x.

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 11

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 1:

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:

Lời giải:

Đáp án đúng: B

Thuật toán sinh tổ hợp chập k của n phần tử hoạt động bằng cách tìm từ phải sang trái phần tử a[i] đầu tiên mà a[i] < n - k + i. Sau đó tăng a[i] lên 1 đơn vị và cập nhật các phần tử phía sau a[i] theo quy tắc a[j] = a[j-1] + 1 với j > i.

Xét cấu hình 1 4 5 6:

* Phương án A: 2 1 3 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.
* Phương án B: 1 2 4 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 2 (vì 2 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 3. Các phần tử phía sau sẽ là a[3] = 3 + 1 = 4, a[4] = 4 + 1 = 5. Vậy cấu hình sinh ra là 1 3 4 5, khác với cấu hình 1 4 5 6.
* Phương án C: 1 3 5 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 3 (vì 3 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 4. Các phần tử phía sau sẽ là a[3] = 4 + 1 = 5, a[4] = 5 + 1 = 6. Vậy cấu hình sinh ra là 1 4 5 6.
* Phương án D: 2 1 4 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.

Vậy, cấu hình 1 3 5 6 sinh ra cấu hình 1 4 5 6 theo thuật toán sinh tổ hợp.

Câu 2:

Đồ thị đủ Kn là đồ thị đơn vô hướng có n đỉnh. Bậc của mỗi đỉnh là:

Lời giải:

Đáp án đúng: C

Trong đồ thị đủ Kn, mỗi đỉnh được nối với tất cả các đỉnh còn lại. Vì vậy, mỗi đỉnh sẽ có bậc là n - 1. Đáp án C là đáp án chính xác.

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)}. 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 đường đi từ đỉnh 1 đến đỉnh 6 tìm được bằng phép duyệt theo chiều sâu là đường đi nào dưới đây?

Lời giải:

Đáp án đúng: C

Duyệt đồ thị theo chiều sâu (DFS) bắt đầu từ đỉnh 1. Ta xét các đỉnh kề với đỉnh 1 theo thứ tự từ điển: 2, 3, 6.

- Nếu đi theo đỉnh 2: Ta có đường đi 1 - 2. Từ đỉnh 2, xét các đỉnh kề theo thứ tự từ điển: 3, 5, 6.
- Nếu đi theo đỉnh 3: Ta có đường đi 1 - 2 - 3. Từ đỉnh 3, các đỉnh kề là 1, 2. Đã duyệt 1 và 2 nên quay lui.
- Nếu đi theo đỉnh 5: Ta có đường đi 1 - 2 - 5. Từ đỉnh 5, xét các đỉnh kề theo thứ tự từ điển: 4, 6.
- Nếu đi theo đỉnh 4: Ta có đường đi 1 - 2 - 5 - 4. Từ đỉnh 4, xét các đỉnh kề theo thứ tự từ điển: 5, 6.
- Nếu đi theo đỉnh 5: Đã duyệt.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 5 - 4 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 5 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 3: Ta có đường đi 1 - 3. Từ đỉnh 3, các đỉnh kề là 1, 2. Đã duyệt 1 và 2 nên quay lui.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 6. Đây là một đường đi từ 1 đến 6.

Như vậy, các đường đi từ 1 đến 6 có thể tìm được bằng DFS là: 1 - 6, 1 - 2 - 6, 1 - 2 - 5 - 6, 1 - 2 - 5 - 4 - 6. Do các đỉnh được xét theo thứ tự từ điển, đường đi tìm thấy đầu tiên sẽ là 1 - 6.

Câu 4:

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

Lời giải:

Đáp án đúng: B

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.

Câu 5:

Có bao nhiêu xâu nhị phân độ dài 5 sao cho bít đầu và bít cuối bằng nhau?

Lời giải:

Đáp án đúng: D

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.

Câu 6:

Cho mạng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6} và tập cung E = {(1,6),(2,1),(2,5),(2,6),(3,1),(3,2),(5,4),(5,6),(6,4)}. Khả năng thông qua trên các cung được cho như sau: c(1,6) = 6, c(2,1)=5, c(2,5) = 2, c(2,6) = 4, c(3,1) = 9, c(3,2) = 7, c(5,4) = 8, c(5,6) = 6, c(6,4) = 8. Hỏi luồng cực đại trên G có giá trị bằng bao nhiêu?

Lời giải: