Đáp án đúng: B
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!
Câu hỏi liên quan
Gọi số câu hỏi học sinh phải trả lời từ 5 câu đầu là x. Theo đề bài, x ≥ 4.
Vậy x có thể là 4 hoặc 5.
Trường hợp 1: x = 4, tức là học sinh phải chọn 4 câu từ 5 câu đầu và 4 câu còn lại từ 5 câu sau. Số cách chọn là C(5,4) * C(5,4) = 5 * 5 = 25.
Trường hợp 2: x = 5, tức là học sinh phải chọn 5 câu từ 5 câu đầu và 3 câu còn lại từ 5 câu sau. Số cách chọn là C(5,5) * C(5,3) = 1 * 10 = 10.
Tổng số cách chọn là 25 + 10 = 35.
Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất trong đồ thị có trọng số không âm. Thuật toán này tìm đường đi ngắn nhất từ một đỉnh nguồn đã chọn đến tất cả các đỉnh còn lại trong đồ thị.
Tại sao các phương án khác không đúng:
- Phương án 1: Tìm đường đi ngắn nhất giữa *các cặp đỉnh bất kì* của đồ thị thường được giải quyết bằng thuật toán Floyd-Warshall.
- Phương án 3: Dijkstra có thể tìm đường đi ngắn nhất giữa hai đỉnh, nhưng nó thực tế tìm đường đi ngắn nhất từ đỉnh nguồn đến *tất cả* các đỉnh khác, rồi mới có thể xác định đường đi ngắn nhất đến đỉnh đích cụ thể. Phương án 2 chính xác hơn vì nó bao quát toàn bộ quá trình hoạt động của thuật toán.
- Phương án 4: Tương tự phương án 3, Dijkstra có thể được sử dụng để tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích. Tuy nhiên, trong quá trình đó, nó sẽ tìm ra đường đi ngắn nhất đến tất cả các đỉnh khác. Do đó, phương án 2 mô tả chính xác và đầy đủ hơn mục đích của thuật toán Dijkstra.
Cả thuật toán Prim và Kruskal đều là các thuật toán tham lam được sử dụng để tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số. Điểm giống nhau cốt lõi giữa hai thuật toán này là cả hai đều cố gắng xây dựng cây khung bằng cách chọn các cạnh có trọng số nhỏ nhất một cách tham lam, đồng thời đảm bảo không tạo ra chu trình (cycle) trong cây khung đang xây dựng.
Phân tích các đáp án:
- Đáp án 1: Dừng khi kết nạp được tất cả các cạnh vào cây khung. - Sai. Cây khung chỉ chứa n-1 cạnh (với n là số đỉnh của đồ thị).
- Đáp án 2: Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung - Sai. Cây khung có n đỉnh và n-1 cạnh.
- Đáp án 3: Thuật toán chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây khung và không tạo ra chu trình. - Gần đúng. Mô tả đúng việc chọn cạnh nhỏ nhất và không tạo chu trình, nhưng "liên thuộc với các đỉnh đã thuộc cây khung" đúng hơn với Prim, còn Kruskal chọn cạnh nhỏ nhất bất kì không quan trọng là liên thuộc đỉnh nào đã có.
- Đáp án 4: Thuật toán xây dựng cây khung ngắn nhất. - Đúng. Đây là mục tiêu chung của cả hai thuật toán. Cả Prim và Kruskal đều tìm cách xây dựng cây khung có tổng trọng số các cạnh là nhỏ nhất có thể.
Vậy, đáp án chính xác nhất là 4, vì nó thể hiện mục tiêu chung của cả hai thuật toán.
Trong thuật toán Ford-Fulkerson để giải bài toán luồng cực đại, bước tăng luồng được thực hiện trên các cạnh nằm trên đường đi tăng (đường đi đánh dấu). Đường đi tăng là đường đi từ đỉnh phát (source) đến đỉnh thu (sink) mà trên đó ta có thể tăng luồng. Thuật toán sẽ lặp đi lặp lại việc tìm đường đi tăng và tăng luồng trên đường đi đó cho đến khi không còn đường đi tăng nào nữa. Do đó, đáp án chính xác là các cạnh nằm trên đường đi đánh dấu.
.jpg)
