Toán rời rạcThi thử trắc nghiệm ôn tập Toán rời rạc – Đề #15 Đăng vào 31 Tháng 7, 2026 bởi admin Thi thử trắc nghiệm ôn tập Toán rời rạc – Đề #15 Thi thử trắc nghiệm ôn tập Toán rời rạc – Đề #15 Số câu30Quiz ID987 Câu 1 Câu 1: Cây là đồ thị vô hướng liên thông: A Không có chu trình. B Không có đỉnh cô lập C Không có cạnh cầu D Không có đỉnh treo Câu 2 Câu 2: Mạng là một đồ thị có hướng, A trong đó có một đỉnh cô lập. Mỗi cung $e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E$ được gán một giá trị không âm qij gọi là khả năng thông qua của cung e. B trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu. Mỗi cung $e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E$ được gán một giá trị không âm qij gọi là khả năng thông qua C trong đó có duy nhất một đỉnh s có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t có cung đi ra gọi là điểm thu. Mỗi cung $e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E$ được gán một giá trị không âm qij gọi là khả năng thông qua của cung D trong đó có duy nhất một đỉnh s có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu. Mỗi cung $e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E$ được gán một giá trị không âm qij gọi là khả năng thông qua của c Câu 3 Câu 3: Cho mạng G, điểm phát s điểm thu t. Tính cân bằng của luồng f trên mạng G phải thỏa mãn cho: A Tất cả các đỉnh của G. B Tất cả các đỉnh của G trừ đỉnh phát s. C Tất cả các đỉnh của G rừ đỉnh thu t. D Tất cả các đỉnh của G trừ đỉnh phát s và đỉnh thu t. Câu 4 Câu 4: Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) trong đó X + V, Y= V - X là: A Tập hợp tất cả các cung (vi , vj) sao cho hoặc vi x X, vj x Y và vj x X, vi x Y B Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi x X, vj x Y hoặc vj x X, vi x Y C Tập hợp tất cả các cung (vi , vj) sao cho hoặc vi x X, vj x X hoặc vj x X, vi x Y D Tập hợp tất cả các cung (vi , vj) sao cho hoặc vi x X, vj x Y hoặc vj x Y, vi x Y Câu 5 Câu 5: 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: A khả năng thông qua của lát cắt (X,Y) bằng tổng khả năng thông qua của các cung đi ra khỏi đỉnh s B khả năng thông qua của lát cắt (X,Y) bằng tổng khả năng thông qua của các cung đi vào đỉnh t C khả năng thông qua của lát cắt (X,Y) lớn nhất. D khả năng thông qua của lát cắt (X,Y) bé nhất. Câu 6 Câu 6: Cho đồ thị G = (V,E) vô hướng. Bậc của các đỉnh 1, 2, 3, 4, 5 tương ứng là: A 3, 3, 4, 6, 4 B 3, 4, 6, 4, 4 C 3, 4, 6, 4, 5 D 3, 4, 5, 4, 4 Câu 7 Câu 7: Có bao nhiêu cạnh trong đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 6? A 60 B 45 C 30 D 20 Câu 8 Câu 8: Đồ thị G vô hướng nào trong các đồ thị sau là tồn tại nếu các đỉnh có số bậc lần lượt là: A 2, 4, 3, 1, 4, 2, 5 B 3, 4, 2, 1, 4, 2, 6 C 5, 2, 2, 1, 3, 2, 4 D 2, 1, 4, 3, 4, 2, 7 Câu 9 Câu 9: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là: A I, A, E, G, K, B, C, F, H, D B I, A, E, G, C, K, B, F, H, D C I, A, B, C, D, E, G, H, F, K D I, A, B, D, E, G, C, F, H, K Câu 10 Câu 10: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K) là: A K, A, B, C, D, E, F, G, H, I B K, A, C, E, G, B, D, F, H, I C K, I, E, G, F, H, A, B, C, D D K, I, A, E, G, B, C, F, H, D Câu 11 Câu 11: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là: A I, A, C, H, E, G, B, D, F, K B I, A, B, C, D, E, G, F, H, K C I, A, C, K, E, G, B, D, F, H D I, E, F, G, H, A, B, C, D, K Câu 12 Câu 12: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(H) là: A H, G, F, D, E, F, A, B, C, I B H, F, G, E, K, I, A, C, B, D C H, G, F, B, D, E, K, A, C, I D H, E, F, G, H, I, A, B, C, D Câu 13 Câu 13: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là gì: A I, A, D, E, G, B, C, F, H, K B I, A, B, C, D, E, F, G, H,K C I, E, F, G, H, A, B, C, D, K D I, A, C, E, G, B, D, F, H, K Câu 14 Câu 14: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K): A K, B, D, F, H, A, C, E, G, I B K, B, A, C, D, F, E, G, H, I C K, B, F, H, A, C, D, E, G, I D K, E, F, G, H, A, B, C, D, I Câu 15 Câu 15: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là: A C, A, B, E, F, D, G, H, K, C, N B C, A, B, K, N, I, D, E, F, H, G C C, A, E, G, B, D, F, H, K, I, N D C, A, E, G, F, H, N, B, D, I, K Câu 16 Câu 16: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(I) là: A I, A, C, E, G, B, F, H, D, K, N B I, C, E, F, G, K, H, N, B, D, A C I, G, B, F, N, K, E, C, D, H, A D I, G, H, N, K, B, A, C, E, F, D Câu 17 Câu 17: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(A) là: A A, B, K, D, C, E, F, G, H, N, I B A, B, D, K, I, N, C, E, G, H, F C A, C, E, F, D, B, I, N, K, H, B D A, K, N, D, F, H, G, E, C, I, B Câu 18 Câu 18: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là: A G, H, I, N, K, B, A, C, D, E, F B G, H, N, K, B, A, D, C, E, F, I C G, H, N, K, B, A, C, D, E, I, F D G, A, B, C, D, E, F, N, K, H, I Câu 19 Câu 19: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(K) là: A K, I, A, C, E, G, B, D, F, H B K, I, A, B, C, D, E, F, G, H C K, I, A, B, C, D, F, H, G, E D K, A, C, D, B, I, G, H, F, E Câu 20 Câu 20: Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1): A 1, 2, 4, 7, 3, 6, 8, 5, 9, 10 B 1, 7, 6, 3, 9, 8, 5, 10, 4, 2 C 1, 2, 6, 4, 5, 10, 9, 8, 3, 7 D 1, 2, 4, 7, 8, 9, 5, 10, 3, 6 Câu 21 Câu 21: Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(2): A 2, 1, 3, 4, 5, 10, 6, 9, 7, 8 B 2, 1, 7, 4, 3, 6, 8, 5, 9, 10 C 2, 1, 3, 5, 4, 10, 6, 9, 7, 8 D 2, 1, 7, 3, 6, 9, 4, 5, 8, 10 Câu 22 Câu 22: Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán DFS(1): A 1, 2, 7, 4, 5, 10, 3, 6, 9, 8 B 1, 2, 3, 6, 9, 4, 5, 10, 8, 7 C 1, 2, 3, 4, 5, 10, 6, 9, 7, 8 D 1, 2, 7, 8, 3, 6, 9, 5, 10, 4 Câu 23 Câu 23: Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán DFS(10): A 10, 5, 4, 1, 2, 3, 6, 9, 8, 7 B 10, 5, 4, 1, 2, 7, 8, 6, 9, 3 C 10, 4, 5, 2, 1, 6, 9, 7, 8, 3 D 10, 4, 5, 1, 2, 3, 6, 9, 8, 7 Câu 24 Câu 24: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Kruskal có tập cạnh là: A T = { (1,2), (1, 4), (2, 3), (2, 6), (6,3), (6, 7) } B) B T = { (1,2), (1, 4), (1, 3), (2, 6), (4,5), (6, 7) } C T = { (1,2), (1, 4), (2, 4), (2, 6), (4,5), (6, 7) } D T = { (1,2), (1, 4), (2, 3), (4,5) ,(2, 6), (6, 7) } Câu 25 Câu 25: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh là: A T = {(3,6),(1,8),(8,2), (3,6), (6,7), (8,5), (5,7)} B T = {(1,2),(3,8),(8,5), (3,6), (6,7), (2,4), (4,7)} C T = {(5,7),(5,6),(8,2), (3,6), (6,7), (8,5), (8,4)} D T = {(1,8),(3,8),(8,2), (3,6), (6,7), (8,5), (8,4)} Câu 26 Câu 26: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh: A T ={(2,5)(2,6)(2,3)(6,2)(4,1)(5,4)} B T ={(5,3)(3,7)(2,3)(6,2)(4,1)(7,4)} C T ={(5,1)(3,5)(2,3)(6,2)(4,1)(7,4)} D T ={(4,7)(3,5)(2,3)(6,2)(4,1)(3,6)} Câu 27 Câu 27: Một công thức được gọi là có dạng chuẩn tắc hội nếu …? A Nó là hội của các biểu thức hội cơ bản B Nó là hội của các biểu thức tuyển cơ bản C Nó là tuyển của các biểu thức hội cơ bản D Nó là tuyển của các biểu thức tuyển cơ bản Câu 28 Câu 28: Một công thức được gọi là có dạng chuẩn tắc tuyển nếu …? A Nó là hội của các biểu thức hội cơ bản B Nó là hội của các biểu thức tuyển cơ bản C Nó là tuyển của các biểu thức hội cơ bản D Nó là tuyển của các biểu thức tuyển cơ bản Câu 29 Câu 29: Giả sử p1, p2, … , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, … , pn được gọi là một biểu thức hội cơ bản nếu nó có dạng? A $F = {q_1} \vee {q_2} \vee ... \vee {q_n}$ với qj = pj hoặc ${q_j} = \overline {{p_j}} (j = 1,...,n)$ B $F = {q_1} \vee {q_2} \vee ... \vee {q_n}$ C $F = {q_1} \wedge {q_2} \wedge ... \wedge {q_n}$ Câu 30 Câu 30: Biểu thức $(P \wedge Q) \to (P \vee Q)$ tương đương logic với biểu thức nào sau đây? A $(P \wedge Q) \vee (P \vee Q)$ B $(P \wedge Q) \vee (\overline {P \vee Q} )$ C $(\overline {P \wedge Q} ) \vee (P \vee Q)$ D $(\overline {P \wedge Q} ) \wedge (P \vee Q)$ Thi thử trắc nghiệm ôn tập Toán rời rạc – Đề #14 Thi thử trắc nghiệm ôn tập Toán rời rạc – Đề #16
