Data Structures & Algorithms — Complete Exam Answer Set

Full solutions with all programs in Java. Marking scheme: Group A (10×2 = 20) · Group B (5×10 = 60) · Group C (2×15 = 30)

Table of Contents

GROUP 'A' — Short Answer Questions

1. Define Data Structure with an example.

A data structure is a systematic way of organizing, storing, and managing data in a computer so that it can be accessed and modified efficiently. Example: An array stores a fixed-size collection of elements of the same type in contiguous memory, e.g., int[] marks = {80, 75, 90, 65, 88};.

2. Differentiate between linear and non-linear data structures.

Linear Non-linear
Elements arranged sequentially, one after another Elements arranged hierarchically/in a network
Single level; traversal in one run Multiple levels; cannot traverse in one run
Memory utilization is less efficient Memory utilization is more efficient
Examples: Array, Stack, Queue, Linked List Examples: Tree, Graph

3. Define algorithm. What are the characteristics of a good algorithm?

An algorithm is a finite, step-by-step set of well-defined instructions to solve a particular problem. Characteristics: Input (zero or more), Output (at least one), Definiteness (each step unambiguous), Finiteness (terminates after finite steps), and Effectiveness (each step basic and feasible).

4. What is time and space complexity?

Time complexity measures the amount of time an algorithm takes to run as a function of input size n (e.g., O(n), O(log n)). Space complexity measures the amount of memory an algorithm requires during execution as a function of input size n. Both are usually expressed using asymptotic (Big-O) notation.

5. Define tail recursion with an example.

Tail recursion is a form of recursion where the recursive call is the last operation performed in the function, with no pending computation afterward. This allows compilers to optimize it into a loop (saving stack space).

void printNums(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    printNums(n - 1);   // last statement → tail recursion
}

6. What are PUSH and POP operations?

These are the two fundamental operations of a stack (LIFO structure). PUSH inserts an element on the top of the stack. POP removes and returns the element from the top of the stack.

7. What are postfix and infix expressions?

  • Infix: Operator placed between operands, e.g., A + B. (Human-readable, needs precedence/parentheses.)
  • Postfix (Reverse Polish): Operator placed after operands, e.g., A B +. (No parentheses needed; easily evaluated by a stack.)

8. When to prefer a linked list over an array (real-life example).

Prefer a linked list when the number of elements is unknown/changes frequently and many insertions/deletions occur in the middle, since arrays require shifting and have fixed size. Real-life example: A music playlist where songs are frequently added or removed at any position — each song points to the next one, so reordering is just relinking pointers.

9. What is a circular and priority queue?

  • Circular Queue: A linear queue in which the last position is connected back to the first position, forming a circle. It reuses vacant spaces left by dequeued elements, avoiding the "false overflow" of a simple queue.
  • Priority Queue: A queue where each element has a priority; elements with higher priority are dequeued before those with lower priority (and FIFO order is kept among equal priorities).

10. What is concatenation in the linked list?

Concatenation is the operation of joining two linked lists into a single list by linking the last node (tail) of the first list to the head (first node) of the second list, so traversal continues seamlessly from list 1 into list 2.

GROUP 'B' — Descriptive Answers

B1. Incremental Approach and Divide-and-Conquer Approach (5+5)

Incremental Approach The problem is solved by building up the solution one element/step at a time. After processing each element, the partial solution remains correct, and the next element is incorporated into it.

Example — Insertion Sort: The array is divided into a sorted part and an unsorted part. We take one element at a time from the unsorted part and insert it into its correct position in the sorted part. For [5, 2, 4, 1]: start with [5]; insert 2 → [2,5]; insert 4 → [2,4,5]; insert 1 → [1,2,4,5]. The sorted region grows incrementally by one element each pass.

Divide-and-Conquer Approach The problem is solved in three steps:

  1. Divide the problem into smaller subproblems of the same type.
  2. Conquer the subproblems by solving them recursively.
  3. Combine the subsolutions to form the final solution.

Example — Merge Sort: The array is divided into two halves, each half is sorted recursively, and the two sorted halves are merged. For [5,2,4,1]: divide → [5,2] and [4,1]; sort → [2,5] and [1,4]; merge → [1,2,4,5]. Its time complexity is O(n log n).

Key difference: Incremental works element-by-element on a single problem instance, while divide-and-conquer recursively breaks the problem into independent subproblems and combines them.

B2. Recursion + Tower of Hanoi (2+3+5)

Definition (2): Recursion is a programming technique in which a method calls itself directly or indirectly to solve a problem by breaking it into smaller instances of the same problem.

Principles of Recursion (3):

  1. Base Case: A terminating condition that stops further recursion (prevents infinite recursion).
  2. Recursive Case: The method calls itself with a smaller/simpler argument that moves toward the base case.
  3. State Stacking: Each call is stored on the system stack, and execution resumes (unwinds) in reverse order after the base case is reached.

Tower of Hanoi Program (5): Move n disks from source to destination using an auxiliary peg, never placing a larger disk on a smaller one.

public class TowerOfHanoi {
    static void towerOfHanoi(int n, char src, char aux, char dest) {
        if (n == 1) {                              // base case
            System.out.println("Move disk 1 from " + src + " to " + dest);
            return;
        }
        towerOfHanoi(n - 1, src, dest, aux);       // step 1
        System.out.println("Move disk " + n + " from " + src + " to " + dest); // step 2
        towerOfHanoi(n - 1, aux, src, dest);       // step 3
    }

    public static void main(String[] args) {
        int n = 3;
        towerOfHanoi(n, 'A', 'B', 'C');  // A=source, B=auxiliary, C=destination
    }
}

For n disks, the total number of moves required is 2ⁿ − 1.

B3. Stack Applications + Infix→Postfix (2+4+4)

Two applications of stack (2):

  1. Expression conversion and evaluation (infix to postfix, evaluating postfix).
  2. Function call management (recursion uses the system/call stack); also used in undo operations and backtracking.

Algorithm: Infix → Postfix Conversion (4):

  1. Scan the infix expression from left to right.
  2. If the symbol is an operand, append it to the postfix output.
  3. If the symbol is (, push it onto the stack.
  4. If the symbol is ), pop from the stack to output until ( is found; discard the pair of parentheses.
  5. If the symbol is an operator, pop from the stack to output all operators having higher or equal precedence, then push the current operator.
  6. After scanning, pop all remaining operators from the stack to the output.

Worked example (4): Convert A + B * C

Symbol Stack Postfix Output
A (empty) A
+ + A
B + A B
* + * A B
C + * A B C
end (empty) A B C * +

* has higher precedence than +, so B*C is grouped first → ABC*+.

B4. Queue Underflow + Limitations + Circular Queue Deletion (1+2+3+4)

Queue Underflow (1): The condition that occurs when we attempt to delete (dequeue) an element from an empty queue (i.e., front > rear or queue size is 0).

Limitations of a Simple (Linear) Queue (2):

  1. False overflow / inefficient memory use: Once rear reaches the last index, no more insertion is allowed even if front cells are vacant (due to deletions). The freed space is wasted.
  2. No reuse of space without shifting: To reuse the front space, all elements must be shifted, which is costly (O(n)).

Algorithm: Delete from Circular Queue (3):

  1. If front == -1, the queue is empty → report underflow, stop.
  2. Store the element: item = queue[front].
  3. If front == rear (only one element), reset front = rear = -1.
  4. Otherwise, move front circularly: front = (front + 1) % SIZE.
  5. Return item.

Program (4):

public class CircularQueue {
    static final int SIZE = 5;
    static int[] queue = new int[SIZE];
    static int front = -1, rear = -1;

    static int deleteCQ() {
        if (front == -1) {                  // step 1: underflow
            System.out.println("Queue Underflow");
            return -1;
        }
        int item = queue[front];            // step 2
        if (front == rear)                  // step 3: single element
            front = rear = -1;
        else
            front = (front + 1) % SIZE;     // step 4: circular move
        return item;                        // step 5
    }

    public static void main(String[] args) {
        // assume queue already filled
        queue[0] = 10; queue[1] = 20; queue[2] = 30;
        front = 0; rear = 2;
        System.out.println("Deleted: " + deleteCQ());
        System.out.println("Deleted: " + deleteCQ());
    }
}

B5. Data Field vs Link Field + Insertion at Specific Position (3+3+4)

Data field vs Link field (3):

Data Field Link Field
Stores the actual information/value of the node Stores the reference (address) of the next node
Holds user data (e.g., an integer, name) Holds a reference, not user data
Loss of it means loss of information Loss of it breaks the chain/connection

A node = [ Data Field | Link Field ].

Algorithm: Insertion at a specific position p (3):

  1. Create a new node and assign data to it.
  2. If position is 1, set newNode.next = head, head = newNode, stop.
  3. Traverse to the node at position p−1 (call it temp).
  4. If temp is null, position is invalid → stop.
  5. Set newNode.next = temp.next.
  6. Set temp.next = newNode.

Program (4):

public class InsertAtPosition {
    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; this.next = null; }
    }
    static Node head = null;

    static void insertAtPosition(int value, int pos) {
        Node newNode = new Node(value);

        if (pos == 1) {                        // insert at head
            newNode.next = head;
            head = newNode;
            return;
        }
        Node temp = head;
        for (int i = 1; i < pos - 1 && temp != null; i++)
            temp = temp.next;                  // reach (pos-1)th node

        if (temp == null) { System.out.println("Invalid position"); return; }

        newNode.next = temp.next;              // relink
        temp.next = newNode;
    }

    static void display() {
        for (Node t = head; t != null; t = t.next)
            System.out.print(t.data + " -> ");
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        insertAtPosition(10, 1);
        insertAtPosition(30, 2);
        insertAtPosition(20, 2);   // insert 20 between 10 and 30
        display();                 // 10 -> 20 -> 30 -> NULL
    }
}

B6. PUSH/POP Algorithms + Infix→Postfix Conversion (4+6)

PUSH Algorithm:

  1. If top == SIZE − 1 → Stack Overflow, stop.
  2. Increment top: top = top + 1.
  3. Insert element: stack[top] = item.

POP Algorithm:

  1. If top == −1 → Stack Underflow, stop.
  2. Retrieve element: item = stack[top].
  3. Decrement top: top = top − 1; return item.

Java implementation of PUSH and POP:

public class StackOps {
    static final int SIZE = 100;
    static int[] stack = new int[SIZE];
    static int top = -1;

    static void push(int item) {
        if (top == SIZE - 1) { System.out.println("Stack Overflow"); return; }
        stack[++top] = item;                // increment then insert
    }

    static int pop() {
        if (top == -1) { System.out.println("Stack Underflow"); return -1; }
        return stack[top--];                // retrieve then decrement
    }

    public static void main(String[] args) {
        push(10); push(20); push(30);
        System.out.println("Popped: " + pop()); // 30
        System.out.println("Popped: " + pop()); // 20
    }
}

Convert (A + B) * (C - D) / E + F * G step by step using a stack (6): (Precedence: * / > + -; ( lowest inside stack until matched.)

Symbol Stack Postfix Output
( (
A ( A
+ ( + A
B ( + A B
) (empty) A B +
* * A B +
( * ( A B +
C * ( A B + C
- * ( - A B + C
D * ( - A B + C D
) * A B + C D -
/ / A B + C D - *
E / A B + C D - * E
+ + A B + C D - * E /
F + A B + C D - * E / F
* + * A B + C D - * E / F
G + * A B + C D - * E / F G
end (empty) A B + C D - * E / F G * +

Postfix result: A B + C D - * E / F G * +

Explanation: Parentheses force A+B and C-D to be evaluated first. * and / (left-to-right) handle (A+B)*(C-D) then /E. Finally F*G is computed and added, with + (lowest precedence) combined last.

GROUP 'C' — Long Answers

C1. Online Food Delivery Service (4+4+4+3)

a. Most suitable queue + justification (4): A Priority Queue is most suitable. Orders are classified into priority levels (Express > Premium > Normal). A priority queue serves higher-priority orders before lower-priority ones, exactly matching the requirement that urgent orders are processed first. To also maintain arrival order among orders of the same priority, a stable priority queue (FIFO within equal priority) is used — this guarantees fairness for customers of the same category.

b. Enqueue and Dequeue operations with examples (4):

  • Enqueue (Insertion): A new order is inserted according to its priority. It is placed before all lower-priority orders but after equal- or higher-priority orders that arrived earlier.
    • Example: Queue = [Express, Premium, Normal]. A new Premium order arrives → inserted after the existing Premium but before Normal → [Express, Premium, Premium(new), Normal].
  • Dequeue (Deletion): The order with the highest priority (and earliest arrival among equals) is removed for processing.
    • Example: From [Express, Premium, Normal], dequeue removes Express first → processed order = Express.

c. Simple Queue vs Priority Queue (4):

Simple Queue Priority Queue
Pure FIFO — first inserted is first processed Highest priority is processed first
Order of processing depends only on arrival time Order depends on priority, then arrival time
All elements treated equally Elements ranked by priority value
Insertion always at rear Insertion at position based on priority
Cannot handle urgent orders specially Designed to handle urgent orders first

d. Efficiency + fairness (3): The priority queue ensures efficiency for urgent orders because Express orders, having the highest priority, are always dequeued before Premium/Normal — they never wait behind less urgent orders. It maintains fairness within the same category because the structure preserves FIFO order among equal-priority orders: the Premium order that arrived earlier is served before a later Premium order. Thus urgency is respected across categories while arrival fairness is respected within a category.

C2. Balanced Parentheses + String Reversal using Stack (10+5)

Algorithm (Balanced Parentheses):

  1. Create an empty stack.
  2. Scan the expression character by character.
  3. If the character is an opening bracket ( [ {, push it.
  4. If it is a closing bracket ) ] }, check the stack:
    • If the stack is empty → unbalanced.
    • Pop the top; if it does not match the corresponding opening bracket → unbalanced.
  5. After scanning, if the stack is empty, the expression is balanced; otherwise it is unbalanced.

Java Program (10):

import java.util.Stack;

public class BalancedParentheses {
    static boolean isBalanced(String expr) {
        Stack<Character> stack = new Stack<>();
        for (char ch : expr.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);                       // opening bracket
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return false;    // no matching open
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{'))
                    return false;                     // mismatch
            }
        }
        return stack.isEmpty();   // balanced only if stack is empty
    }

    public static void main(String[] args) {
        String expr = "{[A+(B-C)]*D}";
        System.out.println(expr + " -> " +
            (isBalanced(expr) ? "Balanced" : "Not Balanced"));
    }
}

Example trace for {[A+(B-C)]*D}: push {, push [, push (, then ) matches ( (pop), ] matches [ (pop), } matches { (pop). Stack ends empty → Balanced.

How a stack reverses a string (5): A stack is LIFO, so the last character pushed is the first popped — popping the entire string outputs it in reverse.

  1. Push every character of the string onto the stack one by one.
  2. Pop each character and append it to the result string.
  3. The popped sequence is the reversed string.
import java.util.Stack;

public class ReverseString {
    static String reverse(String str) {
        Stack<Character> stack = new Stack<>();
        for (char ch : str.toCharArray()) stack.push(ch); // push all
        StringBuilder rev = new StringBuilder();
        while (!stack.isEmpty()) rev.append(stack.pop());  // pop all
        return rev.toString();
    }
    public static void main(String[] args) {
        System.out.println(reverse("HELLO"));  // OLLEH
    }
}

For "HELLO": push H,E,L,L,O → pop O,L,L,E,H → "OLLEH".

C3. Linked List Operations + Full Program (5+10)

Operations of a Linked List (5):

  1. Creation: Allocate and initialize nodes, linking them via references to form the list.
  2. Insertion: Add a node at the beginning, end, or a specific position by adjusting references.
  3. Deletion: Remove a node from the beginning, end, or a specific position and relink neighbors.
  4. Traversal: Visit each node from head to the last node (where link = null) to read/display data.
  5. Searching: Scan nodes sequentially to find a node containing a given value.

(Additional operations include updating a node's value and concatenating two lists.)

Program — Singly Linked List with Insertion, Deletion, Traversal (10):

public class SinglyLinkedList {
    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; this.next = null; }
    }
    static Node head = null;

    // INSERTION at end
    static void insertEnd(int value) {
        Node newNode = new Node(value);
        if (head == null) { head = newNode; return; }
        Node temp = head;
        while (temp.next != null) temp = temp.next;
        temp.next = newNode;
    }

    // DELETION of a node by value
    static void deleteNode(int value) {
        if (head == null) { System.out.println("List empty"); return; }

        if (head.data == value) {            // delete head
            head = head.next;
            return;
        }
        Node temp = head, prev = null;
        while (temp != null && temp.data != value) {
            prev = temp;
            temp = temp.next;
        }
        if (temp == null) { System.out.println("Value " + value + " not found"); return; }
        prev.next = temp.next;               // relink
    }

    // TRAVERSAL
    static void traverse() {
        if (head == null) { System.out.println("List is empty"); return; }
        for (Node temp = head; temp != null; temp = temp.next)
            System.out.print(temp.data + " -> ");
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        insertEnd(10);
        insertEnd(20);
        insertEnd(30);
        insertEnd(40);
        System.out.print("After insertion: ");
        traverse();                 // 10 -> 20 -> 30 -> 40 -> NULL

        deleteNode(20);
        System.out.print("After deleting 20: ");
        traverse();                 // 10 -> 30 -> 40 -> NULL
    }
}

Output:

After insertion: 10 -> 20 -> 30 -> 40 -> NULL
After deleting 20: 10 -> 30 -> 40 -> NULL

This program demonstrates dynamic creation (insertEnd), reference-based deletion with relinking (deleteNode), and sequential reading (traverse) — the three core linked-list operations.

End of answer set.