JavaScript is required
Danh sách đề

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Đề 11

50 câu hỏi 60 phút

Thẻ ghi nhớ
Luyện tập
Thi thử
Nhấn để lật thẻ
1 / 50

Giả sử dãy 1 4 5 6 là cấu hình hiện tại tổ hợp chập 4 của 6 phần tử. Cấu hình nào sau đây sinh ra cấu hình này theo thuật toán sinh:

A.

2135

B.

1246

C.

1356

D.
2145
Đáp án
Đáp án đúng: B
Thuật toán sinh tổ hợp chập k của n phần tử hoạt động bằng cách tìm từ phải sang trái phần tử a[i] đầu tiên mà a[i] < n - k + i. Sau đó tăng a[i] lên 1 đơn vị và cập nhật các phần tử phía sau a[i] theo quy tắc a[j] = a[j-1] + 1 với j > i.

Xét cấu hình 1 4 5 6:

* Phương án A: 2 1 3 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.
* Phương án B: 1 2 4 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 2 (vì 2 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 3. Các phần tử phía sau sẽ là a[3] = 3 + 1 = 4, a[4] = 4 + 1 = 5. Vậy cấu hình sinh ra là 1 3 4 5, khác với cấu hình 1 4 5 6.
* Phương án C: 1 3 5 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 3 (vì 3 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 4. Các phần tử phía sau sẽ là a[3] = 4 + 1 = 5, a[4] = 5 + 1 = 6. Vậy cấu hình sinh ra là 1 4 5 6.
* Phương án D: 2 1 4 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.

Vậy, cấu hình 1 3 5 6 sinh ra cấu hình 1 4 5 6 theo thuật toán sinh tổ hợp.

Danh sách câu hỏi:

Lời giải:
Đáp án đúng: B
Thuật toán sinh tổ hợp chập k của n phần tử hoạt động bằng cách tìm từ phải sang trái phần tử a[i] đầu tiên mà a[i] < n - k + i. Sau đó tăng a[i] lên 1 đơn vị và cập nhật các phần tử phía sau a[i] theo quy tắc a[j] = a[j-1] + 1 với j > i.

Xét cấu hình 1 4 5 6:

* Phương án A: 2 1 3 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.
* Phương án B: 1 2 4 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 2 (vì 2 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 3. Các phần tử phía sau sẽ là a[3] = 3 + 1 = 4, a[4] = 4 + 1 = 5. Vậy cấu hình sinh ra là 1 3 4 5, khác với cấu hình 1 4 5 6.
* Phương án C: 1 3 5 6: Tìm từ phải sang trái, phần tử đầu tiên thỏa mãn a[i] < n - k + i là a[2] = 3 (vì 3 < 6 - 4 + 2 = 4). Tăng a[2] lên 1 thành 4. Các phần tử phía sau sẽ là a[3] = 4 + 1 = 5, a[4] = 5 + 1 = 6. Vậy cấu hình sinh ra là 1 4 5 6.
* Phương án D: 2 1 4 5: Đây không phải là một tổ hợp hợp lệ vì các phần tử không được sắp xếp tăng dần.

Vậy, cấu hình 1 3 5 6 sinh ra cấu hình 1 4 5 6 theo thuật toán sinh tổ hợp.
Lời giải:
Đáp án đúng: C
Trong đồ thị đủ Kn, mỗi đỉnh được nối với tất cả các đỉnh còn lại. Vì vậy, mỗi đỉnh sẽ có bậc là n - 1. Đáp án C là đáp án chính xác.
Lời giải:
Đáp án đúng: C
Duyệt đồ thị theo chiều sâu (DFS) bắt đầu từ đỉnh 1. Ta xét các đỉnh kề với đỉnh 1 theo thứ tự từ điển: 2, 3, 6.

- Nếu đi theo đỉnh 2: Ta có đường đi 1 - 2. Từ đỉnh 2, xét các đỉnh kề theo thứ tự từ điển: 3, 5, 6.
- Nếu đi theo đỉnh 3: Ta có đường đi 1 - 2 - 3. Từ đỉnh 3, các đỉnh kề là 1, 2. Đã duyệt 1 và 2 nên quay lui.
- Nếu đi theo đỉnh 5: Ta có đường đi 1 - 2 - 5. Từ đỉnh 5, xét các đỉnh kề theo thứ tự từ điển: 4, 6.
- Nếu đi theo đỉnh 4: Ta có đường đi 1 - 2 - 5 - 4. Từ đỉnh 4, xét các đỉnh kề theo thứ tự từ điển: 5, 6.
- Nếu đi theo đỉnh 5: Đã duyệt.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 5 - 4 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 5 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 2 - 6. Đây là một đường đi từ 1 đến 6.
- Nếu đi theo đỉnh 3: Ta có đường đi 1 - 3. Từ đỉnh 3, các đỉnh kề là 1, 2. Đã duyệt 1 và 2 nên quay lui.
- Nếu đi theo đỉnh 6: Ta có đường đi 1 - 6. Đây là một đường đi từ 1 đến 6.

Như vậy, các đường đi từ 1 đến 6 có thể tìm được bằng DFS là: 1 - 6, 1 - 2 - 6, 1 - 2 - 5 - 6, 1 - 2 - 5 - 4 - 6. Do các đỉnh được xét theo thứ tự từ điển, đường đi tìm thấy đầu tiên sẽ là 1 - 6.

Câu 4:

Phát biểu nào sau đây là đúng?

Lời giải:
Đáp án đúng: B

Câu hỏi này kiểm tra kiến thức về chu trình Euler trong lý thuyết đồ thị.


Phương án A: Sai. Phát biểu này mô tả chu trình Hamilton, không phải chu trình Euler.


Phương án B: Đúng. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.

Lời giải:
Đáp án đúng: D

Phân tích bài toán:

Đề bài yêu cầu tìm số xâu nhị phân có độ dài 5 thỏa mãn điều kiện bít đầu và bít cuối bằng nhau.

Cách giải:

Ta chia bài toán thành 2 trường hợp:

- Trường hợp 1: Bít đầu và bít cuối đều là 0. Khi đó, ta có xâu dạng 0 _ _ _ 0. Có 3 vị trí ở giữa, mỗi vị trí có 2 lựa chọn (0 hoặc 1). Vậy có 2*2*2 = 8 xâu.

- Trường hợp 2: Bít đầu và bít cuối đều là 1. Khi đó, ta có xâu dạng 1 _ _ _ 1. Tương tự trường hợp 1, có 3 vị trí ở giữa, mỗi vị trí có 2 lựa chọn (0 hoặc 1). Vậy có 2*2*2 = 8 xâu.

Tổng cộng, có 8 + 8 = 16 xâu thỏa mãn.

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 15:

Cho n, r là các số nguyên không âm sao cho r ≤ n. Khi đó.

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 16:

Cho tập A = {1,2,3,4,5,6}. Cho A1 = {1,2}, A2 = {3,4}, A3 = {5,6}. Quan hệ tương đương R trên A sinh ra phân hoạch A1, A2, A3 là.

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 23:

Cho quan hệ R = {(a,b)| a ≡ b(mod 5)} trên tập {-12, -11, …,11, 12}. Hãy xác định [2]R?

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 24:

Biểu thức logic không chứa thành phần nào dưới đây.

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 27:

Khi xây dựng một thuật toán cần chú ý đến các đặc trưng sau đây.

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 31:

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

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

Begin 

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

Else

If a > b then Test:=Test(a-b,b)

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

End;

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 35:

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

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 37:

Ma trận kề của đồ thị vô hướng G = (V, E) có tính chất:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 38:

Ma trận kề của đồ thị có hướng không phải là:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 39:

Độ dài của một chu trình trên đồ thị G là:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 40:

Cho G = (V, E) là đồ thị vô hướng liên thông n đỉnh. T = (VT, ET) được gọi là cây khung của đồ thị G nếu:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 41:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 42:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 43:

Một công thức được gọi là có dạng chuẩn tắc hội nếu …?

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 45:

Phương pháp phản chứng là phương pháp?

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 46:

Quy tắc suy luận nào sau đây là quy tắc tam đoạn luận?

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 48:

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau: Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:  (ảnh 1)

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Câu 49:

Câu nào sau đây là một mệnh đề:

Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP