Free Practice Quiz Question List

10 Trees and Graph Algorithms Online Quiz Questions

Use this free practice quiz with 20 questions to review 10 Trees and Graph Algorithms, test your knowledge, and prepare for your next test or exam.

20 questions

Choose one

1 point

Which statement correctly describes an adjacency matrix for a graph?

A
It uses O(|V|+|E|) space and tests an edge in O(|V|) time.
B
It uses O(|V|^2) space and tests whether a specified edge exists in O(1) time.
C
It uses O(|E|) space and tests an edge in O(|E|) time.
D
It uses O(|V|) space and tests an edge in O(log |V|) time.

True or false

1 point

Adding any new edge to a tree creates exactly one cycle.

A
True
B
False

Written response

1 point

What is the term for the vertex immediately next to a given vertex on the path toward the root?

Fill in the blank

1 point

Breadth-first search uses a to process vertices in level order.

Choose one

1 point

Which description best defines a spanning tree of a connected graph?

A
A subgraph containing only vertices of odd degree
B
A subgraph containing every vertex and forming a tree
C
A subgraph containing every edge of the original graph
D
A cycle with minimum total edge weight

Choose all

1 point

A rooted tree has root r with children a and b; a has children c and d; b has child e. Select all statements that are true.

A
c and d are siblings.
B
e is a child of b.
C
a and b are siblings of c.
D
r is an ancestor of c.

Written response

1 point

In a rooted tree, r is the root; r has children a and b; a has children c and d; and b has child e. What is the height of the tree?

Choose one

1 point

Which action is characteristic of Kruskal's minimum-spanning-tree algorithm?

A
It repeatedly chooses the vertex with the greatest degree.
B
It starts from one vertex and always expands through that vertex's cheapest incident edge.
C
It sorts edges by increasing weight and adds an edge when it connects different components.
D
It performs BFS and records the first edge used to reach each vertex.

True or false

1 point

A directed cycle prevents a topological ordering from existing.

A
True
B
False

Choose all

1 point

Which of the following are applications of decision trees? Select all correct choices.

A
Classification
B
Diagnosis
C
Game strategies
D
Program control flow

Open ended

1 point

Explain the main operational difference between breadth-first search and depth-first search. Include the usual adjacency-list running time of each and one task for which either method is especially suitable.

Choose one

1 point

Which test correctly determines whether a connected undirected graph with $n$ vertices is a tree?

A
Check only whether every vertex has degree at most two.
B
Check whether the graph has at least n edges.
C
Check that the graph is connected, has n-1 edges, and contains no cycle.
D
Check whether a BFS visits vertices in alphabetical order.

Choose one

1 point

Which condition defines a binary tree?

A
Every vertex has exactly two children.
B
Every vertex has at most two children.
C
Every leaf has exactly two parents.
D
All vertices must lie at the same depth.

Choose one

1 point

An undirected graph is known to be a tree with 9 vertices. How many edges must it have?

A
7
B
8
C
9
D
10

True or false

1 point

In an unweighted graph, breadth-first search can find a shortest path from a source vertex to every reachable vertex.

A
True
B
False

Written response

1 point

Which minimum-spanning-tree algorithm sorts all edges by increasing weight and adds an edge whenever it joins two previously disconnected components?

Choose one

1 point

For a graph with vertices $A,B,C,D$ and edges $AB, AC, BC, BD, CD$ , which edge set is a spanning tree?

A
$AB, AC, BC$
B
$AB, BC, CA, AD$
C
$AB, AC, BD, CD$
D
$AB, AC, BC, BD, CD$

Choose one

1 point

In a rooted tree, $r$ is the root, $b$ is a child of $r$ , and $e$ is a child of $b$ . What is the depth of $e$ ?

Written response

1 point

An unweighted graph has edges $s\mathord{-}a$ , $s\mathord{-}b$ , $a\mathord{-}c$ , $b\mathord{-}d$ , $c\mathord{-}x$ , and $d\mathord{-}x$ . What shortest-path distance does BFS assign from $s$ to $x$ , measured in edges?

Fill in the blank

1 point

During depth-first search of an undirected graph, encountering an already visited neighbor that is not the current vertex's indicates that the graph contains a cycle.