Trong bảng Karnaugh, 2 ô gọi là kề nhau nếu...?

Chúng nằm trên cùng 1 hàng

Chúng nằm trên cùng 1 cột

Nếu chúng cùng nằm trên 1 hàng, 1 cột hoặc chúng là ô đầu, ô cuối của cùng một hàng hoặc 1 cột nào đó

Nếu chúng là hai ô liền nhau hoặc chúng là ô đầu và ô cuối của cùng một hàng hoặc 1 cột nào đó

Trả lời:

Đáp án đúng: D

Trong bảng Karnaugh, hai ô được gọi là kề nhau nếu chúng liền kề nhau về mặt vật lý (nằm cạnh nhau) hoặc chúng là ô đầu và ô cuối của cùng một hàng hoặc một cột. Tính chất kề nhau này cho phép ta nhóm các ô lại với nhau để đơn giản hóa biểu thức logic.

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 1

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 50:

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

Lời giải:

Đáp án đúng: B

Bậc của đồ thị là tổng bậc của tất cả các đỉnh. Trong trường hợp này, bậc của đồ thị G là 2 + 2 + 3 + 4 + 5 = 16.

Câu 1:

Hoán vị nào sau đây đứng liền sau hoán vị 1 3 4 2 theo thuật toán sinh

Lời giải:

Đáp án đúng: B

Thuật toán sinh hoán vị hoạt động như sau:

1. Tìm j lớn nhất: Tìm j lớn nhất sao cho a[j] < a[j+1]. Nếu không tồn tại j, thì đây là hoán vị cuối cùng.
2. Tìm l lớn nhất: Tìm l lớn nhất sao cho a[l] > a[j].
3. Đổi chỗ: Đổi chỗ a[j] và a[l].
4. Lật ngược: Lật ngược đoạn từ a[j+1] đến a[n].

Trong trường hợp này, hoán vị hiện tại là 1 3 4 2.

* Bước 1: Tìm j lớn nhất sao cho a[j] < a[j+1]. Ở đây, j = 2 (vì 3 < 4).
* Bước 2: Tìm l lớn nhất sao cho a[l] > a[j] (tức a[l] > 3). Ở đây, l = 3 (vì 4 > 3).
* Bước 3: Đổi chỗ a[j] và a[l]. Ta được hoán vị 1 4 3 2.
* Bước 4: Lật ngược đoạn từ a[j+1] đến a[n] (tức là lật ngược đoạn 3 2). Ta được hoán vị 1 4 2 3.

Vậy, hoán vị kế tiếp của 1 3 4 2 là 1 4 2 3. Tuy nhiên, đáp án này không có trong các lựa chọn. Có vẻ như có sự nhầm lẫn trong các đáp án được cung cấp, vì không có đáp án nào đúng.

Câu 2:

Trong lớp có 15 bạn nam và 15 bạn nữ. Hỏi có bao nhiêu cách bầu ra ban cán bộ lớp bao gồm 1 bạn nam và 2 bạn nữ?

Lời giải:

Đáp án đúng: B

Số cách chọn 1 bạn nam từ 15 bạn nam là C(15,1) = 15.
Số cách chọn 2 bạn nữ từ 15 bạn nữ là C(15,2) = 15! / (2! * 13!) = (15 * 14) / 2 = 105.
Vậy, số cách bầu ra ban cán bộ lớp bao gồm 1 bạn nam và 2 bạn nữ là: 15 * 105 = 1575.

Câu 3:

Có 5 công việc đánh số 1, 2, 3, 4, 5 và 5 người thợ được đánh số 1, 2, 3, 4, 5. Tùy thuộc tay nghề chuyên môn, mỗi thợ chỉ có thể thực hiện 1 số công việc nào đó: Người thợ 1 chỉ có thể thực hiện công việc 4, thợ 2 chỉ có thể thực hiện công việc 1 hoặc 5, thợ 3 chỉ có thể thực hiện công việc 4, thợ 4 chỉ có thể thực hiện công việc 2 hoặc 3, thợ 5 chỉ có thể thực hiện công việc 1 hoặc 5. Hỏi có thể chọn ra nhiều nhất bao nhiêu công việc để phân công cho thợ sao cho mỗi công việc chỉ được thực hiện bởi duy nhất 1 người thợ (phù hợp tay nghề chuyên môn) và mỗi thợ không được thực hiện quá 1 công việc?

Lời giải:

Đáp án đúng: B

Bài toán này thuộc loại bài toán tìm cặp ghép cực đại trong đồ thị hai phía. Ta có thể biểu diễn mối quan hệ giữa thợ và công việc bằng một đồ thị hai phía, trong đó một bên là tập các thợ, một bên là tập các công việc, và có cạnh nối giữa thợ và công việc nếu thợ đó có thể thực hiện công việc đó.

Thợ 1: Công việc 4
Thợ 2: Công việc 1, 5
Thợ 3: Công việc 4
Thợ 4: Công việc 2, 3
Thợ 5: Công việc 1, 5

Ta sẽ thử tìm một phương án phân công sao cho số công việc được thực hiện là lớn nhất:

1. Phân công thợ 1 cho công việc 4.
2. Phân công thợ 4 cho công việc 2.
3. Phân công thợ 5 cho công việc 1.
Như vậy, ta đã phân công được 3 công việc (1, 2, 4) cho 3 thợ (1, 4, 5).

Ta cũng có thể phân công như sau:

1. Phân công thợ 1 cho công việc 4.
2. Phân công thợ 4 cho công việc 3.
3. Phân công thợ 2 cho công việc 5.
Như vậy, ta cũng phân công được 3 công việc (3, 4, 5) cho 3 thợ (1, 2, 4).

Nếu ta cố gắng phân công 4 công việc, điều này có vẻ không khả thi vì thợ 3 cũng muốn làm công việc 4, nhưng công việc 4 đã được giao cho thợ 1. Tương tự, thợ 2 và thợ 5 đều có thể làm công việc 1 hoặc 5, nhưng nếu cả hai đều được phân công, một người sẽ phải làm công việc 1 và người còn lại làm công việc 5. Điều này vẫn chỉ cho phép tối đa 3 công việc được thực hiện.

Vậy, số công việc nhiều nhất có thể phân công là 3.

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 rộng (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?

Lời giải:

Đáp án đúng: B

Để tìm độ dài đường đi ngắn nhất từ đỉnh 6 đến đỉnh 3 trong đồ thị bằng thuật toán duyệt theo chiều rộng (BFS), ta thực hiện các bước sau:

1. Bắt đầu từ đỉnh 6: Duyệt các đỉnh kề của đỉnh 6 theo thứ tự từ điển. Các đỉnh kề của 6 là: 1, 2, 4, 5.

2. Duyệt các đỉnh kề của 6:
- Từ 6 đến 1 (độ dài đường đi = 1)
- Từ 6 đến 2 (độ dài đường đi = 1)
- Từ 6 đến 4 (độ dài đường đi = 1)
- Từ 6 đến 5 (độ dài đường đi = 1)

3. Duyệt các đỉnh kề của 1, 2, 4, 5 (theo thứ tự duyệt)
- Từ 1: Các đỉnh kề của 1 là 2, 3, 6. Ta đã duyệt 6, nên xét 2 và 3.
- Từ 6 -> 1 -> 2 (độ dài đường đi = 2)
- Từ 6 -> 1 -> 3 (độ dài đường đi = 2)
Vậy ta đã tìm thấy đường đi từ 6 đến 3 với độ dài bằng 2.

Vậy độ dài đường đi ngắn nhất từ đỉnh 6 đến đỉnh 3 là 2.

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

Câu 5:

Hỏi có bao nhiêu bộ có thứ tự (A, B) sao cho: A, B là 2 tập con của {1, 2, 3, 4}. Số phần tử của A hợp với B là 4; Số phần tử của A giao B là 1

Lời giải: