IT-303 Data Structure - 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. 8 Marks
   aDiscuss about Asymptotic Notations with suitable examples.
   How to answer

   • Define Asymptotic Notations and their significance in algorithm analysis.
   • Explain Big-O ($O$) notation with mathematical definition and graphical representation.
   • Explain Omega ($\Omega$) notation with definition and graph.
   • Explain Theta ($\Theta$) notation with definition and graph.
   • Provide simple mathematical/algorithmic examples for each notation.
2. 6 Marks
   bList and explain non-linear data structures with examples.
   How to answer

   • Define non-linear data structures and contrast briefly with linear structures.
   • Explain Trees: terminology (root, node, edge, leaf) and types (binary tree, BST) with a diagram.
   • Explain Graphs: vertices, edges, directed vs undirected graphs with a diagram.
   • Provide real-world examples and applications for both trees and graphs.
3. 7 Marks
   aDifferentiate between primitive & non-primitive data structures in brief.
   How to answer

   • Define primitive data structures (built-in, direct hardware manipulation).
   • Define non-primitive data structures (derived, complex data organisation).
   • Provide a tabular comparison based on memory, operations, definition, and complexity.
   • List examples: primitive (int, float, char, boolean) vs non-primitive (arrays, lists, stacks, queues, trees, graphs).
4. 7 Marks
   bWrite the procedure for evaluation of addition of two polynomials.
   How to answer

   • Explain node/structure representation for a polynomial term (coefficient and exponent).
   • State the algorithm/procedure using pointers traversing both polynomials.
   • Compare powers: if equal, add coefficients; if unequal, attach the higher exponent term.
   • Append any remaining terms of either polynomial.
   • Illustrate with a simple example of adding two polynomials.
5. 8 Marks
   aDiscuss about Quick sort in detail.
   How to answer

   • Explain the Divide and Conquer strategy of Quick Sort.
   • Describe the partitioning procedure and pivot selection.
   • Provide algorithm/pseudocode for QuickSort and Partition.
   • Work through a step-by-step example with an unsorted array.
   • Analyze time complexity (Best: $O(n \log n)$, Worst: $O(n^2)$) and space complexity.
6. 6 Marks
   bWrite about Binary Search applications and procedure.
   How to answer

   • Define Binary Search and state its prerequisite (sorted array).
   • Explain the step-by-step procedure/algorithm (iterative or recursive).
   • Mention its time complexity ($O(\log n)$).
   • List applications: finding bounds, dictionary lookups, search in sorted data, debugging/bisection methods.
7. 8 Marks
   aWhat is Stack? Explain the operations of Stack with neat Sketch.
   How to answer

   • Define Stack as a LIFO (Last In First Out) linear data structure.
   • Draw a neat sketch illustrating Push and Pop operations at the top.
   • Explain PUSH operation with algorithm and overflow condition.
   • Explain POP operation with algorithm and underflow condition.
   • Briefly explain PEEK and IsEmpty operations.
8. 6 Marks
   bWrite and explain an algorithm to implement Josephus problem.
   How to answer

   • Define and explain the Josephus problem scenario ($n$ people in a circle, every $k$-th executed).
   • Explain implementation using a Circular Linked List or Recursive relation $J(n, k) = (J(n-1, k) + k) \pmod n$.
   • Provide step-by-step algorithm.
   • Illustrate execution with a small trace (e.g., $n=5, k=2$).
9. 7 Marks
   aDiscuss the Stack applications with suitable examples.
   How to answer

   • List key applications of stacks.
   • Explain expression evaluation and conversion (infix to postfix/prefix) with an example.
   • Explain balanced parenthesis checking.
   • Explain function call management / recursion stack and backtracking (e.g., DFS).
10. 7 Marks
    bList an algorithm to perform the insertion operations in a doubly linked list.
    How to answer

    • Define node structure of a doubly linked list (data, prev, next).
    • Algorithm for insertion at the beginning.
    • Algorithm for insertion at the end.
    • Algorithm for insertion after/before a given node.
    • Show pointer updates clearly using diagrams.
11. 7 Marks
    aList and explain about the basic operations that can be performed on a linked list.
    How to answer

    • List basic operations: Traversal, Insertion, Deletion, Searching, and Sorting.
    • Explain traversal procedure from head to null.
    • Explain insertion (at start, end, specific position).
    • Explain deletion (from start, end, specific value).
    • Explain searching for an element.
12. 7 Marks
    bWrite an algorithm to perform the insertion operations in a circular linked list.
    How to answer

    • Explain circular linked list structure where last node points to the first.
    • Provide algorithm for insertion in an empty circular list.
    • Provide algorithm for insertion at the beginning (updating last node's link).
    • Provide algorithm for insertion at the end.
    • Provide algorithm for insertion after a specified node.
13. 6 Marks
    aExplain different ways representation of graphs.
    How to answer

    • Explain Adjacency Matrix representation with structure, space complexity $O(V^2)$, and an example.
    • Explain Adjacency List representation with array of linked lists, space complexity $O(V+E)$, and an example.
    • Briefly mention Incidence Matrix representation.
    • Compare matrix vs list representations in terms of space and query time.
14. 8 Marks
    bShow the result of inserting 15, 17, 6, 19, 11, 10, 13, 20, 8, 14, 12 one at a time into an initially empty binary tree.
    How to answer

    • Recognize that insertion into a standard empty binary tree usually denotes a Binary Search Tree (BST).
    • Insert 15 as root.
    • Show sequential step-by-step additions of 17 (right of 15), 6 (left of 15), 19 (right of 17), 11 (right of 6), 10 (left of 11), 13 (right of 11), 20 (right of 19), 8 (left of 10), 14 (right of 13), 12 (left of 13).
    • Draw the final resulting BST clearly showing all nodes and branches.
15. 14 Marks
    Write short notes on any two of the following:

    1. a)Depth First Search
    2. b)Time Complexity
    3. c)Fibonacci Search
    How to answer

    • For Depth First Search: explain traversal technique using a stack/recursion, algorithm, time complexity $O(V+E)$, and a sample traversal.
    • For Time Complexity: explain concept of measuring algorithm execution time with respect to input size, orders of growth, best/average/worst cases.
    • For Fibonacci Search: explain divide-and-conquer search based on Fibonacci numbers, advantages over binary search, algorithm, and time complexity $O(\log n)$.