CY-303 Data Structure - 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 is Abstract data type? Explain with the help of example.
   How to answer

   • Define Abstract Data Type (ADT) as a mathematical model with data objects and operations.
   • Contrast ADT specification with implementation details.
   • Provide an example such as List, Stack, or Queue ADT with defined operations (e.g., push, pop, peek).
2. 7 Marks
   bDifferentiate array and linked list.
   How to answer

   • Tabulate differences between Array and Linked List.
   • Compare on memory allocation (static vs dynamic/contiguous vs non-contiguous).
   • Compare access complexity ($O(1)$ vs $O(n)$).
   • Compare insertion/deletion efficiency and memory overhead.
3. 7 Marks
   aWhat is the application of linked list. And also write the algorithm how to add two polynomials using linked list.
   How to answer

   • List major applications of linked lists (polynomial manipulation, dynamic memory management, graph adjacency list, implementation of stacks/queues).
   • Define node structure for polynomial: coefficient, exponent, next pointer.
   • Write algorithm for adding two polynomials by traversing both lists and comparing exponents.
   • Explain handling of cases: exponents equal, greater, or remaining terms.
4. 7 Marks
   bWrite a program in C to insert a node at any specified position in doubly linked list.
   How to answer

   • Define doubly linked list `struct Node` containing `data`, `prev`, and `next` pointers.
   • Allocate memory for the new node.
   • Traverse to the specified position $(pos - 1)$.
   • Adjust four pointers: new node's next and prev, previous node's next, and following node's prev.
   • Provide complete and syntactically correct C function or program.
5. 7 Marks
   aWhat is the difference between data and information? Give one example of each.
   How to answer

   • Define Data: raw, unorganized, unanalyzed facts and figures.
   • Define Information: processed, structured, meaningful data with context.
   • Provide clear examples for both (e.g., student marks vs average grade/report card).
6. 7 Marks
   bHow to represent 2-D array in memory? Explain with the help of example.
   How to answer

   • Explain Row-Major Order and Column-Major Order memory mappings for 2D arrays.
   • Provide general address calculation formulas for $A[i][j]$ in both orders.
   • Illustrate with a numeric example showing base address, row/column size, and computed address.
7. 7 Marks
   aWrite an algorithm to convert infix expression into postfix form using Stack. Also evaluate the given postfix form using stack $$2 \ 3 \ 9 * + \ 2 \ 3 \text{ ^ } - \ 6 \ 2 \ / \ +$$
   How to answer

   • State step-by-step algorithm for Infix to Postfix conversion using an operator stack.
   • Present tabular evaluation of postfix expression: $2 \ 3 \ 9 * + \ 2 \ 3 \text{ ^ } - \ 6 \ 2 \ / \ +$.
   • Step 1: $3 * 9 = 27$; $2 + 27 = 29$.
   • Step 2: $2^3 = 8$; $29 - 8 = 21$.
   • Step 3: $6 / 2 = 3$; $21 + 3 = 24$.
   • Conclude final result is 24.
8. 7 Marks
   bWrite a program in 'C' to implementation of QUEUE.
   How to answer

   • Define MAX size, array `queue[]`, and pointers `front = -1`, `rear = -1`.
   • Implement `enqueue()` checking for overflow condition.
   • Implement `dequeue()` checking for underflow condition.
   • Implement `display()` to traverse and print elements.
   • Provide `main()` menu-driven demonstration.
9. 7 Marks
   aWhat are the differences between i) Height and depth ii) Order and degree
   How to answer

   • Part (i): Define Height (number of edges on longest path from node to a leaf) vs Depth (number of edges from root to that node).
   • Part (ii): Define Degree (number of children of a node / max children of any node) vs Order (maximum number of children a node can have in multi-way trees like B-tree).
10. 7 Marks
    bShow that the maximum number of nodes in a binary tree of height $h$ is $2^{h+1}-1$.
    How to answer

    • State that the maximum number of nodes at level $i$ is $2^i$ (assuming root at level 0).
    • Sum the nodes across levels from $i=0$ to $h$: $N = \sum_{i=0}^{h} 2^i$.
    • Use the sum of a geometric series: $S = \frac{a(r^n - 1)}{r - 1} = \frac{1(2^{h+1} - 1)}{2 - 1} = 2^{h+1} - 1$.
    • Alternatively prove via mathematical induction on height $h$.
11. 7 Marks
    aConstruct the steps to configure a B-tree of order 5 for the following data: 78, 21, 11, 97, 85, 74, 63, 45, 42, 57, 20, 16, 19, 32, 30, 31.
    How to answer

    • State B-tree properties of order 5: maximum 4 keys and 5 children per node; split at 5 keys promoting the middle (3rd) key.
    • Show step-by-step insertions of each key in sorted order within nodes.
    • Illustrate node splits upon reaching capacity.
    • Draw intermediate and the final balanced B-tree.
12. 7 Marks
    bExplain Dijkstra Algorithm with the help of example.
    How to answer

    • State the purpose of Dijkstra's algorithm (single-source shortest paths in weighted graphs with non-negative edge weights).
    • Outline algorithm steps: initialize distances, visited set, pick unvisited minimum distance vertex, relax outgoing edges.
    • Provide a small weighted graph as an example.
    • Show step-by-step distance updates and final shortest path tree.
13. 7 Marks
    aWrite a Heap sort algorithm. Use Heap sort algorithm to sort the following element: $$\text{D A T A S T R U C T U R E S.}$$
    How to answer

    • Write pseudocode/algorithm for Heap Sort (build-max-heap and repeated extract-max with heapify).
    • Convert input characters D, A, T, A, S, T, R, U, C, T, U, R, E, S into a max-heap.
    • Demonstrate step-by-step extraction of root to sorted partition followed by re-heapification.
    • Output the final sorted array of characters in alphabetical order.
14. 7 Marks
    bDifferentiate internal sorting and external sorting. Also enlists the name of two sorting techniques of each.
    How to answer

    • Define Internal Sorting: sorting performed entirely in main memory (RAM).
    • Define External Sorting: sorting massive data sets residing in secondary storage (disk/tape).
    • Tabulate differences (memory capacity, speed, I/O cost).
    • List two techniques of internal sorting (e.g., Quick Sort, Bubble Sort) and two of external sorting (e.g., Multiway Merge Sort, Polyphase Merge Sort).
15. 7 Marks
    aBinary search is more efficient than Linear search. Justify your answer.
    How to answer

    • Compare time complexities: Linear search is $O(n)$, Binary search is $O(\log n)$.
    • Explain mechanism: Linear search checks sequentially, while binary search halves search space each iteration.
    • Demonstrate with numerical comparison of comparisons needed for large $n$ (e.g., $n = 10^6$: $10^6$ vs ~20 comparisons).
    • Note the requirement of sorted input for binary search.
16. 7 Marks
    bWrite short note on Hashing and Indexing.
    How to answer

    • Discuss Hashing: hash function, direct addressing, $O(1)$ average time complexity, collision resolution techniques (chaining, open addressing).
    • Discuss Indexing: concept of data structure to optimize retrieval, primary and secondary indices, dense vs sparse index.
    • Highlight contrast/relationship between hashing and indexing for fast data retrieval.