Khi thiết kế thuật toán đệ quy thì ta cần xác định các yêu cầu sau:

Xác định được phần cơ sở và phần đệ quy

Xác định được phần cơ sở và phần truy hồi

Xác định được phần suy biến và phần quy nạp

Xác định được phần dừng và phần lặp vô hạn

Trả lời:

Đáp án đúng: A

Khi thiết kế thuật toán đệ quy, ta cần xác định hai thành phần chính: phần cơ sở (base case) và phần đệ quy (recursive case). Phần cơ sở là trường hợp đơn giản nhất mà thuật toán có thể giải quyết trực tiếp mà không cần gọi đệ quy. Phần đệ quy là trường hợp mà thuật toán tự gọi chính nó với một đầu vào nhỏ hơn, tiến gần hơn đến phần cơ sở. Phương án 1 mô tả chính xác hai thành phần này.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 6

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 15:

Cấu trúc của chương trình con đệ quy gồm:

Lời giải:

Đáp án đúng: B

Chương trình con đệ quy là chương trình con gọi lại chính nó. Một chương trình đệ quy cần có hai phần: phần cơ sở (base case) là trường hợp đơn giản có thể giải quyết trực tiếp mà không cần đệ quy, và phần đệ quy (recursive case) là trường hợp mà chương trình gọi lại chính nó với một đầu vào nhỏ hơn, tiến gần hơn đến phần cơ sở.

Câu 16:

Số các các chỉnh hợp lặp chập k của n là:

Lời giải:

Đáp án đúng: C

Chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự gồm k phần tử, mỗi phần tử được chọn từ n phần tử đã cho, và có thể lặp lại các phần tử. Số lượng chỉnh hợp lặp chập k của n được tính bằng công thức n^k. Do đó, đáp án đúng là N^k.

Câu 17:

Cho thuật toán:

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;

Với n=151. Kết quả nào đúng trong số những kết quả dưới đây?

Lời giải:

Đáp án đúng: C

Thuật toán `Test(n)` in ra các chữ số của `n` theo thứ tự ngược lại.

- Khi `n = 151`, vì `n >= 10`, nên thuật toán in ra `n mod 10 = 151 mod 10 = 1`.
- Sau đó, thuật toán gọi đệ quy `Test(n div 10) = Test(151 div 10) = Test(15)`.
- Trong `Test(15)`, vì `n >= 10`, nên thuật toán in ra `n mod 10 = 15 mod 10 = 5`.
- Sau đó, thuật toán gọi đệ quy `Test(n div 10) = Test(15 div 10) = Test(1)`.
- Trong `Test(1)`, vì `(n > 0) and (n < 10)` là đúng, nên thuật toán in ra `n = 1`.

Vậy, kết quả in ra là `151`.

Câu 18:

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)` in ra các chữ số của `n` theo thứ tự ngược lại. Nếu `n` nhỏ hơn 10, nó in ra `n`. Nếu `n` lớn hơn hoặc bằng 10, nó in ra chữ số cuối cùng của `n` (n mod 10) và sau đó gọi đệ quy `Test(n div 10)`, in ra các chữ số còn lại theo thứ tự ngược lại. Vì vậy, thuật toán in ra các chữ số của `n` theo thứ tự đảo ngược.

Câu 19:

Một đa giác lồi n cạnh sẽ có bao nhiêu đường chéo? (Một đa giác được gọi là lồi nếu mọi đoạn thẳng nối 2 điểm bên trong hoặc trên biên nằm hoàn toàn trong nó)

Lời giải:

Đáp án đúng: A

Một đa giác lồi n cạnh có n đỉnh. Từ mỗi đỉnh, ta có thể vẽ đường chéo đến (n - 3) đỉnh còn lại (trừ chính đỉnh đó và 2 đỉnh kề nó). Như vậy, tổng số đường chéo được tính là n(n - 3). Tuy nhiên, mỗi đường chéo được đếm 2 lần (ví dụ, đường chéo nối đỉnh A và đỉnh B được đếm cả từ đỉnh A và từ đỉnh B). Vì vậy, số đường chéo thực tế là n(n - 3) / 2.

Câu 20:

Một hội nghị bàn tròn của phái đoàn các nước: Việt Nam 3 người; Lào 2 người; Campuchia 1 người; Thái Lan 2 người. Có bao nhiêu cách xếp chỗ ngồi cho mọi thành viên sao cho người cùng quốc tịch ngồi cạnh nhau?

Lời giải: