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

  • 1
  • 2
  • 3
  • 4
In a binary tree, each node can have a maximum of two children. This characteristic distinguishes binary trees from other tree structures and allows for efficient search and manipulation.

What is the significance of topological sorting in dependency resolution?

  • It helps in identifying isolated components in the graph.
  • It is used to compute the transitive closure of a graph.
  • It is used to find the maximum flow in a network.
  • It provides a linear order of tasks or events, allowing for systematic resolution of dependencies.
Topological sorting is significant in dependency resolution as it provides a linear order of tasks or events. This order ensures that tasks dependent on others are processed in the correct sequence, helping in the systematic resolution of dependencies.

How does the presence of cycles in a graph affect the possibility of performing topological sorting?

  • Cycles have no impact on topological sorting.
  • Cycles make topological sorting deterministic.
  • Cycles make topological sorting impossible.
  • Cycles make topological sorting more efficient.
The presence of cycles in a graph makes topological sorting impossible. Topological sorting is designed for directed acyclic graphs (DAGs), and cycles introduce ambiguity in the order of nodes, preventing a clear linear ordering of vertices.

You're designing a scheduling application where tasks are added and removed frequently. Would you use a singly linked list or a doubly linked list to implement the task list? Justify your choice.

  • Array
  • Circular linked list
  • Doubly linked list
  • Singly linked list
In this scenario, a doubly linked list would be a better choice. The reason is that tasks are added and removed frequently, and a doubly linked list allows for easy insertion and deletion of elements at both the beginning and end of the list, providing efficient operations for a scheduling application.

The optimal substructure property ensures that the solution to a subproblem can be used to solve the _______ problem.

  • Current
  • Larger
  • Original
  • Smaller
The optimal substructure property ensures that the solution to a subproblem can be used to solve the original, larger problem. It is a key property for dynamic programming algorithms to efficiently solve problems by breaking them down into smaller subproblems.

Consider a scenario where you are tasked with finding the shortest path for a robot to navigate through a maze with obstacles. How would you adapt BFS to handle this situation effectively?

  • Implement A* Algorithm
  • Modify BFS to account for obstacles
  • Use Depth-First Search (DFS)
  • Utilize Dijkstra's Algorithm with a heuristic
Adapting BFS for a maze with obstacles can be done by incorporating a heuristic approach, similar to A* Algorithm. A* considers both the cost to reach a point and an estimate of the remaining distance to the goal. In the context of a maze, this modification helps BFS navigate efficiently around obstacles, making it more effective for pathfinding in complex environments compared to the traditional BFS approach.

Imagine you're sorting a large dataset stored on disk using Quick Sort. How would you mitigate the risk of running out of memory during the sorting process?

  • Employ an external sorting algorithm such as Merge Sort
  • Increase the size of available memory
  • Split the dataset into smaller chunks and sort them individually
  • Use an in-memory caching mechanism to reduce disk I/O operations
When sorting large datasets stored on disk, mitigating the risk of running out of memory involves using an in-memory caching mechanism. This mechanism allows frequently accessed data to be stored in memory, reducing disk I/O operations and minimizing the chance of memory exhaustion.

In the context of LCS, what is a subsequence?

  • A sequence of elements that appear in the same order as in the original sequence but not necessarily consecutively.
  • A sequence of elements with the same value.
  • A subarray where elements are adjacent and in consecutive positions.
  • A subset of elements with the same value.
In the context of LCS, a subsequence is a sequence of elements that appear in the same order as in the original sequence but not necessarily consecutively. It allows for gaps between elements in the subsequence.

Explain the process of radix sort step by step with an example.

  • Applications and use cases of radix sort
  • Pseudocode and implementation details
  • Step-wise explanation
  • Theoretical analysis and proofs
Radix sort involves sorting elements based on individual digits. Starting from the least significant digit (LSD) to the most significant digit (MSD), elements are grouped and rearranged. The process is repeated until all digits are considered, resulting in a sorted array. Pseudocode and implementation details provide a clearer understanding.

You are designing a navigation app that needs to find the shortest route between two locations on a map. Would you choose BFS or DFS for this task? Justify your choice.

  • Both BFS and DFS
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Neither BFS nor DFS
In this scenario, BFS would be the preferable choice. BFS explores neighboring locations first, ensuring that the shortest path is found before moving to more distant locations. It guarantees the shortest route for unweighted graphs, making it suitable for navigation systems. DFS, on the other hand, may find a solution faster in certain cases but does not guarantee the shortest path.