Exploring Trees and Graphs Quiz

What is the height of a binary tree with 15 nodes in the best-case scenario?

• 3

• 4

• 5

• 6

Answer explanation

In a balanced binary tree, the height is minimized. For 15 nodes, the best-case height is 4, as a complete binary tree with 15 nodes has 4 levels (2^4 - 1 = 15). Thus, the correct answer is 4.

Which of the following is a characteristic of a complete binary tree?

• All levels are completely filled except possibly the last, which is filled from left to right.

• All nodes have two children.

• All leaf nodes are at the same level.

• It is a binary search tree.

Answer explanation

A complete binary tree is defined by having all levels fully filled except possibly the last, which must be filled from left to right. This distinguishes it from other types of binary trees, making the first choice correct.

In a graph, what is the term used to describe a path that starts and ends at the same vertex without repeating any edges?

• Cycle

• Circuit

• Loop

• Walk

Answer explanation

A circuit is a path in a graph that starts and ends at the same vertex without repeating any edges. While a cycle also starts and ends at the same vertex, it can repeat vertices, making 'circuit' the correct term for this definition.

Which data structure is used to implement a breadth-first search (BFS) on a graph?

• Stack

• Queue

• Priority Queue

• Linked List

Answer explanation

A breadth-first search (BFS) uses a queue to explore nodes level by level. Nodes are enqueued as they are discovered and dequeued for exploration, ensuring that all nodes at the current depth are processed before moving deeper.

What is the time complexity of searching for an element in a balanced binary search tree (BST)?

Answer explanation

In a balanced binary search tree (BST), the height is logarithmic relative to the number of nodes, allowing search operations to be performed in O(log n) time. This makes O(log n) the correct choice for search time complexity.

Which of the following is true for a tree data structure?

• It can have cycles.

• It is a type of graph.

• It must be a binary tree.

• It has no root node.

Answer explanation

A tree is a type of graph characterized by its acyclic nature and hierarchical structure. It does not have cycles, can have various forms (not just binary), and must have a root node.

In a directed graph, what is the term for a vertex with no incoming edges?

• Sink

• Source

• Isolated

• Terminal

Answer explanation

In a directed graph, a vertex with no incoming edges is called a 'Source'. It can send edges to other vertices but does not receive any. A 'Sink' is the opposite, having no outgoing edges.

Which traversal method visits the root node first, then the left subtree, and finally the right subtree?

• In-order

• Pre-order

• Post-order

• Level-order

Answer explanation

The pre-order traversal method visits the root node first, followed by the left subtree and then the right subtree. This is why the correct answer is 'Pre-order'.

Answer explanation

In a connected graph with n vertices, the minimum number of edges required to keep all vertices connected is n-1. This forms a tree structure, which is the simplest connected graph.

Which of the following algorithms is used to find the shortest path in a weighted graph?

• Depth-first search

• Breadth-first search

• Dijkstra's algorithm

• Kruskal's algorithm

Answer explanation

Dijkstra's algorithm is specifically designed to find the shortest path in a weighted graph, making it the correct choice. In contrast, depth-first and breadth-first search do not account for weights, and Kruskal's algorithm is used for minimum spanning trees.