Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Kruskal có tập cạnh là:

T = { (1,2), (1, 4), (2, 3), (2, 6), (6,3), (6, 7) } B)

T = { (1,2), (1, 4), (1, 3), (2, 6), (4,5), (6, 7) }

T = { (1,2), (1, 4), (2, 4), (2, 6), (4,5), (6, 7) }

T = { (1,2), (1, 4), (2, 3), (4,5) ,(2, 6), (6, 7) }

Trả lời:

Đáp án đúng: D

Thuật toán Kruskal để tìm cây khung nhỏ nhất hoạt động như sau: 1. Sắp xếp các cạnh theo trọng số tăng dần. 2. Duyệt qua các cạnh đã sắp xếp, thêm cạnh vào cây khung nếu nó không tạo thành chu trình. Áp dụng thuật toán Kruskal cho đồ thị đã cho: 1. Sắp xếp các cạnh theo trọng số tăng dần: (1,2):1, (1,4):2, (2,3):2, (4,5):3, (2,6):4, (6,7):4, (3,6):5 2. Bắt đầu xây dựng cây khung: * Chọn cạnh (1,2) - không tạo chu trình. * Chọn cạnh (1,4) - không tạo chu trình. * Chọn cạnh (2,3) - không tạo chu trình. * Chọn cạnh (4,5) - không tạo chu trình. * Chọn cạnh (2,6) - không tạo chu trình. * Chọn cạnh (6,7) - không tạo chu trình. Vậy, cây khung nhỏ nhất H = (V,T) có tập cạnh T = { (1,2), (1, 4), (2, 3), (4,5), (2, 6), (6, 7) }.

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 12

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 27:

Cho công thức logic mệnh đề: \(A = (p \to q) \wedge (\neg r \vee \neg q)\), hãy cho biết giá trị của A là gì?

Lời giải:

Đáp án đúng: C

Để xác định giá trị của công thức logic mệnh đề \(A = (p \to q) \wedge (\neg r \vee \neg q)\), chúng ta cần phân tích biểu thức này.

Biểu thức có hai phần chính được kết hợp bằng phép AND (\(\wedge\)):

1. \(p \to q\): Đây là phép kéo theo. \(p \to q\) chỉ sai khi p đúng và q sai, và đúng trong tất cả các trường hợp còn lại.
2. \(\neg r \vee \neg q\): Đây là phép OR của phủ định của r và phủ định của q. \(\neg r \vee \neg q\) đúng khi ít nhất một trong hai \(\neg r\) hoặc \(\neg q\) đúng.

Để A đúng, cả hai phần trên phải đúng. Tuy nhiên, chúng ta không có thông tin về giá trị của p, q và r. Do đó, giá trị của A phụ thuộc vào giá trị của p, q và r.

Ví dụ:

* Nếu p = True, q = True, r = True: \(A = (True \to True) \wedge (\neg True \vee \neg True) = True \wedge (False \vee False) = True \wedge False = False\)
* Nếu p = True, q = False, r = False: \(A = (True \to False) \wedge (\neg False \vee \neg False) = False \wedge (True \vee True) = False \wedge True = False\)
* Nếu p = False, q = True, r = False: \(A = (False \to True) \wedge (\neg False \vee \neg True) = True \wedge (True \vee False) = True \wedge True = True\)

Vì giá trị của A thay đổi tùy thuộc vào giá trị của p, q và r, chúng ta không thể xác định giá trị cụ thể của A mà không có thêm thông tin.

Do đó, đáp án chính xác là "Không xác định được".

Câu 28:

Cho đồ thị G liên thông có 5 đỉnh. Hỏi cây khung của G có mấy cạnh, mấy đỉnh?

Lời giải:

Đáp án đúng: B

Cây khung của một đồ thị liên thông G là một cây bao gồm tất cả các đỉnh của G và một số cạnh của G sao cho không có chu trình. Nếu cây khung có n đỉnh, thì nó sẽ có n-1 cạnh. Trong trường hợp này, đồ thị G có 5 đỉnh, do đó cây khung của G cũng sẽ có 5 đỉnh và 5-1 = 4 cạnh.

Câu 29:

Một cây có ít nhất mấy đỉnh treo?

Lời giải:

Đáp án đúng: B

Trong lý thuyết đồ thị, một đỉnh treo (hay còn gọi là lá) là một đỉnh có bậc bằng 1. Một cây là một đồ thị liên thông không có chu trình. Xét một cây bất kỳ có ít nhất hai đỉnh. Vì cây là liên thông, mọi đỉnh đều phải có bậc ít nhất là 1. Nếu một cây chỉ có một đỉnh bậc 1 thì các đỉnh còn lại phải có bậc lớn hơn hoặc bằng 2 để đảm bảo tính liên thông (nếu có các đỉnh khác). Tuy nhiên, điều này sẽ tạo ra chu trình hoặc làm cho đồ thị không phải là cây. Do đó, một cây luôn có ít nhất hai đỉnh bậc 1. Ví dụ, xét một đoạn thẳng nối hai đỉnh, mỗi đỉnh có bậc 1. Vậy nên, một cây có ít nhất 2 đỉnh treo.

Câu 30:

Câu nào sau đây KHÔNG là một mệnh đề?

Lời giải:

Đáp án đúng: B

Mệnh đề là một câu khẳng định có tính đúng hoặc sai. Tức là, một câu chỉ có thể đúng hoặc sai, không thể vừa đúng vừa sai, hoặc không xác định được tính đúng sai.

"Hôm nay không phải thứ hai" là một mệnh đề vì có thể xác định được tính đúng sai của nó.
"x là bạn cùng lớp với Lan" không phải là một mệnh đề vì không thể xác định được tính đúng sai của nó nếu không biết x là ai. Giá trị chân lý phụ thuộc vào biến số x. Đây là một mệnh đề chứa biến.
"Nếu hôm nay trời nắng thì tôi sẽ đi chơi" là một mệnh đề vì có thể xác định được tính đúng sai của nó.
"Có một người trong lớp không biết môn toán Rời rạc" là một mệnh đề vì có thể xác định được tính đúng sai của nó.

Vậy, đáp án đúng là câu "x là bạn cùng lớp với Lan" vì nó không phải là một mệnh đề.

Câu 1:

Cho X = {1,2,3,4,5,6,7,8,9} A = {1,2,3,8}, B = {2,4,8,9}, C = {6,7,8,9}. Tìm xâu bit biểu diễn tập: \((A \cap B) \cup C\)

Lời giải:

Đáp án đúng: B

Để tìm xâu bit biểu diễn tập (A ∩ B) ∪ C, ta thực hiện các bước sau:

1. Tìm A ∩ B: A ∩ B là tập hợp các phần tử chung của A và B. Trong trường hợp này, A = {1, 2, 3, 8} và B = {2, 4, 8, 9}. Vậy, A ∩ B = {2, 8}.

2. Tìm (A ∩ B) ∪ C: (A ∩ B) ∪ C là hợp của tập (A ∩ B) và C. Ta có A ∩ B = {2, 8} và C = {6, 7, 8, 9}. Vậy, (A ∩ B) ∪ C = {2, 6, 7, 8, 9}.

3. Biểu diễn bằng xâu bit: Tập X = {1, 2, 3, 4, 5, 6, 7, 8, 9} có 9 phần tử. Xâu bit biểu diễn một tập con của X sẽ có độ dài là 9. Vị trí thứ i trong xâu bit là 1 nếu phần tử i thuộc tập con, và là 0 nếu không thuộc.

Trong trường hợp này, (A ∩ B) ∪ C = {2, 6, 7, 8, 9}. Vậy xâu bit sẽ là:

- Vị trí 1 (phần tử 1): 0
- Vị trí 2 (phần tử 2): 1
- Vị trí 3 (phần tử 3): 0
- Vị trí 4 (phần tử 4): 0
- Vị trí 5 (phần tử 5): 0
- Vị trí 6 (phần tử 6): 1
- Vị trí 7 (phần tử 7): 1
- Vị trí 8 (phần tử 8): 1
- Vị trí 9 (phần tử 9): 1

Vậy xâu bit biểu diễn là 010001111.

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

Câu 2:

Cho tập A = {a,b,5}. Hỏi tập nào là tập lũy thừa của tập A?

Lời giải: