FUNDAMENTALS OF ALGORITHMS - UNIT 2 MCQS

What is a binary tree and how is it structured?

• A binary tree is a hierarchical data structure where each node has at most two children.

• A binary tree is a flat data structure with no hierarchical relationships.

• A binary tree can have any number of children for each node.

• A binary tree is a linear data structure with nodes connected in a single line.

Explain the difference between a binary tree and a threaded binary tree.

• A binary tree is used for sorting data, whereas a threaded binary tree is used for searching data.

• A binary tree has nodes with at most two children, while a threaded binary tree uses null pointers to link to in-order predecessors and successors.

• A binary tree stores data in a linear fashion, while a threaded binary tree stores data in a circular manner.

• A binary tree can have any number of children, while a threaded binary tree has a fixed number of children.

What are the different types of tree traversal methods?

• Depth-First (Pre-order, In-order, Post-order) and Breadth-First

• Sequential and Recursive Traversal

• Level-Order and Random-Order

• Circular and Linear Traversal

Describe the in-order traversal of a binary tree.

• The in-order traversal visits nodes in random order.

• In-order traversal only visits leaf nodes of the tree.

• The in-order traversal of a binary tree results in visiting nodes in non-decreasing order.

• The in-order traversal of a binary tree results in a descending order.

How do you represent a binary tree in an array?

• Use an array where the root is at index 0, left child at 2i + 1, and right child at 2i + 2.

• Use an array where the root is at index 1, left child at 2i, and right child at 2i + 1.

• Represent the binary tree using a matrix format with rows for each level.

• Store the binary tree as a linked list instead of an array.

What is a graph and how can it be represented?

• A graph is a collection of vertices connected by edges, and it can be represented using adjacency lists, adjacency matrices, or edge lists.

• A graph is a type of chart used for data visualization.

• A graph consists of only edges without any vertices.

• A graph can only be represented as a pie chart.

Define connected components in a graph.

• A connected component is any subset of vertices in a graph.

• A connected component is a single vertex with no edges.

• A connected component is a set of vertices that are all isolated from each other.

• A connected component in a graph is a maximal set of vertices such that there is a path between any two vertices in the set.

What is a spanning tree and how is it formed?

• A spanning tree is a subgraph that connects only some vertices of a graph.

• A spanning tree is a subgraph that connects all vertices of a graph without cycles.

• A spanning tree is a complete graph with all edges.

• A spanning tree is a graph that contains cycles.

Explain Dijkstra's algorithm for finding the shortest path.

• Dijkstra's algorithm is a method for finding the average weight of edges in a graph.

• Dijkstra's algorithm is a method for finding the shortest path in a weighted graph.

• Dijkstra's algorithm finds the longest path in a graph.

• Dijkstra's algorithm is used for sorting data in a list.

What is transitive closure in the context of graphs?

• Transitive closure only applies to directed graphs without cycles.

• The transitive closure is the shortest path between all pairs of vertices.

• The transitive closure is a method for finding the minimum spanning tree of a graph.

• The transitive closure of a graph is a graph that contains an edge from vertex A to vertex B if there is a path from A to B in the original graph.