Một đơn vị lúc bắt đầu thành lập có 14 người. Cần chọn ra một người làm trưởng phòng, một người làm phó phòng, một người làm kế toán trưởng. Hỏi có bao nhiêu cách chọn mà không ai làm kiêm nhiệm?

1001

2184

364

512

Trả lời:

Đáp án đúng: B

Ta có bài toán chọn 3 người từ 14 người vào 3 vị trí khác nhau (trưởng phòng, phó phòng, kế toán trưởng) và không ai kiêm nhiệm. Đây là bài toán về chỉnh hợp chập 3 của 14. Số cách chọn là: A(3, 14) = 14! / (14-3)! = 14! / 11! = 14 * 13 * 12 = 2184. Vậy, có 2184 cách chọn.

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 7

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 33:

Cho đồ thị vô hướng G = (V, E), khẳng định nào dưới đây là đúng?

Lời giải:

Đáp án đúng: C

Thuật toán BFS (Breadth-First Search) hay còn gọi là tìm kiếm theo chiều rộng, bắt đầu từ một đỉnh u và duyệt tất cả các đỉnh kề với u trước, sau đó duyệt các đỉnh kề với các đỉnh vừa duyệt. Do đó, BFS(u) sẽ duyệt tất cả các đỉnh nằm trong cùng thành phần liên thông với đỉnh u.

- Phương án A sai vì BFS(u) chỉ duyệt thành phần liên thông chứa u, không duyệt tất cả các thành phần liên thông của đồ thị nếu đồ thị không liên thông.
- Phương án B sai vì BFS(u) chỉ tìm đường đi giữa hai đỉnh nếu chúng thuộc cùng một thành phần liên thông. Nếu hai đỉnh không thuộc cùng thành phần liên thông thì không có đường đi giữa chúng.
- Phương án C đúng vì BFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u theo đúng định nghĩa và cách hoạt động của thuật toán BFS.
- Phương án D sai vì nếu đồ thị có chu trình, BFS(u) có thể duyệt một số đỉnh nhiều lần nếu không có cơ chế đánh dấu đỉnh đã duyệt. Tuy nhiên, thuật toán BFS thường sử dụng một mảng để đánh dấu các đỉnh đã được duyệt, đảm bảo mỗi đỉnh chỉ được duyệt một lần trong cùng một lần gọi BFS(u). Mặc dù vậy, phương án C vẫn chính xác hơn vì nó tập trung vào mục đích chính của BFS là duyệt thành phần liên thông.

Câu 34:

Phát biểu nào sau đây là sai khi nói đến đồ thị phân đôi đầy đủ K_m,n.

Lời giải:

Đáp án đúng: C

Câu hỏi kiểm tra kiến thức về đồ thị phân đôi đầy đủ.

Phương án A đúng vì đây là định nghĩa của đồ thị phân đôi đầy đủ.
Phương án B đúng vì đây là một phần của định nghĩa đồ thị phân đôi đầy đủ.
Phương án C sai vì phát biểu này không đúng với định nghĩa đồ thị phân đôi đầy đủ. Trong đồ thị phân đôi đầy đủ, một cạnh chỉ tồn tại giữa một đỉnh thuộc tập con thứ nhất và một đỉnh thuộc tập con thứ hai, không phải đỉnh nào cũng thuộc cả hai tập con.
Phương án D đúng vì đồ thị phân đôi đầy đủ K_m,n có m+n đỉnh và mn cạnh.

Vậy đáp án sai là C.

Câu 35:

Đồ thị có đường đi vô hướng Euler khi và chỉ khi:

Lời giải:

Đáp án đúng: A

Một đồ thị vô hướng có đường đi Euler khi và chỉ khi nó liên thông và có đúng hai đỉnh bậc lẻ. Vì vậy, đáp án đúng là A. Liên thông và có hai đỉnh bậc lẻ.

Câu 36:

Số màu trong đồ thị hình bánh xe W_n (với n chẵn) là:

Lời giải:

Đáp án đúng: C

Đồ thị bánh xe W_n được tạo ra bằng cách nối một đỉnh trung tâm với tất cả các đỉnh của một đồ thị chu trình C_n.

Khi n chẵn, đồ thị chu trình C_n có số màu là 2. Đỉnh trung tâm cần một màu khác với 2 màu đã dùng để tô màu cho C_n. Do đó, số màu cần thiết để tô màu đồ thị bánh xe W_n là 3.

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

Câu 37:

Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:

Lời giải:

Đáp án đúng: D

Cả thuật toán Prim và Kruskal đều là các thuật toán tham lam được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số. Dưới đây là phân tích chi tiết:

A. Dừng khi kết nạp được tất cả các cạnh vào cây khung. Sai. Cây khung (spanning tree) chỉ chứa n-1 cạnh, với n là số đỉnh của đồ thị. Không phải tất cả các cạnh đều được kết nạp.

B. Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung. Sai. Như đã nói ở trên, cây khung chỉ có n-1 cạnh. Phương án này sai vì số cạnh không đúng.

C. Thuật toán chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây khung và không tạo ra chu trình. Đúng. Đây là điểm giống nhau cốt lõi giữa hai thuật toán. Cả hai đều ưu tiên chọn cạnh nhỏ nhất và đảm bảo không tạo thành chu trình khi thêm vào cây khung đang xây dựng.

D. Thuật toán xây dựng cây khung ngắn nhất. Đúng nhưng không đủ chi tiết. Đây là mục tiêu của cả hai thuật toán, nhưng không phải là sự giống nhau trong cách chúng hoạt động cụ thể. Phương án C mô tả sự giống nhau chi tiết hơn trong quá trình xây dựng cây khung.

Như vậy, đáp án C chính xác nhất vì nó mô tả chi tiết cách cả hai thuật toán tiếp cận việc xây dựng cây khung nhỏ nhất, cụ thể là chọn cạnh có trọng số tối thiểu và không tạo chu trình.

Câu 38:

Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal:

Lời giải: