All Question paper with solution mean

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.

DFS algorithm in data structures -Btech aktu

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.

stack in data structures -Btech aktu

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.

spanning tree in data structures -Btech aktu

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.
spanning trees in data structures -Btech aktu
spanning trees example in data structures -Btech aktu

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.


kruskal's algorithm in data structures -Btech aktu
kruskal's algorithm in data structures -Btech aktu

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


washall algorithm in data structures -Btech aktu
washall algorithm in data structures -Btech aktu

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

Dijkstra shortest path algorithm in data structures and algorithm


Dijkstra shortest path algorithm
Important Questions | Short Questions Series | Quantum-data structures | last year's question paper -B.Tech AKTU

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

Important QuestionQuestion Links
Data Structure – Unit-1UNIT-1
Data Structure – Unit-2UNIT-2
Data Structure – Unit-3UNIT-3
Data Structure – Unit-4UNIT-4
Data Structure – Unit-5Unit-5
Important Short Questions- Data StructureShort Question List
Last Year’s Question PaperExam 2021-22
Quantum -Data structureQuantum

AKTU Important Links | Btech Syllabus

Link NameLinks
Btech AKTU CircularsLinks
Btech AKTU SyllabusLinks
Btech AKTU Student DashboardStudent Dashboard
AKTU RESULT (One VIew)Student Result

Important Links-Btech (AKTU)| Data Structures Syllabus

Btech InformationInfo Link
Data Structure SyllabusSyllabus-DS

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

Leave a Comment