Với 10 chữ số 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ta có thể lập nên bao nhiêu số khác nhau thoả mãn các điều kiện sau: - Mỗi chữ số phải có mặt một lần trong số lập nên.

Câu 13:

Một nông dân mua 3 con bò, 2 con heo, 4 con gà từ một người có 6 con bò, 5 con heo và 8 con gà. Người nông dân này sẽ có bao nhiêu sự lựa chọn?

Lời giải:

Đáp án đúng: A

Để giải bài toán này, ta cần tính số cách chọn bò, heo và gà riêng biệt, sau đó nhân chúng lại với nhau.

* Số cách chọn 3 con bò từ 6 con bò là tổ hợp chập 3 của 6, ký hiệu là C(6, 3) = 6! / (3! * 3!) = (6 * 5 * 4) / (3 * 2 * 1) = 20.
* Số cách chọn 2 con heo từ 5 con heo là tổ hợp chập 2 của 5, ký hiệu là C(5, 2) = 5! / (2! * 3!) = (5 * 4) / (2 * 1) = 10.
* Số cách chọn 4 con gà từ 8 con gà là tổ hợp chập 4 của 8, ký hiệu là C(8, 4) = 8! / (4! * 4!) = (8 * 7 * 6 * 5) / (4 * 3 * 2 * 1) = 70.

Vậy, tổng số cách lựa chọn là tích của các cách chọn bò, heo và gà: 20 * 10 * 70 = 14000.

Câu 14:

Giả sử một tổ bộ môn có 10 nam và 15 nữ. Có bao nhiêu cách chọn một hội đồng gồm 6 uỷ viên trong đó số uỷ viên nam bằng số uỷ viên nữ?

Lời giải:

Đáp án đúng: C

Để chọn một hội đồng gồm 6 ủy viên với số ủy viên nam bằng số ủy viên nữ, ta cần chọn 3 nam và 3 nữ. Số cách chọn 3 nam từ 10 nam là tổ hợp chập 3 của 10, ký hiệu là C(10, 3). Số cách chọn 3 nữ từ 15 nữ là tổ hợp chập 3 của 15, ký hiệu là C(15, 3).

Số cách chọn 3 nam từ 10 nam là: C(10, 3) = 10! / (3! * 7!) = (10 * 9 * 8) / (3 * 2 * 1) = 120.
Số cách chọn 3 nữ từ 15 nữ là: C(15, 3) = 15! / (3! * 12!) = (15 * 14 * 13) / (3 * 2 * 1) = 455.

Vì việc chọn nam và chọn nữ là hai hành động độc lập, ta nhân số cách chọn nam với số cách chọn nữ để được tổng số cách chọn hội đồng: 120 * 455 = 54600.

Vậy, có 54600 cách chọn một hội đồng gồm 6 ủy viên trong đó số ủy viên nam bằng số ủy viên nữ.

Câu 15:

Khi xây dựng chu trình Hamilton, nếu lấy hai cạnh liên thuộc với một đỉnh đặt vào chu trình thì:

Lời giải:

Đáp án đúng: B

Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần, mỗi đỉnh chỉ được ghé thăm một lần duy nhất. Khi xây dựng chu trình Hamilton, nếu đã chọn hai cạnh liên thuộc với một đỉnh (tức là hai cạnh nối với đỉnh đó) để đưa vào chu trình, thì không thể chọn thêm bất kỳ cạnh nào khác liên thuộc với đỉnh đó nữa, vì như vậy đỉnh đó sẽ được ghé thăm nhiều hơn một lần. Do đó, ta phải xóa tất cả các cạnh còn lại liên thuộc với đỉnh đó.

Câu 16:

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

Lời giải:

Đáp án đúng: D

Đồ thị bánh xe W_n được tạo thành từ một chu trình C_n và một đỉnh trung tâm được nối với tất cả các đỉnh của chu trình. Khi n lẻ, chu trình C_n cần 3 màu để tô. Đỉnh trung tâm cần một màu khác với hai màu được sử dụng nhiều nhất trong chu trình. Do đó, số màu tối thiểu cần thiết để tô màu đồ thị bánh xe W_n khi n lẻ là 3.

Câu 17:

Độ phức tạp của thật toán Floyd là:

Lời giải:

Đáp án đúng: C

Thuật toán Floyd-Warshall dùng để giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có trọng số. Thuật toán này duyệt qua tất cả các đỉnh trung gian để cập nhật khoảng cách ngắn nhất giữa mọi cặp đỉnh. Vì có ba vòng lặp lồng nhau (duyệt qua tất cả các đỉnh bắt đầu, đỉnh kết thúc và đỉnh trung gian), độ phức tạp của thuật toán là O(n³).

Câu 18:

Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi:

Lời giải: