CSC211 · TU past paper

Data Structures and Algorithms 2078 question paper

The complete TU 2078 exam paper for Data Structures and Algorithms (CSC211), all 12 questions with solved model answers written to the mark scheme.

Past Papers2081 2080 2079 2078 2077 2075 2074

Tap a question to open its answer.

110 marksTypes of Linked ListHideAnswer
Explain circular linked list with example. How do you implement linked list operation in singly linked list? Explain.[10]
--- A circular linked list is a linked list in which the last node does not contain a NULL pointer. Instead, the link field of the last node points back to the first node of the list, forming a circle or loop. Every node in the list has ...

210 marksBinary Search Tree, Insertion, Deletion, TAnswer

What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.[10]

Binary Search Tree: Definition, Insertion and Deletion

Definition of Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

All keys in the left sub-tree of the root are smaller than the key in the root node.
All keys in the right sub-tree of the root are greater than the key in the root node.
The left and right sub-trees of the root are again binary search trees (recursive definition).

Example:

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

Here, every left child < parent < right child.

Node Structure

Each node in a BST contains:

A data/key field
A pointer to the left child
A pointer to the right child

C Program: BST Insertion and Deletion

#include <stdio.h>
#include <stdlib.h>

/* ── Node structure ── */
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

/* ── Helper: create a new node ── */
struct Node* createNode(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data  = value;
    newNode->left  = NULL;
    newNode->right = NULL;
    return newNode;
}

/* ════════════════════════════════
   INSERTION
   ════════════════════════════════
   Algorithm:
   1. If tree is empty, new node becomes root.
   2. If value < current node data, go LEFT.
   3. If value > current node data, go RIGHT.
   4. Repeat until NULL position found; insert there.
*/
struct Node* insert(struct Node *root, int value) {
    /* Base case: empty tree or reached insertion point */
    if (root == NULL) {
        return createNode(value);
    }

    if (value < root->data) {
        /* Insert in left sub-tree */
        root->left = insert(root->left, value);
    }
    else if (value > root->data) {
        /* Insert in right sub-tree */
        root->right = insert(root->right, value);
    }
    else {
        /* Duplicate keys are not inserted */
        printf("Value %d already exists in BST.\n", value);
    }

    return root;
}

/* ════════════════════════════════
   FIND MINIMUM NODE
   (Used during deletion)
   Returns the node with minimum key
   in a given sub-tree (leftmost node).
════════════════════════════════ */
struct Node* findMin(struct Node *root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

/* ════════════════════════════════
   DELETION
   ════════════════════════════════
   Three cases:
   Case 1: Node has NO child (leaf)
           --> Simply delete the node.

   Case 2: Node has ONE child
           --> Replace node with its child.

   Case 3: Node has TWO children
           --> Find in-order successor
               (smallest in right sub-tree).
           --> Copy successor's value to node.
           --> Delete the in-order successor.
*/
struct Node* deleteNode(struct Node *root, int value) {
    /* Base case: value not found */
    if (root == NULL) {
        printf("Value %d not found in BST.\n", value);
        return NULL;
    }

    if (value < root->data) {
        /* Value lies in left sub-tree */
        root->left = deleteNode(root->left, value);
    }
    else if (value > root->data) {
        /* Value lies in right sub-tree */
        root->right = deleteNode(root->right, value);
    }
    else {
        /* Node to be deleted is found */

        /* Case 1: Leaf node (no children) */
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }

        /* Case 2a: Only right child exists */
        else if (root->left == NULL) {
            struct Node *temp = root->right;
            free(root);
            return temp;
        }

        /* Case 2b: Only left child exists */
        else if (root->right == NULL) {
            struct Node *temp = root->left;
            free(root);
            return temp;
        }

        /* Case 3: Node has two children */
        else {
            /* Find in-order successor (min of right sub-tree) */
            struct Node *successor = findMin(root->right);

            /* Copy successor's value to current node */
            root->data = successor->data;

            /* Delete the in-order successor from right sub-tree */
            root->right = deleteNode(root->right, successor->data);
        }
    }

    return root;
}

/* ════════════════════════════════
   IN-ORDER TRAVERSAL (Left-Root-Right)
   Prints BST in sorted order
════════════════════════════════ */
void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

/* ════════════════════════════════
   MAIN FUNCTION
════════════════════════════════ */
int main() {
    struct Node *root = NULL;

    /* Inserting nodes */
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of BST: ");
    inorder(root);
    printf("\n");

    /* Delete a leaf node */
    root = deleteNode(root, 20);
    printf("After deleting 20: ");
    inorder(root);
    printf("\n");

    /* Delete a node with one child */
    root = deleteNode(root, 30);
    printf("After deleting 30: ");
    inorder(root);
    printf("\n");

    /* Delete a node with two children */
    root = deleteNode(root, 50);
    printf("After deleting 50: ");
    inorder(root);
    printf("\n");

    return 0;
}

Sample Output:

Inorder traversal of BST: 20 30 40 50 60 70 80
After deleting 20: 30 40 50 60 70 80
After deleting 30: 40 50 60 70 80
After deleting 50: 40 60 70 80

Explanation

Deleting 20 removes a leaf node directly. Deleting 30 removes a node with only one child (40), so 40 takes its place. Deleting 50 (the root, which now has two children 40 and 70) is handled by Case 3: the in-order successor, 60 (the smallest value in the right sub-tree rooted at 70), replaces 50's value, and the original node holding 60 is then removed from the right sub-tree. The in-order traversal after each deletion confirms that the BST property (left < parent < right at every node) is preserved throughout, which is why the printed sequence always stays sorted.

310 marksBasic Concept of Queue, Queue as an ADT, PAnswer

Define Queue. Write are different applications of queue? Explain queue operations with example.[10]

Queue: Definition, Applications, and Operations

1. Definition of Queue

A Queue is a linear data structure that follows the FIFO (First In First Out) principle, meaning the element inserted first is the element removed first. It is an ordered collection of elements in which insertion takes place at one end called the REAR and deletion takes place at the other end called the FRONT.

A queue can be compared to a real-life queue of people standing in a line -- the person who joins first gets served first.

FRONT                          REAR
  |                              |
  v                              v
[ 10 | 20 | 30 | 40 | 50 ]
  ^                              ^
(Deletion side)          (Insertion side)

2. Applications of Queue

Queues are widely used in computer science and real-life scenarios:

#	Application	Description
1	CPU Scheduling	Processes are scheduled for CPU execution in a queue (Round Robin, FCFS)
2	Printer Spooling	Print jobs are queued and processed one by one in order
3	Keyboard Buffer	Keystrokes are stored in a queue and processed in order
4	BFS (Breadth First Search)	Graph traversal uses a queue to visit nodes level by level
5	IO Buffers	Data transfer between processes uses queues as buffers
6	Simulation	Queues model real-world waiting lines (bank, ticket counter)
7	Network Packet Handling	Data packets are queued for transmission over a network
8	Operating System	Job scheduling, interrupt handling use queues

3. Queue Operations

The primary operations performed on a queue are:

3.1 Basic Operations

Operation	Description
Enqueue (Insert)	Add an element at the REAR of the queue
Dequeue (Delete)	Remove an element from the FRONT of the queue
IsEmpty	Check whether the queue is empty
IsFull	Check whether the queue is full
Peek / Front	Return the front element without removing it

3.2 Queue Declaration (Array-based)

#define MAXSIZE 5

struct queue {
    int items[MAXSIZE];
    int front;
    int rear;
};
typedef struct queue Q;

Initially: front = -1, rear = -1

3.3 IsEmpty Operation

int IsEmpty(Q *q) {
    if (q->front == -1)
        return 1;   // Queue is empty
    else
        return 0;
}

3.4 IsFull Operation

int IsFull(Q *q) {
    if (q->rear == MAXSIZE - 1)
        return 1;   // Queue is full
    else
        return 0;
}

3.5 Enqueue Operation

Algorithm:

Check if queue is full. If full, print overflow and exit.
If queue is empty, set front = 0.
Increment rear by 1.
Insert the new element at items[rear].

void Enqueue(Q *q, int newitem) {
    if (IsFull(q)) {
        printf("Queue Overflow! Cannot insert.");
        return;
    }
    if (IsEmpty(q))
        q->front = 0;
    q->rear = q->rear + 1;
    q->items[q->rear] = newitem;
    printf("%d inserted into queue.\n", newitem);
}

3.6 Dequeue Operation

Algorithm:

Check if queue is empty. If empty, print underflow and exit.
Store the front element.
If front == rear, reset both to -1 (queue becomes empty).
Otherwise, increment front by 1.
Return the stored element.

int Dequeue(Q *q) {
    int val;
    if (IsEmpty(q)) {
        printf("Queue Underflow! Cannot delete.");
        return -1;
    }
    val = q->items[q->front];
    if (q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front = q->front + 1;
    return val;
}

4. Worked Example

Perform the following operations on a queue of size 5: Enqueue(10), Enqueue(20), Enqueue(30), Dequeue(), Enqueue(40), Dequeue()

Step-by-step Trace:

Initial State:

front = -1,  rear = -1
Queue: [  |  |  |  |  ]

Step 1: Enqueue(10)

front = 0,  rear = 0
Queue: [ 10 |  |  |  |  ]

Step 2: Enqueue(20)

front = 0,  rear = 1
Queue: [ 10 | 20 |  |  |  ]

Step 3: Enqueue(30)

front = 0,  rear = 2
Queue: [ 10 | 20 | 30 |  |  ]

Step 4: Dequeue() --> returns 10

front = 1,  rear = 2
Queue: [  | 20 | 30 |  |  ]

Step 5: Enqueue(40)

front = 1,  rear = 3
Queue: [  | 20 | 30 | 40 |  ]

Step 6: Dequeue() --> returns 20

front = 2,  rear = 3
Queue: [  |  | 30 | 40 |  ]

Final State: front = 2, rear = 3, containing 30 and 40 in the queue.

Conclusion

The queue correctly follows FIFO order throughout this trace: the elements 10 and then 20 were removed in the same order they were inserted, and the two remaining elements, 30 and 40, stay in the array between the current front and rear indices, ready to be dequeued in that same order. This worked example, together with the array-based structure and the Enqueue/Dequeue/IsEmpty/IsFull operations defined above, completes the description of the queue data structure and its uses.

45 marksNumericalConversion from infix to postfix/prefix exHideAnswer
Evaluate the expression ABCD-x+ using stack where A=5, B=4, C=3 and D=7. [5]
Postfix expression: A B C D - x + where x denotes multiplication - Operand values: - $A = 5$ - $B = 4$ - $C = 3$ - $D = 7$ So the expression to evaluate is: A B C D - + --- - Scan left to right. - Operand → push onto stack. - Operator ...

Postfix expression: A B C D - x + where x denotes multiplication - Operand values: - $A = 5$ - $B = 4$ - $C = 3$ - $D = 7$ So the expression to evaluate is: A B C D - + --- - Scan left to right. - Operand → push onto stack. - Operator ...
55 marksFactorial, Fibonacci Sequence, GCD, Tower HideAnswer
Write a recursive program to find nth fibonacci number. [5]
Recursive Program to Find nth Fibonacci Number

Concept

The Fibonacci sequence is defined as:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) for n >= 2
This is a naturally recursive problem because the definition of F(n) directly refers to smaller instances of itself. Recursive solutions are well-suited for problems that are naturally recursive in structure.

Recurrence Relation
F(n) = F(n-1) + F(n-2)
Base cases:
F(0) = 0 F(1) = 1
Algorithm
Algorithm Fibonacci(n): if n == 0: return 0 else if n == 1: return 1 else: return Fibonacci(n-1) + Fibonacci(n-2)
C Program
#include <stdio.h> /* Recursive function to find nth Fibonacci number */ int fibonacci(int n) { /* Base cases */ if (n == 0) return 0; else if (n == 1) return 1; else /* Recursive case: F(n) = F(n-1) + F(n-2) */ return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n; printf("Enter the value of n: "); scanf("%d", &n); printf("Fibonacci(%d) = %d\n", n, fibonacci(n)); return 0; }
Dry Run (Trace) for n = 5
fibonacci(5) = fibonacci(4) + fibonacci(3) = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1)) = ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + 1) = ((1 + 1) + (1 + 0)) + ((1 + 0) + 1) = (2 + 1) + (1 + 1) = 3 + 2 = 5
So, F(5) = 5 which is correct (0, 1, 1, 2, 3, 5).

Sample Output
Enter the value of n: 5 Fibonacci(5) = 5
Complexity Analysis

Aspect Value
Time Complexity O(2^n) -- exponential due to overlapping subproblems
Space Complexity O(n) -- recursive call stack depth

Note: The recursive computation of Fibonacci numbers involves excessive costs due to overlapping subproblems (the same subproblems are computed multiple times). This is why it is not considered an efficient divide-and-conquer algorithm. Dynamic programming or memoization can reduce this to O(n).
65 marksBasic Concept, List and ADT, Array ImplemeHideAnswer
Explain array implementation of list. [5]
An array implementation of a list (also called an ArrayList) is a method of implementing a linear list using a one-dimensional array as the underlying storage structure. Elements are stored in contiguous (sequential) memory locations, an...
75 marksNumericalComparison Sorting AlgorithmsHideAnswer
Hand test selection sort with array of numbers 4, 71, 32, 19, 61, 2, -5 in descending order. [5]
Given data: - Array: $[4, 71, 32, 19, 61, 2, -5]$ - Number of elements: $n = 7$ - Sort order: Descending - Algorithm: Selection Sort --- Selection sort (descending): In each pass, find the largest element in the unsorted portion and swap...
Given data: - Array: $[4, 71, 32, 19, 61, 2, -5]$ - Number of elements: $n = 7$ - Sort order: Descending - Algorithm: Selection Sort --- Selection sort (descending): In each pass, find the largest element in the unsorted portion and swap...
85 marksIntroduction to Searching, Search AlgorithHideAnswer
Write a program to implement sequential search algorithm. [5]
Sequential search (also called linear search) is a method to search for an item in a data structure by checking each element one by one from the beginning until the target element is found or the list ends. --- --- --- Case Condition Tim...
95 marksDefinition and Representation of Graphs, GHideAnswer
What is graph traversal? Explain. [5]
Graph traversal (also called graph search) is the process of visiting (checking and/or updating) each vertex in a graph systematically, exactly once. It is a technique used to visit all the nodes of a graph in a specific order, ensuring ...
105 marksAsymptotic notations and common functionsHideAnswer
How do you find complexity of algorithms? Explain. [5]
The complexity of an algorithm is a measure of the amount of time and/or space required by an algorithm as a function of the size of the input. It helps us evaluate and compare algorithms in terms of their efficiency. --- Time complexity...
115 marksLinear Queue, Circular Queue, Priority QueHideAnswer
What is priority queue? Why do you need this type of queue? [5]
A priority queue is a special type of queue in which each element is assigned a priority value, and elements are processed (removed) according to their priority rather than their order of insertion (i.e., not strictly FIFO). - In an asce...
125 marksDivide and Conquer SortingHideAnswer
Write short notes on: a. Divide and Conquer sorting b. AVL Tree [5]
--- Divide and Conquer is an important problem-solving technique that makes use of recursion. It consists of two main parts: - Divide: The original problem is broken into smaller sub-problems, which are solved recursively. - Conquer: The...

Aspect	Value
Time Complexity	O(2^n) -- exponential due to overlapping subproblems
Space Complexity	O(n) -- recursive call stack depth

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081 paper 2080 paper 2079 paper 2077 paper 2075 paper 2074 paper