wayground logo

Free Printable Worksheets

NEW

Font size

S
M
L
XL
Worksheets

Ghvg

Total questions: 41

Worksheet time: 21mins

Name
Class
Date
1.

Trong tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các đỉnh cần khám phá?

a)

Stack

b)

Queue

c)

Priority Queue

d)

List

2.

Đâu là đặc điểm chính của thuật toán DFS?

a)

Luôn tìm đường đi ngắn nhất

b)

Khám phá tất cả các đỉnh cùng mức trước

c)

Dễ dẫn đến đi vào chu trình nếu không đánh dấu

d)

Sử dụng hàng đợi

3.

Giả sử đồ thị có nn đỉnh và mm cạnh. Độ phức tạp thời gian của DFS/BFS là bao nhiêu?

a)

O(n^2)

b)

O(n+m)

c)

O(n.m)

d)

O(log n)

4.

Với một đồ thị vô hướng liên thông, nếu thực hiện BFS từ một đỉnh, điều gì xảy ra?

a)

Chỉ thăm được một phần đồ thị

b)

Có thể bỏ sót chu trình

c)

Tất cả các đỉnh được thăm

d)

Không có kết quả chính xác

5.

Một đồ thị vô hướng liên thông có chu trình Euler khi nào?

a)

Tất cả các đỉnh đều có bậc lẻ

b)

Có đúng 2 đỉnh bậc lẻ

c)

Tất cả các đỉnh có bậc chẵn

d)

Đồ thị có hướng

6.

Trong đồ thị có hướng, điều kiện để tồn tại chu trình Euler là gì?

a)

Bậc vào = bậc ra với mọi đỉnh

b)

Có đúng 2 đỉnh có bậc vào ≠ bậc ra

c)

Có ít nhất một đỉnh cô lập

d)

Tồn tại ít nhất một chu trình

7.

Thuật toán nào dùng để tìm chu trình Euler hiệu quả nhất?

a)

Prim

b)

Dijkstra

c)

Hierholzer

d)

Kruskal

8.

Đồ thị Hamilton là gì?

a)

Đồ thị có chu trình đi qua tất cả các đỉnh đúng một lần và quay về đỉnh xuất phát

b)

Đồ thị có cạnh nối tất cả các cặp đỉnh

c)

Đồ thị có ít nhất một chu trình

d)

Đồ thị có chu trình đi qua mỗi cạnh đúng một lần

9.

Phát biểu nào sau đây là đúng về bài toán Hamilton?

a)

Luôn có lời giải với mọi đồ thị đầy đủ

b)

Là bài toán P

c)

Là bài toán NP-complete

d)

Có thể giải bằng BFS

10.

Điều nào là không đúng về đồ thị Hamilton?

a)

Không phải mọi đồ thị liên thông đều là Hamilton

b)

Đồ thị có chu trình Euler thì luôn có chu trình Hamilton

c)

Đồ thị đầy đủ với ≥3 đỉnh luôn là Hamilton

d)

Việc tìm chu trình Hamilton là khó về tính toán

11.

Nếu trong DFS, bạn không đánh dấu đỉnh đã thăm, điều gì có thể xảy ra?

a)

Đồ thị không còn liên thông

b)

Không bao giờ tìm được đích

c)

Bị lặp vô hạn nếu đồ thị có chu trình

d)

Không có ảnh hưởng gì

12.

Trong BFS, thứ tự thăm đỉnh phụ thuộc vào:

a)

Mức độ của đỉnh

b)

Số cạnh nối ra từ đỉnh

c)

Thứ tự đưa vào hàng đợi

d)

Trọng số của cạnh

13.

DFS thường được cài đặt bằng:

a)

Queue

b)

Stack (hoặc đệ quy)

c)

Min-Heap

d)

Priority Queue

14.

Mục đích chính của DFS khi áp dụng trong phân tích thành phần liên thông là gì?

a)

Xác định chu trình

b)

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

c)

Phân chia các cụm đỉnh riêng biệt

d)

Đếm số cạnh

15.

Tìm đường đi ngắn nhất từ một đỉnh trong đồ thị vô hướng không trọng số nên dùng thuật toán nào?

a)

DFS

b)

Dijkstra

c)

BFS

d)

Kruskal

16.

Phát biểu đúng về chu trình Euler và Hamilton trong đồ thị:

a)

Mọi đồ thị có chu trình Hamilton đều có chu trình Euler

b)

Nếu có chu trình Euler thì chắc chắn có chu trình Hamilton

c)

Có chu trình Euler không có nghĩa có chu trình Hamilton

d)

Hai khái niệm hoàn toàn tương đương

17.

Thuật toán nào sau đây không sử dụng trọng số của cạnh?

a)

BFS

b)

Dijkstra

c)

A*

d)

Bellman-Ford

18.

Trong một hệ thống thành phố được mô hình hóa bằng đồ thị, việc lập tuyến đường cho xe thu gom rác đi qua mọi con đường đúng một lần chính là bài toán:

a)

TSP

b)

Chu trình Hamilton

c)

Đường đi Euler

d)

DFS nâng cao

19.

Với đồ thị có 8 đỉnh, khi nào tồn tại đường đi Euler không phải là chu trình Euler?

a)

Khi tất cả các đỉnh bậc chẵn

b)

Khi đúng 2 đỉnh bậc lẻ

c)

Khi có đỉnh bậc 0

d)

Khi đồ thị có hướng

20.

Phát biểu nào sau đây là sai?

a)

Chu trình Euler đi qua mỗi cạnh đúng 1 lần

b)

Đường đi Hamilton đi qua mỗi đỉnh đúng 1 lần

c)

Nếu đồ thị có chu trình Hamilton thì có chu trình Euler

d)

Chu trình Hamilton có thể không tồn tại trong đồ thị liên thông

21.

Trong tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng để lưu trữ các đỉnh cần khám phá?

a)

Stack

b)

Queue

c)

Priority Queue

d)

List

22.

Đâu là đặc điểm chính của thuật toán DFS?

a)

Luôn tìm đường đi ngắn nhất

b)

Khám phá tất cả các đỉnh cùng mức trước

c)

Dễ dẫn đến đi vào chu trình nếu không đánh dấu

d)

Sử dụng hàng đợi

23.

Giả sử đồ thị có nn đỉnh và mm cạnh. Độ phức tạp thời gian của DFS/BFS là bao nhiêu?

a)

O(n^2)

b)

O(n+m)

c)

O(n.m)

d)

O(log n)

24.

Với một đồ thị vô hướng liên thông, nếu thực hiện BFS từ một đỉnh, điều gì xảy ra?

a)

Chỉ thăm được một phần đồ thị

b)

Có thể bỏ sót chu trình

c)

Tất cả các đỉnh được thăm

d)

Không có kết quả chính xác

25.

Một đồ thị vô hướng liên thông có chu trình Euler khi nào?

a)

Tất cả các đỉnh đều có bậc lẻ

b)

Có đúng 2 đỉnh bậc lẻ

c)

Tất cả các đỉnh có bậc chẵn

d)

Đồ thị có hướng

26.

Trong đồ thị có hướng, điều kiện để tồn tại chu trình Euler là gì?

a)

Bậc vào = bậc ra với mọi đỉnh

b)

Có đúng 2 đỉnh có bậc vào ≠ bậc ra

c)

Có ít nhất một đỉnh cô lập

d)

Tồn tại ít nhất một chu trình

27.

Thuật toán nào dùng để tìm chu trình Euler hiệu quả nhất?

a)

Prim

b)

Dijkstra

c)

Hierholzer

d)

Kruskal

28.

Đồ thị Hamilton là gì?

a)

Đồ thị có chu trình đi qua tất cả các đỉnh đúng một lần và quay về đỉnh xuất phát

b)

Đồ thị có cạnh nối tất cả các cặp đỉnh

c)

Đồ thị có ít nhất một chu trình

d)

Đồ thị có chu trình đi qua mỗi cạnh đúng một lần

29.

Phát biểu nào sau đây là đúng về bài toán Hamilton?

a)

Luôn có lời giải với mọi đồ thị đầy đủ

b)

Là bài toán P

c)

Là bài toán NP-complete

d)

Có thể giải bằng BFS

30.

Điều nào là không đúng về đồ thị Hamilton?

a)

Không phải mọi đồ thị liên thông đều là Hamilton

b)

Đồ thị có chu trình Euler thì luôn có chu trình Hamilton

c)

Đồ thị đầy đủ với ≥3 đỉnh luôn là Hamilton

d)

Việc tìm chu trình Hamilton là khó về tính toán

31.

Nếu trong DFS, bạn không đánh dấu đỉnh đã thăm, điều gì có thể xảy ra?

a)

Đồ thị không còn liên thông

b)

Không bao giờ tìm được đích

c)

Bị lặp vô hạn nếu đồ thị có chu trình

d)

Không có ảnh hưởng gì

32.

Trong BFS, thứ tự thăm đỉnh phụ thuộc vào:

a)

Mức độ của đỉnh

b)

Số cạnh nối ra từ đỉnh

c)

Thứ tự đưa vào hàng đợi

d)

Trọng số của cạnh

33.

DFS thường được cài đặt bằng:

a)

Queue

b)

Stack (hoặc đệ quy)

c)

Min-Heap

d)

Priority Queue

34.

Mục đích chính của DFS khi áp dụng trong phân tích thành phần liên thông là gì?

a)

Xác định chu trình

b)

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

c)

Phân chia các cụm đỉnh riêng biệt

d)

Đếm số cạnh

35.

Tìm đường đi ngắn nhất từ một đỉnh trong đồ thị vô hướng không trọng số nên dùng thuật toán nào?

a)

DFS

b)

Dijkstra

c)

BFS

d)

Kruskal

36.

Phát biểu đúng về chu trình Euler và Hamilton trong đồ thị:

a)

Mọi đồ thị có chu trình Hamilton đều có chu trình Euler

b)

Nếu có chu trình Euler thì chắc chắn có chu trình Hamilton

c)

Có chu trình Euler không có nghĩa có chu trình Hamilton

d)

Hai khái niệm hoàn toàn tương đương

37.

Thuật toán nào sau đây không sử dụng trọng số của cạnh?

a)

BFS

b)

Dijkstra

c)

A*

d)

Bellman-Ford

38.

Trong một hệ thống thành phố được mô hình hóa bằng đồ thị, việc lập tuyến đường cho xe thu gom rác đi qua mọi con đường đúng một lần chính là bài toán:

a)

TSP

b)

Chu trình Hamilton

c)

Đường đi Euler

d)

DFS nâng cao

39.

Với đồ thị có 8 đỉnh, khi nào tồn tại đường đi Euler không phải là chu trình Euler?

a)

Khi tất cả các đỉnh bậc chẵn

b)

Khi đúng 2 đỉnh bậc lẻ

c)

Khi có đỉnh bậc 0

d)

Khi đồ thị có hướng

40.

Phát biểu nào sau đây là sai?

a)

Chu trình Euler đi qua mỗi cạnh đúng 1 lần

b)

Đường đi Hamilton đi qua mỗi đỉnh đúng 1 lần

c)

Nếu đồ thị có chu trình Hamilton thì có chu trình Euler

d)

Chu trình Hamilton có thể không tồn tại trong đồ thị liên thông

41.

Quang hợp quyết định khoảng bao nhiêu % năng suất cây trồng?

a)

90 - 95%

b)

80- 85%

c)

60 - 65%

d)

70 - 75%

Similar Resources on Wayground

A Scrapless Home

40 questions

A Scrapless Home

quiz

Worksheet

•

1st Grade - Professio...

BIO 2ND SEM

40 questions

BIO 2ND SEM

quiz

Worksheet

•

Professional Development

Bài tập ôn thi Sinh học di truyền 151 đến 187

37 questions

Bài tập ôn thi Sinh học di truyền 151 đến 187

quiz

Worksheet

•

Professional Development

mô vi sinh đề 1

38 questions

mô vi sinh đề 1

quiz

Worksheet

•

Professional Development

Bài Quiz không có tiêu đề

44 questions

Bài Quiz không có tiêu đề

quiz

Worksheet

•

Professional Development