Cho đồ thị vô hướng G = (V, E), với |V| = n; |E|=m. Tổng bậc của tất cả các đỉnh trong đồ thị G là?

-1.m

-2.m

1.m

2.m

Trả lời:

Đáp án đúng: D

Trong một đồ thị vô hướng, mỗi cạnh (E) kết nối hai đỉnh. Do đó, mỗi cạnh đóng góp 2 vào tổng bậc của tất cả các đỉnh trong đồ thị. Vì vậy, tổng bậc của tất cả các đỉnh sẽ là 2 lần số cạnh (m).

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 5

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 1:

Giả sử A = (3,7,5,4) là một hoán vị hiện tại của tập {3,5,7,4}, bộ nào sau đây là hoán vị tiếp theo của hoán vị A trong thuật toán liệt kê hoán vị bằng phương pháp sinh.

Lời giải:

Đáp án đúng: A

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

1. Tìm phần tử a[k] từ cuối dãy lên: Tìm từ cuối dãy lên phần tử a[k] sao cho a[k] < a[k+1]. Nếu không tìm thấy, đây là hoán vị cuối cùng.
2. Tìm phần tử a[l] từ cuối dãy lên: Tìm từ cuối dãy lên phần tử a[l] sao cho a[l] > a[k].
3. Đổi chỗ a[k] và a[l]: Đổi chỗ hai phần tử này.
4. Đảo ngược đoạn từ k+1 đến cuối dãy: Đảo ngược thứ tự các phần tử từ vị trí k+1 đến cuối dãy.

Áp dụng vào ví dụ A = (3, 7, 5, 4):

* Bước 1: Tìm a[k]. Ta thấy 5 < 4 là sai, 7 < 5 là sai, 3 < 7 là đúng. Vậy k = 1 và a[k] = 3.
* Bước 2: Tìm a[l]. Ta thấy 4 > 3 là đúng, 5 > 3 là đúng, 7 > 3 là đúng. Vậy l = 3 và a[l] = 4.
* Bước 3: Đổi chỗ a[k] và a[l]: A trở thành (4, 7, 5, 3).
* Bước 4: Đảo ngược đoạn từ k+1 đến cuối dãy: Đảo ngược (7, 5, 3) thành (3, 5, 7). Vậy A trở thành (3, 4, 5, 7).

Vậy hoán vị tiếp theo của (3, 7, 5, 4) là (3, 4, 5, 7).

Câu 2:

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),(1,5)}. Hỏi chu trình nào dưới đây là chu trình Euler?

Lời giải:

Đáp án đúng: A

Để một chu trình là chu trình Euler, nó phải đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần và quay trở lại đỉnh xuất phát. Ta cần kiểm tra xem các chu trình được đưa ra có thỏa mãn điều kiện này hay không.

* Kiểm tra phương án A: 1 – 3 – 2 – 5 – 4 – 6 – 1
Chu trình này không đi qua cạnh (1,6), do đó nó không phải là chu trình Euler.

* Kiểm tra phương án B: 6 – 4 – 5 – 2 – 3 – 1 – 6
Chu trình này không đi qua cạnh (4,6) và không đi qua tất cả các cạnh, do đó nó không phải là chu trình Euler.

* Kiểm tra phương án C: 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1
Chu trình này đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần: (3,2), (2,1), (1,5), (5,2), (2,6), (6,5), (5,4), (4,6), (6,1), (1,3). Do đó, đây là chu trình Euler.

Vậy đáp án đúng là C.

Câu 3:

Cho đồ thị có hướ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)}. Hỏi có thể tiến hành sắp xếp TOPO các đỉnh trên G hay không?

Lời giải:

Đáp án đúng: A

Đồ thị có hướng G có thể sắp xếp TOPO khi và chỉ khi đồ thị không có chu trình. Để kiểm tra xem đồ thị đã cho có chu trình hay không, ta có thể thực hiện duyệt đồ thị (DFS hoặc BFS) và kiểm tra tính reachable của các đỉnh. Hoặc có thể kiểm tra bằng thuật toán Tarjan hoặc Kosaraju. Trong trường hợp này, ta nhận thấy có chu trình 1 -> 6 -> 4 -> (không đi đến 1 được) hoặc 2 -> 1 -> 6 -> 4 -> (không đi đến 2 được) , nhưng không có chu trình.
Tuy nhiên, ta thấy có chu trình 2 -> 1 -> 6 -> 4 -> quay lại (không trực tiếp). Hoặc 3 -> 1 -> 6 -> 4 -> (không trực tiếp quay lại 3). Do đó, đồ thị này có chu trình và không thể sắp xếp TOPO.

Câu 4:

Hỏi có bao nhiêu cách phân tích 10 thành tổng của các số nguyên dương?

Lời giải:

Đáp án đúng: B

Số cách phân tích số nguyên dương n thành tổng các số nguyên dương là $2^{n-1}$. Vậy số cách phân tích 10 thành tổng các số nguyên dương là $2^{10-1} = 2^9 = 512$. Không có đáp án đúng trong các phương án đã cho. Tuy nhiên, nếu câu hỏi là số cách phân tích 10 thành tổng các số nguyên dương *không phân biệt thứ tự* thì đáp án sẽ khác và phức tạp hơn, liên quan đến hàm phân hoạch (partition function).

Câu 5:

Hỏi phương trình sau đây có bao nhiêu nghiệm nguyên dương: X1 + X2 + X3 + X4 = 11

Lời giải:

Đáp án đúng: B

Đây là bài toán chia kẹo Euler (stars and bars). Ta cần tìm số nghiệm nguyên dương của phương trình X1 + X2 + X3 + X4 = 11.

Vì các biến Xi đều là nghiệm nguyên dương, ta đặt Yi = Xi - 1, với Yi >= 0. Khi đó phương trình trở thành:
(Y1 + 1) + (Y2 + 1) + (Y3 + 1) + (Y4 + 1) = 11
Y1 + Y2 + Y3 + Y4 = 11 - 4 = 7

Số nghiệm nguyên không âm của phương trình này là tổ hợp chập 3 của (7 + 4 - 1), tức là C(7 + 4 - 1, 4 - 1) = C(10, 3).

C(10, 3) = 10! / (3! * 7!) = (10 * 9 * 8) / (3 * 2 * 1) = 10 * 3 * 4 = 120.

Vậy, số nghiệm nguyên dương của phương trình là 120.

Câu 6:

Cho đồ thị có hướng G= (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6} và tập cung E = {(2,1),(2,5),(2,6),(3,1),(3,2),(5,4),(5,6),(6,1),(6,4)}. Trọng số các cung được cho sau đây: w(2,1) = 5, w(2,5) = 1, w(2,6) = 4, w(3,1) = 1, w(3,2) = 2, w(5,4) = 8, w(5,6) = 1, w(6,1) = 1, w(6,4) = 3. Hỏi đường đi ngắn nhất từ đỉnh 3 đến đỉnh 4 có độ dài bằng bao nhiêu?

Lời giải: