CS-303 Data Structures - Jun 2023 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 abstract data types? Explain.
   How to answer

   • Definition of Abstract Data Type (ADT)
   • Separation of interface and implementation
   • Key examples: List ADT, Stack ADT, Queue ADT, Tree ADT, Graph ADT
   • Operations defined for common ADTs
2. 7 Marks
   bWhat is a linked list .explain its operations with examples.
   How to answer

   • Definition of linked list (node structure with data and pointer/next)
   • Basic operations: Insertion (beginning, end, given position), Deletion, Traversal, Search
   • Diagrammatic representation of nodes and pointers
   • Example of performing operations on a sample list
3. 7 Marks
   aDifferentiate between the stack and queue.
   How to answer

   • Tabular comparison between stack and queue
   • Order of processing (LIFO vs FIFO)
   • Endpoints/pointers (Single end - Top vs Two ends - Front and Rear)
   • Operations: push/pop vs enqueue/dequeue
   • Common real-world and computational applications
4. 7 Marks
   bWrite a 'C' program to convert the infix expression to postfix expression.
   How to answer

   • Algorithm for infix to postfix conversion using a stack
   • Definitions of precedence function and stack helper functions (push, pop, isEmpty)
   • Complete C program reading an infix string and outputting postfix string
   • Handling of '(' and ')' properly
5. 7 Marks
   aWrite an algorithm for insert and delete operations in circular linked list.
   How to answer

   • Definition/structure of circular linked list
   • Step-by-step algorithm for insertion (at beginning / at end)
   • Step-by-step algorithm for deletion (from beginning / from end / specific node)
   • Pointer updating logic to maintain circularity
6. 7 Marks
   bHow a binary search tree is traversed? Explain with a suitable example.
   How to answer

   • Definition of BST property
   • Traversal techniques: Inorder (Left, Root, Right), Preorder (Root, Left, Right), Postorder (Left, Right, Root)
   • Note that inorder traversal gives elements in ascending order
   • Example BST drawn with computed traversals
7. 14 Marks
   Insert the following list of elements from the avl 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 elements: 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20, 47 showing rotations (LL, RR, LR, RL) when balance factor exceeds $\pm 1$
   • Intermediate and final AVL tree diagrams after complete insertion
   • Step-by-step deletion of 18, then 2, then 30
   • Perform rotations if tree becomes unbalanced after each deletion and draw the resulting AVL trees
8. 7 Marks
   aWhat is heap data structure ?explain its operations with a suitable example.
   How to answer

   • Definition of heap (complete binary tree satisfying heap property)
   • Difference between Min-heap and Max-heap
   • Operations: Insert, Delete (extract-max/min), Heapify
   • Step-by-step example with diagrams showing insertion and deletion
9. 7 Marks
   bSort the following list of elements 30, 56, 78, 99, 12, 43, 10, 24, 85 by using merge sort.
   How to answer

   • Divide array into two halves recursively until single elements remain
   • Show recursive division tree for [30, 56, 78, 99, 12, 43, 10, 24, 85]
   • Show step-by-step merge passes combining sorted sub-arrays
   • Final sorted list: 10, 12, 24, 30, 43, 56, 78, 85, 99
10. 7 Marks
    aCompare and contrast bfs and dfs.
    How to answer

    • Tabular comparison between BFS and DFS
    • Data structures: Queue for BFS, Stack (or recursion) for DFS
    • Traversal strategy: Level-order vs backtracking along deep branches
    • Time and space complexities
    • Typical use cases for each
11. 7 Marks
    bDiscuss kruskals algorithm with an following graph.

    

    How to answer

    • Explain Kruskal's algorithm steps (sort edges, iteratively add minimum edge if it doesn't form a cycle)
    • List of all edges sorted by weight: (1,2): 3, (0,4): 4, (4,2): 5, (4,1): 6 (rejected, forms cycle 1-2-4), (4,3): 7, etc.
    • Step-by-step edge selection and cycle detection
    • Edges included in MST: (1,2), (0,4), (4,2), (4,3)
    • Calculate total minimum weight = 3 + 4 + 5 + 7 = 19
    • Draw the resulting MST
12. 7 Marks
    aExplain shell sort algorithm and simulate it for the following data 35, 33, 42, 10, 14, 19, 27, 44.
    How to answer

    • Explain shell sort concept (generalized insertion sort with gap sequence $h$)
    • Choose initial gap, e.g., $gap = \lfloor N/2 \rfloor = 4$
    • Show array after pass with gap = 4
    • Show array after pass with gap = 2
    • Show final pass with gap = 1 (standard insertion sort on nearly sorted array)
    • Final sorted sequence: 10, 14, 19, 27, 33, 35, 42, 44
13. 7 Marks
    bExplain sequential search and simulate it for the following data 4, 21, 36, 14, 62, 91, 8, 22, 81, 77, 10.
    How to answer

    • Explain sequential/linear search mechanism and algorithm
    • State time complexity: Best case $O(1)$, Worst/Average case $O(n)$
    • Simulate searching for an element present (e.g., key = 8) showing comparisons from index 0
    • Simulate searching for an element not present or at the end
14. 14 Marks
    Write short notes on any two of the following:

    1. i)Stack using linked list
    2. ii)Indexing
    3. iii)B tree
    4. iv)Priority queue
    How to answer

    • For Stack using linked list: Node structure, push and pop at head node, advantages over array implementation
    • For Indexing: Concept of index records, dense vs sparse index, primary vs secondary indices to speed retrieval
    • For B tree: Self-balancing multiway search tree, properties (order m, min/max keys, balanced height), search/insertion basics
    • For Priority queue: Definition, elements with priority keys, operations (insert, extract-max/min), heap-based implementation