Nội dung của nguyên lý bù trừ phát biểu trên hai tập hợp hữu hạn A, B:

Nếu A và B là hai tập hợp rời nhau thì: N( A+B )= N(A) + N(B)

Nếu A và B là hai tập hợp thì: N(A . B ) = N(A).N(B)

Nếu A và B là hai tập hợp thì: N(A+B)= N(A) + N(B) – N(A+B)

Nếu có N đồ vật được đặt vào K hộp thì sẽ tồn tại một hộp chứa ít nhất đồ vật.

Trả lời:

Đáp án đúng: C

Nguyên lý bù trừ (hay còn gọi là nguyên lý bao hàm và loại trừ) dùng để tính số phần tử của hợp các tập hợp. Trong trường hợp hai tập hợp hữu hạn A và B, số phần tử của hợp A ∪ B (ký hiệu là A + B trong các đáp án) được tính bằng tổng số phần tử của A và B trừ đi số phần tử của giao A ∩ B. Do đó, công thức đúng là N(A ∪ B) = N(A) + N(B) - N(A ∩ B). Đáp án thứ nhất chỉ đúng khi A và B rời nhau (giao nhau bằng rỗng). Các đáp án còn lại không liên quan đến nguyên lý bù trừ.

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 10

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

Các hoán vị của n phần tử:

Lời giải:

Đáp án đúng: C

Hoán vị của n phần tử là một cách sắp xếp có thứ tự n phần tử đó thành một dãy. Đáp án 3 mô tả chính xác định nghĩa này. Các đáp án khác mô tả các khái niệm khác như tổ hợp, chỉnh hợp không lặp, chỉnh hợp lặp.

Câu 20:

Có bao nhiêu xâu nhị phân có độ dài nhỏ hơn hoặc bằng 8 bắt đầu là bít 1?

Lời giải:

Đáp án đúng: A

Câu hỏi yêu cầu tìm số lượng xâu nhị phân có độ dài nhỏ hơn hoặc bằng 8, bắt đầu bằng bít 1. - Độ dài 1: Có 1 xâu (1) - Độ dài 2: Có 2¹ xâu (10, 11) - Độ dài 3: Có 2² xâu (100, 101, 110, 111) - Độ dài 4: Có 2³ xâu - Độ dài 5: Có 2⁴ xâu - Độ dài 6: Có 2⁵ xâu - Độ dài 7: Có 2⁶ xâu - Độ dài 8: Có 2⁷ xâu Vậy tổng số xâu là: 1 + 2¹ + 2² + 2³ + 2⁴ + 2⁵ + 2⁶ + 2⁷

Câu 21:

Cần phải có tối thiểu bao nhiêu sinh viên ghi tên vào lớp Toán học rời rạc để chắc chắn rằng sẽ có ít nhất 6 người cùng đạt một điểm thi, nếu thang điểm gồm 5 bậc A, B, C, D, E, F?

Lời giải:

Đáp án đúng: D

Đây là một bài toán ứng dụng nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu). Nguyên lý này nói rằng nếu có n chuồng bồ câu và n+1 con bồ câu, thì ít nhất một chuồng phải có ít nhất 2 con bồ câu. Mở rộng ra, nếu có n chuồng và k*n + 1 con bồ câu thì có ít nhất một chuồng có k+1 con bồ câu trở lên. Trong bài toán này, các bậc điểm (A, B, C, D, E, F) đóng vai trò là "chuồng", và sinh viên đóng vai trò là "bồ câu". Ta có 6 "chuồng" (bậc điểm). Chúng ta muốn tìm số lượng sinh viên tối thiểu (số "bồ câu") sao cho chắc chắn có ít nhất 6 sinh viên ("6 con bồ câu") cùng đạt một bậc điểm (cùng "chuồng"). Áp dụng nguyên lý Dirichlet mở rộng: Nếu có n chuồng và k*n + 1 con bồ câu thì có ít nhất một chuồng chứa k+1 con bồ câu trở lên. Ở đây, ta muốn k+1 = 6, tức là k = 5. Và n = 6 (số bậc điểm). Vậy, số sinh viên tối thiểu cần có là k*n + 1 = 5 * 6 + 1 = 30 + 1 = 31. Vì vậy, cần phải có tối thiểu 31 sinh viên để chắc chắn rằng có ít nhất 6 người cùng đạt một điểm thi.

Câu 22:

Đồ thị nào trong các đồ thị không phẳng sau đây có tính chất: bỏ đi một đỉnh bất kỳ và các cạnh liên thuộc với nó tạo ra một đồ thị phẳng.

Lời giải:

Đáp án đúng: A

Đồ thị K₅ là đồ thị đầy đủ với 5 đỉnh. Khi bỏ đi một đỉnh và các cạnh liên thuộc với nó, ta được đồ thị đầy đủ với 4 đỉnh, tức là K₄. Đồ thị K₄ là một đồ thị phẳng. Các đồ thị K₆ và K₇ không có tính chất này. Đồ thị K₂ là đồ thị phẳng nên không thỏa mãn điều kiện đề bài.

Câu 23:

Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng: (Chọn phương án đúng)

Lời giải:

Đáp án đúng: D

Thuật toán Prim là một thuật toán tham lam được sử dụng để tìm cây khung nhỏ nhất cho một đồ thị liên thông có trọng số. Các thuật toán khác như Dijkstra (tìm đường đi ngắn nhất), BFS (tìm kiếm theo chiều rộng) và DFS (tìm kiếm theo chiều sâu) không được thiết kế để trực tiếp tìm cây khung nhỏ nhất.

Câu 24:

Ta gọi đỉnh v là đỉnh treo trong đồ thị vô hướng G = (V,E) A).

Lời giải: