GATE CS & DA Preparation Guide Module 6 – Programming, data structures and algorithms (CS sections 4-5; DA section 4)

Programming in C and data structures (GATE CS)

Trace C programs on recursion, pointers and strings, and count stack, tree and heap states the way GATE CS section 4 asks, with every output recorded.

Intermediate
25 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Clang 21.0.0 and GCC 16.2.0
By MySmartCoPilot

Free: Two shapes of question, and one method for both · A static local is shared by every call · Pointer steps and sizes follow the type · 2 more sections. With a pass: 2 in-depth parts and 3 interview answers, about 16 minutes.

What you will learn

Trace recursive C functions and count calls, returns and printed output
Predict what exam-style programs do with pointers, arrays, strings, scope and storage classes
Answer counting questions on stacks, queues, linked lists, BSTs, heaps and graph representations

Before you start

MCQ, MSQ and NAT: GATE marking and when to guess

What you’ll learn · Before you start

What you will learn

Trace recursive C functions and count calls, returns and printed output
Predict what exam-style programs do with pointers, arrays, strings, scope and storage classes
Answer counting questions on stacks, queues, linked lists, BSTs, heaps and graph representations

Before you start

MCQ, MSQ and NAT: GATE marking and when to guess

On this page

A recursive C function with a static counter is called twice and prints 15, then 30, where a quick reading predicts 15 both times. Questions like that fill section 4 of the GATE CS syllabus, which is one line long: “Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.”

Its questions come in two shapes. Programming in C is examined by tracing: you are given a short program and report what it prints, or how many times a function runs. The data structures are examined by counting: the array after some heap insertions, the orders a stack can produce, the shape of a binary search tree. Both reward a slow written trace over intuition. Below are the method and five solved examples, each with a figure to step through.

Two shapes of question, and one method for both

What each family asks for, and the trap in it:

Family	What you report	Watch for
Recursion	printed values, the number of calls	static and global variables
Pointers and arrays	values reached through pointers, byte offsets	the row size of a 2-D array
Strings	lengths, sizes, changed text	`sizeof` against `strlen`, literals
Stacks and queues	contents after operations, possible orders	the full and empty tests
Linked lists	the list after pointer changes	a lost head, the final NULL
Trees and BSTs	traversal orders, shapes, heights	the order of insertion
Heaps	the array after insertions or deletions	indices from 0 or from 1
Graphs	the size of a representation	matrix against lists

Trace on paper. Give every call a row with its parameters and locals, and keep one row for each static or global variable, which every call shares.
Check that the program is valid C. A program with undefined behaviour: Behaviour for which the C standard sets no requirement at all, such as writing into a string literal. A program that has it has no single correct output, so an exam question about it has no value to trace towards., such as one that changes a string literal, has no correct output, so no amount of tracing finds one.
Count from small cases. For questions on data structures, work out n = 1, 2 and 3 by hand and match the pattern with a formula you know: A sequence of whole numbers that counts, among other things, the orders a stack can give when 1 to n are pushed in order and the shapes of binary search trees on n keys. count stack orders and BST shapes, and heaps have exact index formulas.

Every program here was compiled under C17 with -Wall -Wextra by clang 21, with the address and undefined-behaviour sanitizers, and by GCC 16, assuming a 4-byte int and 8-byte pointers. Both compilers agreed on the five programs below.

Checkpoint

Check: Trace, check, count

Question 1 of 2 An exam program writes into a string literal and then prints it. Following step 2 of the method, what do you report?
Choose one answer.

The changed string, since the program compiles That it has no single correct output, because changing a literal is undefined behaviour The original string, since a literal cannot change A compile error

Show the answer: Question 1 of 2

Answer: That it has no single correct output, because changing a literal is undefined behaviour

A string literal must never be modified, and a program that does it has undefined behaviour: the standard places no requirement on what it does. That is why step 2 comes before any tracing: such a program has no correct output to trace towards.
Question 2 of 2 You trace a recursive function int f(int n) that declares static int seen; and int t;, and also changes a global int total. Which variables get one row for the whole trace, instead of a row in every call? Choose every right answer.
Choose every answer that is right.

total, the global n, the parameter t, the ordinary local seen, the static local
Show the answer: Question 2 of 2
Answer:
- total, the global
- seen, the static local
Parameters and ordinary locals belong to one call, so each call's row holds its own. Static locals and globals exist once for the whole program, so they get one row that every call changes, and that row is where most printed values come from.

A static local is shared by every call

static_calls.c C · static_calls.c

/* A static local variable is set to 0 once, before the program starts, and keeps its value between calls. */
#include <stdio.h>

int count(int n) {
    static int calls = 0;
    calls++;
    if (n > 1) {
        count(n - 1);
        count(n - 2);
    }
    return calls;
}

int main(void) {
    printf("%d\n", count(5));
    printf("%d\n", count(5));
    return 0;
}

Both compilers, sanitizers on for clang Python · static_calls_session.py

from cc import both

both("static_calls.c")

Output

$ clang -std=c17 -Wall -Wextra -fsanitize=address,undefined static_calls.c -o ./static_calls-clang
$ ./static_calls-clang
15
30
$ gcc-16 -std=c17 -Wall -Wextra static_calls.c -o ./static_calls-gcc
$ ./static_calls-gcc
15
30

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 static_calls_session.py

calls is a static local variable: A variable declared static inside a C function. It is created and set once, before the program starts, and every call of the function shares it, while ordinary locals and parameters are new in each call.: it is created once and shared by every call, while each call gets its own n. Each call adds 1, and a call with n > 1 makes two more, so the number of calls obeys C(n) = 1 + C(n − 1) + C(n − 2) with C(1) = C(0) = 1, which gives 15 for count(5). The second call from main carries on from 15 and prints 30. Step through the nine calls of count(4), the tree below: the frames come and go, and the one counter keeps counting.

count(4) makes 9 calls, so the static counter ends at 9

Text description of the diagram

The tree has count(4) at the top, as call 1. Each call with n greater than 1 has two children: count(n - 1) on the left and count(n - 2) on the right.

count(4), call 1, calls count(3) and count(2).
count(3), call 2, calls count(2), call 3, and count(1), call 6.
count(2), call 3, calls count(1), call 4, and count(0), call 5.
count(2), call 7, the right child of count(4), calls count(1), call 8, and count(0), call 9.

The leaves are the calls with n equal to 1 or 0, which make no further calls. The calls are numbered in the order they start, which is the order a depth-first walk visits them, left child first. There are 9 calls in all, so after count(4) the static counter holds 9.

Interactive · step by step count(4), one call at a time Step through the calls. The frames on the left come and go with the calls; the static counter on the right is one variable that every call adds 1 to.

The drawing shows the whole scene; its 12 steps are listed below.

Every step as text

Before the first call. The static counter exists before main runs, and it is set to 0 once. No call of count has a frame yet.
Call 1, count(4). main calls count(4). The call gets a frame with its own n = 4, adds 1 to the shared counter, and, since 4 > 1, will call count(3) and then count(2).
Call 2, count(3). count(3) gets a new frame one level deeper, with its own n = 3. The counter is not new, it is the same variable, and it becomes 2.
Call 3, count(2). count(3) calls count(2) first. Three frames are now live, each with its own n, and the one counter reads 3.
Call 4, count(1). count(2) calls count(1). With n = 1 the test n > 1 fails, so this call only adds 1, making 4, and returns.
Call 5, count(0). The frame of count(1) is gone, and count(2) makes its second call, count(0), at the same depth. It adds 1 and returns at once.
Call 6, count(1). count(0) and then count(2) return. Back in count(3), the second call is count(1), at depth 2. The counter carries on from 5 to 6.
Call 7, count(2). count(1) and count(3) return, and count(4) makes its second call, count(2), at depth 1. The counter reads 7.
Call 8, count(1). This count(2) calls count(1) at depth 2, which adds 1 and returns.
Call 9, count(0). Its second call, count(0), takes the counter to 9. That is the last of the nine calls in the recursion tree.
Every frame is gone. count(2) and then count(4) return. count(4) returns the value the counter holds then, 9, and main prints it. Every frame is gone; the counter stays.
A second call from main. Nothing sets the counter back to 0, so a second count(4) from main would start from 9, add 9 more and print 18. That is why the lesson's program prints 15 and then 30 for count(5).

The figure’s last step is the trap: nothing resets the counter.

Checkpoint

Check: Static locals in recursion

Question 1 of 2 In the figure, main calls count(4) once. What does count(4) return?
Type a number.
Your answer

Show the answer: Question 1 of 2

Answer: 9

count(4) makes 9 calls, the nine boxes of the tree, and each one adds 1 to the one static counter. count(4) returns the counter after its two calls have finished, so it returns 9.
Question 2 of 2 Suppose calls lost its static and became an ordinary local, int calls = 0;. What would main print for its two calls of count(5)?
Choose one answer.

0 and 0 15 and 30 15 and 15 1 and 1

Show the answer: Question 2 of 2

Answer: 1 and 1

An ordinary local is created afresh in every call. The top call of count(5) sets its own calls to 0, adds 1 and returns 1, whatever its recursive calls did in their own frames, and the second call from main does the same.

Pointer steps and sizes follow the type

array_2d.c C · array_2d.c

/* A 2-D array is an array of rows: a + 1 steps over a whole row, *a + 1 over one int. */
#include <stdio.h>

int main(void) {
    int a[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    printf("%d %d %d\n", *(*(a + 1) + 2), *(a[2] + 3), (*a)[1]);
    printf("%td %td\n", (char *)(a + 1) - (char *)a, (char *)(*a + 1) - (char *)*a);
    printf("%zu %zu %zu\n", sizeof a, sizeof a[0], sizeof **a);
    return 0;
}

Rows, elements and sizes Python · array_2d_session.py

from cc import both

both("array_2d.c")

Output

$ clang -std=c17 -Wall -Wextra -fsanitize=address,undefined array_2d.c -o ./array_2d-clang
$ ./array_2d-clang
7 12 2
16 4
48 16 4
$ gcc-16 -std=c17 -Wall -Wextra array_2d.c -o ./array_2d-gcc
$ ./array_2d-gcc
7 12 2
16 4
48 16 4

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 array_2d_session.py

a array decay: In most C expressions an array name turns into a pointer to its first element. For int a[3][4] the first element is a row, so a becomes a pointer to a row of 4 ints and a + 1 steps a whole row. to a pointer to its first row, so a + 1 moves a whole row of four ints, 16 bytes, while *a + 1 moves one int, 4 bytes. Because x[i] means *(x + i), *(*(a + 1) + 2) is a[1][2], which is 7, and *(a[2] + 3) is a[2][3], which is 12. The sizes follow the same rule: 48 bytes for the array, 16 for a row, 4 for an element. Step through the first expression, one operator at a time:

Interactive · step by step Evaluating *(*(a + 1) + 2) in int a[3][4] Step through the expression from the inside out. Each step is one operator, and the right-hand boxes say where the pointer is and what it points to.

The drawing shows the whole scene; its 8 steps are listed below.

Every step as text

Three rows of four. int a[3][4] is an array of 3 rows, each an array of 4 ints. With a 4-byte int a row is 16 bytes and the whole array 48, which is what sizeof a, sizeof a[0] and sizeof **a print.
a is a pointer to row 0. In an expression, a decays to a pointer to its first element, and its first element is row 0, an array of 4 ints. So the pointer's type is pointer to a row.
a + 1 steps one row. Adding 1 to a pointer moves it by the size of what it points to. That is a whole row here, so a + 1 is 16 bytes on, at row 1.
*(a + 1) is row 1. *(a + 1) is row 1 itself, an array of 4 ints. Used in an expression it decays in turn, to a pointer to its first int, the 5.
+ 2 steps two ints. Now the pointer points to an int, so adding 2 moves it by 2 ints, 8 bytes, from the 5 to the 7 at byte 24.
The last * reads 7. The outer * reads the int there, 7. Because x[i] means (x + i), the same element is also a[1][2], (a[1] + 2) and (*(a + 1))[2].
*a + 1 steps one int. *a is row 0, which decays to a pointer to its first int, so *a + 1 moves 4 bytes, one int. The program prints 16 for the step of a + 1 and 4 for the step of *a + 1.
*(a[2] + 3) is 12. a[2] is row 2, which decays to a pointer to the 9. Three ints on is the last element, so *(a[2] + 3) is a[2][3], which is 12.

strings.c C · strings.c

/* An array initialised from a string is a copy you may change; a string literal must never be changed. */
#include <stdio.h>
#include <string.h>

void reverse(char *s) {
    size_t n = strlen(s);
    for (size_t i = 0; i < n / 2; i++) {
        char t = s[i];
        s[i] = s[n - 1 - i];
        s[n - 1 - i] = t;
    }
}

int main(void) {
    char word[] = "GATE2027";
    const char *lit = "GATE2027";
    printf("%zu %zu %zu\n", sizeof word, strlen(word), sizeof lit);
    reverse(word);
    printf("%s %s\n", word, lit);
    printf("%c %d\n", *(lit + 4), lit[8]);
    return 0;
}

An array you may change, a literal you may not Python · strings_session.py

from cc import both

both("strings.c")

Output

$ clang -std=c17 -Wall -Wextra -fsanitize=address,undefined strings.c -o ./strings-clang
$ ./strings-clang
9 8 8
7202ETAG GATE2027
2 0
$ gcc-16 -std=c17 -Wall -Wextra strings.c -o ./strings-gcc
$ ./strings-gcc
9 8 8
7202ETAG GATE2027
2 0

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 strings_session.py

word is an array of 9 bytes, eight characters and the null character: The character with code 0, written '\0', that ends every C string. strlen counts the characters before it, while sizeof of a char array counts it too., and the program may change it. lit is a pointer, 8 bytes, to a literal that must never be changed. strlen stops at the null character, so it reports 8. Called on lit, reverse would change a literal, and the behaviour would be undefined. The figure sets them side by side:

Interactive · step by step An array you may change, a literal you may not Step through the declarations and each line the program prints. The left column is the array the program owns; the right column is the pointer and the literal it points to.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

A copy in an array. word is an array of 9 chars, sized by its initialiser. It holds a copy of the literal's 8 characters and the null character that ends every string, and the program may change it.
A pointer to the literal. lit is not an array but a pointer, which holds the address of the literal's own characters. Writing through it would change a string literal, which the program must never do, and const makes the compiler reject a direct write such as lit[0] = 'g'.
9 8 8. sizeof word counts the whole array, 9 bytes with the null character. strlen(word) counts the characters before the null, 8. sizeof lit is the size of a pointer, 8 bytes on this 64-bit system.
reverse changes the copy. reverse(word) swaps characters inside the array, which belongs to the program, so word now reads 7202ETAG. The literal is untouched, and lit still prints GATE2027.
2 and 0. lit + 4 points to the fifth character, so *(lit + 4) is the 2. lit[8] is the null character itself, which printf with %d shows as 0.
A call that has no answer. reverse(lit) would write into the literal. The behaviour would be undefined, so there would be no right output at all, which is why reverse is only ever called on the array.

Checkpoint

Check: Pointer steps, sizes and strings

Question 1 of 2 For the program's array, int a[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, what is ((a + 2) + 1)?
Type a number.
Your answer

A hint

Step through it as the figure does, from the inside out.

Show the answer: Question 1 of 2

Answer: 10

a + 2 steps two rows on, to row 2. * gives that row, which decays to a pointer to its first int, 9, and + 1 steps one int, to 10. The expression is a[2][1].
Question 2 of 2 In the strings program, const char *lit = "GATE2027";. What is sizeof lit on the lesson's 64-bit system?
Choose one answer.

8, because the literal has 8 characters 9, the literal with its null character 8, the size of a pointer 4, the size of an int

Show the answer: Question 2 of 2

Answer: 8, the size of a pointer

sizeof applied to a pointer gives the size of the pointer, 8 bytes here, whatever it points to. The program printed 9 8 8: the array's 9 bytes, strlen's 8 characters and the pointer's 8 bytes.

A heap insertion climbs; a list reversal turns each pointer once

heap_insert.c C · heap_insert.c

/* Inserting keys one by one into a max-heap stored in an array from index 0: parent of i is (i - 1) / 2. */
#include <stdio.h>

int main(void) {
    int keys[] = {30, 15, 40, 10, 50, 35};
    int h[6];
    int n = 0;
    for (int k = 0; k < 6; k++) {
        int i = n++;
        int swaps = 0;
        h[i] = keys[k];
        while (i > 0 && h[(i - 1) / 2] < h[i]) {
            int p = (i - 1) / 2;
            int t = h[p];
            h[p] = h[i];
            h[i] = t;
            i = p;
            swaps++;
        }
        printf("insert %d, %d swap(s):", keys[k], swaps);
        for (int j = 0; j < n; j++) printf(" %d", h[j]);
        printf("\n");
    }
    return 0;
}

Six insertions into a max-heap Python · heap_insert_session.py

from cc import both

both("heap_insert.c")

Output

$ clang -std=c17 -Wall -Wextra -fsanitize=address,undefined heap_insert.c -o ./heap_insert-clang
$ ./heap_insert-clang
insert 30, 0 swap(s): 30
insert 15, 0 swap(s): 30 15
insert 40, 1 swap(s): 40 15 30
insert 10, 0 swap(s): 40 15 30 10
insert 50, 2 swap(s): 50 40 30 10 15
insert 35, 1 swap(s): 50 40 35 10 15 30
$ gcc-16 -std=c17 -Wall -Wextra heap_insert.c -o ./heap_insert-gcc
$ ./heap_insert-gcc
insert 30, 0 swap(s): 30
insert 15, 0 swap(s): 30 15
insert 40, 1 swap(s): 40 15 30
insert 10, 0 swap(s): 40 15 30 10
insert 50, 2 swap(s): 50 40 30 10 15
insert 35, 1 swap(s): 50 40 35 10 15 30

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 heap_insert_session.py

In a max-heap: A complete binary tree, usually stored in an array, in which every parent's key is at least as large as its children's keys, so the largest key is at the root., each key goes to the end of the array and swaps with its parent, at (i − 1)/2, while it is the larger. 40 climbs one level, 50 climbs two and 35 one, so the final array is 50, 40, 35, 10, 15, 30 after 4 swaps. A heap stored from index 1 has its parent at i/2 and its children at 2i and 2i + 1, so check which one a question uses. The six insertions, on the tree the array stores:

Interactive · step by step Inserting 30, 15, 40, 10, 50, 35 into a max-heap Step through the six insertions. Each new key goes into the next free position, then swaps with its parent while it is the larger. The boxes are array positions, drawn where they sit in the tree.

The drawing shows the whole scene; its 11 steps are listed below.

Every step as text

Insert 30. The heap is empty, so 30 goes to a[0], the root. A key with no parent has nothing to swap with.
Insert 15. The next free position is a[1], the left child of the root. Its parent, a[(1 − 1) / 2] = a[0], holds 30, which is larger, so 15 stays. No swap.
Insert 40. 40 goes to a[2], whose parent is a[0]. 40 is larger than 30, which breaks the heap rule.
40 climbs to the root. 40 and 30 swap, the first swap. 40 is now at the root, with no parent left to compare with. The array reads 40, 15, 30.
Insert 10. 10 goes to a[3], the left child of a[1]. Its parent holds 15, which is larger, so 10 stays where it is.
Insert 50. 50 goes to a[4], whose parent is a[(4 − 1) / 2] = a[1], holding 15. 50 is larger, so they swap.
50 swaps with 15. The second swap moves 50 up to a[1] and 15 down to a[4]. Now 50's parent is the root, 40, which is smaller.
50 reaches the root. The third swap puts 50 at the root and 40 at a[1]. 50 climbed two levels, the whole height of this tree.
Insert 35. 35 goes to a[5], whose parent is a[2], holding 30. 35 is larger, so they swap, the fourth swap.
35 stops below 50. 35 is now at a[2] and 30 at a[5]. Its new parent is the root, 50, which is larger, so the climb stops after one level.
50 40 35 10 15 30. Read by position, the array is 50, 40, 35, 10, 15, 30, after 4 swaps in all, as the program printed. Every parent is at least as large as its children, so the largest key, 50, is at the root.

reverse_list.c C · reverse_list.c

/* Reversing a singly linked list in place: each node's next pointer is turned round exactly once. */
#include <stdio.h>
#include <stdlib.h>

struct node {
    int key;
    struct node *next;
};

static struct node *push(struct node *head, int key) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->key = key;
    n->next = head;
    return n;
}

static void print(const struct node *p) {
    for (; p != NULL; p = p->next) printf(p->next ? "%d -> " : "%d\n", p->key);
}

static struct node *reverse(struct node *head, int *changed) {
    struct node *prev = NULL;
    while (head != NULL) {
        struct node *next = head->next;
        head->next = prev;
        (*changed)++;
        prev = head;
        head = next;
    }
    return prev;
}

int main(void) {
    struct node *list = NULL;
    int changed = 0;
    for (int k = 5; k >= 1; k--) list = push(list, 10 * k);
    print(list);
    list = reverse(list, &changed);
    print(list);
    printf("next pointers changed: %d\n", changed);
    while (list != NULL) {
        struct node *next = list->next;
        free(list);
        list = next;
    }
    return 0;
}

Five nodes turned round Python · reverse_list_session.py

from cc import both

both("reverse_list.c")

Output

$ clang -std=c17 -Wall -Wextra -fsanitize=address,undefined reverse_list.c -o ./reverse_list-clang
$ ./reverse_list-clang
10 -> 20 -> 30 -> 40 -> 50
50 -> 40 -> 30 -> 20 -> 10
next pointers changed: 5
$ gcc-16 -std=c17 -Wall -Wextra reverse_list.c -o ./reverse_list-gcc
$ ./reverse_list-gcc
10 -> 20 -> 30 -> 40 -> 50
50 -> 40 -> 30 -> 20 -> 10
next pointers changed: 5

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 reverse_list_session.py

The loop keeps three pointers: prev for the part already reversed, head for the node being turned round, and next, saved before the turn so that the rest of the list is not lost. Each node’s next pointer changes once, five changes for five nodes, and the old tail comes back as the new head. Forgetting to save next first is the classic bug: the list is cut after one node. The same loop on the same five nodes, with head called curr:

Interactive · step through it Reversing 10 → 20 → 30 → 40 → 50 in place Three pointers, prev, curr and next, turn every link around in one pass.

being compared or looked at
being moved or written
in its final place

Pseudo-code

prev ← null; curr ← head
while curr ≠ null:
next ← curr.next
curr.next ← prev
prev ← curr; curr ← next
head ← prev

Reverse 10 → 20 → 30 → 40 → 50 in place. prev starts at null and curr at the head.

When it finishes: 50 → 40 → 30 → 20 → 10.

Links changed 0

Checkpoint

Check: Heap insertion and list reversal

Question 1 of 2 The program's max-heap ends as 50, 40, 35, 10, 15, 30, stored from index 0. Now insert 45. Where does 45 end up?
Choose one answer.

At a[6], with no swap At a[1], after one swap with 40 At a[2], after one swap with 35 At the root, after two swaps

Show the answer: Question 1 of 2

Answer: At a[2], after one swap with 35

A new key goes to the next free position, a[6]. Its parent is a[2] = 35 < 45, so they swap; then 45's parent is a[0] = 50 > 45, so the climb stops. The array is 50, 40, 45, 10, 15, 30, 35.
Question 2 of 2 In the reversal loop, two lines are swapped, so head->next = prev; runs before next = head->next;. What does the function return for the list 10 → 20 → 30 → 40 → 50?
Choose one answer.

A list of one node, 10; the other four are lost Nothing, because the loop never stops The list reversed, as usual A list that reads freed memory

Show the answer: Question 2 of 2

Answer: A list of one node, 10; the other four are lost

Saving next has to come first. With the lines swapped, head->next is set to prev, which is NULL on the first pass, and only then copied into next, so the loop ends after one node and returns 10 alone. The lesson calls this the classic bug: the list is cut after one node.

Practise in GATE’s three formats

Practise all four ideas, starting with the one you know least.

C semantics traps, each reproduced with two compilers Pro: opens with a Pro, Premium or Ultimate pass

The hardest C questions in the section turn on rules that ordinary programs rarely meet: the order of evaluation, short-circuit operators, value parameters, integer division and undefined behaviour. Each rule is shown by a program built with both compilers, so you see what the standard allows next to what real compilers did.

In this part:

Evaluation order and short-circuit side effects, traced
Value parameters, decayed arrays and truncating division
Undefined behaviour reproduced: a changed literal, an overflow and a read past the end
Conversions and old-style declarations: two traps the compilers report

1 diagram · 11 runnable examples (C, Python) · about 8 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

The counting playbook for stacks, trees and heaps, with the counts checked by enumeration Pro: opens with a Pro, Premium or Ultimate pass

Counting questions have exact answers, and each comes from a formula you can check on small cases. This part derives the formulas, confirms the counts of calls, stack orders, tree shapes and heaps with programs that try every case, and works the queue and graph formulas with numbers.

In this part:

Call counts, from a recurrence to a closed form
Stack orders and BST shapes: Catalan numbers counted two ways
Heaps: index formulas, linear-time building and the number of heaps
Rebuilding a tree from two traversals, and when two are not enough
Circular queues and graph storage: the formulas worked with numbers
Exercise: delete the maximum from a heap
- Delete the maximum from an array max-heap and count the swaps

2 diagrams · 6 runnable examples (C, Python) · 1 exercise with sample tests · about 10 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher · Warm-up

In C, what is the difference between char s[] = "GATE"; and char *s = "GATE";?

The first declares an array of 5 chars that holds a copy of the literal: four letters and the null character. The array belongs to the program, so s[0] = 'g' is allowed, sizeof s is 5, and s can never point anywhere else. The second declares a pointer that holds the address of the literal's own array. sizeof s is the size of a pointer, 8 bytes on a 64-bit system, and s may later point elsewhere, but writing through it, as in s[0] = 'g', is undefined behaviour, because a string literal must never be modified; on many systems it sits in read-only memory and the program crashes. Declaring the pointer as const char * makes the compiler reject that write. strlen(s) is 4 in both cases.
Fresher to mid

A recursive C function keeps a static counter, and you are asked what main prints. How do you trace it under exam time, and what changes if the result is computed as f(n - 1) + f(n - 2) while both calls update that static?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to senior

A short C program prints different results with two compilers. How do you decide whether you are looking at undefined behaviour, unspecified behaviour or a compiler bug? Use printf("%d %d", i++, i++) and g(1) - g(2), where g changes a global, as your examples.

Model answer, Pro. First step and follow-ups
Fresher to mid

How many different max-heaps can be built from the keys 1 to 5? Explain the method so that it also works for 7 or 10 keys, and say how you would check your answer.

Model answer, Pro. First step and follow-ups

Key takeaways

Section 4 is examined by tracing programs and counting data-structure states; check that a program is valid C first.
A static local is shared by every call, so a printed value can depend on every call made before.
Pointers step by the size of what they point to, and sizeof of a char array counts the null that strlen stops before.
A max-heap insertion climbs while the key beats its parent; a list reversal saves next before each turn.

Terms in this lesson

array decay: In most C expressions an array name turns into a pointer to its first element. For int a[3][4] the first element is a row, so a becomes a pointer to a row of 4 ints and a + 1 steps a whole row.
max-heap: A complete binary tree, usually stored in an array, in which every parent's key is at least as large as its children's keys, so the largest key is at the root.
null character: The character with code 0, written '\0', that ends every C string. strlen counts the characters before it, while sizeof of a char array counts it too.
static local variable: A variable declared static inside a C function. It is created and set once, before the program starts, and every call of the function shares it, while ordinary locals and parameters are new in each call.
undefined behaviour: Behaviour for which the C standard sets no requirement at all, such as writing into a string literal. A program that has it has no single correct output, so an exam question about it has no value to trace towards.

References

GATE 2027 syllabus, Computer Science and Information Technology (CS), section 4 (Indian Institute of Technology Madras (GATE 2027))
Programming languages: C, working draft N2176 (C17) (ISO/IEC JTC1/SC22/WG14)
Programming languages: C, working draft N3220 (C23 and later) (ISO/IEC JTC1/SC22/WG14)
UndefinedBehaviorSanitizer (The LLVM Project)
AddressSanitizer (The LLVM Project)
Clang Compiler User's Manual (The LLVM Project)
GCC: options to request or suppress warnings (Free Software Foundation (GNU Project))
A000108: Catalan numbers (The OEIS Foundation)
A056971: number of (binary) heaps on n elements (The OEIS Foundation)
heap (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology)

Report a problem with this lesson

In this module: Programming, data structures and algorithms (CS sections 4-5; DA section 4)

Programming in C and data structures (GATE CS) Free core, Pro depth: 9 of 25 minutes free
Asymptotics, recurrences, sorting and hashing Free core, Pro depth: 7 of 25 minutes free
Greedy, DP, divide and conquer, MSTs, shortest paths Free core, Pro depth: 9 of 25 minutes free
Python, data structures and algorithms (GATE DA) Free core, Pro depth: 8 of 25 minutes free

Your country

Programming in C and data structures (GATE CS)

What you will learn

Before you start

What you will learn

Before you start

Two shapes of question, and one method for both

A static local is shared by every call

Pointer steps and sizes follow the type

A heap insertion climbs; a list reversal turns each pointer once

Practise in GATE’s three formats

C semantics traps, each reproduced with two compilers Pro: opens with a Pro, Premium or Ultimate pass

The counting playbook for stacks, trees and heaps, with the counts checked by enumeration Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

In C, what is the difference between char s[] = "GATE"; and char *s = "GATE";?

A recursive C function keeps a static counter, and you are asked what main prints. How do you trace it under exam time, and what changes if the result is computed as f(n - 1) + f(n - 2) while both calls update that static?

A short C program prints different results with two compilers. How do you decide whether you are looking at undefined behaviour, unspecified behaviour or a compiler bug? Use printf("%d %d", i++, i++) and g(1) - g(2), where g changes a global, as your examples.

How many different max-heaps can be built from the keys 1 to 5? Explain the method so that it also works for 7 or 10 keys, and say how you would check your answer.

Key takeaways

References

Related tools