Data Structures & Algorithms (DSA) SPPU Endsem Question Paper May 2024

Questions

1. Q1

   1. a)

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

      [6]
   2. b)

      Clearly indicate the content of stack during conversion of given infix expression to prefix. A^B*C–D+E/F/(G+H)

      [6]
   3. c)

      Write a C++ pseudocode algorithm for the following operation of simple queue using linked representation. i) enqueue () ii) dequeue() iii) print_Queue() 2

      [6]
   OR

2. Q2

   1. a)

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

      [6]
   2. b)

      Consider the following circular queue of characters of size 6. “_” denotes an empty queue location. Initial queue configuration is Front = 1, Rear = 3 and having letters as shown below. i) F is added to the queue ii) Two letters are deleted iii) K, L, M are added to the queue iv) R is added to the queue v) Two letters are deleted vi) S is added to the queue vii) Two letters are deleted Show the queue content of queue with Front and Rear as the above options take place.

      [6]
   3. c)

      What is double ended queue? Mention Types of double ended queue. Explain enqueue and dequeue operations of double ended queue.

      [6]

3. Q3

   1. a)

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

      [6]
   2. b)

      Write the C++ pseudocode algorithm for creating expression tree from postfix expression.

      [6]
   3. c)

      Construct an inorder threaded binary search tree for the following set of elements. 100, 50, 200, 300, 20, 150, 70, 180, 120, 30 Show all steps.

      [5]
   OR

4. Q4

   1. a)

      Write C++ pseudocode algorithm for preorder traversal of threaded binary tree.

      [6]
   2. b)

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

      [6]
   3. c)

      Explain the following terms with respect to tree. i) Root ii) Leaf node iii) Siblings iv) Degree of a node v) Degree of tree

      [5]

5. Q5

   1. a)

      Find the minimum spanning tree using Prim’s algorithm for the following graph.

      [6]
   2. b)

      Obtain an AVL tree by inserting one data element at a time in the following sequence: 50, 55, 60, 15, 10, 40, 20, 45, 30, 70, 80. Label the rotations appropriately at each stage

      [7]
   3. c)

      Write short note on OBST

      [5]
   OR

6. Q6

   1. a)

      Write an application of Topological sorting with suitable example.

      [6]
   2. b)

      For a given tree, Identify whether it is AVL tree or not? If it is not an AVL tree, convert it into balanced AVL tree. After conversion, insert node 15 in the tree. Delete node 20 from the tree. After insertion and deletion operation, if the tree is imbalanced, make it balanced AVL tree. 4

      [7]
   3. c)

      Construct Heap to Sort given values in ascending order using MAXheap sort, 5, 3, 17, 10, 84, 19, 22. (Note : Make a use of Heapify)

      [5]

7. Q7

   1. a)

      Differentiate between sequential file and direct access file.

      Also asked:Dec 2025 ·May 2025

      [6]
   2. b)

      Write a pseudo code to perform the following operations on Sequential file : i) Insert record ii) Delete record

      [6]
   3. c)

      What are the characteristics of good hash function? List different techniques to resolve collision in hash table and explain any one with suitable example.

      [5]
   OR

8. Q8

   1. a)

      Explain the Index sequential file organization with advantages and disadvantage.

      [6]
   2. b)

      Explain Linear probing with and without replacement with suitable examples.

      [6]
   3. c)

      What is File? Differentiate between text file and binary file. … … …

      [5]