IT-303 Data Structures - Dec 2025 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aDefine data structure. Distinguish between linear and non linear data structures and list the various operations that can be performed on data structure.
   How to answer

   • Define data structure as organization of data with operations
   • Distinguish linear vs non-linear with examples
   • List operations: traversing, searching, insertion, deletion, sorting, merging
2. 7 Marks
   bConsider an array $A[1:n]$ Given a position, write an algorithm to insert an element in the Array. If the position is empty, the element is inserted easily. If the position is already occupied the element should be inserted with the minimum number of shifts.
   How to answer

   • Check bounds and position validity for A[1:n]
   • Handle empty position vs shifting elements
   • Shift with minimum moves and insert, update n
   • Give pseudocode and time complexity
3. 7 Marks
   aGive the postfix and prefix forms of the expression.

   1. i)$A + B * (C - D) / (P - R)$
   2. ii)$-A+B-C+D$
   How to answer

   • Apply precedence: *, / over + and parentheses
   • Derive postfix for (i) and prefix for (i)
   • Convert (ii) $-A+B-C+D$ handling unary/binary
   • Show stack-based conversion steps
4. 7 Marks
   bClassify the different types of queues. Illustrate the difference between a queues and linked lists with an example
   How to answer

   • Classify queues: simple, circular, priority, double-ended
   • Define FIFO vs linked list dynamic structure
   • Compare operations, memory, pointers with example
   • Illustrate enqueue/dequeue vs insert/delete in list
5. 7 Marks
   aDescribe about stack ADT in detail. Give an algorithm for push and pop operations on stack using a linked list.
   How to answer

   • Define stack ADT with LIFO operations
   • Specify push, pop, peek, isEmpty, isFull
   • Give linked-list based push/pop algorithm with top pointer
   • Discuss overflow/underflow handling
6. 7 Marks
   bDefine a binary tree. Give an example and What are the applications of binary tree?
   How to answer

   • Define binary tree: max 2 children, terminology
   • Give example diagram with root, left/right subtree
   • List applications: expression trees, BST, heap, Huffman
7. 7 Marks
   aCreate an expression tree for the expression $a*(b+c)+((d+e*f)*g)$.
   How to answer

   • Parse expression $a*(b+c)+((d+e*f)*g)$ by precedence
   • Build subtrees for (b+c), e*f, d+..., *g
   • Combine with * and + at root
8. 7 Marks
   bSimulate the result of inserting 3,1,4,6,2,8,9 into an initially empty AVL Tree.
   How to answer

   • Insert 3,1,4 sequentially with BST rule
   • Insert 6,2,8,9 showing rotations LL, RR, LR, RL
   • Show balance factor updates and final AVL tree
9. 7 Marks
   aIllustrate the steps in the construction of a heap of records with the following key values: 12,33,67,8,7,80,5,23
   How to answer

   • Start with array/complete tree representation
   • Insert keys 12,33,67,8,7,80,5,23 one by one with heapify
   • Show intermediate heap after each insertion
10. 7 Marks
    bConsider the binary search tree given below find the result of in-order, pre-order, and post-order traversals

    

    How to answer

    • Read BST structure from given figure
    • List in-order (sorted), pre-order (root-left-right)
    • List post-order (left-right-root)
11. 7 Marks
    aExplain the working of Dijkstra's algorithm with the help of an example graph.
    How to answer

    • Define shortest path and initialization of distances
    • Iteratively select min-distance unvisited vertex and relax edges
    • Show distance table steps on example graph
12. 7 Marks
    bFormulate the minimum spanning tree for the following graph (Using Prim's Algorithm).

    

    How to answer

    • Start from arbitrary vertex, maintain MST set
    • Repeatedly add minimum-weight edge to non-MST vertex
    • Show edge selection steps and total cost
13. 7 Marks
    aCompare working of binary search and linear search technique with example.
    How to answer

    • Describe linear search sequential scan O(n)
    • Describe binary search divide-and-conquer on sorted array O(log n)
    • Compare with example trace and prerequisites
14. 7 Marks
    bDiscuss the common collision resolution strategies used in closed hashing system.
    How to answer

    • Define collision in closed hashing (open addressing)
    • Explain linear probing, quadratic probing, double hashing
    • Compare clustering, probe sequences with example
15. 7 Marks
    aSort the sequence 96, 31, 27,42,76,61,10,4 using shell sort and radix sort and prepare the required steps.
    How to answer

    • Apply shell sort with decreasing gaps showing passes
    • Apply radix sort digit-wise (units, tens) with buckets
    • Present intermediate arrays and final sorted sequence
16. 7 Marks
    bWrite Short notes on:

    1. i)Polynomial Manipulation
    2. ii)Red Black Tree
    3. iii)Hashing
    How to answer

    • Polynomial manipulation: array/linked representation and operations
    • Red Black Tree: properties, rotations, balancing
    • Hashing: hash functions, collisions, applications