Toán rời rạc - Chương 5: cây

Một cây có 15 đỉnh thì có bao nhiêu cạnh?

A. \(15\)

B. \(14\)

C. \(16\)

D. \(30\)

Một cây có ít nhất 2 đỉnh luôn có ít nhất bao nhiêu lá?

A. \(0\)

B. \(1\)

C. \(2\)

D. \(3\)

Mô tả nào đúng về một cây vô hướng?

A. liên thông và không có chu trình

B. không liên thông và không có chu trình

C. liên thông và mọi đỉnh bậc chẵn

D. đầy đủ và hai phía

Thêm một cạnh nối hai đỉnh chưa kề nhau của một cây sẽ

A. vẫn cho một cây

B. làm đồ thị mất liên thông

C. tạo hai chu trình

D. tạo đúng một chu trình

Xóa một cạnh bất kỳ khỏi một cây có ít nhất hai đỉnh sẽ

A. làm đồ thị mất liên thông

B. tạo một chu trình

C. không thay đổi số thành phần liên thông

D. tạo đồ thị đầy đủ

Một rừng có 20 đỉnh và 4 thành phần liên thông. Số cạnh của rừng là

A. \(20\)

B. \(16\)

C. \(19\)

D. \(24\)

Một cây \(m\)-phân đầy đủ có \(i\) đỉnh trong. Số lá bằng

A. \(mi\)

B. \(i+m\)

C. \(mi+1\)

D. \((m-1)i+1\)

Một cây nhị phân đầy đủ có 10 đỉnh trong. Số lá là

A. \(10\)

B. \(20\)

C. \(11\)

D. \(21\)

Một cây nhị phân hoàn hảo có chiều cao 4 (gốc ở mức 0). Tổng số đỉnh là

A. \(15\)

B. \(16\)

C. \(31\)

D. \(32\)

Một cây khung của đồ thị 12 đỉnh có bao nhiêu cạnh?

A. \(12\)

B. phụ thuộc vào đồ thị

C. \(10\)

D. \(11\)

Số cây gắn nhãn trên 5 đỉnh là

A. \(25\)

B. \(125\)

C. \(120\)

D. \(625\)

Dãy Prüfer của một cây gắn nhãn 9 đỉnh có độ dài

A. \(7\)

B. \(8\)

C. \(9\)

D. \(6\)

Trong dãy Prüfer của một cây gắn nhãn, một nhãn xuất hiện 3 lần. Bậc của đỉnh mang nhãn đó là

A. \(4\)

B. \(3\)

C. \(2\)

D. \(5\)

Có bao nhiêu cây gắn nhãn trên \(\{1,2,3,4,5\}\) có dãy bậc \((3,2,1,1,1)\) theo đúng thứ tự nhãn?

A. \(6\)

B. \(12\)

C. \(3\)

D. \(1\)

Nếu mọi trọng số cạnh của một đồ thị liên thông đều phân biệt thì cây khung nhỏ nhất

A. không tồn tại

B. có ít nhất hai cây

C. chứa mọi cạnh

D. là duy nhất

Trong thuật toán Kruskal, ở mỗi bước ta chọn

A. cạnh nặng nhất chưa xét

B. cạnh nhẹ nhất chưa xét mà không tạo chu trình

C. đỉnh có bậc nhỏ nhất

D. mọi cạnh kề gốc

Trong một cây có gốc, mỗi đỉnh khác gốc có

A. không có cha

B. đúng một cha

C. ít nhất hai cha

D. cùng cha với gốc

Trong phép duyệt tiền thứ tự một cây có gốc, một đỉnh luôn được thăm

A. sau mọi hậu duệ

B. chỉ khi là lá

C. cùng lúc với cha

D. trước mọi hậu duệ của nó

Đường kính của một cây là

A. số lá của cây

B. bậc lớn nhất

C. độ dài đường đi đơn dài nhất

D. số cạnh kề gốc

Tập tâm của một cây luôn gồm

A. một đỉnh hoặc hai đỉnh kề nhau

B. đúng ba đỉnh

C. tất cả các lá

D. mọi đỉnh bậc lớn nhất