Liệt kê là phương pháp.

Đưa ra một công thức cho lời giải bài toán

Chỉ ra nghiệm tốt nhất theo một nghĩa nào đó của bài toán.

Đưa ra danh sách tất cả các cấu hình tổ hợp có thể có.

Chỉ ra một nghiệm hoặc chứng minh bài toán không có nghiệm

Trả lời:

Đáp án đúng: C

Phương pháp liệt kê là cách tiếp cận giải quyết bài toán bằng cách tạo ra một danh sách đầy đủ tất cả các cấu hình tổ hợp có thể có, sau đó kiểm tra từng cấu hình để tìm ra nghiệm phù hợp hoặc nghiệm tốt nhất. - Phương án A không đúng vì liệt kê không đưa ra công thức trực tiếp cho lời giải. - Phương án B không đúng vì liệt kê không nhất thiết chỉ ra nghiệm tốt nhất; nó có thể chỉ đơn giản là tìm một nghiệm thỏa mãn. - Phương án C đúng vì liệt kê chính là việc tạo ra danh sách tất cả các cấu hình tổ hợp có thể. - Phương án D không hoàn toàn đúng vì liệt kê không chỉ dừng lại ở việc chỉ ra một nghiệm; nó có thể tìm kiếm tất cả các nghiệm hoặc chứng minh không có nghiệm sau khi đã duyệt qua tất cả các cấu hình.

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

Một thuật toán liệt kê phải đảm bảo:

Lời giải:

Đáp án đúng: B

Một thuật toán liệt kê (enumeration algorithm) đúng nghĩa phải đảm bảo bao phủ toàn bộ không gian nghiệm mà không có bất kỳ sự trùng lặp nào. Điều này có nghĩa là thuật toán không được bỏ sót bất kỳ một cấu hình (solution) nào thuộc tập các cấu hình cần liệt kê, đồng thời cũng không được lặp lại bất kỳ cấu hình nào đã được liệt kê trước đó.

- Phương án A chỉ đề cập đến việc không duyệt các cấu hình không thuộc tập các cấu hình, nhưng không đảm bảo việc không bỏ sót hoặc lặp lại các cấu hình hợp lệ.

- Phương án B là đầy đủ và chính xác nhất, bao gồm cả hai yêu cầu quan trọng của một thuật toán liệt kê: không bỏ xót và không lặp lại.

- Phương án C chỉ đề cập đến việc không bỏ xót, nhưng không đề cập đến việc tránh lặp lại các cấu hình.

- Phương án D chỉ đề cập đến việc không duyệt lại các cấu hình đã duyệt, nhưng không đảm bảo việc không bỏ sót các cấu hình.

Do đó, phương án B là đáp án chính xác nhất.

Câu 27:

Định nghĩa bằng đệ qui là phương pháp.

Lời giải:

Đáp án đúng: A

Định nghĩa bằng đệ quy là một phương pháp định nghĩa một đối tượng hoặc một khái niệm thông qua chính nó. Điều này có nghĩa là, để hiểu hoặc xác định đối tượng, bạn cần tham chiếu đến chính đối tượng đó trong định nghĩa. Ví dụ kinh điển là định nghĩa giai thừa của một số nguyên n: n! = n * (n-1)!. Trong trường hợp này, giai thừa của n được định nghĩa thông qua giai thừa của (n-1), tức là chính nó (giai thừa). Do đó, đáp án A là chính xác nhất.

Câu 28:

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

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

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: