CS-303 Data Structures - Dec 2024 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
   aWrite an algorithm for traversing nodes in a single linked list? Explain with an example.
   How to answer

   • Definition of single linked list node structure (data, next pointer)
   • Step-by-step traversal algorithm using a temporary pointer until NULL
   • Trace example on a linked list with 3-4 sample nodes
   • Time complexity analysis (O(n))
2. 7 Marks
   bDefine data structures. Classify different types of data structures.
   How to answer

   • Definition of Data Structure
   • Broad classification: Primitive vs Non-primitive
   • Non-primitive: Linear (Arrays, Stacks, Queues, Linked Lists) vs Non-linear (Trees, Graphs)
   • Classification hierarchy diagram
3. 7 Marks
   aCompare and contrast the characteristics of arrays and linked lists as abstract data types.
   How to answer

   • Definition of arrays and linked lists as ADTs
   • Comparison table based on memory allocation (static vs dynamic), access time (O(1) vs O(n)), insertion/deletion costs, and memory overhead
   • Summary of trade-offs and use cases
4. 7 Marks
   bDescribe the concept of a dynamic array and how it differs from a static array in terms of memory management and flexibility.
   How to answer

   • Definition of dynamic array (resizable array)
   • Concept of capacity vs size, doubling strategy upon overflow
   • Comparison with static array in memory management (stack vs heap, compile-time fixed size vs runtime dynamic allocation)
   • Amortized time complexity of append operation
5. 7 Marks
   aWrite an algorithm which reverses the order of elements on stack using one additional stack and some additional variables.
   How to answer

   • State problem constraints: original stack S, auxiliary stack S_aux, temp variables
   • Algorithm steps: loop n times popping elements to find and place items into bottom positions or by systematically transferring using variables
   • Trace with a small stack [1, 2, 3]
   • Time and space complexity analysis (O(n^2) time, O(n) space)
6. 7 Marks
   bExplain the addition and deletion operations performed on a circular queue with necessary algorithms.
   How to answer

   • Concept and need of a circular queue over a linear queue
   • Enqueue algorithm using modulo arithmetic: `rear = (rear + 1) % MAX`, overflow check
   • Dequeue algorithm: `front = (front + 1) % MAX`, underflow check
   • Illustrative circular array diagram with front and rear pointers
7. 7 Marks
   aWrite an algorithm for Push and Pop operations on Stack using linked list.
   How to answer

   • Define node structure containing data and next pointer, along with top pointer
   • Push algorithm: Allocate node, set next to top, update top to new node
   • Pop algorithm: Check underflow (top == NULL), save top data, move top to top->next, free old top node
   • Time complexity of both operations: O(1)
8. 7 Marks
   bWhat is a DeQueue? Explain its operation with example.
   How to answer

   • Definition of DeQueue (Double-Ended Queue)
   • Four basic operations: insertFront, insertRear, deleteFront, deleteRear
   • Types: Input-restricted DeQueue and Output-restricted DeQueue
   • Step-by-step example demonstrating insertion and deletion at both ends
9. 7 Marks
   aConstruct an expression tree for the expression $(a + b * c) + ((d * e + f) * g)$. Apply inorder, preorder and postorder traversals on tree.
   How to answer

   • Parse expression based on operator precedence and parentheses
   • Draw the resulting binary expression tree (root is `+`)
   • Inorder traversal sequence (produces infix expression)
   • Preorder traversal sequence (prefix expression)
   • Postorder traversal sequence (postfix expression)
10. 7 Marks
    bCreate a binary search tree for the following numbers $45, 26, 10, 60, 70, 30, 40$. Start from an empty binary search tree. Delete keys $10$, $60$ and $45$ one after the other and show the trees at each stage.
    How to answer

    • Step-by-step insertion of 45, 26, 10, 60, 70, 30, 40 and sketch of initial BST
    • Delete key 10 (leaf node) and sketch updated BST
    • Delete key 60 (node with one child, 70) and sketch updated BST
    • Delete key 45 (root node with two children, replace with inorder successor or predecessor) and sketch final BST
11. 7 Marks
    aDescribe the algorithms used to perform single and double rotation on AVL tree.
    How to answer

    • Definition of AVL tree and Balance Factor
    • Single Rotations: Left Rotation (RR) and Right Rotation (LL) with algorithms/steps and diagrams
    • Double Rotations: Left-Right (LR) and Right-Left (RL) rotations with algorithms/steps and diagrams
    • Complexity of rotations: O(1)
12. 7 Marks
    bDifferentiate between Depth first search and Breadth First search algorithm.
    How to answer

    • Overview of DFS and BFS as graph traversal algorithms
    • Tabular comparison based on: data structure used (stack vs queue), order of visiting vertices, memory complexity, time complexity
    • Applications of each (e.g., shortest path for BFS, topological sorting/cycle detection for DFS)
13. 7 Marks
    aDefine minimum spanning tree. Write down Prim's algorithm to find minimum spanning tree.
    How to answer

    • Definition of Minimum Spanning Tree (MST) for a connected, weighted, undirected graph
    • Greedy strategy of Prim's algorithm
    • Step-by-step algorithm: initialize MST set, choose minimum weight crossing edge, add vertex to set until all vertices are included
    • Time complexity using adjacency matrix / min-heap
14. 7 Marks
    bSort the following elements using quick sort: $55, 72, 12, 45, 88, 38, 27, 33, 91, 80$
    How to answer

    • State chosen pivot element (e.g., first element 55 or last element 80)
    • Show pass-by-pass partitioning showing placement of pivot in its correct sorted position
    • Recursively apply quick sort on left and right sub-arrays
    • Final sorted sequence: 12, 27, 33, 38, 45, 55, 72, 80, 88, 91
15. 7 Marks
    aApply Binary search to search $36$ in following list: $21, 12, 36, 32, 38, 23, 56, 83, 92, 5, 10, 15$
    How to answer

    • Pre-requisite: Sort the given array first: 5, 10, 12, 15, 21, 23, 32, 36, 38, 56, 83, 92
    • Set initial low = 0, high = 11
    • Show iterations with low, high, mid calculation and comparison against key 36
    • Conclude with index where key 36 is found
16. 7 Marks
    bWrite short notes : i) Hashing and Indexing ii) Heap Sort iii) Red Black Tree
    How to answer

    • Hashing and Indexing: Hash functions, hash tables, collision resolution techniques, index structures
    • Heap Sort: Binary heap definition (max-heap/min-heap), heapify operation, sorting algorithm steps, O(n log n) complexity
    • Red-Black Tree: Definition, five coloring properties, rebalancing via rotations and recoloring, O(log n) worst-case search