Graph and Trees Quiz

What is a graph in mathematical terms?

• A sequence of numbers

• A mathematical structure modelling relationships between pairs of objects

• A type of tree with vertices and edges

• A collection of unrelated nodes

Answer explanation

A graph is defined as a mathematical structure that models relationships between pairs of objects, consisting of vertices (nodes) and edges (connections). This makes the second choice the correct answer.

In graph theory, what is an edge also known as?

• Node

• Vertex

• Arc

• Path

Answer explanation

In graph theory, an edge is also known as an arc. It represents a connection between two vertices (or nodes) in a graph, while the terms node and vertex refer to the points themselves, and a path is a sequence of edges.

Which of the following is a characteristic of a weighted graph?

• It has no edges

• It has values labelled on each edge

• It only contains directed edges

• It is always undirected

Answer explanation

A weighted graph is characterized by having values labeled on each edge, which represent weights or costs associated with traversing that edge. This distinguishes it from unweighted graphs, which do not have such values.

What does an adjacency list represent in a graph?

• A matrix showing all possible paths

• A list of all the weights on the graph

• A list of nodes with their adjacent nodes

• A diagrammatic representation of the graph

Answer explanation

An adjacency list represents a graph by listing each node along with its directly connected adjacent nodes. This structure efficiently shows the relationships between nodes, making it the correct choice.

How does a directed graph differ from an undirected graph?

• It has no vertices

• The edges have weights

• The edges have a one-way relationship

• It doesn’t use adjacency lists

Answer explanation

A directed graph has edges that represent one-way relationships, meaning each edge has a direction from one vertex to another. In contrast, an undirected graph has edges that represent two-way relationships.

What is a tree in terms of data structure?

• A graph with multiple cycles

• A connected, undirected graph with no cycles

• A directed graph with multiple roots

• A weighted graph with loops

Answer explanation

A tree is defined as a connected, undirected graph with no cycles, meaning there is exactly one path between any two nodes. This distinguishes it from other graph types, making the correct choice the second option.

In a binary tree, what is the maximum number of children each node can have?

• One

• Two

• Three

• Four

Answer explanation

In a binary tree, each node can have at most two children: a left child and a right child. Therefore, the correct answer is 'Two', as it defines the structure of a binary tree.

What is the role of the root node in a tree?

• It is the leaf node

• It branches off to all other nodes

• It is the last node in the tree

• It forms a cycle with other nodes

Answer explanation

The root node is the topmost node in a tree structure and serves as the starting point. It branches off to all other nodes, making it essential for the tree's hierarchy, unlike leaf nodes, which are at the ends.

Which of the following is a use of graph theory in computing?

• Calculating the shortest path for data transmission

• Displaying images in high resolution

• Compiling programming code

• Enhancing audio signals

Answer explanation

Graph theory is essential in computing for tasks like calculating the shortest path for data transmission, optimizing routes in networks. The other options do not directly relate to graph theory applications.

What is an adjacency matrix?

• A list of all nodes and their paths

• A two-dimensional array showing edges between nodes

• A hierarchical structure with roots and leaves

• A sequence of numbers representing node values

Answer explanation

An adjacency matrix is a two-dimensional array that represents a graph, where each cell indicates whether an edge exists between nodes. This makes "A two-dimensional array showing edges between nodes" the correct choice.