Câu 1: Đồ thị trong toán học là gì?

A. Tập hợp các đỉnh và các cạnh nối các đỉnh đó

B. Đường thẳng trên mặt phẳng

C. Biểu đồ hình cột

D. Hình tròn trên mặt phẳng

Câu 2: Đỉnh trong đồ thị là gì?

A. Điểm đại diện cho một đối tượng hoặc vị trí

B. Đường nối các điểm

C. Vùng không gian

D. Một đoạn thẳng

Câu 3: Cạnh trong đồ thị biểu diễn cho gì?

A. Mối liên kết hoặc kết nối giữa hai đỉnh

B. Một điểm đặc biệt

C. Vùng trống giữa các đỉnh

D. Một hình dạng

Câu 4: Đồ thị vô hướng là gì?

A. Đồ thị mà các cạnh không có hướng xác định

B. Đồ thị có hướng rõ ràng cho từng cạnh

C. Đồ thị chỉ có một đỉnh

D. Đồ thị có trọng số

Câu 5: Đồ thị có hướng là gì?

A. Đồ thị mà mỗi cạnh có hướng xác định từ đỉnh này đến đỉnh khác

B. Đồ thị không có cạnh

C. Đồ thị với các cạnh không có hướng

D. Đồ thị chỉ có một đỉnh

Câu 6: Độ của một đỉnh trong đồ thị vô hướng là gì?

A. Số cạnh nối với đỉnh đó

B. Số đỉnh kề nhau

C. Chiều dài cạnh

D. Số cạnh có hướng từ đỉnh đó

Câu 7: Độ vào của một đỉnh trong đồ thị có hướng là gì?

A. Số cạnh hướng vào đỉnh đó

B. Số cạnh hướng ra khỏi đỉnh đó

C. Tổng số cạnh nối đỉnh đó

D. Không liên quan

Câu 8: Độ ra của một đỉnh trong đồ thị có hướng là gì?

A. Số cạnh hướng ra khỏi đỉnh đó

B. Số cạnh hướng vào đỉnh đó

C. Tổng số cạnh nối đỉnh đó

D. Không liên quan

Câu 9: Đường đi trong đồ thị là gì?

A. Dãy các đỉnh liên tiếp nhau mà không cần thiết phải khác nhau

B. Dãy đỉnh không liền kề

C. Tập hợp tất cả các đỉnh

D. Đoạn thẳng trong đồ thị

Câu 10: Chu trình trong đồ thị là gì?

A. Đường đi bắt đầu và kết thúc tại cùng một đỉnh

B. Đường đi không lặp lại đỉnh

C. Đường thẳng nối hai đỉnh

D. Không có chu trình

Câu 11: Đường đi Euler là gì?

A. Đường đi đi qua tất cả các cạnh đúng một lần

B. Đường đi đi qua tất cả các đỉnh đúng một lần

C. Chu trình có trọng số nhỏ nhất

D. Đường thẳng nối hai đỉnh

Câu 12: Chu trình Euler là gì?

A. Chu trình đi qua tất cả các cạnh đúng một lần

B. Chu trình đi qua tất cả các đỉnh đúng một lần

C. Chu trình ngắn nhất

D. Không có chu trình

Câu 13: Đường đi Hamilton là gì?

A. Đường đi đi qua tất cả các đỉnh đúng một lần

B. Đường đi đi qua tất cả các cạnh đúng một lần

C. Chu trình có trọng số lớn nhất

D. Đường thẳng nối hai đỉnh

Câu 14: Chu trình Hamilton là gì?

A. Chu trình đi qua tất cả các đỉnh đúng một lần

B. Chu trình đi qua tất cả các cạnh đúng một lần

C. Chu trình ngắn nhất

D. Không có chu trình

Câu 15: Đồ thị có chu trình Euler khi nào?

A. Tất cả các đỉnh có độ chẵn hoặc đúng hai đỉnh có độ lẻ

B. Có ít nhất một đỉnh độ lẻ

C. Không có đỉnh độ lẻ

D. Có nhiều hơn hai đỉnh độ lẻ

Câu 16: Đồ thị có chu trình Hamilton là vấn đề?

A. Bài toán NP-đầy đủ (khó giải)

B. Dễ giải quyết

C. Không tồn tại

D. Luôn có

Câu 17: Đồ thị đầy đủ là gì?

A. Đồ thị mà mỗi cặp đỉnh đều được nối với nhau bởi một cạnh

B. Đồ thị không có cạnh

C. Đồ thị có hướng

D. Đồ thị có chu trình Euler

Câu 18: Đồ thị con là gì?

A. Đồ thị gồm một tập con các đỉnh và các cạnh của đồ thị ban đầu

B. Đồ thị có ít đỉnh hơn đồ thị gốc

C. Đồ thị mới tạo ra hoàn toàn khác đồ thị ban đầu

D. Đồ thị không có đỉnh

Câu 19: Đồ thị liên thông là gì?

A. Đồ thị mà giữa mọi cặp đỉnh đều tồn tại đường đi nối chúng

B. Đồ thị không có cạnh

C. Đồ thị có chu trình

D. Đồ thị không có đỉnh

Câu 20: Độ dài đường đi trong đồ thị có trọng số được tính như thế nào?

A. Tổng trọng số các cạnh trên đường đi

B. Số đỉnh trên đường đi

C. Số cạnh trên đường đi

D. Trung bình trọng số cạnh

Câu 21: Thuật toán Dijkstra dùng để làm gì?

A. Tìm đường đi ngắn nhất trong đồ thị có trọng số không âm

B. Tìm chu trình Euler

C. Tìm chu trình Hamilton

D. Tìm đồ thị con

Câu 22: Thuật toán Prim dùng để?

A. Tìm cây khung nhỏ nhất trong đồ thị

B. Tìm đường đi ngắn nhất

C. Tìm chu trình Euler

D. Tìm chu trình Hamilton

Câu 23: Thuật toán Kruskal dùng để?

A. Tìm cây khung nhỏ nhất trong đồ thị

B. Tìm đường đi ngắn nhất

C. Tìm chu trình Euler

D. Tìm chu trình Hamilton

Câu 24: Cây khung là gì?

A. Đồ thị con liên thông không có chu trình và chứa tất cả các đỉnh của đồ thị ban đầu

B. Đồ thị có chu trình

C. Đồ thị không có đỉnh

D. Đồ thị có hướng

Câu 25: Đồ thị trọng số là gì?

A. Đồ thị có mỗi cạnh được gán một giá trị số

B. Đồ thị không có cạnh

C. Đồ thị có hướng

D. Đồ thị không có trọng số

Câu 26: Thuật toán BFS (Breadth-First Search) dùng để?

A. Duyệt theo tầng, tìm đường đi ngắn nhất trong đồ thị vô hướng không trọng số

B. Tìm đường đi ngắn nhất trong đồ thị có trọng số

C. Tìm chu trình Euler

D. Tìm chu trình Hamilton

Câu 27: Thuật toán DFS (Depth-First Search) dùng để?

A. Duyệt sâu, kiểm tra liên thông, tìm chu trình trong đồ thị

B. Tìm đường đi ngắn nhất

C. Tìm cây khung nhỏ nhất

D. Tìm đồ thị con

Câu 28: Đồ thị hai phía là gì?

A. Đồ thị mà tập đỉnh có thể chia thành hai tập con sao cho không có cạnh nối đỉnh cùng tập con

B. Đồ thị có hai đỉnh

C. Đồ thị có hai chu trình

D. Đồ thị có trọng số hai loại

Câu 29: Đồ thị hai phía có thể được tô màu bằng bao nhiêu màu?

A. 2 màu

B. 3 màu

C. 1 màu

D. 4 màu

Câu 30: Tính liên thông của đồ thị được hiểu là gì?

A. Mức độ liên kết giữa các đỉnh trong đồ thị

B. Số cạnh trong đồ thị

C. Số đỉnh trong đồ thị

D. Trọng số cạnh

Câu 31: Đường đi ngắn nhất là đường đi?

A. Có tổng trọng số nhỏ nhất giữa hai đỉnh

B. Có nhiều đỉnh nhất

C. Có ít cạnh nhất

D. Có tổng trọng số lớn nhất

Câu 32: Đồ thị rừng là gì?

A. Đồ thị không có chu trình

B. Đồ thị có chu trình

C. Đồ thị đầy đủ

D. Đồ thị có trọng số

Câu 33: Đồ thị cây là gì?

A. Đồ thị liên thông không có chu trình

B. Đồ thị có chu trình

C. Đồ thị rỗng

D. Đồ thị đầy đủ

Câu 34: Số cạnh của đồ thị cây với n đỉnh là?

A. n - 1

B. n

C. n + 1

D. 2n

Câu 35: Thuật toán tìm đường đi ngắn nhất có thể áp dụng cho đồ thị nào?

A. Đồ thị có trọng số không âm

B. Đồ thị không có trọng số

C. Đồ thị có chu trình

D. Đồ thị rỗng

Câu 36: Thuật toán Bellman-Ford dùng để?

A. Tìm đường đi ngắn nhất trong đồ thị có trọng số âm nhưng không có chu trình âm

B. Tìm chu trình Euler

C. Tìm cây khung nhỏ nhất

D. Tìm chu trình Hamilton

Câu 37: Đường đi trong đồ thị có trọng số âm có thể?

A. Tồn tại chu trình âm làm giảm tổng trọng số vô hạn

B. Không tồn tại

C. Luôn là đường đi ngắn nhất

D. Luôn là chu trình Euler

Câu 38: Chu trình âm là gì?

A. Chu trình có tổng trọng số các cạnh là số âm

B. Chu trình có trọng số dương

C. Chu trình có trọng số bằng 0

D. Không tồn tại

Câu 39: Thuật toán Floyd-Warshall dùng để?

A. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị

B. Tìm cây khung nhỏ nhất

C. Tìm chu trình Euler

D. Tìm chu trình Hamilton

Câu 40: Đỉnh bậc k trong đồ thị là gì?

A. Đỉnh có k cạnh nối với nó

B. Đỉnh có trọng số k

C. Đỉnh nằm ở vị trí thứ k

D. Đỉnh không có cạnh nối

Câu 41: Đồ thị có hướng đầy đủ là gì?

A. Mỗi cặp đỉnh có hai cạnh có hướng ngược nhau nối với nhau

B. Đồ thị có hướng không đầy đủ

C. Đồ thị không có cạnh

D. Đồ thị không có đỉnh

Câu 42: Thuật toán kiểm tra đồ thị liên thông là?

A. Dùng DFS hoặc BFS để duyệt đồ thị

B. Tìm đường đi ngắn nhất

C. Tìm cây khung nhỏ nhất

D. Tìm chu trình Euler

Câu 43: Đỉnh kề là gì?

A. Hai đỉnh được nối bởi một cạnh

B. Đỉnh không có cạnh nối

C. Đỉnh nằm trên trục đối xứng

D. Đỉnh nằm xa nhau nhất

Câu 44: Tập các đỉnh kề với đỉnh u là gì?

A. Các đỉnh được nối với u bởi một cạnh

B. Các đỉnh không được nối với u

C. Tập con của đồ thị

D. Tập rỗng

Câu 45: Đồ thị con con trùm (spanning subgraph) là gì?

A. Đồ thị con chứa tất cả các đỉnh của đồ thị ban đầu

B. Đồ thị con không chứa tất cả các đỉnh

C. Đồ thị không có đỉnh

D. Đồ thị không có cạnh

Câu 46: Số cạnh lớn nhất của đồ thị vô hướng với n đỉnh là?

A. n(n-1)/2

B. n

C. n-1

D. 2n

Câu 47: Số cạnh lớn nhất của đồ thị có hướng với n đỉnh là?

A. n(n-1)

B. n

C. n-1

D. 2n

Câu 48: Đồ thị đơn là gì?

A. Đồ thị không có cạnh đa (nhiều cạnh nối cùng cặp đỉnh) và không có vòng (cạnh nối một đỉnh với chính nó)

B. Đồ thị có cạnh đa

C. Đồ thị có vòng

D. Đồ thị có trọng số

Câu 49: Đường đi đơn giản là gì?

A. Đường đi không lặp lại đỉnh

B. Đường đi có thể lặp lại đỉnh

C. Đường đi có nhiều chu trình

D. Đường đi không tồn tại

Câu 50: Đường đi hamilton là đường đi đi qua?

A. Tất cả các đỉnh một lần duy nhất

B. Tất cả các cạnh một lần duy nhất

C. Một phần đỉnh

D. Một phần cạnh

Câu 51: Chu trình Euler tồn tại khi?

A. Đồ thị liên thông và tất cả các đỉnh có bậc chẵn hoặc có đúng hai đỉnh bậc lẻ

B. Đồ thị không liên thông

C. Có nhiều hơn hai đỉnh bậc lẻ

D. Không có đỉnh bậc lẻ

Câu 52: Thuật toán Kruskal chọn cạnh như thế nào?

A. Cạnh có trọng số nhỏ nhất và không tạo chu trình

B. Cạnh có trọng số lớn nhất

C. Cạnh ngẫu nhiên

D. Cạnh có trọng số trung bình

Câu 53: Đồ thị có hướng đầy đủ có bao nhiêu cạnh?

A. n(n-1)

B. n(n-1)/2

C. n-1

D. n

Câu 54: Đồ thị vô hướng đầy đủ có bao nhiêu cạnh?

A. n(n-1)/2

B. n(n-1)

C. n-1

D. n

Câu 55: Đỉnh xuất phát trong thuật toán tìm đường đi ngắn nhất là?

A. Đỉnh bắt đầu tìm đường đi

B. Đỉnh kết thúc

C. Đỉnh trung gian

D. Không quan trọng

Câu 56: Đồ thị có trọng số là đồ thị?

A. Mỗi cạnh có gán một giá trị số

B. Không có cạnh

C. Có nhiều đỉnh

D. Có chu trình

Câu 57: Đồ thị rỗng là đồ thị?

A. Không có đỉnh và cạnh

B. Có một đỉnh duy nhất

C. Có nhiều đỉnh

D. Có nhiều cạnh

Câu 58: Thuật toán BFS bắt đầu duyệt từ?

A. Đỉnh xuất phát

B. Đỉnh có bậc cao nhất

C. Đỉnh có bậc thấp nhất

D. Đỉnh cuối cùng

Câu 59: Thuật toán DFS sử dụng cấu trúc dữ liệu gì?

A. Ngăn xếp (stack) hoặc đệ quy

B. Hàng đợi (queue)

C. Danh sách liên kết

D. Mảng tĩnh

Câu 60: Tập con của đỉnh là gì?

A. Một phần các đỉnh trong đồ thị

B. Tập hợp tất cả các đỉnh

C. Tập rỗng

D. Tập các cạnh