BCAMCABSc ITB.Tech CSE

Data Structures — syllabus, exam questions and lab programs

Your scheme may call it Data Structures & File Processing.

This is the most important paper in the whole degree, and it is not close. Everything a product company asks in an interview comes from here. Everything a service company asks in its written round comes from here. And it is the paper with the highest backlog rate in every batch we have taught, for one reason: it is taught as definitions to memorise when it is really a paper about drawing.

The subject is short to describe. You will meet about eight structures — array, stack, queue, linked list, tree, heap, graph, hash table — and for each one you answer three questions: how is it laid out in memory, what does it cost to insert, delete and search, and when would you choose it over the others. That is the whole paper.

If you are behind, do not start at the beginning. Start with linked lists, because they are the bridge from C to everything else, and because half the exam questions are a linked list wearing a different name. A stack is a linked list where you only touch one end. A queue is one where you touch both. A tree is one where each node points at two.

We teach this

Data Structures is one of the papers we teach at WebPrims

This is not only a page about Data Structures. It is a subject we teach in a classroom on Majitha Road — tuition for Data Structures, if that is the word you were searching for — and a good share of every batch is college students taking it alongside their own semester. Bring your scheme and we cover what is on it.

What that means in practice: the whole syllabus gets covered rather than the parts that make a good demo, you write code on a machine instead of copying it into a file, and the lab work gets done here rather than the night before submission.

What we will not say is that this guarantees you marks or a job. We do not run placements and we do not promise results. Come and sit in a class, decide for yourself.

₹4,500 / month— one rate, any subjectMon–Sat, batches at 11, 1, 3 and 5Majitha Road, Amritsar

The syllabus, unit by unit

What each unit actually contains, and whether it is there because it matters or because it is on the paper. Unit order and numbering vary between GNDU, PTU and your batch’s scheme — check your own before you plan a revision week.

1

Introduction, arrays and complexity

Primitive and non-primitive structures, linear versus non-linear, arrays in one and two dimensions, row-major and column-major address calculation, sparse matrices, and asymptotic notation — big O, omega and theta.

The address calculation formula is asked almost every year and takes ten minutes to learn. Big O you will use forever.

2

Stacks and their applications

Push, pop and peek, stack overflow and underflow, infix to postfix and prefix conversion, evaluating a postfix expression, checking balanced parentheses, and recursion as a stack.

Infix to postfix is guaranteed to appear. Learn the algorithm as a table you fill in, not as a paragraph.

3

Queues

Simple queue, the wasted-space problem, circular queue and the modulo trick, double-ended queue, priority queue, and queue implementation with arrays and with linked lists.

Why a circular queue exists is a favourite question. Draw the array with front and rear moving round it.

4

Linked lists

Singly, doubly and circular lists; insert at beginning, end and a given position; delete by value and by position; reverse a list; search; and the comparison against arrays.

The centre of the paper and of every interview. If you can reverse a singly linked list on paper without hesitating, you are ahead of most of your batch.

5

Trees

Terminology, binary tree, binary search tree, the three traversals with recursion and without, insertion and deletion in a BST, height and balance, AVL trees with the four rotations, and B-trees as an idea.

Traversals are free marks — practise until you can write all three from memory. AVL rotations look terrifying and are four fixed patterns.

6

Graphs

Representation as an adjacency matrix and adjacency list, breadth-first and depth-first search, spanning trees, Prim's and Kruskal's algorithms, and Dijkstra's shortest path.

Usually the last unit and the least revised, so the questions are often the easiest marks on the paper.

7

Searching, sorting and hashing

Linear and binary search; bubble, selection, insertion, merge and quick sort with their best, average and worst cases; hash functions; and collision handling by chaining and by open addressing.

Know the complexity table cold. Quick sort's worst case being O(n squared) on already-sorted data is asked constantly.

8

File processing

Sequential, indexed sequential, direct and relative file organisation, the idea of an index, and external sorting on files too large for memory.

Dry, and in the syllabus because databases need it. Two or three definitions carry the whole unit.

What is worth keeping after the exam

Revise all of it — the marks are the marks. But it is worth knowing which half of this paper you will still be using in two years, and which half exists because it is on the paper.

Stays with you

  • +Complexity — the ability to say a piece of code will not survive ten thousand rows before you write it
  • +Linked lists, trees and hash tables, which are the backbone of every interview you will sit
  • +Knowing which structure to reach for, which is the actual skill this paper is trying to teach
  • +Graph traversal, which turns up anywhere there is a network, a map or a dependency

For the exam, and then gone

  • −Row-major address calculation with a base address — pure exam arithmetic
  • −Writing sorting algorithms by hand; in real work you call the library's sort
  • −Sparse matrix triplet representation, unless you end up in scientific computing
  • −The file organisation unit, which a database course covers properly later

Questions that come up year after year

Not a guess paper, and not a promise about what will be set. These are the questions this subject keeps asking because they are the ones that test whether you understood it.

  1. 01Convert an infix expression to postfix, showing the stack at each step
  2. 02Write an algorithm to reverse a singly linked list
  3. 03Insert and delete a node in a binary search tree, with diagrams
  4. 04Compare the time complexity of quick sort, merge sort and bubble sort
  5. 05Explain collision resolution in hashing with an example
  6. 06Traverse a given binary tree in inorder, preorder and postorder
  7. 07Difference between an array and a linked list
  8. 08Write a program for a circular queue using an array

What students get wrong

From teaching this paper, not from a list somewhere. Each of these costs marks every year.

Wrong — Learning the definitions of all eight structures and none of the operations.

Right — Papers ask you to do things, not to define them. For every structure, be able to draw an insert and a delete. Definitions carry two marks; the operations carry ten.

Wrong — Writing linked list code without drawing the pointers first.

Right — Draw the boxes and arrows, decide the order of the reassignments, then write the code. Almost every wrong linked-list answer is two statements in the wrong order — and a diagram makes that order obvious.

Wrong — Saying quick sort is faster than merge sort, full stop.

Right — Quick sort is usually faster in practice and O(n squared) in the worst case; merge sort is always O(n log n) but needs extra space. The examiner is looking for the trade-off, not for a winner.

Wrong — Losing the head of a linked list while reversing it, then not noticing.

Right — Keep three pointers — previous, current and next — and set next before you touch current's link. If you only keep two, the rest of the list is gone the moment you reverse the first pointer.

Lab file programs

These compile and run as written — type them in, break them, and fix them. Copying a program into a file you never ran is how a practical viva goes badly.

Reverse a singly linked list

The most asked question in this paper and in interviews. Three pointers, one pass.

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

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

struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL;
    struct Node *curr = head;
    struct Node *next = NULL;

    while (curr != NULL) {
        next = curr->next;   /* save it before we overwrite the link */
        curr->next = prev;   /* turn the arrow round */
        prev = curr;         /* shuffle both pointers forward */
        curr = next;
    }
    return prev;             /* prev is the old tail, now the head */
}

struct Node *push(struct Node *head, int value) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = value;
    n->next = head;
    return n;
}

void print(struct Node *head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main(void) {
    struct Node *head = NULL;
    int i;

    for (i = 5; i >= 1; i--) {
        head = push(head, i);
    }

    printf("Before:  ");
    print(head);
    head = reverse(head);
    printf("After:   ");
    print(head);
    return 0;
}

Circular queue using an array

Shows why the modulo is there. Handles full and empty correctly, which is where marks go.

c
#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

int isFull(void) {
    return (rear + 1) % SIZE == front;
}

int isEmpty(void) {
    return front == -1;
}

void enqueue(int value) {
    if (isFull()) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty()) {
        front = 0;
    }
    rear = (rear + 1) % SIZE;
    queue[rear] = value;
    printf("Inserted %d\n", value);
}

void dequeue(void) {
    if (isEmpty()) {
        printf("Queue is empty\n");
        return;
    }
    printf("Removed %d\n", queue[front]);
    if (front == rear) {
        front = rear = -1;          /* the queue just became empty */
    } else {
        front = (front + 1) % SIZE;
    }
}

int main(void) {
    enqueue(10); enqueue(20); enqueue(30);
    dequeue();
    enqueue(40); enqueue(50); enqueue(60);
    return 0;
}

Binary search tree — insert and inorder traversal

Inorder on a BST prints the values in sorted order, which is the point of the structure.

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node *insert(struct Node *root, int value) {
    if (root == NULL) {
        struct Node *n = malloc(sizeof(struct Node));
        n->data = value;
        n->left = n->right = NULL;
        return n;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;                    /* duplicates ignored */
}

void inorder(struct Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main(void) {
    struct Node *root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    int i;

    for (i = 0; i < 7; i++) {
        root = insert(root, values[i]);
    }

    printf("Inorder: ");
    inorder(root);
    printf("\n");
    return 0;
}

Long questions, answered the way they are marked

Not model answers to reproduce. What the examiner is checking for, and where the marks actually sit in each one.

Convert the infix expression A + B * C - D / E into postfix, showing the stack.

Answer: A B C * + D E / -. Show the table — three columns, symbol read, stack contents, output so far — and fill a row for every character. Examiners give most of the marks for the working, so a correct answer with no table scores worse than a slightly wrong one with a complete table. The rules to state first: operands go straight to output; an operator pops everything of higher or equal precedence before it is pushed; a closing bracket pops until the opening one.

Compare arrays and linked lists.

Memory: an array is one contiguous block, a list is scattered nodes joined by pointers. Size: fixed at declaration versus grown at run time. Access: an array reaches element n in constant time, a list has to walk there. Insert and delete in the middle: an array shifts everything after it, a list rewires two pointers. Extra cost: a list pays a pointer per node. Finish with the judgement — arrays when you mostly read by index, lists when you mostly insert and delete.

What is hashing? Explain collision and how it is resolved.

Hashing maps a key to an array index through a hash function, so a lookup is constant time instead of a search. A collision is two keys landing on the same index, which is unavoidable once there are more possible keys than slots. Two families of answer: chaining, where each slot holds a linked list of everything that landed there; and open addressing, where you probe for another free slot — linear probing, quadratic probing, or double hashing. Mention the load factor and that performance degrades as the table fills; that sentence is usually worth a mark on its own.

Write the time complexity of common sorting algorithms.

Bubble, selection and insertion: O(n squared) average and worst; insertion is O(n) on nearly sorted data. Merge sort: O(n log n) in all three cases, O(n) extra space, stable. Quick sort: O(n log n) average, O(n squared) worst when the pivot is always the smallest or largest element — which is what happens on already-sorted input with a naive pivot. Heap sort: O(n log n) always, in place, not stable. Draw it as a table with best, average, worst and space columns; that is what the examiner is looking for.

Difference between — the ones that get asked

Every one of these is a five-mark question somewhere on this syllabus, and the marks are rarely in the first line. They are in the consequences underneath it.

Singly vs Doubly linked list

A singly linked node knows the next node. A doubly linked node knows the next and the previous. The second pointer costs memory and buys backward traversal and cheap deletion.

 Singly linkedDoubly linked
Pointers per nodeOne — next.Two — next and prev.
TraversalForward only.Both directions.
Delete a node you have a pointer toO(n) — you must walk from the head to find the one before it.O(1) — the previous node is right there.
Memory per nodeLess.One extra pointer per node.
Insert before a known nodeNeeds the predecessor, so O(n).O(1).
ReversalNeeds three pointers and care.Swap next and prev on each node.

Where people lose the marks

In the exam, draw the nodes as boxes with arrows before you write a word. Half of the marks in a linked-list question are for a correct diagram, and every pointer bug you will ever write becomes visible the moment you draw it.

BFS vs DFS

BFS explores level by level using a queue. DFS goes as deep as it can before backtracking, using a stack or recursion. The data structure is the whole difference.

 BFSDFS
Data structureQueue — first in, first out.Stack, or the call stack via recursion.
OrderAll neighbours, then their neighbours.One path to the end, then back up and try the next.
Shortest path in an unweighted graphYes — the first time you reach a node is by the shortest route.No guarantee.
SpaceO(width) — can be large on a wide graph.O(depth) — can be large on a deep one.
TimeO(V + E)O(V + E)
Good forShortest path, level order, nearest-first searches.Cycle detection, topological sort, maze and backtracking problems.

Where people lose the marks

Both visit every node once, so the time complexity is identical — the difference is the order and the memory profile. If you only remember one thing: BFS uses a queue and finds the shortest path; DFS uses a stack and does not.

Array vs Linked list

An array is one contiguous block, so any element is one calculation away. A linked list is scattered nodes joined by pointers, so reaching element n means walking n steps.

 ArrayLinked list
Memory layoutContiguous.Scattered, joined by pointers.
Access element nO(1) — the address is arithmetic.O(n) — walk from the head.
Insert or delete at the frontO(n) — everything shifts.O(1) — repoint the head.
SizeFixed at creation in C; a dynamic array reallocates.Grows and shrinks one node at a time.
Extra memoryNone beyond the data.One or two pointers per node.
Cache behaviourExcellent — neighbours are physically adjacent.Poor — every node may be a cache miss.

Where people lose the marks

The cache row is the one textbooks skip and real performance depends on. For small n, an array usually beats a linked list even on operations where the complexity table says the opposite, because the array is actually in cache.

General tree vs Binary tree

A general tree lets a node have any number of children. A binary tree caps it at two, which is what makes the standard traversals and the search tree possible.

 General treeBinary tree
Children per nodeAny number.At most two — left and right.
Ordering of childrenNo inherent left or right.Left and right are distinct and meaningful.
TraversalsLevel order and depth first, but no standard inorder.Preorder, inorder, postorder, level order.
RepresentationA list of child pointers per node.Two pointers, or an array using 2i+1 and 2i+2.
Used forFile systems, organisation charts, XML and HTML trees.Search trees, heaps, expression trees, Huffman coding.

Where people lose the marks

Inorder traversal only has a meaning on a binary tree, because it needs a left and a right to sit between. That is usually the follow-up question, and it is the cleanest way to show you understood the difference rather than memorised it.

Multiple choice, with the reason

Universities set an objective section and campus written rounds are almost nothing else. The answer is marked, and every one of them says why — an answer key you can only memorise is worth nothing in a viva.

  1. 01

    What is the time complexity of searching for an element in a balanced binary search tree?

    • aO(1)
    • bO(log n)
    • cO(n)
    • dO(n log n)

    Why — Each comparison discards half the remaining tree. The word balanced matters: in a degenerate BST — values inserted already sorted — it becomes a linked list and the search is O(n).

  2. 02

    Which data structure is used to convert an infix expression to postfix?

    • aQueue
    • bStack
    • cLinked list
    • dBinary tree

    Why — Operators wait on a stack until something of lower precedence arrives. The same structure handles bracket matching and the function call stack, which is the deeper point.

  3. 03

    In the worst case, quick sort runs in:

    • aO(n log n)
    • bO(n)
    • cO(n squared)
    • dO(log n)

    Why — When every pivot turns out to be the smallest or largest element — classically, already-sorted input with a naive first-element pivot — each partition removes one item instead of half.

  4. 04

    A circular queue of size n is considered full when:

    • arear == n - 1
    • bfront == rear
    • c(rear + 1) % n == front
    • drear == front - 1

    Why — The modulo is what makes it circular. One slot is deliberately left unused so that full and empty can be told apart; without that, front == rear would mean both.

  5. 05

    Which traversal of a binary search tree outputs the values in sorted order?

    • aPreorder
    • bInorder
    • cPostorder
    • dLevel order

    Why — Inorder visits left, root, right — and in a BST everything on the left is smaller and everything on the right is larger. This property is the reason a BST is worth building.

  6. 06

    What is the minimum number of pointers you need to reverse a singly linked list in one pass?

    • aOne
    • bTwo
    • cThree
    • dFour

    Why — Previous, current and next. With only two, reversing current's link loses the rest of the list, because nothing is still pointing at it.

  7. 07

    Which of these is NOT a method of collision resolution in hashing?

    • aSeparate chaining
    • bLinear probing
    • cDouble hashing
    • dBinary partitioning

    Why — Binary partitioning is not a hashing technique. The real families are chaining, where each slot holds a list, and open addressing, which includes linear probing, quadratic probing and double hashing.

  8. 08

    A stack is used to implement recursion because it provides:

    • aRandom access
    • bFirst in, first out order
    • cLast in, first out order
    • dConstant time search

    Why — The most recent call must finish first, which is exactly last in, first out. Every recursive program can be rewritten iteratively using an explicit stack, and that is a common long question.

Viva questions, and what a good answer sounds like

GNDU’s own scheme says the viva runs one-to-one beside the practical exam, about the code you are writing at that moment. These are the questions that get asked, and what the examiner is listening for in the reply.

“Why would you choose a linked list over an array?”

When the size is not known in advance, or when inserting and deleting in the middle is frequent — a list rewires two pointers where an array shifts every element after the gap. You give up constant-time access by index for it.

“Your BST search is O(n). What went wrong?”

The tree is unbalanced, almost certainly because the values went in already sorted, so every node has one child and it degenerated into a linked list. AVL or red-black trees exist to stop exactly that.

“Draw what happens to the pointers when you delete the middle node of a doubly linked list.”

The previous node's next must point past the deleted node, and the following node's prev must point back before it — two reassignments, and the order does not matter here because both neighbours are still reachable. Then free the node.

“Is a stack always implemented with an array?”

No. An array stack is fixed in size and can overflow; a linked stack grows until memory runs out but pays a pointer per node. The operations and their complexity are identical either way.

“What is the load factor of a hash table and why does it matter?”

The number of stored entries divided by the number of slots. As it rises, collisions rise and lookups drift from constant time towards linear — which is why a table is resized and rehashed once it passes a threshold.

“Explain your sorting choice in this program.”

The answer the examiner wants names a trade-off rather than a favourite: merge sort when worst-case time matters and extra memory is available, quick sort when average speed matters and memory does not, insertion sort when the data is small or nearly sorted.

Past the syllabus

Your paper stops somewhere, and a job interview does not. If you want the version of this subject that goes further than the scheme asks for, there is a full course for it.

CallWhatsAppFree demo