Search Header Logo

Đường đi ngắn nhất

Authored by Khang Minh

Mathematics

University

Used 1+ times

Đường đi ngắn nhất
AI

AI Actions

Add similar questions

Adjust reading levels

Convert to real-world scenario

Translate activity

More...

    Content View

    Student View

10 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Thuật toán nào sau đây không thể xử lý đồ thị có cạnh trọng số âm?

Bellman–Ford

Dijkstra

SPFA

Floyd–Warshall

2.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Độ phức tạp thời gian trung bình của thuật toán Dijkstra trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

O (V2)

O(E + VlogV)

O(ElogV)

O(VE)

3.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Bellman–Ford lặp tối đa bao nhiêu lần qua tất cả các cạnh để tìm đường đi ngắn nhất trong đồ thị có V đỉnh?

V lần

V−1 lần

E lần

E−1 lần

4.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Trong thuật toán Dijkstra, nếu bạn khởi tạo tất cả khoảng cách từ đỉnh nguồn bằng vô cực và đỉnh nguồn bằng 0, thì tại bước nào giá trị khoảng cách của một đỉnh mới được “cố định” (không còn thay đổi nữa)?

Khi đỉnh đó được đưa ra khỏi hàng đợi ưu tiên lần đầu

Khi mọi cạnh tới nó đã được thả qua

Khi tất cả các đỉnh khác đã được xử lý

Khi duyệt hết toàn bộ đồ thị

5.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Thuật toán nào sau đây có thể vừa phát hiện chu trình âm trong đồ thị vừa tìm đường đi ngắn nhất từ một nguồn?

Dijkstra với kiểm tra dấu hiệu cạnh âm

Bellman–Ford

Floyd–Warshall với biến thể phát hiện chu trình

SPFA không kèm kiểm soát

6.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Trong thuật toán Dijkstra, điều kiện nào sau đây phải đúng để thuật toán hoạt động chính xác?

Đồ thị phải vô hướng và không có cạnh nào có trọng số âm

Đồ thị có thể có cạnh âm nhưng không có chu trình âm

Đồ thị phải có ít nhất một cạnh âm

Đồ thị bắt buộc phải kết nối đầy đủ

7.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Bellman–Ford sẽ phát hiện chu trình âm bằng cách nào?

So sánh dist[] trước và sau mỗi vòng lặp, nếu không đổi là có chu trình âm

Chạy thêm một vòng “relax all edges”; nếu còn cập nhật được, tức tồn tại chu trình âm

Đếm số cạnh âm; nếu ≥ V thì có chu trình âm

Kiểm tra xem tổng trọng số đường đi ngắn nhất có âm hay không

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?