BE Computer Engineering (IOE, TU) Data Structure and Algorithm (IOE, CT 552) Question Paper 2079 Nepal

(a) Stack, LIFO behaviour and Infix-to-Postfix algorithm

Stack: A stack is a linear data structure in which insertion and deletion of elements take place only at one end, called the top. It follows the LIFO (Last-In, First-Out) principle — the element inserted most recently is the first one to be removed.

PUSH adds an element on top of the stack; POP removes the element currently on top. For example, after PUSH(A), PUSH(B), PUSH(C) the stack (top → bottom) is C, B, A; a POP returns C first, then B, then A — confirming LIFO behaviour.

Infix → Postfix algorithm (using an operator stack):

1. Initialise an empty operator stack and an empty output string.
2. Scan the infix expression left to right:
   a. If the token is an operand, append it to the output.
   b. If the token is '(', push it onto the stack.
   c. If the token is ')', pop and output operators until '(' is
      popped (discard the '(').
   d. If the token is an operator o1:
        while the stack top o2 is an operator with
            precedence(o2) > precedence(o1), OR
            precedence(o2) == precedence(o1) and o1 is left-associative,
        pop o2 to the output.
        Then push o1.
3. After scanning, pop all remaining operators to the output.

Precedence: ^ (highest, right-associative) > *, / > +, -.

(b) Converting A + B * (C - D) / E ^ F

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

(a) Building the BST: 50, 30, 70, 20, 40, 60, 80, 35, 45

Insert each key, going left if smaller than the current node and right if larger:

              50
            /    \
          30      70
         /  \    /  \
       20   40  60   80
           /
          35
            \
             45

• 50 root; 30<50 → left; 70>50 → right; 20<50,<30 → left of 30; 40<50,>30 → right of 30; 60>50,<70 → left of 70; 80>50,>70 → right of 70; 35<50,>30,<40 → left of 40; 45<50,>30,>40 → right of 40.

(b) Traversals

• Preorder (Root, Left, Right): 50, 30, 20, 40, 35, 45, 70, 60, 80
• Inorder (Left, Root, Right): 20, 30, 35, 40, 45, 50, 60, 70, 80 (sorted order)
• Postorder (Left, Right, Root): 20, 35, 45, 40, 30, 60, 80, 70, 50

(c) Deleting key 30 (a node with two children)

Strategy: When the node to be deleted has two children, replace its key with its inorder successor (smallest key in its right subtree) or inorder predecessor (largest in its left subtree), then delete that successor/predecessor node (which has at most one child).

Node 30 has children 20 (left) and 40 (right). Its inorder successor is the smallest key in the right subtree rooted at 40, which is 35. We copy 35 into the deleted node’s position and remove the original 35 node. The resulting tree:

              50
            /    \
          35      70
         /  \    /  \
       20   40  60   80
              \
               45

(a) BFS vs DFS

Both run in $O(V+E)$ time using an adjacency list.

(b) Dijkstra’s algorithm from source A

Edges: A→B(4), A→C(1), C→B(2), B→D(1), C→D(5), D→E(3).

We maintain tentative distances; each iteration picks the unvisited vertex with the smallest distance and relaxes its outgoing edges.

Shortest distances from A:

• A → A = 0
• A → C = 1 (path A–C)
• A → B = 3 (path A–C–B)
• A → D = 4 (path A–C–B–D)
• A → E = 7 (path A–C–B–D–E)

(a) Quick Sort — working principle and algorithm

Quick Sort is a divide-and-conquer, in-place sorting algorithm. It chooses a pivot element, then partitions the array so that all elements smaller than the pivot lie to its left and all larger elements to its right — placing the pivot in its final sorted position. It then recursively sorts the two sub-arrays.

QUICKSORT(A, low, high):
    if low < high:
        p = PARTITION(A, low, high)   // pivot in final place
        QUICKSORT(A, low, p - 1)
        QUICKSORT(A, p + 1, high)

PARTITION(A, low, high):           // Lomuto scheme, pivot = A[high]
    pivot = A[high]
    i = low - 1
    for j = low to high - 1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i], A[j]
    swap A[i+1], A[high]
    return i + 1

(b) Sorting {42, 23, 74, 11, 65, 58, 94, 36, 99, 87} (pivot = last element)

Partition 1 (pivot = 87, range 0–9): all of 42,23,74,11,65,58,36 are ≤ 87, while 94 and 99 are > 87. Pivot 87 settles before 94,99. {42, 23, 74, 11, 65, 58, 36, 87, 94, 99} — 87 fixed; left = indices 0–6, right = {94, 99}.

Partition of left {42,23,74,11,65,58,36} (pivot = 36): elements ≤36 are 23,11; pivot lands at position 2. {23, 11, 36, 42, 65, 58, 74} — 36 fixed. Left = {23,11}, right = {42,65,58,74}.

Partition {23,11} (pivot = 11): → {11, 23} — both fixed.

Partition {42,65,58,74} (pivot = 74): all ≤ 74 → {42, 65, 58, 74}, 74 fixed; left = {42,65,58}. Partition {42,65,58} (pivot = 58): 42 ≤ 58 → {42, 58, 65}, 58 fixed.

Partition {94,99} (pivot = 99): → {94, 99}.

Final sorted array: {11, 23, 36, 42, 58, 65, 74, 87, 94, 99}

(c) Time complexity

Let $T(n)$ be the running time. Partitioning costs $O(n)$.

• Best case: the pivot splits the array into two equal halves: $T(n) = 2T(n/2) + O(n) \Rightarrow T(n) = O(n\log n)$.
• Worst case: the pivot is always the smallest or largest element, giving a split of size $0$ and $n-1$: $T(n) = T(n-1) + O(n) \Rightarrow T(n) = O(n^2)$.

The worst case occurs when the array is already sorted (ascending or descending) and the pivot is chosen as the first or last element, producing maximally unbalanced partitions.

Singly linked list — insert at end and delete by key

A node holds data and a next pointer; head points to the first node.

Insert at end

struct Node { int data; struct Node *next; };

void insertEnd(struct Node **head, int value) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (*head == NULL) {        // empty list
        *head = newNode;
        return;
    }
    struct Node *p = *head;
    while (p->next != NULL)      // walk to last node
        p = p->next;
    p->next = newNode;           // link new node at the end
}

Pointer diagram (insert X at end):

Before:  head -> [A|*] -> [B|*] -> NULL
After:   head -> [A|*] -> [B|*] -> [X|NULL]
                              ^------------ p->next now points to X

Delete node with a given key

void deleteKey(struct Node **head, int key) {
    struct Node *cur = *head, *prev = NULL;
    if (cur != NULL && cur->data == key) {   // key in first node
        *head = cur->next;
        free(cur);
        return;
    }
    while (cur != NULL && cur->data != key) { // search
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return;                  // key not found
    prev->next = cur->next;                    // bypass the node
    free(cur);
}

Pointer diagram (delete B):

Before:  head -> [A|*] -> [B|*] -> [C|NULL]
                  prev      cur
After:   head -> [A|*] ----------> [C|NULL]      (B freed)
                  prev->next = cur->next

(a) Recursion and termination conditions [3]

Recursion is a technique in which a function calls itself, directly or indirectly, to solve a problem by reducing it to smaller instances of the same problem.

For a recursive function to terminate correctly it must satisfy:

1. Base case — at least one non-recursive condition that stops further calls.
2. Progress toward the base case — every recursive call must move the argument closer to the base case (e.g. a smaller n).
3. Correct combination — results of the smaller calls must be combined correctly to give the solution of the original problem.

(b) Recursive Fibonacci and its inefficiency [5]

int fib(int n) {
    if (n <= 1)            // base cases: fib(0)=0, fib(1)=1
        return n;
    return fib(n - 1) + fib(n - 2);
}

Why it is inefficient: The two recursive calls overlap and recompute the same sub-problems repeatedly (e.g. fib(n-2) is evaluated by both fib(n-1) and the second branch). The number of calls grows like the Fibonacci numbers themselves, giving an exponential time complexity of $O(\varphi^n) \approx O(2^n)$, where $\varphi \approx 1.618$.

The iterative version computes each Fibonacci value once, storing only the previous two:

int fibIter(int n) {
    int a = 0, b = 1, t;
    for (int i = 2; i <= n; i++) { t = a + b; a = b; b = t; }
    return n == 0 ? 0 : b;
}

It runs in $O(n)$ time and $O(1)$ space, far more efficient. (The recursive version can also be made $O(n)$ using memoization.)

Circular queue

A circular queue is a linear queue implemented over a fixed-size array in which the last position is logically connected back to the first, so the array is treated as a circle. The indices front and rear wrap around using modulo arithmetic ((rear + 1) % SIZE).

Why preferred over a linear queue: In a simple linear array queue, once rear reaches the last index, no more elements can be inserted even if the front cells are empty after dequeues — wasting space. A circular queue reuses the freed front cells, achieving full utilisation of the array without shifting elements.

ENQUEUE (insert)

ENQUEUE(Q, item):
    if (rear + 1) % SIZE == front:      // queue full
        report overflow; return
    if front == -1:                      // first insertion
        front = 0
    rear = (rear + 1) % SIZE
    Q[rear] = item

DEQUEUE (remove)

DEQUEUE(Q):
    if front == -1:                      // queue empty
        report underflow; return
    item = Q[front]
    if front == rear:                    // last element removed
        front = rear = -1
    else:
        front = (front + 1) % SIZE
    return item

Conditions (with front/rear initialised to -1)

• Queue-empty: front == -1
• Queue-full: (rear + 1) % SIZE == front

(a) Hashing and collision [3]

Hashing is a technique that maps a key to an index (the home address) in a fixed-size table using a hash function $h(key)$, allowing search, insertion and deletion in average $O(1)$ time.

A collision occurs when two distinct keys hash to the same table index, i.e. $h(k_1) = h(k_2)$ with $k_1 \ne k_2$. Because a finite table cannot give every possible key a unique slot, collisions are unavoidable and must be resolved.

(b) Collision-resolution techniques [5]

Linear probing (open addressing): On a collision, probe the next slots sequentially — $h(k), h(k)+1, h(k)+2, \dots$ (mod table size) — until an empty slot is found.

• Advantage: simple; uses no extra pointers, and good cache locality.
• Disadvantage: suffers from primary clustering — long runs of occupied slots form, degrading performance as the load factor rises; the table can also become full.

Chaining (separate chaining): Each table slot holds the head of a linked list; all keys hashing to that slot are stored in its list.

• Advantage: the table never “fills up” — it handles any number of collisions gracefully and deletion is simple.
• Disadvantage: needs extra memory for pointers, and performance degrades to $O(n)$ if many keys map to one chain; loses cache locality.

AVL tree

An AVL tree is a self-balancing binary search tree in which, for every node, the balance factor = height(left subtree) − height(right subtree) is restricted to −1, 0, or +1. Whenever an insertion/deletion violates this, a rotation (LL, RR, LR or RL) restores balance, keeping the height $O(\log n)$.

Inserting 30, 20, 40, 10, 25, 22

Insert 30: root. BF(30)=0.

30

Insert 20: left of 30. BF(30)=+1 — balanced.

  30
 /
20

Insert 40: right of 30. BF(30)=0 — balanced.

  30
 /  \
20   40

Insert 10: left of 20. BF(20)=+1, BF(30)=+1 — still balanced.

     30
    /  \
   20   40
  /
 10

Insert 25: right of 20. BF(20)=0, BF(30)=+1 — balanced.

     30
    /  \
   20   40
  /  \
 10   25

Insert 22: goes left of 25 (22<30, >20, <25). Now BF(25)=+1, BF(20)=−1, BF(30)=+2 — unbalanced. The imbalance at node 30 is Left-Right (LR): inserted in the right subtree (25) of 30’s left child (20). Perform an LR rotation (left-rotate 20, then right-rotate 30), bringing 25 up:

        25
       /  \
      20   30
     /  \    \
    10   22   40

All balance factors are now in {−1, 0, +1}; the tree is balanced.

Summary of rotations: Only one rebalancing was needed — an LR rotation at node 30 after inserting 22.

(a) Asymptotic notations [4]

For running time $f(n)$:

• Big-O (upper bound): $f(n) = O(g(n))$ if $\exists\, c>0, n_0$ such that $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$. It bounds the worst-case growth from above.
• Big-Omega ($\Omega$, lower bound): $f(n) = \Omega(g(n))$ if $\exists\, c>0, n_0$ such that $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$. It bounds growth from below (best case).
• Big-Theta ($\Theta$, tight bound): $f(n) = \Theta(g(n))$ if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$, i.e. $c_1 g(n) \le f(n) \le c_2 g(n)$. It means $f$ grows exactly like $g$.

(b) Complexity of the code fragment [4]

for (i = 1; i <= n; i++)          // outer loop
    for (j = 1; j <= n; j = j*2)  // inner loop: j doubles
        x = x + 1;

• The outer loop runs $n$ times.
• In the inner loop, j starts at 1 and doubles each iteration (1, 2, 4, 8, …) until it exceeds $n$. The number of iterations is the number of doublings to reach $n$, which is $\lfloor \log_2 n \rfloor + 1 = \Theta(\log n)$.

Total iterations $= n \times \log_2 n$.

Time complexity = $O(n \log n)$.

(a) Binary search algorithm [4]

int binarySearch(int A[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (A[mid] == key)      return mid;     // found
        else if (A[mid] < key)  low  = mid + 1;  // search right half
        else                    high = mid - 1;  // search left half
    }
    return -1;                                   // not found
}

Why the array must be sorted: Binary search decides which half to discard by comparing the key with the middle element. This is only valid if all elements to the left of mid are smaller and all to the right are larger — i.e. the array is sorted. On an unsorted array the discarded half might still contain the key, so the result would be wrong.

(b) Linear search vs Binary search [4]

Binary search is far faster on large sorted arrays because the search space is halved at every comparison, giving logarithmic time, whereas linear search may scan the whole array.

Stack using a linked list

A stack can be implemented with a singly linked list where the top pointer plays the role of the stack top and points to the most recently inserted node. Both push and pop operate at the head of the list, so each takes $O(1)$ time and the stack grows/shrinks dynamically without a fixed size.

struct Node { int data; struct Node *next; };
struct Node *top = NULL;        // empty stack

Push (insert at head)

void push(int value) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;        // new node points to old top
    top = newNode;              // top now points to new node
}

Pop (remove from head)

int pop() {
    if (top == NULL) {          // underflow
        printf("Stack empty\n");
        return -1;
    }
    struct Node *temp = top;
    int value = temp->data;
    top = top->next;            // move top to next node
    free(temp);
    return value;
}

Pointer diagram (push X):

Before: top -> [B|*] -> [A|NULL]
After:  top -> [X|*] -> [B|*] -> [A|NULL]

Advantage over an array-based stack

A linked-list stack has no fixed capacity — it grows and shrinks dynamically at run time, so there is no overflow as long as memory is available (and no wasted pre-allocated space), whereas an array-based stack is limited to a predefined size.