CS-303 Data Structures - Nov 2022 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
   aWhat are the different operations performed on data structures? Explain.
   How to answer

   • Definition of primary data structure operations
   • Traversal, Insertion, Deletion
   • Searching (Linear, Binary) and Sorting
   • Merging and Updating operations with brief descriptions
2. 7 Marks
   bHow linked list is represented in memory? Explain.
   How to answer

   • Node structure consisting of Data and Next pointer
   • Dynamic memory allocation representation
   • Array/parallel-array representation in memory
   • Diagrammatic illustration of contiguous vs non-contiguous storage with head pointer and NULL termination
3. 7 Marks
   aExplain the operations performed on stack with a program.
   How to answer

   • Definition of Stack and LIFO principle
   • Explanation of Push, Pop, Peek/Display operations
   • Conditions for Overflow and Underflow
   • C program implementation using array or linked list
4. 7 Marks
   bConvert the following infix to post fix expression. $$A + B - C * D * E \$ F \$ G$$
   How to answer

   • Table showing token scanned, stack status, and postfix expression
   • Application of precedence and associativity rules (note: exponentiation '$' is right-associative)
   • Final postfix expression derivation
5. 7 Marks
   aExplain briefly about the Circular Linked list and it operations.
   How to answer

   • Definition of Circular Linked List (last node points to first)
   • Advantages and disadvantages compared to singly linked list
   • Key operations: Insertion (beginning, end), Deletion (beginning, end), and Traversal
   • Illustrative diagrams for structure and operations
6. 7 Marks
   bWhat are the different terminologies used in the trees? Explain with suitable diagrams.
   How to answer

   • General tree definition
   • Definitions of key terminologies: Root, Child, Parent, Siblings, Leaf/Terminal node, Non-terminal node, Degree, Level, Height/Depth, Path
   • Labeled tree diagram demonstrating each term clearly
7. 14 Marks
   Insert the following list of elements from the red black tree. Delete the elements 18, 2, 30 from the 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20 and 47.
   How to answer

   • Step-by-step insertion of 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20, 47 showing rotations and recoloring
   • Resulting Red-Black tree after all insertions
   • Step-by-step deletion of 18, 2, and 30 with necessary fixes for double black violations
   • Final Red-Black tree structure
8. 7 Marks
   aWrite a 'C' program, how to insert and delete elements in the Binary search tree?
   How to answer

   • Definition of BST node structure in C
   • Recursive or iterative insert() function logic
   • deleteNode() function handling 3 cases: node with 0 children, 1 child, and 2 children (finding inorder successor/predecessor)
   • Main driver program showing creation and verification
9. 7 Marks
   bDiscuss Kruskal's algorithm with an following graph.

   

   How to answer

   • Explanation of Kruskal's algorithm steps
   • Sorted list of all edges by weight
   • Selection of edges one by one rejecting edges forming cycles
   • List of edges included in the final MST and total minimum weight calculation
10. 7 Marks
    aSolve BFS and DFS traversal of following graph.

    

    How to answer

    • BFS algorithm using queue: specify starting vertex (typically 1), show visited queue status, output traversal order
    • DFS algorithm using stack/recursion: show backtrack path and output traversal sequence
    • State assumptions regarding neighbor selection order (e.g., numerical order)
11. 7 Marks
    bDiscuss Prims algorithm with an following graph.

    

    How to answer

    • Algorithm steps for Prim's method starting from a chosen root vertex (e.g., 0)
    • Step-by-step vertex inclusion and edge selection table
    • Drawing of the resulting MST
    • Sum of weights of the MST edges
12. 7 Marks
    aExplain bubble sort algorithm and simulate it for the following data 35, 33, 42, 10, 14, 19, 27, 44.
    How to answer

    • Working principle of Bubble sort algorithm
    • Pass-by-pass tracing of the array [35, 33, 42, 10, 14, 19, 27, 44]
    • State of array after each pass until fully sorted
    • Time and space complexity analysis
13. 7 Marks
    bExplain Binary search and simulate it for the following data 4, 21, 36, 14, 62, 91, 8, 22, 81, 77, 10.
    How to answer

    • Binary search prerequisite (data must be sorted)
    • Sorting the data: [4, 8, 10, 14, 21, 22, 36, 62, 77, 81, 91]
    • Choosing an example target element to search (or explaining step-by-step logic)
    • Calculation of low, high, mid in successive iterations
14. 14 Marks
    Write short notes on any two of the following:

    1. i)Queue using linked list
    2. ii)Hashing
    3. iii)B+ tree
    4. iv)Post fix expression evaluation
    How to answer

    • Queue using linked list: Front and Rear pointer operations, Enqueue at rear, Dequeue at front with $O(1)$ complexity
    • Hashing: Hash function, Hash table, Collision resolution techniques (Chaining, Open Addressing)
    • B+ tree: Multi-way search tree, all keys stored at leaf level linked together, properties and advantages for indexing
    • Postfix evaluation: Stack-based algorithm scanning left to right, operands pushed, operators pop two operands and push result