**Table Of Contents**

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*Unit-01 *Unit-02 *Unit-03 *Unit-04 *Unit-05 *Short-Q/Ans *Question-Paper with solution 21-22Data Structures:

## 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. **

**Most Important Question For All Units** **|** **Short Questions Series |**

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

Important Question | Question Links |
---|---|

Data Structure – Unit-1 | UNIT-1 |

Data Structure – Unit-2 | UNIT-2 |

Data Structure – Unit-3 | UNIT-3 |

Data Structure – Unit-4 | UNIT-4 |

Data Structure – Unit-5 | Unit-5 |

Important Short Questions- Data Structure | Short Question List |

Last Year’s Question Paper | Exam 2021-22 |

Quantum -Data structure | Quantum |

## AKTU Important Links | Btech Syllabus

Link Name | Links |
---|---|

Btech AKTU Circulars | Links |

Btech AKTU Syllabus | Links |

Btech AKTU Student Dashboard | Student Dashboard |

AKTU RESULT (One VIew) | Student Result |

## Important Links-Btech (AKTU)| Data Structures Syllabus

Label | Links |
---|---|

Btech Information | Info Link |

Btech CSE | CSE-LINK |

Quantum-Page | Link |

Data Structure Syllabus | Syllabus-DS |

## 4 thoughts on “Unit-4 Data Structures Important Questions with the solution – AKTU”