FUNDAMENTALS OF ALGORITHMS - UNIT II

Which of the following best describes the relationship between trees and graphs?

• Trees are a specific type of graph

• Graphs are a specific type of tree

• Trees and graphs are completely unrelated structures

• Trees and graphs are identical structures

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

• 1

• 2

• 3

• Unlimited

Which traversal method would be most appropriate for evaluating a mathematical expression represented as a binary tree?

• Inorder

• Preorder

• Postorder

• Level-order

What is the primary advantage of using a threaded binary tree over a regular binary tree?

• Reduced memory usage

• Faster insertion of new nodes

• More efficient traversal

• Better balance of the tree structure

When converting a general tree to a binary tree using the left-child right-sibling representation, what does the right child represent?

• The parent node

• The first child of the original node

• The next sibling of the original node

• A duplicate of the original node

In graph theory, what does a vertex with no incoming edges in a directed graph represent?

• A leaf node

• A source

• A sink

• An isolated vertex

Which graph representation would be most space-efficient for a very large, sparse graph?

• Adjacency matrix

• Adjacency list

• Incidence matrix

• Edge list

How does a depth-first search (DFS) differ from a breadth-first search (BFS) in graph traversal?

• DFS uses a queue, while BFS uses a stack

• DFS explores as far as possible along each branch before backtracking

• BFS is only applicable to weighted graphs

• DFS can only be used on directed graphs

In the context of social network analysis, what might a connected component represent?

• A group of mutual friends

• The most influential person in the network

• The shortest path between two users

• The total number of users in the network

Which of the following is NOT a characteristic of a minimum spanning tree?

• It connects all vertices

• It has no cycles

• It has the minimum total edge weight

• It always has exactly one leaf node