Q1. Write down any two data structures which are appropriate for representing a graph. Write down an algorithm for the Depth First Traversal of a graph by using one of your two data structures.
Q2. Write down the Dijkstra’s shortest path algorithm to calculate the entire pair shortest path in a weighted directed graph.
Q3. What do you mean by garbage collection and how is it helpful for managing the external fragmentation in main memory? Give an illustration to show that the best fit allocation of memory leads to the external fragmentation.
Q4. How multi-way search tree is distinct from the binary search tree? Write a condition to choose one of the branches from an internal node (or root) of the 3-way search tree based on the possibility of getting the item in the tree, if the item is in the tree. No backtracking must be permitted.