Data Structures & Algorithms (DSA) SPPU Endsem Question Paper Nov 2025

Questions

1. Q1

   1. a)

      Represent the following graphs using adjacency matrix.

      [6]
   2. b)

      Explain Floyd Warshall algorithm to calculate shortest paths.

      [6]
   3. c)

      Construct the minimal spanning tree for the graph shown below using Kruskal's algorithm. 2

      [6]
   OR

2. Q2

   1. a)

      Find the MST for the following graph using Prims algorithm.

      Also asked:May 2025

      [6]
   2. b)

      Explain Depth first traversal of a graph with example.

      [6]
   3. c)

      Find Single source shortest path using Dijkstra's Algorithm. Select source as vertex 1.

      [6]

3. Q3

   1. a)

      What is K-D tree? Show creation of 2-D tree with example.

      [6]
   2. b)

      Consider following : Input: keys[] = {10, 12, 20}, freq[] = {34, 8, 50} Draw all possible BSTs. Find minimum cost of the BST.

      [6]
   3. c)

      Do the following operations on the tree : i) Zig Zag Rotation ii) Zag Zig Rotation

      [6]
   OR

4. Q4

   1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]
   2. b)

      Define Red- Black tree, state its properties and give suitable example.

      Also asked:May 2025

      [6]
   3. c)

      i) Illustrate AA tree. ii) Define splay tree. List the operations and rotations that can be performed on splay tree. 3

      [6]

5. Q5

   1. a)

      Explain the various cases of node deletion in B- tree.

      [6]
   2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]
   3. c)

      Explain indexing and types of indexing techniques.

      [5]
   OR

6. Q6

   1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]
   2. b)

      Answer the following questions w.r.t. trie tree: i) Which of the following is not true?

      [6]
   3. a)

      Trie requires less storage space than hashing

   4. b)

      Trie allows listing of all the words with same prefix

   5. c)

      Tries are collision free

   6. d)

      Trie is also known as prefix tree ii) What can be the maximum depth of the trie with n strings and m as the maximum sting the length?

   7. a)

      log2n b) log2m

   8. c)

      n d) m iii) Which of the following is true about the trie?

   9. a)

      root is letter a

   10. b)

       path from root to the leaf yields the string

   11. c)

       children of nodes are randomly ordered

   12. d)

       each node stores the associated keys iv) Auto complete and spell checkers can be implemented efficiently using the trie.

   13. a)

       True b) False v) What traversal over trie gives the lexicographical sorting of the set of the strings?

   14. a)

       postorder b) preorders

   15. c)

       inorder d) level order 4 vi) What is/are the key feature(s) of trie tree?

   16. a)

       Fast String Operations b) Efficient Prefix Searches

   17. c)

       Memory Compactness d) All of the above

   18. c)

       What are multiway search trees? Explain its need and applications.

       [5]

7. Q7

   1. a)

      Differentiate between sequential & linked organization.

      [6]
   2. b)

      What is indexed sequential access file organization? Write two advantages & disadvantages of it.

      Also asked:May 2025 ·May 2024

      [6]
   3. c)

      What is Direct access file? State its advantages.

      [5]
   OR

8. Q8

   1. a)

      Differentiate between dense & sparse indices.

      [6]
   2. b)

      Explain Sequential file organization and discuss their advantages and disadvantages.

      Also asked:May 2025 ·May 2024

      [6]
   3. c)

      This part has equations that don’t show as text. Open the PDF to read it.

      [5]