Trees and Graphs: Interactive Learning Quizzes for Computer Science MSc

Question 1

Which of the following is NOT an application of trees?

Accepted Answer

Hashing

Answer

Binary Search Trees

Answer

Huffman Coding

Answer

Database Indexing

Question 2

What is the minimum number of edges that a connected graph with n vertices must have?

Accepted Answer

n - 1

Answer

n

Answer

n + 1

Answer

2n

Question 3

What is the purpose of a spanning tree in a graph?

Accepted Answer

To connect all the nodes in the graph with the minimum possible number of edges.

Answer

To find the shortest path between two nodes in the graph.

Answer

To determine if the graph is connected or not.

Answer

To represent a network of computers.

Question 4

What is the time complexity of the Depth-First Search (DFS) algorithm for a graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

O(V)

Answer

O(E)

Answer

O(V^2)

Question 5

Which data structure is commonly used for efficient implementation of a priority queue?

Accepted Answer

Binary heap

Answer

Binary search tree

Answer

Linked list

Answer

Stack

Question 6

What is the longest path between any two nodes in a tree called?

Accepted Answer

Diameter

Answer

Shortest path

Answer

Radius

Answer

Height

Question 7

What is the key difference between a graph and a tree?

Accepted Answer

Graphs can have cycles, while trees cannot.

Answer

Trees can have cycles, while graphs cannot.

Answer

Graphs are always connected, while trees may not be.

Answer

Trees are always connected, while graphs may not be.

Question 8

What is the maximum height of a complete binary tree with n nodes?

Accepted Answer

log(n) + 1

Answer

log(n)

Answer

n

Answer

n^2

Question 9

A property that distinguishes trees from graphs is:

Accepted Answer

A node can have at most one parent.

Answer

There are no cycles in the structure.

Answer

All nodes are connected to the root.

Answer

Edges are uni-directional.

Question 10

In a complete graph with 'n' nodes, the maximum edge count is:

Accepted Answer

n * (n+1) / 2

Answer

n-1

Answer

n * (n-1)

Answer

2n-1

Question 11

To visit nodes in the sequence root, left subtree, right subtree, which traversal method is used?

Accepted Answer

Pre-order

Answer

In-order

Answer

Post-order

Answer

Breadth-first search

Question 12

For finding the shortest path between nodes in a weighted graph, which algorithm is suitable?

Accepted Answer

Dijkstra's algorithm

Answer

Depth-first search

Answer

Breadth-first search

Answer

Prim's algorithm

Question 13

Kruskal's algorithm, used for finding minimum spanning trees, has a time complexity of:

Accepted Answer

O(n log n)

Answer

O(n^2)

Answer

O(n^3)

Answer

O(2^n)

Question 14

For a balanced binary search tree, what is the time complexity of searching for an element?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 15

Which algorithm efficiently finds the shortest path between two nodes in a weighted graph?

Accepted Answer

Dijkstra's algorithm

Answer

Depth-first search

Answer

Breadth-first search

Answer

Bellman-Ford algorithm

Question 16

What is the main purpose of a minimum spanning tree?

Accepted Answer

To find the minimum weight set of edges that connects all nodes

Answer

To find the shortest path between all pairs of nodes

Answer

To find the maximum weight path between all pairs of nodes

Answer

To find the maximum weight set of edges that connects all nodes

Question 17

What is the definition of a binary tree?

Accepted Answer

A tree where every node has a maximum of two child nodes

Answer

A tree where every node has a minimum of two child nodes

Answer

A tree where every node has an arbitrary number of child nodes

Answer

A tree where every node has only one child node

Question 18

What is the time complexity of finding the diameter of a tree using a brute-force approach?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(n^3)

Question 19

What is the minimum number of edges required to make a graph with n vertices connected?

Accepted Answer

n-1

Answer

n

Answer

n+1

Answer

n-2

Question 20

What is the Kruskal's algorithm primarily used for?

Accepted Answer

Finding the minimum spanning tree of a weighted graph

Answer

Finding the shortest path between two vertices in a graph

Answer

Detecting cycles in a graph

Answer

Finding the connected components of a graph

Question 21

What is the time complexity of searching for a node in a balanced tree with N nodes?

Accepted Answer

O(log N)

Answer

O(N)

Answer

O(N^2)

Answer

O(1)

Question 22

Which graph traversal algorithm employs a stack to track visited vertices?

Accepted Answer

Depth-first search

Answer

Breadth-first search

Answer

Dijkstra's algorithm

Answer

Bellman-Ford algorithm

Question 23

What is the minimum number of edges needed for a connected graph with N vertices?

Accepted Answer

N-1

Answer

N

Answer

N+1

Answer

2N

Question 24

What is the key distinction between directed and undirected graphs?

Accepted Answer

Directed graphs have edges with arrows indicating direction, while undirected graphs do not.

Answer

Undirected graphs have edges with weights, while directed graphs do not.

Answer

Directed graphs can represent one-way relationships, while undirected graphs cannot.

Answer

Undirected graphs can be converted to directed graphs, but not vice versa.

Question 25

What is the chromatic number of a graph?

Accepted Answer

The minimum number of colors needed to color the vertices without adjacent vertices having the same color.

Answer

The maximum number of edges in the graph.

Answer

The number of vertices in the graph.

Answer

The degree of the most connected vertex in the graph.

Question 26

What is the time complexity of inserting a node into a balanced binary search tree with N nodes?

Accepted Answer

O(log N)

Answer

O(N)

Answer

O(N^2)

Answer

O(1)

Question 27

In the context of solving the traveling salesman problem, how can a minimum spanning tree (MST) be effectively employed?

Accepted Answer

Transform the problem into a minimum spanning tree and identify the minimum weight Hamiltonian cycle within that tree.

Answer

Construct a minimum spanning tree to determine the shortest path between all pairs of vertices.

Answer

Utilize the minimum spanning tree to identify the maximum weight path between all pairs of vertices.

Question 28

What is the key difference between a binary search tree (BST) and a balanced binary search tree (BBST)?

Accepted Answer

A BST enforces the binary search tree property, while a BBST enforces both the binary search tree property and a balance property.

Answer

A BST allows duplicate values, while a BBST does not.

Answer

A BST can be implemented using an array, while a BBST cannot.

Answer

A BBST is always a complete binary tree, while a BST is not.

Question 29

Which method effectively converts a binary tree into a heap?

Accepted Answer

Heapify

Answer

Depth-first search

Answer

Breadth-first search

Answer

Merge sort

Question 30

Which data structure is most commonly used to represent a network of interconnected nodes?

Accepted Answer

Adjacency list

Answer

Binary tree

Answer

Hash table

Answer

Heap

Question 31

Finding the minimum element in a min-heap has a time complexity of:

Accepted Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Question 32

Which of the following is a common application of depth-first search (DFS) in computer science?

Accepted Answer

Finding connected components in a graph

Answer

Storing data in a database

Answer

Creating a binary search tree

Answer

Sorting a list of numbers

Question 33

The fundamental difference between a directed and an undirected graph is that:

Accepted Answer

Directed edges have a defined direction, while undirected edges do not.

Answer

Directed graphs can contain cycles, while undirected graphs cannot.

Answer

Directed graphs have weights associated with edges, while undirected graphs do not.

Question 34

What is the primary purpose of finding a spanning tree of a graph?

Accepted Answer

To find a subset of edges that connects all nodes in a graph with the minimum total weight.

Answer

To represent a network of computers

Answer

To store data in a hierarchical structure

Question 35

Which data structure is commonly used to implement a priority queue?

Accepted Answer

Binary heap

Answer

Stack

Answer

Linked list

Answer

Queue

Question 36

Kruskal's algorithm is primarily used for:

Accepted Answer

Finding the minimum spanning tree of a weighted graph

Answer

Sorting a list of numbers

Answer

Finding the shortest path between two nodes

Question 37

A significant advantage of using a tree data structure is its:

Accepted Answer

Efficient searching and insertion

Answer

Large storage capacity

Answer

Ability to represent complex relationships

Answer

Easy implementation