Free Printable Toán rời rạc (module 2)

1.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal. Hãy điền vào những vị trí đã bị che.

a)

A = 2

b)

A = 1

c)

A = 4

d)

A = 3

2.

Vùng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị bằng thuật toán FordBellman. Hãy điền vào những vị trí đã bị che.

a)

A = 4

b)

A = 2

c)

A = 3

d)

A = 1

3.

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

a)

G4 là đồ thị đường

b)

G4 là đồ thị hai phía

c)

G4 là cây

d)

Không phát biểu nào đúng

4.

Vùng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị bằng thuật toán FordBellman. Hãy điền vào những vị trí đã bị che.

a)

A = ∞; B = 4

b)

A = 3; B = 4

c)

A = 2; B = 3

d)

A = 4; B = 3

5.

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

a)

a.

Nếu tìm đường đi đến một đỉnh xác định thì thuật toán Dijkstra có thể dừng khi nhãn đỉnh đó được cố định

b)

Thuật toán Dijkstra chỉ làm việc với đồ thị có trọng số cạnh là âm

c)

Thuật toán Dijkstra chỉ làm việc với đồ thị có trọng số cạnh là dương

d)

Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại

6.

Đồ thị có chu trình Hamilton nào?

a)

1 → 7 → 6 → 2 → 3 → 5 → 4 → 1

b)

1 → 6 → 7 → 3 → 2 → 5 → 4 → 1

c)

1 → 6 → 7 → 2 → 5 → 3 → 4 → 1

d)

1 → 6 → 7 → 2 → 3 → 5 → 4 → 1

7.

Đâu là đường đi trên G?

a)

7 → 2 → 6 → 4 → 9

b)

3 → 2 → 6 → 4 → 8

c)

3 → 2 → 6 → 4 → 9

d)

3 → 2 → 6 → 9 → 1

8.

Cạnh nào là cầu?

a)

(2, 7)

b)

(4, 9)

c)

(8, 1)

d)

(9, 6)

9.

Thứ tự các đỉnh khi duyệt đồ thị bằng thuật toán tìm kiếm rộng là gì?

a)

1 → 2 → 4 → 5 → 6

b)

1 → 2 → 4 → 5 → 6

c)

1 → 2 → 5 → 4 → 6

d)

1 → 2 → 4 → 6 → 5

10.

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

a)

a.

Không phát biểu nào đúng

b)

b.

Thuật toán Dijkstra chỉ làm việc với đồ thị có trọng số cạnh là âm

c)

Thuật toán Dijkstra chỉ làm việc với đồ thị có trọng số cạnh là dương

d)

Thuật toán Dijkstra có thể làm việc được với đồ thị có chu trình âm

11.

Đỉnh nào là đỉnh rẽ nhánh?

a)

.

Đỉnh 2

b)

Đỉnh 4

c)

Đỉnh 6

d)

Đỉnh 8

12.

Bảng bên phải của hình mô tả quá trình tìm đường đi Euler của đồ thị. Hãy điền vào những vị trí đã bị che.

a)

A = 3

b)

A = 4

c)

A = 2

d)

A = 1

13.

Vùng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị bằng thuật toán FordBellman. Hãy điền vào những vị trí đã bị che.

a)

A = 3; B = 3

b)

A = 3; B = 4

c)

A = 4; B = 3

d)

A = 2; B = 3

14.

Bảng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại của đồ thị bằng thuật toán Dijkstra. Hãy điền vào những vị trí đã bị che.

a)

A = 1; B = 4; C = 5; D = 4

b)

A = ∞; B = 3; C = 6; D = 3

c)

A = ∞; B = 1; C = 8; D = 1

d)

A = 1; B = 2; C = 7; D = 2

15.

Cây bên phải của hình mô tả quá trình tìm chu trình Hamilton của đồ thị. Hãy điền vào những vị trí đã bị che.

a)

A = 1

b)

A = 5

c)

A = 3

d)

A = 4

16.

Cây bên phải của hình mô tả quá trình tìm chu trình Hamilton của đồ thị. Hãy điền vào những vị trí đã bị che.

a)

A = 3; B = 4

b)

A = 4; B = 4

c)

A = 3; B = 2

d)

A = 5; B = 5

17.

Bảng bên phải của hình mô tả quá trình duyệt đồ thị bằng thuật toán tìm kiếm sâu khử đệ quy. Hãy điền vào những vị trí đã bị che.

a)

A = 4

b)

A = 3

c)

A = 1

d)

A = 2

18.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim. Hãy điền vào những vị trí đã bị che

a)

A = 8

b)

A = 6

c)

A = 7

d)

A = 5

19.

Bảng bên phải của hình mô tả quá trình tìm đường đi Euler của đồ thị. Hãy điền vào những vị trí đã bị che.

a)

A = 1; B = 3

b)

A = 2; B = 3

c)

A = 1; B = d

d)

A = 1; B = 4

20.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal. Hãy điền vào những vị trí đã bị che.

a)

A = 2; B = 3; C = 7; D = 6

b)

A = 1; B = 5; C = 7; D = 7

c)

A = 1; B = 4; C = 3; D = 8

d)

A = 2; B = 4; C = 3; D = 6

21.

Bảng bên phải của hình mô tả một phần quá trình tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng thuật toán Floyd. Hãy điền vào những vị trí đã bị che.

a)

A = 3; B = 1; C = 3; D = 2

b)

A = 2; B = 2; C = 3; D = 1

c)

A = 2; B = 1; C = 3; D = 4

d)

A = 4; B = 1; C = 3; D = 1

22.

Bảng bên phải của hình mô tả quá trình tìm chu trình Euler của đồ thị. Hãy điền vào những vị trí đã bị che.

a)

A = 3; B = 5; C = 4; D = f

b)

A = 5; B = 3; C = 2; D = d f

c)

A = 1; B = 2; C = 1; D = d f

d)

A = 4; B = 4; C = 3; D = f

23.

Bảng bên phải của hình mô tả quá trình duyệt đồ thị bằng thuật toán tìm kiếm rộng. Hãy điền vào những vị trí đã bị che.

a)

A = 5

b)

A = 4

c)

A = 1

d)

A = 2

24.

Phát biểu nào sau đây là đúng về thuật toán Prim?

a)

Cạnh được kết nạp là cạnh có trọng số nhỏ nhất

b)

Cạnh được kết nạp là cạnh có trọng số lớn nhất trong các cạnh nối 1 đỉnh đã ở trong cây và 1 đỉnh chưa ở trong cây

c)

Cạnh được kết nạp là cạnh có trọng số nhỏ nhất trong các cạnh nối 1 đỉnh đã ở trong cây và 1 đỉnh chưa ở trong cây

d)

Cạnh được kết nạp là cạnh có trọng số nhỏ nhất nối 2 đỉnh chưa được kết nạp vào câ

25.

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

a)

Tất cả các cạnh của cây đều là cầu

b)

Cây có n đỉnh thì có n cạnh

c)

Tất cả các đỉnh không là lá của cây đều là đỉnh rẽ nhánh

d)

Trên cây tồn tại ít nhất 2 lá

26.

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

a)

Thuật toán Floyd hữu hiệu hơn chạy thuật toán FordBellman cho từng đỉnh

b)

Thuật toán Floyd tìm đường đi ngắn nhất từ các đỉnh đến 1 đỉnh

c)

Thuật toán Floyd làm việc trên đồ thị có trọng số cạnh bất kỳ và không có chu trình âm

d)

Thuật toán Floyd tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh

27.

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

a)

Thuật toán FordBellman chỉ làm việc được với đồ thị có trọng số cạnh là dương

b)

Thuật toán FordBellman làm việc được với cả đồ thị có hướng và vô hướng

c)

Không phát biểu nào sai

d)

Thuật toán FordBellman tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại

28.

Phát biểu nào sau đây là đúng

a)

1 → 9 → 6 → 2 → 3 là đường đi trên G

b)

Đồ thị không có lá

c)

Tất cả các phát biểu đều đúng

d)

1 → 9 → 4 → 8 → 1 là chu trình trên G

29.

Cây bên phải hình miêu tả quá trình duyệt đồ thị bằng tìm kiếm sâu đệ quy. Hãy điền vào những vị trí đã bị che

a)

A = 2; B = 3

b)

A = 2; B = 5

c)

A = 1; B = 4

d)

A = 1; B = 5

30.

Thứ tự duyệt các đỉnh khi duyệt đồ thị bằng thuật toán tìm kiếm sâu là gì?

a)

a.1 → 8 → 6 → 2 → 7 → 9

b)

b.

1 → 8 → 9 → 2 → 7 → 6

c)

c.

1 → 8 → 6 → 7 → 2 → 9

d)

d.

1 → 8 → 9 → 6 → 7 → 2

31.

Cho ma trận ở bên trái và bốn đồ thị G6a, G6b, G6c, G6d ở bên phải hình sau:

Ma trận là ma trận kề của đồ thị nào?

a)

G6c

b)

G6d

c)

G6a

d)

G6b

32.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim. Hãy điền vào những vị trí đã bị che.

a)

A = 1; B = 2; C = 7; D = 2

b)

A = ∞; B = 2; C = 5; D = 1

c)

A = 1; B = 4; C = 5; D = 4

d)

A = ∞; B = 3; C = 6; D = 3

33.

Vùng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị bằng thuật toán FordBellman. Hãy điền vào những vị trí đã bị che.

a)

A = 6; B = 1; C = 3; D = 4

b)

A = 4; B = 3; C = 2; D = 2

c)

A = 6; B = 1; C = 3; D = 3

d)

A = 2; B = 2; C = 2; D = 5

34.

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

a)

Không phát biểu nào đúng

b)

6 → 9 → 8 → 4 → 9 → 6 là chu trình

c)

2 → 6 → 4 → 9 → 7 là đường đi đơn

d)

1 → 9 → 4 → 6 → 9 → 1 là đường đi đơn

35.

Bảng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại của đồ thị bằng thuật toán Dijkstra. Hãy điền vào những vị trí đã bị che.

a)

A = 5

b)

A = 9

c)

A = 6

d)

.A = 1

36.

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

a)

Tất cả các cạnh của cây đều là cầu

b)

Cây có n đỉnh thì có n cạnh

c)

Tất cả các đỉnh của cây đều là lá

d)

Trên cây có một và chỉ một đỉnh rẽ nhánh

37.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal. Hãy điền vào những vị trí đã bị che.

a)

A = 4; B = 6

b)

A = 3; B = 4

c)

A = 2; B = 4

d)

A = 5; B = 6

38.

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

a)

Thuật toán Floyd tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại

b)

Không phát biểu nào đúng

c)

Thuật toán Floyd tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh

d)

Thuật toán Floyd tìm đường đi ngắn nhất từ các đỉnh đến 1 đỉnh

39.

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

a)

1 → 9 → 4 → 3 → 1 là chu trình trên G

b)

1 → 9 → 3 → 2 → 7 là đường đi trên G

c)

Tất cả các phát biểu đều sai

d)

Đồ thị có lá

40.

Bảng bên phải của hình mô tả một phần quá trình tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng thuật toán Floyd. Hãy điền vào những vị trí đã bị che

a)

A = 6; B = 1

b)

A = 5; B = 9

c)

A = 6; B = 3

d)

A = 5; B = 6

41.

Thứ tự duyệt các đỉnh khi duyệt đồ thị bằng thuật toán tìm kiếm rộng là gì?

a)

1 → 8 → 9 → 6 → 7 → 2

b)

1 → 8 → 6 → 2 → 7 → 9

c)

1 → 8 → 9 → 2 → 7 → 6

d)

1 → 8 → 6 → 9 → 7 → 2

42.

Bảng bên phải của hình mô tả một phần quá trình tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng thuật toán Floyd. Hãy điền vào những vị trí đã bị che

a)

A = 9

b)

A = ∞

c)

A = 5

d)

A = 6

43.

Bảng bên phải của hình mô tả quá trình tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại của đồ thị bằng thuật toán Dijkstra. Hãy điền vào những vị trí đã bị che.

a)

A = 6; B = 5

b)

A = 5; B = 6

c)

A = 2; B = 5

d)

A = 9; B = 6

44.

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

a)

Đồ thị là nửa Euler vì không có chu trình Euler

b)

Đồ thị là nửa Euler vì có đường đi Euler

c)

Đồ thị không là Euler hay nửa Euler vì có 4 đỉnh bậc lẻ

d)

Đồ thị là Euler vì có chu trình Euler

45.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim. Hãy điền vào những vị trí đã bị che.

a)

A = 5; B = 3

b)

A = 3; B = 2

c)

A = 4; B = 3

d)

A = 6; B = 2

46.

Phát biểu nào sau đây là đúng

a)

Đỉnh 5 kề với đỉnh 6

b)

Đỉnh 9 kề với đỉnh 2

c)

Đỉnh 4 liên thông với đỉnh 8

d)

Đỉnh 1 liên thông với đỉnh 3

47.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim. Hãy điền vào những vị trí đã bị che.

a)

A = 2; B = 4

b)

A = 1; B = 2

c)

A = 1; B = 3

d)

A = 2; B = 3

48.

Thứ tự duyệt các đỉnh khi duyệt đồ thị bằng thuật toán tìm kiếm rộng là gì?

a)

1 → 4 → 5 → 6 → 2 → 3 → 7

b)

1 → 5 → 6 → 2 → 7 → 4 → 3

c)

1 → 4 → 3 → 2 → 7 → 5 → 6

d)

1 → 4 → 5 → 6 → 3 → 2 → 7

49.

Ma trận là ma trận kề của đồ thị nào?

a)

G7d

b)

G7a

c)

G7b

d)

G7c

50.

Thứ tự các đỉnh khi duyệt đồ thị bằng thuật toán tìm kiếm sâu là gì?

a)

1 → 2 → 5 → 4 → 6

b)

1 → 2 → 4 → 6 → 5

c)

1 → 2 → 4 → 5 → 6

d)

1 → 4 → 2 → 5 → 6

51.

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

a)

Thuật toán FordBellman chỉ làm việc được với đồ thị có trọng số cạnh là âm

b)

Thuật toán FordBellman chỉ làm việc được với đồ thị có trọng số cạnh là dương

c)

Thuật toán FordBellman làm việc được với cả đồ thị có chu trình âm

d)

Thuật toán FordBellman tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại

52.

Đây là ai

a)

lớp trưởng

b)

Badboy

c)

Không biết

d)

Người ngoài trái đất

53.

Bảng bên phải của hình mô tả quá trình tìm tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal. Hãy điền vào những vị trí đã bị che.

a)

a.

A = 8; B = 2

b)

A = 5; B = 3

c)

A = 1; B = 2

d)

A = 1; B = 3

Toán rời rạc (module 2)

Total questions: 53

Worksheet time: 27mins

Similar Resources on Wayground