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 - Đề 1

50 câu hỏi 60 phút

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

Hoán vị nào sau đây đứng liền sau hoán vị 1 3 4 2 theo thuật toán sinh

A.

2145

B.

1423

C.
2143
Đáp án
Đáp án đúng: B
Thuật toán sinh hoán vị hoạt động như sau:

1. Tìm j lớn nhất: Tìm j lớn nhất sao cho a[j] < a[j+1]. Nếu không tồn tại j, thì đây là hoán vị cuối cùng.
2. Tìm l lớn nhất: Tìm l lớn nhất sao cho a[l] > a[j].
3. Đổi chỗ: Đổi chỗ a[j] và a[l].
4. Lật ngược: Lật ngược đoạn từ a[j+1] đến a[n].

Trong trường hợp này, hoán vị hiện tại là 1 3 4 2.

* Bước 1: Tìm j lớn nhất sao cho a[j] < a[j+1]. Ở đây, j = 2 (vì 3 < 4).
* Bước 2: Tìm l lớn nhất sao cho a[l] > a[j] (tức a[l] > 3). Ở đây, l = 3 (vì 4 > 3).
* Bước 3: Đổi chỗ a[j] và a[l]. Ta được hoán vị 1 4 3 2.
* Bước 4: Lật ngược đoạn từ a[j+1] đến a[n] (tức là lật ngược đoạn 3 2). Ta được hoán vị 1 4 2 3.

Vậy, hoán vị kế tiếp của 1 3 4 2 là 1 4 2 3. Tuy nhiên, đáp án này không có trong các lựa chọn. Có vẻ như có sự nhầm lẫn trong các đáp án được cung cấp, vì không có đáp án nào đúng.

Danh sách câu hỏi:

Lời giải:
Đáp án đúng: B
Thuật toán sinh hoán vị hoạt động như sau:

1. Tìm j lớn nhất: Tìm j lớn nhất sao cho a[j] < a[j+1]. Nếu không tồn tại j, thì đây là hoán vị cuối cùng.
2. Tìm l lớn nhất: Tìm l lớn nhất sao cho a[l] > a[j].
3. Đổi chỗ: Đổi chỗ a[j] và a[l].
4. Lật ngược: Lật ngược đoạn từ a[j+1] đến a[n].

Trong trường hợp này, hoán vị hiện tại là 1 3 4 2.

* Bước 1: Tìm j lớn nhất sao cho a[j] < a[j+1]. Ở đây, j = 2 (vì 3 < 4).
* Bước 2: Tìm l lớn nhất sao cho a[l] > a[j] (tức a[l] > 3). Ở đây, l = 3 (vì 4 > 3).
* Bước 3: Đổi chỗ a[j] và a[l]. Ta được hoán vị 1 4 3 2.
* Bước 4: Lật ngược đoạn từ a[j+1] đến a[n] (tức là lật ngược đoạn 3 2). Ta được hoán vị 1 4 2 3.

Vậy, hoán vị kế tiếp của 1 3 4 2 là 1 4 2 3. Tuy nhiên, đáp án này không có trong các lựa chọn. Có vẻ như có sự nhầm lẫn trong các đáp án được cung cấp, vì không có đáp án nào đúng.
Lời giải:
Đáp án đúng: B
Số cách chọn 1 bạn nam từ 15 bạn nam là C(15,1) = 15.
Số cách chọn 2 bạn nữ từ 15 bạn nữ là C(15,2) = 15! / (2! * 13!) = (15 * 14) / 2 = 105.
Vậy, số cách bầu ra ban cán bộ lớp bao gồm 1 bạn nam và 2 bạn nữ là: 15 * 105 = 1575.
Lời giải:
Đáp án đúng: B
Bài toán này thuộc loại bài toán tìm cặp ghép cực đại trong đồ thị hai phía. Ta có thể biểu diễn mối quan hệ giữa thợ và công việc bằng một đồ thị hai phía, trong đó một bên là tập các thợ, một bên là tập các công việc, và có cạnh nối giữa thợ và công việc nếu thợ đó có thể thực hiện công việc đó.

Thợ 1: Công việc 4
Thợ 2: Công việc 1, 5
Thợ 3: Công việc 4
Thợ 4: Công việc 2, 3
Thợ 5: Công việc 1, 5

Ta sẽ thử tìm một phương án phân công sao cho số công việc được thực hiện là lớn nhất:

1. Phân công thợ 1 cho công việc 4.
2. Phân công thợ 4 cho công việc 2.
3. Phân công thợ 5 cho công việc 1.
Như vậy, ta đã phân công được 3 công việc (1, 2, 4) cho 3 thợ (1, 4, 5).

Ta cũng có thể phân công như sau:

1. Phân công thợ 1 cho công việc 4.
2. Phân công thợ 4 cho công việc 3.
3. Phân công thợ 2 cho công việc 5.
Như vậy, ta cũng phân công được 3 công việc (3, 4, 5) cho 3 thợ (1, 2, 4).

Nếu ta cố gắng phân công 4 công việc, điều này có vẻ không khả thi vì thợ 3 cũng muốn làm công việc 4, nhưng công việc 4 đã được giao cho thợ 1. Tương tự, thợ 2 và thợ 5 đều có thể làm công việc 1 hoặc 5, nhưng nếu cả hai đều được phân công, một người sẽ phải làm công việc 1 và người còn lại làm công việc 5. Điều này vẫn chỉ cho phép tối đa 3 công việc được thực hiện.

Vậy, số công việc nhiều nhất có thể phân công là 3.
Lời giải:
Đáp án đúng: B
Để tìm độ dài đường đi ngắn nhất từ đỉnh 6 đến đỉnh 3 trong đồ thị bằng thuật toán duyệt theo chiều rộng (BFS), ta thực hiện các bước sau:

1. Bắt đầu từ đỉnh 6: Duyệt các đỉnh kề của đỉnh 6 theo thứ tự từ điển. Các đỉnh kề của 6 là: 1, 2, 4, 5.

2. Duyệt các đỉnh kề của 6:
- Từ 6 đến 1 (độ dài đường đi = 1)
- Từ 6 đến 2 (độ dài đường đi = 1)
- Từ 6 đến 4 (độ dài đường đi = 1)
- Từ 6 đến 5 (độ dài đường đi = 1)

3. Duyệt các đỉnh kề của 1, 2, 4, 5 (theo thứ tự duyệt)
- Từ 1: Các đỉnh kề của 1 là 2, 3, 6. Ta đã duyệt 6, nên xét 2 và 3.
- Từ 6 -> 1 -> 2 (độ dài đường đi = 2)
- Từ 6 -> 1 -> 3 (độ dài đường đi = 2)
Vậy ta đã tìm thấy đường đi từ 6 đến 3 với độ dài bằng 2.

Vậy độ dài đường đi ngắn nhất từ đỉnh 6 đến đỉnh 3 là 2.

Do đó, đáp án đúng là A.
Lời giải:
Đáp án đúng: D
Gọi X = {1, 2, 3, 4}.
Ta có |A \u222a B| = 4 và |A \u2229 B| = 1.
Suy ra |A| + |B| = |A \u222a B| + |A \u2229 B| = 4 + 1 = 5.
Vì A \u2229 B khác rỗng nên ta chọn 1 phần tử thuộc A \u2229 B từ tập X có 4 cách.
Gọi phần tử đó là x. Khi đó A' = A \ {x} và B' = B \ {x} là hai tập con rời nhau của X \ {x} và |A' \u222a B'| = 3.
Với mỗi phần tử y thuộc X \ {x}, ta có 3 khả năng:
- y thuộc A' (và không thuộc B')
- y thuộc B' (và không thuộc A')
- y không thuộc A' và B'
Vậy mỗi phần tử thuộc X \ {x} có 3 cách chọn.
Vì |X \ {x}| = 3 nên số cách chọn A' và B' là 3^3 = 27.
Do đó số bộ (A, B) thỏa mãn là 4 * 27 = 108.
Tuy nhiên, không có đáp án nào trùng với kết quả này. Có lẽ có một lỗi trong các đáp án đã cho. Để giải thích rõ hơn, ta xem xét một cách tiếp cận khác.

Chọn một phần tử chung cho A và B: có 4 cách.
Chọn 3 phần tử còn lại để đưa vào A hoặc B hoặc không thuộc A và B. Vì A \u222a B = {1,2,3,4}, nên mỗi phần tử trong {1,2,3,4} \ {phần tử chung} phải thuộc A hoặc B.
Vậy mỗi phần tử có 2 lựa chọn: thuộc A hoặc thuộc B.
Vậy có 2^3 = 8 cách chọn.
Vậy có tất cả 4*2^3 = 4*8 = 32 cách chọn.
Chọn các phần tử thuộc A giao B: có C(4,1) = 4 cách.
Chọn các phần tử thuộc A \ B, B \ A. Gọi số phần tử của A \ B là x, số phần tử của B \ A là y. Ta có x + y = 3. x, y >=0
Có các trường hợp:
+ x = 0, y = 3: C(3,0) * C(3,3) = 1
+ x = 1, y = 2: C(3,1) * C(2,2) = 3
+ x = 2, y = 1: C(3,2) * C(1,1) = 3
+ x = 3, y = 0: C(3,3) * C(0,0) = 1
=> Tổng số cách chọn = 1 + 3 + 3 + 1 = 8
Vậy số bộ (A,B) = 4*8 = 32
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:

Nhận xét nào sau đây là SAI.

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 A = {11, 12, 13, 14, 15}. Quan hệ R được xác định: ∀a,b ∈ A, aRb ⇔ a + b = 2k (k=1,2,...) Quan hệ R được biểu diễn 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 17:

Cho tập A = {1, 2, 3, 4, 5, 6} và quan hệ tương đương R trên A như sau: R = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,1), (4,5), (5,4)}. Xác định phân hoạch do R sinh ra.

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

Biểu thức hằng đúng 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 20:

Cho A và B là hai tập hợp. Hiệu của A và B được ký hiệu A-B, 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 21:

Cho A và B là hai tập hợp. Hiệu đối xứng của A và B được ký hiệu A - B, 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 22:

Quan hệ thứ tự là một quan hệ 2 ngôi và có cá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 23:

Cho A = {a, b, c, e} ; B = {c, d, f, g}. Tập A - B 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 24:

Cho tập A = {1, 2, 3, 4}. Trong các quan hệ trên tập A cho dưới đây, quan hệ nào là quan hệ tương đương?

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

Hoán vị nào dưới đây là hoán vị kế tiếp của hoán vị 2 1 3 4 5 6 7 8 9.

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

Thuật toán được qọi là đệ quy 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 27:

Nội dung của nguyên lý Dirichlet được phát biể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 28:

Nội dung của nguyên lý bù trừ phát biểu trên hai tập hợp hữu hạn A, B. 

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

Trong cách biểu diễn đồ thị bằng danh sách cạnh chúng ta lưu trữ:

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:

Đồ thị dưới dạng ma trận kề:

Đồ thị dưới dạng ma trận kề:Là đồ thị: (ảnh 1)

Là đồ 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

Câu 36:

Thuật toán Floy được dùng để:

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:

Giá trị của luồng cực đại trong mạng:

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:

Nếu G = (V, E) là một đa đồ 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

Câu 39:

Số màu của một đồ thị phẳng 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 mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) được gọi là lát cắt hẹp nhất 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 42:

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

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là:  (ả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 43:

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1):

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1):   (ả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 44:

Cho đồ thị như hình vẽ. Hãy cho biết kế|t quả thực hiện thuật toán DFS(10):

Cho đồ thị như hình vẽ. Hãy cho biết kế|t quả thực hiện thuật toán DFS(10): (ả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
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 47:

Bảng chân trị của biểu thức logic E(q1,q2,..,qn) 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

Câu 49:

Trong bảng Karnaugh, 2 ô gọi là kề nhau 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