Unit-4 Data Structures Important Questions with the solution – AKTU

This is Btech, MCA, and BCA’s common subject, “data structures.” Providing Unit-4 Data Structures Important Questions with the solution – AKTU, Last year’s question paper with solutions, and many more study materials that will help students or bachelor’s exam

Dudes 🤔.. You want more useful details regarding this subject. Please keep in mind this as well.

Important Questions For Data Structures: 
*Unit-01     *Unit-02    
*Unit-03    *Unit-04 
*Unit-05    *Short-Q/Ans
*Question-Paper with solution 21-22 

Q1. Write a DFS algorithm to traverse a graph. Apply the same algorithm for the graph given in Fig. 1 by considering node 1 as starting node.

Ans. Depth First Search (DFS): The general idea behind a depth first search beginning at a starting node A is as follows:

a. First, we examine the starting node A.

b. Then, we examine each node along a path P which begins at A; that is, we process neighbour of A, then a neighbour of neighbour of A, and so on.

c.This algorithm uses a stack instead of queue.

Q2. Illustrate the importance of various traversing techniques in graphs along with their applications.

Ans. Various types of traversing techniques are:

1. Breadth First Search (BFS)                              2. Depth First Search (DFS)

Importance of BFS:

• 1. It is one of the single source shortest path algorithms, so it is used to compute the shortest path.
• 2. It is also used to solve puzzles such as the Rubik’s Cube.
• 3. BFS is not only the quickest way of solving the Rubik’s Cube, but also the most optimal way of solving it.

Application of BFS: Breadth first search can be used to solve many problems in graph theory, for example:

• 1. Copying garbage collection.
• 2. Finding the shortest path between two nodes u and u, with path length measured by number of edges (an advantage over depth first search).
• 3. Ford-Fulkerson method for computing the maximum flow in a flow network.
• 4. Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
• 5. Construction of the failure function of the Aho-Corasick pattern matcher.
• 6. Testing bipartiteness of a graph.

Importance of DFS: DFS is very important algorithm as based upon DFS, there are O(V + E)-time algorithms for the following problems

• 1. Testing whether graph is connected.
• 2. Computing a spanning forest of G.
• 3. Computing the connected components of G.
• 4. Computing a path between two vertices of G or reporting that no such path exists.
• 5. Computing a cycle in G or reporting that no such cycle exists.

Application of DFS: Algorithms that use depth first search as a building block include:

• 1. Finding connected components.
• 2. Topological sorting.
• 3. Finding 2-(edge or vertex)-connected components.
• 4. Finding 3-(edge or vertex)-connected components.
• 5. Finding the bridges of a graph.
• 6. Generating words in order to plot the limit set of a group.
• 7. Finding strongly connected components.

Q3. Define spanning tree. Also, construct a minimum spanning tree using Prim’s algorithm for the given graph.

Ans. Spanning tree:

• 1. A spanning tree of an undirected graph is a sub-graph that is a tree which contains all the vertices of graph.
• 2. A spanning tree ofa connected graph G contains all the vertices and has the edges which connect all the vertices. So, the number of edges will be 1 less than the number of nodes.
• 3. If graph is not connected, i.e., a graph with n vertices has edges less than n-1 then no spanning tree is possible.
• 4. A connected graph may have more than one spanning trees.

Q4. Consider the following undirected graph.

a. Find the adjacency list representation of the graph.

b. Find a minimum cost-spanning tree by Kruskal’s algorithm.

Ans. 

Q5. Write the Floyd Warshall algorithm to compute the all pair shortest path. Apply the algorithm on following graph:

    Ans.                                 

Q6. Find out the shortest path from node 1 to node 4 in a given graph (fig. ) using Dijkstra shortest path algorithm.

Ans. 

Cracking AKTU B.Tech: Quantum Data Structures – Last Year’s Short Questions Paper

AKTU Important Links | Btech Syllabus

Important Links-Btech (AKTU)| Data Structures Syllabus