Số tổ hợp lặp chập r từ tập n phần tử bằng:

C(n+r,r)

C(n+r+1,r)

C(n+r-1,r-1)

C(n+r-1,r)

Trả lời:

Đáp án đúng: D

Số tổ hợp lặp chập r từ một tập hợp n phần tử được tính bằng công thức C(n+r-1, r). Công thức này xuất phát từ việc ta có thể biểu diễn bài toán tổ hợp lặp như bài toán chia kẹo Euler, trong đó ta cần chia r cái kẹo cho n đứa trẻ, và mỗi đứa trẻ có thể nhận được không hoặc nhiều hơn một cái kẹo. Số cách chia sẽ là C(n+r-1, r). Phương án A: C(n+r, r) - Sai. Phương án B: C(n+r+1, r) - Sai. Phương án C: C(n+r-1, r-1) - Sai, mặc dù có liên quan nhưng không chính xác. C(n+r-1, r-1) = C(n+r-1, n-1) Phương án D: C(n+r-1, r) - Đúng.

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

Kết quả của thuật toán dưới đây:

Procedure Test (n:integer);

Begin

If (n>0) and (n<10) then Write(n)

If n>=10 then begin

Write(n mod 10);

Test (n div 10);

End;

Lời giải:

Đáp án đúng: B

Thuật toán `Test(n)` thực hiện in ra các chữ số của `n` theo thứ tự ngược lại nếu `n` lớn hơn hoặc bằng 10. Nếu `n` nhỏ hơn 10 và lớn hơn 0, nó in ra chính `n`.

Ví dụ:
- Nếu `n = 123`, thuật toán sẽ in ra:
- `3` (từ `123 mod 10`)
- Sau đó gọi `Test(12)`
- `2` (từ `12 mod 10`)
- Sau đó gọi `Test(1)`
- `1` (vì `1 > 0` và `1 < 10`)
Vậy kết quả in ra là `321`.

- Nếu `n = 5`, thuật toán sẽ in ra `5` (vì `5 > 0` và `5 < 10`).

Như vậy, thuật toán in ra các chữ số của `n` theo thứ tự đảo ngược.

Câu 30:

Thuật toán đệ quy dưới đây tính:

Function Test(a,b): Integer;

Begin

If (b = a) or (b = 0) then Test:=1

Else Test := Test (a-1,b-1) + Test (a-1,b);

End;

Lời giải:

Đáp án đúng: D

Đoạn code trên thực chất tính tổ hợp chập b của a, ký hiệu là C(a, b).

Giải thích:

* Trường hợp cơ sở:
* `If (b = a) or (b = 0) then Test:=1`: Điều này tương ứng với C(a, a) = 1 và C(a, 0) = 1. Tức là, nếu chọn a phần tử từ a phần tử hoặc chọn 0 phần tử từ a phần tử, thì chỉ có 1 cách.
* Bước đệ quy:
* `Else Test := Test (a-1,b-1) + Test (a-1,b)`: Điều này tương ứng với công thức C(a, b) = C(a-1, b-1) + C(a-1, b).
Công thức này có nghĩa là, để chọn b phần tử từ a phần tử, ta có hai trường hợp:
1. Chọn phần tử thứ a, khi đó ta cần chọn b-1 phần tử từ a-1 phần tử còn lại (C(a-1, b-1)).
2. Không chọn phần tử thứ a, khi đó ta cần chọn b phần tử từ a-1 phần tử còn lại (C(a-1, b)).

Như vậy, hàm `Test(a, b)` tính toán chính xác tổ hợp chập b của a.

Câu 31:

Ngôn ngữ Pascal chuẩn quy định đặt tên biến không quá 8 kí tự, các kí tự trong tên biến chỉ là các chữ cái từ a…z hoặc các chữ số từ 0..9 và phải bắt đầu bằng chữ cái. Có bao nhiêu tên biến khác nhau thỏa mãn yêu cầu trên?

Lời giải:

Đáp án đúng: A

The question asks for the number of different variable names that can be created according to standard Pascal rules: no more than 8 characters, only letters a..z and digits 0..9, and must start with a letter.

A variable name can be 1 to 8 characters long. The first character must be a letter (26 choices). Each subsequent character can be a letter or a digit (36 choices).

Therefore, the total number of variable names is:
26 + 26*36 + 26*36^2 + ... + 26*36^7 = 26 * (1 + 36 + 36^2 + ... + 36^7)

This can be expressed as 26 * sum(36^k) for k = 0 to 7.

Câu 32:

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?

Lời giả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.

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: