Chọn phát biểu nào sau đây là chính xác nhất:

Cho G là đồ thị bất kỳ. Một đường đi trong G là đường Hamilton khi và chỉ khi đường đi đó đi qua tất cả các cạnh trong G và mỗi cạnh xuất hiện đúng một lần.

Cho G là đồ thị bất kỳ. Một đường sơ cấp trong G là đường Hamilton khi và chỉ khi đường đi đó đi qua tất cả các đỉnh trong G và mỗi đỉnh xuất hiện đúng một lần.

Cho G là đồ thị bất kỳ. Một đường sơ cấp trong G là đường Hamilton khi và chỉ khi đường đi đó đi qua tất cả các cạnh trong G.

Cho G là đồ thị bất kỳ. Một đường đi trong G là đường Hamilton khi và chỉ khi 69 đường đi đó đi qua tất cả các đỉnh trong G.

Trả lời:

Đáp án đúng: B

Đường Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ xuất hiện một lần duy nhất. Vì vậy, phương án 2 là đáp án chính xác nhất. Các phương án còn lại mô tả không đúng về đường Hamilton hoặc nhầm lẫn với các khái niệm khác như đường Euler.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 2

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 1:

Xét các hàm từ R tới R, hàm nào là khả nghịch:

Lời giải:

Đáp án đúng: C

Hàm khả nghịch (hay hàm ngược) là hàm mà mỗi giá trị của miền giá trị chỉ tương ứng với một giá trị duy nhất của miền xác định. Điều này có nghĩa là hàm phải đơn ánh (injective) và toàn ánh (surjective). Nói cách khác, hàm phải là song ánh (bijective).

1. \(f(x) = x^2 - 4x + 5\) tương đương \(f(x)=(x-2)^2+1\). Hàm này không đơn ánh vì ví dụ \(f(1) = f(3) = 2\). Do đó, hàm này không khả nghịch.
2. \(f(x) = x^4\). Hàm này cũng không đơn ánh vì ví dụ \(f(1) = f(-1) = 1\). Do đó, hàm này không khả nghịch.
3. \(f(x) = x^3\). Hàm này là đơn ánh và toàn ánh trên R. Vì vậy, hàm này khả nghịch. Hàm ngược của nó là \(f^{-1}(x) = \sqrt[3]{x}\).
4. \(f(x) = 6 - x^2\). Hàm này không đơn ánh vì ví dụ \(f(1) = f(-1) = 5\). Do đó, hàm này không khả nghịch.

Vậy, chỉ có hàm \(f(x) = x^3\) là khả nghịch.

Câu 2:

Cho tập A = {a, b}, B = {0, 1, 2} câu nào dưới đây là SAI:

Lời giải:

Đáp án đúng: A

A = {a, b}, |A| = 2
B = {0, 1, 2}, |B| = 3
A x B = {(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}
B x A = {(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}
|A x B| = |A| * |B| = 2 * 3 = 6
|B x A| = |B| * |A| = 3 * 2 = 6
Vậy |A x B| = |B x A| = |A| x |B| = |B| x |A|
Nhưng A x B ≠ B x A
=> Đáp án A sai

Câu 3:

Có bao nhiêu xâu nhị phân độ dài là 8 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11.

Lời giải:

Đáp án đúng: A

Gọi A là tập các xâu nhị phân độ dài 8 bắt đầu bởi 00, B là tập các xâu nhị phân độ dài 8 kết thúc bởi 11. Bài toán yêu cầu tính |A ∪ B|.

Ta có:
- Tổng số xâu nhị phân độ dài 8 là 2^8 = 256.
- Số xâu nhị phân độ dài 8 bắt đầu bằng 00 là: |A| = 2^(8-2) = 2^6 = 64.
- Số xâu nhị phân độ dài 8 kết thúc bằng 11 là: |B| = 2^(8-2) = 2^6 = 64.
- Số xâu nhị phân độ dài 8 vừa bắt đầu bằng 00 vừa kết thúc bằng 11 là: |A ∩ B| = 2^(8-2-2) = 2^4 = 16.

Theo nguyên lý bao hàm và loại trừ, ta có:
|A ∪ B| = |A| + |B| - |A ∩ B| = 64 + 64 - 16 = 112.

Vậy, có 112 xâu nhị phân độ dài 8 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11.

Câu 4:

Trong lớp CNTT có 50 sinh viên học tiếng Anh; 20 sinh viên học tiếng Pháp và 10 sinh viên học cả Anh và Pháp. Cho biết sĩ số của lớp là 80. Hỏi có bao nhiêu sinh viên không học tiếng Anh, Pháp.

Lời giải:

Đáp án đúng: D

Số sinh viên học tiếng Anh hoặc tiếng Pháp là: 50 + 20 - 10 = 60. Vì sĩ số lớp là 80, nên số sinh viên không học tiếng Anh hoặc tiếng Pháp là: 80 - 60 = 20.

Câu 5:

Số xâu nhị phân độ dài 4 có bít cuối cùng bằng 1 là:

Lời giải:

Đáp án đúng: A

Ta cần tìm số xâu nhị phân độ dài 4 có bit cuối cùng bằng 1. Vì bit cuối cùng đã được xác định là 1, ta chỉ cần xét 3 bit đầu tiên. Mỗi bit trong 3 bit đầu tiên có thể là 0 hoặc 1, tức là có 2 lựa chọn. Vậy số lượng xâu nhị phân thỏa mãn là 2 * 2 * 2 = 8.

Câu 6:

Cho A ={1, 2, 3, 4, 5}. Quan hệ R được xác định: \(\forall a,b \in A,aRb \Leftrightarrow a + b = 2k(k = 1,2,...)\). Quan hệ R được biểu diễn là:

Lời giải: