Một học viên phải trả lời 8 trong số 10 câu hỏi cho một kỳ thi. Học viên này có bao nhiêu sự lựa chọn nếu học viên phải trả lời 3 câu hỏi đầu tiên?

252

186

Trả lời:

Đáp án đúng: A

Vì học viên phải trả lời 3 câu hỏi đầu tiên, nên học viên chỉ cần chọn 5 câu hỏi nữa từ 7 câu hỏi còn lại (10 câu hỏi trừ 3 câu đầu). Số cách chọn 5 câu hỏi từ 7 câu hỏi là tổ hợp chập 5 của 7, ký hiệu là C(7, 5) hoặc 7C5. Công thức tính tổ hợp chập k của n là: C(n, k) = n! / (k! * (n - k)!) trong đó "!" là ký hiệu của giai thừa. Vậy, C(7, 5) = 7! / (5! * 2!) = (7 * 6 * 5!)/(5! * 2 * 1) = (7 * 6) / 2 = 42 / 2 = 21. Vậy số sự lựa chọn của học viên là 21.

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 2

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 34:

Những đơn đồ thị vô hướng nào dưới đây tồn tại nếu bậc của các đỉnh lần lượt là:

Lời giải:

Đáp án đúng: C

Để một dãy số là dãy bậc của một đồ thị vô hướng, tổng các bậc phải là một số chẵn và phải thỏa mãn định lý Erdos-Gallai.

Câu 35:

Trong biểu diễn đồ thị bằng danh sách kề, mỗi danh sách kề chứa:

Lời giải:

Đáp án đúng: B

Trong biểu diễn đồ thị bằng danh sách kề, mỗi danh sách kề của một đỉnh *u* sẽ chứa danh sách các đỉnh *v* kề với đỉnh *u*. Nói cách khác, nó liệt kê tất cả các đỉnh có cạnh nối trực tiếp với đỉnh đang xét.

Phương án A không đúng vì danh sách kề chứa các đỉnh, không phải các cạnh.
Phương án C không đúng vì danh sách kề chỉ chứa các đỉnh kề, không chứa cạnh và cũng không phải tất cả các đỉnh kề và cạnh kề với nó.
Phương án D không đúng vì danh sách kề không chứa thông tin về bậc của đỉnh.

Câu 36:

Đồ thị liên thông G có một đỉnh có bậc bằng một thì:

Lời giải:

Đáp án đúng: C

Trong lý thuyết đồ thị, một chu trình Hamilton là một chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần. Nếu một đồ thị liên thông G có một đỉnh có bậc bằng một (tức là đỉnh đó chỉ nối với một đỉnh khác), thì không thể có một chu trình Hamilton. Điều này là do khi đi qua đỉnh bậc một đó, không có cách nào để rời khỏi nó mà không đi qua đỉnh kề với nó lần thứ hai, vi phạm định nghĩa của chu trình Hamilton.

Chu trình Euler là một chu trình đi qua tất cả các cạnh của đồ thị đúng một lần. Một đồ thị có chu trình Euler khi và chỉ khi tất cả các đỉnh của nó đều có bậc chẵn. Đỉnh bậc một làm đồ thị không có chu trình Euler.

Đồ thị có đỉnh bậc 1 chắc chắn không có chu trình.

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

Câu 37:

Thuật toán Dijkstra được dùng để:

Lời giải:

Đáp án đúng: D

Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số không âm. Nó được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn (đỉnh bắt đầu) đến tất cả các đỉnh còn lại trong đồ thị. Do đó, đáp án B là chính xác nhất.

Các phương án khác:
- A không đúng vì thuật toán Floyd-Warshall được sử dụng để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.
- C và D đúng một phần, nhưng không đầy đủ bằng B. Dijkstra có thể dùng để tìm đường đi ngắn nhất giữa hai đỉnh, nhưng mục tiêu chính của nó là tìm đường đi ngắn nhất từ một đỉnh đến *tất cả* các đỉnh khác.

Câu 38:

Đồ thị G = (V, E) được gọi là đồ thị vô hướng nếu:

Lời giải:

Đáp án đúng: B

Đồ thị vô hướng là đồ thị mà các cạnh không có hướng, nghĩa là không có sự phân biệt giữa điểm đầu và điểm cuối của cạnh. Vì vậy, một đồ thị G được gọi là đồ thị vô hướng nếu tất cả các cạnh của nó đều là cạnh vô hướng. Các phương án khác không chính xác vì chỉ cần một cạnh có hướng hoặc chỉ một vài cạnh vô hướng không đủ để kết luận toàn bộ đồ thị là vô hướng.

Câu 39:

Chu trình đơn trên đồ thị G là:

Lời giải: