Trees

Question 1

is a connected undirected graph with no
simple circuits.

Answer 1

Tree

Question 2

Theorem in Tree

Answer 2

There is a unique simple path between any
two of its nodes

Question 3

A (not-necessarily-connected) undirected graph without simple circuits is called a

Answer 3

forest

Question 4

You can think of it as a set of trees having disjoint sets of nodes.

Answer 4

forest

Question 5

True or False. A graph is a Tree because it is a connected graph with no simple circuits

Answer 5

True

Question 6

A tree is not a tree “because it’s not connected”. In this case it’s called (blank) in which each connected component is a tree.

Answer 6

Forest

Question 7

An undirected graph without simple circuits is called a

Answer 7

Forest

Question 8

is a tree in which one node has
been designated the root.

Answer 8

rooted tree

Question 9

True or False. Every edge is (implicitly or explicitly) directed away from the root

Answer 9

True

Question 10

There is directed edge from u to v. What type of vertex is “u”?

Answer 10

Parent

Question 11

There is directed edge from u to v. What type of vertex is “v”?

Answer 11

Child

Question 12

Vertices with the same parents.

Answer 12

Siblings

Question 13

Vertices in path from the root to vertex v, excluding v itself, including the root.

Answer 13

Ancestors

Question 14

All vertices that have v as ancestors.

Answer 14

Descendants

Question 15

Vertices that have children.

Answer 15

Internal vertices

Question 16

Subgraphs consisting of v and its
descendants and their incident edges.

Answer 16

Subtree

Question 17

is length of unique path from
root to v.

Answer 17

Level

Question 18

Level of root?

Answer 18

0

Question 19

is maximum of vertices levels.

Answer 19

Height

Question 20

the last child of vertices

Answer 20

leaf/leaves

Question 20

A rooted tree is called (blank) if every internal vertex has no more than m children.

Answer 20

m-ary

Question 21

It is called (blank) if every internal vertex has exactly m children.

Answer 21

full m-array

Question 22

A 2-ary tree is called a

Answer 22

binary tree

Question 23

Can use trees to model the following:

Answer 23

• Saturated hydrocarbons
• Organizational structures
• Computer file systems

Question 24

A tree with n vertices has
(blank) edges.

Answer 24

n - 1

Question 25

A full m-ary tree with I internal vertices and L leaves contains:

Answer 25

n(vertices) = m × I + 1
n(vertices) = I + L

Question 26

The full binary (2-ary) tree in the figure has:
Internal vertices I = 6
Leaves L = 7

Answer 26

13 = (2)(6) + 1
or
13 = 6 + 7

Question 27

For a full m-ary tree:
Given n vertices

Answer 27

I(internal vertices) = (n – 1 ) / m
and
L(leaves) = n–I=[(m–1) × n + 1]/m

Question 28

For a full m-ary tree:
Given I internal vertices

Answer 28

n(vertices) = m × I + 1
and
L(leaves) = n – I = (m – 1) × I + 1

Question 29

For a full m-ary tree:
Given L leaves

Answer 29

n(vertices) = (m × L – 1) / (m – 1)
and
I(internal vertices) = n – L = (L – 1) / (m – 1)

Question 30

Properties of Tree

True or False.
The level of a vertex in a rooted tree is the length
of the path from the root to the vertex (level of
the root is 0)

Answer 30

True

Question 31

Properties of Tree

True or False.
The height of the rooted tree is the maximum of
the levels of vertices (length of the longest path
from the root to any vertex)

Answer 31

True

Question 32

if all leaves are at levels h or h - 1 in a rooted m-ary tree, it is called a?

Answer 32

Balanced Tree

Question 33

Searching for items in a list is one of the most
important tasks that arises in computer science.
Our primary goal is to implement a searching
algorithm that finds items efficiently when the
items are totally ordered. This can be
accomplished through the use of a

Answer 33

Binary Search Tree

Question 34

is a binary tree in which each child of a vertex is designated as a right or left child, no vertex has more than one right child or left child, and each vertex is labeled with a key, which is one of the items

Answer 34

Binary Search Tree