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

Function Test (a,b: integer): integer;

Begin

If a = 0 then Test:=b

Else Test:= Test(b mod a, a);

End;

Ước số chung lớn nhất của hai số a và b.

Số nhỏ nhất trong hai số a và b.

Bội số chung nhỏ nhất của a và b.

Số lớn nhất trong hai số a và b.

Trả lời:

Đáp án đúng: A

Thuật toán đệ quy trên thực hiện tính ước số chung lớn nhất (USCLN) của hai số a và b. Cụ thể, nó dựa trên thuật toán Euclid. Nếu a = 0, thì USCLN(a, b) = b. Nếu không, USCLN(a, b) = USCLN(b mod a, a).

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 15

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

Có bao nhiêu số nguyên không lớn hơn 1000 chia hết cho 7 hoặc 11?

Lời giải:

Đáp án đúng: C

Số các số nguyên không lớn hơn 1000 chia hết cho 7 là \(\left\lfloor \frac{1000}{7} \right\rfloor = 142\). Số các số nguyên không lớn hơn 1000 chia hết cho 11 là \(\left\lfloor \frac{1000}{11} \right\rfloor = 90\). Số các số nguyên không lớn hơn 1000 chia hết cho cả 7 và 11 (tức là chia hết cho 77) là \(\left\lfloor \frac{1000}{77} \right\rfloor = 12\). Theo nguyên lý bao hàm và loại trừ, số các số nguyên không lớn hơn 1000 chia hết cho 7 hoặc 11 là \(142 + 90 - 12 = 220\).

Câu 18:

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

Để chọn một người làm trưởng phòng từ 14 người, có 14 cách chọn. Sau khi chọn trưởng phòng, còn lại 13 người. Để chọn một người làm phó phòng từ 13 người còn lại, có 13 cách chọn. Cuối cùng, để chọn một người làm kế toán trưởng từ 12 người còn lại, có 12 cách chọn.
Vậy, tổng số cách chọn là 14 * 13 * 12 = 2184.

Câu 19:

Có bao nhiêu số nguyên dương gồm đúng 3 chữ số chia hết cho 3 và chia hết cho 4?

Lời giải:

Đáp án đúng: B

Số chia hết cho cả 3 và 4 thì chia hết cho BCNN(3, 4) = 12. Vậy, ta cần tìm số các số nguyên dương có 3 chữ số chia hết cho 12.
Số nhỏ nhất có 3 chữ số chia hết cho 12 là 108 (12 x 9 = 108).
Số lớn nhất có 3 chữ số chia hết cho 12 là 996 (12 x 83 = 996).
Vậy các số cần tìm là 12 x 9, 12 x 10, ..., 12 x 83. Số lượng các số này là 83 - 9 + 1 = 75.

Câu 20:

Nếu G = (V,E) là một đồ thị vô hướng thì:

Lời giải:

Đáp án đúng: C

Trong một đồ thị vô hướng G = (V, E), tổng bậc của tất cả các đỉnh bằng hai lần số cạnh (∑deg(v) = 2|E|). Vì 2|E| là một số chẵn, nên tổng bậc của tất cả các đỉnh phải là một số chẵn. Điều này chỉ xảy ra khi số lượng đỉnh bậc lẻ là một số chẵn, vì nếu có một số lẻ các đỉnh bậc lẻ, thì tổng bậc của các đỉnh sẽ là một số lẻ (tổng của một số chẵn và một số lẻ là một số lẻ).

Câu 21:

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

Lời giải:

Đáp án đúng: A

Thuật toán DFS (Depth-First Search) xuất phát từ một đỉnh u và duyệt theo chiều sâu đến khi không còn đỉnh nào kề với đỉnh đang xét chưa được duyệt. Khi đó, thuật toán quay lui về đỉnh trước đó và tiếp tục duyệt các đỉnh kề chưa được duyệt khác. Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể đến được từ đỉnh u đều đã được duyệt. Do đó, DFS(u) duyệt tất cả các đỉnh trong cùng thành phần liên thông với đỉnh u. Các phương án khác không đúng vì DFS(u) chỉ duyệt các đỉnh có thể đến được từ u, không duyệt toàn bộ đồ thị nếu đồ thị không liên thông và cũng không đảm bảo tìm được đường đi giữa hai đỉnh bất kỳ nếu chúng không thuộc cùng thành phần liên thông. DFS(u) cũng có thể không duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần nếu đồ thị có chu trình.

Câu 22:

Nếu G = (V,E) là một đơn đồ thị vô hướng thì:

Lời giải: