Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là:

C, A, B, E, F, D, G, H, K, C, N

C, A, B, K, N, I, D, E, F, H, G

C, A, E, G, B, D, F, H, K, I, N

C, A, E, G, F, H, N, B, D, I, K

Trả lời:

Đáp án đúng: B

Thuật toán DFS (Depth-First Search) duyệt đồ thị theo chiều sâu. Bắt đầu từ đỉnh C, ta chọn một đỉnh kề chưa được duyệt (ví dụ A). Tiếp tục duyệt từ A theo chiều sâu. Nếu đến một đỉnh không còn đỉnh kề chưa duyệt, ta quay lui (backtrack) đến đỉnh trước đó và chọn một đỉnh kề khác chưa duyệt. Dựa vào đồ thị và thứ tự duyệt, ta có thể loại trừ các đáp án sai. - Bắt đầu từ C. - Duyệt A. - Duyệt E. - Duyệt G. - Duyệt F. - Duyệt H. - Duyệt N. - Quay lui về A, duyệt B. - Quay lui về C, duyệt D. - Quay lui về D, duyệt I. - Quay lui về I, duyệt K. Vậy thứ tự duyệt đúng là C, A, E, G, F, H, N, B, D, I, K.

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 15

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

Có bao nhiêu trường hợp về chân trị của bộ biến mệnh đề (q₁,q₂,..,q_n)?

Lời giải:

Đáp án đúng: B

Với n biến mệnh đề (q1, q2, ..., qn), mỗi biến có 2 giá trị chân trị (đúng hoặc sai). Do đó, số trường hợp về chân trị của bộ biến mệnh đề là 2^n.

Câu 30:

Cho đồ thị G có bậc là 10. Số cạnh của đồ thị G là:

Lời giải:

Đáp án đúng: D

Câu hỏi này có vẻ như đang thiếu thông tin quan trọng. "Bậc của đồ thị" thường liên quan đến bậc của một đỉnh (số cạnh liên thuộc với đỉnh đó) hoặc có thể là bậc lớn nhất của các đỉnh trong đồ thị. Nếu câu hỏi muốn nói đến tổng bậc của tất cả các đỉnh trong đồ thị là 10, thì theo bổ đề bắt tay (handshaking lemma), tổng bậc của tất cả các đỉnh bằng hai lần số cạnh. Tức là 2*|E| = 10, suy ra số cạnh |E| = 5. Tuy nhiên, nếu bậc của đồ thị chỉ đơn giản là đề cập đến bậc của một đỉnh, thì chúng ta không thể xác định số cạnh chỉ với thông tin đó. Giả sử câu hỏi ám chỉ tổng bậc của các đỉnh là 10, thì đáp án đúng nhất là 5.

Câu 1:

Cho 2 tập A={1, 2, 3}, B={a, b, c, 2}. Trong số các tập dưới đây, tập nào là một quan hệ 2 ngôi từ A tới B?

Lời giải:

Đáp án đúng: B

Một quan hệ hai ngôi từ A tới B là một tập hợp các cặp có thứ tự (x, y) trong đó x thuộc A và y thuộc B.

Phương án 1: {(1, a), (3, 3), (2, a)}. Ta thấy 1, 2, 3 đều thuộc A, nhưng 3 không thuộc B. Vậy đây không phải là một quan hệ hai ngôi từ A tới B.

Phương án 2: {(2, 2), (2, c), (3, b)}. Ta thấy 2, 3 đều thuộc A và 2, c, b đều thuộc B. Vậy đây là một quan hệ hai ngôi từ A tới B.

Phương án 3: {(1, a), (2, 2), (3, 1)}. Ta thấy 1, 2, 3 đều thuộc A, nhưng 1 không thuộc B. Vậy đây không phải là một quan hệ hai ngôi từ A tới B.

Phương án 4: {(2, c), (2, 2), (b, 3)}. Ta thấy 2 thuộc A nhưng b không thuộc A và 3 không thuộc B. Vậy đây không phải là một quan hệ hai ngôi từ A tới B.

Vậy, chỉ có phương án 2 là một quan hệ hai ngôi từ A tới B.

Câu 2:

Cho tập A = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} hỏi ta cần lấy ít nhất bao nhiêu phần tử từ tập A để chắc chắn rằng có một cặp có tổng bằng 20.

Lời giải:

Đáp án đúng: A

Ta cần tìm số phần tử ít nhất cần lấy ra từ tập A để chắc chắn có một cặp số có tổng bằng 20. Các cặp số trong A có tổng bằng 20 là (1, 19), (3, 17), (5, 15), (7, 13), (9, 11). Như vậy, ta có 5 cặp số có tổng bằng 20. Xét trường hợp xấu nhất, ta lấy ra các số 19, 17, 15, 13, 11 (5 phần tử). Khi ta lấy thêm 1 phần tử nữa, phần tử đó chắc chắn phải thuộc một trong các số 1, 3, 5, 7, 9. Khi đó ta sẽ có một cặp có tổng bằng 20. Vậy ta cần lấy ít nhất 6 phần tử.

Câu 3:

Có bao nhiêu xâu nhị phân có độ dài bằng 5 mà hoặc có 2 bít đầu tiên là 0 hoặc có 2 bít cuối cùng là 1?

Lời giải:

Đáp án đúng: A

Gọi A là tập hợp các xâu nhị phân độ dài 5 có 2 bit đầu tiên là 00. Gọi B là tập hợp các xâu nhị phân độ dài 5 có 2 bit cuối cùng là 11.

Ta cần tìm |A ∪ B|.

Theo công thức bao hàm và loại trừ, |A ∪ B| = |A| + |B| - |A ∩ B|.

* |A|: Vì 2 bit đầu tiên cố định là 00, còn lại 3 bit có thể là 0 hoặc 1. Vậy |A| = 2^3 = 8.
* |B|: Vì 2 bit cuối cùng cố định là 11, còn lại 3 bit có thể là 0 hoặc 1. Vậy |B| = 2^3 = 8.
* |A ∩ B|: Các xâu thuộc A ∩ B phải có 2 bit đầu là 00 và 2 bit cuối là 11. Vậy xâu có dạng 00_ _11, chỉ còn 1 bit ở giữa có thể là 0 hoặc 1. Vậy |A ∩ B| = 2^1 = 2.

Vậy |A ∪ B| = 8 + 8 - 2 = 14.

Câu 4:

Cần tuyển chọn tối thiểu ra bao nhiêu người để chắc chắn có ít nhất 2 người có cùng ngày sinh trong năm 2016?

Lời giải: