Final end-to-end test

30 questions in GATE format covering all phases (15 one-mark, 15 two-mark; 45 marks). Set a 90-minute timer, work on paper, and enter your answers in the boxes. For MSQ enter all correct letters (e.g. AC); for NAT enter a number. Then press Submit answers (the page scores you, shows which questions were wrong and which lesson to re-read) — or open the key at the very end of these notes.

⏱️

30 questions · 45 marks · 90 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit. Answers are not on this page; enter yours below and press Submit answers, or open the key at the very end of the notes.

Q1MCQ1 markOperators

What does this print?

#include <stdio.h>
int main(void)
{
    printf("%d %d %d %d\n", 6 & 3, 6 | 3, 6 ^ 3, 1 << 3 + 1);
    return 0;
}

• (A) 2 7 5 8
• (B) 2 7 5 9
• (C) 2 7 5 16
• (D) 3 7 4 16

Q2NAT1 markLoops

What does this print?

#include <stdio.h>
int main(void)
{
    int n = 0;
    do {
        n += 3;
    } while (n % 5);
    printf("%d\n", n);
    return 0;
}

Your answer:

Q3MCQ1 markFunction pointers

What does this print?

#include <stdio.h>
int add(int a, int b) { return a + b; }
int mul(int a, int b) { return a * b; }

int main(void)
{
    int (*op[2])(int, int) = {add, mul};
    printf("%d\n", op[1](op[0](2, 3), 4));
    return 0;
}

• (A) 9
• (B) 10
• (C) 14
• (D) 20

Q4MCQ1 markStrings

What does this print?

#include <stdio.h>
void r(char *s)
{
    if (*s) {
        r(s + 1);
        printf("%c", *s);
    }
}

int main(void)
{
    r("gate");
    printf("\n");
    return 0;
}

• (A) gate
• (B) e
• (C) g
• (D) etag

Q5NAT1 markRecursion

What does this print?

#include <stdio.h>
int moves = 0;

void hanoi(int n, char a, char b, char c)
{
    if (n == 0) return;
    hanoi(n - 1, a, c, b);
    moves++;
    hanoi(n - 1, c, b, a);
}

int main(void)
{
    hanoi(6, 'A', 'B', 'C');
    printf("%d\n", moves);
    return 0;
}

Your answer:

Q6MCQ1 markSizes

On a 32-bit system, int a[10]; is passed to void f(int a[]). Inside f, sizeof(a) is:

• (A) 10
• (B) 4
• (C) 44
• (D) 40

Q7NAT1 markAddress

int A[10][20] is stored column-major at base 1000 with 4-byte int. Address of A[5][7]?

Your answer:

Q8NAT1 markStacks

How many output sequences are possible when 1, 2, 3, 4 are pushed in order onto a stack and popped at any time?

Your answer:

Q9MCQ1 markQueues

A queue is implemented with two stacks (push to S1; pop from S2, refilling S2 from S1 only when S2 is empty). The amortised cost per operation is:

• (A) O(n)
• (B) O(n²)
• (C) O(1)
• (D) O(log n)

Q10MCQ1 markLists

With only a head pointer, which operation on a singly linked list of n nodes is Θ(n)?

• (A) deleting the first node
• (B) reading the first key
• (C) deleting the last node
• (D) inserting at the head

Q11NAT1 markTrees

Maximum number of nodes in a binary tree of height 5 (edges)?

Your answer:

Q12MCQ1 markBST

Which traversal of a BST lists the keys in sorted order?

• (A) postorder
• (B) inorder
• (C) preorder
• (D) level order

Q13NAT1 markAVL

Minimum nodes in an AVL tree of height 5 (edges)?

Your answer:

Q14MCQ1 markHeaps

The time to build a heap bottom-up from n unsorted keys is:

• (A) Θ(n)
• (B) Θ(log n)
• (C) Θ(n²)
• (D) Θ(n log n)

Q15NAT1 markGraphs

A simple graph has 10 vertices of degree 3 and 4 vertices of degree 2. How many edges?

Your answer:

Q16MCQ2 marksPointers to arrays

What does this print?

#include <stdio.h>
int main(void)
{
    int a[2][3] = {1, 2, 3, 4, 5, 6};
    int (*p)[3] = a;
    printf("%d %d\n", (*(p + 1))[1], *(*p + 4));
    return 0;
}

• (A) 4 5
• (B) 2 5
• (C) 5 4
• (D) 5 5

Q17MCQ2 marksDynamic memory

What does this print?

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int x, y;
} P;

int main(void)
{
    int i;
    P *a = malloc(3 * sizeof(P)), *q;
    for (i = 0; i < 3; i++) {
        a[i].x = i;
        a[i].y = i * i;
    }
    q = a + 2;
    printf("%d %d %d\n", q->x, (q - 1)->y, (int)sizeof(P));
    free(a);
    return 0;
}

• (A) 2 1 4
• (B) 4 1 8
• (C) 2 1 8
• (D) 2 4 8

Q18MCQ2 marksStacks

What does this print?

#include <stdio.h>
#define MAX 4
int s[MAX], top = -1;

void push(int x) { if (top == MAX - 1) printf("full "); else s[++top] = x; }
int pop(void) { if (top == -1) { printf("empty "); return -1; } return s[top--]; }

int main(void)
{
    int i, t;
    for (i = 1; i <= 5; i++) push(i * 10);
    t = pop();
    t = t + pop();
    push(t);
    printf("%d %d\n", s[top], top);
    return 0;
}

• (A) 70 2
• (B) full 90 2
• (C) full 70 3
• (D) full 70 2

Q19NAT2 marksRecursion

int f(int n) { if (n <= 2) return 1; return f(n − 1) + f(n − 3); } What is f(8)?

Your answer:

Q20MCQ2 marksComplexity

What is the time complexity of for (i = 1; i < n; i *= 2) for (j = 1; j < n; j *= 2) c++;?

• (A) Θ(n)
• (B) Θ(n log n)
• (C) Θ((log n)²)
• (D) Θ(log n)

Q21MSQ2 marksExpressions

Which are true for the expression a + b * (c − d) / e?

• (A) Evaluating its postfix form needs a stack depth of at least 4.
• (B) Its prefix form is + a / * b − c d e.
• (C) Its expression tree has + at the root.
• (D) Its postfix form is a b c d − * e / +.

Q22NAT2 marksCircular queue

A circular queue of size 10 (front = slot before the first element) starts with front = rear = 0. After 7 enqueues, 4 dequeues and 5 enqueues, what is rear?

Your answer:

Q23MCQ2 marksLinked lists

p points to a node in the middle of a doubly linked list (fields prev, next). Which code deletes it correctly?

• (A) p->prev->next = p; p->next->prev = p; free(p);
• (B) p->next = p->prev; p->prev = p->next; free(p);
• (C) free(p); p->prev->next = p->next;
• (D) p->prev->next = p->next; p->next->prev = p->prev; free(p);

Q24NAT2 marksTraversals

A binary tree has inorder 4 2 5 1 6 3 7 and preorder 1 2 4 5 3 6 7. What is the 3rd key in its postorder?

Your answer:

Q25NAT2 marksBST

A BST is built by inserting 15, 10, 20, 8, 12, 17, 25, 6, 11, 13, 22, 27. What is its height (edges)?

Your answer:

Q26MCQ2 marksBST counting

How many BSTs on the keys {1, …, 6} have 3 at the root?

• (A) 10
• (B) 5
• (C) 20
• (D) 14

Q27MCQ2 marksHeaps

Delete the minimum from the min-heap 1 3 2 9 4 5. The result is:

• (A) 2 3 5 9 4
• (B) 3 2 5 9 4
• (C) 2 3 9 4 5
• (D) 2 3 4 9 5

Q28NAT2 marksHeap count

How many distinct max-heaps can be built from 5 distinct keys?

Your answer:

Q29MSQ2 marksGraph traversal

Graph with edges A–B, A–C, B–D, C–D, D–E, E–F. Which are valid BFS orders from A?

• (A) A B C D E F
• (B) A B C E D F
• (C) A C B D E F
• (D) A B D C E F

Q30NAT2 marksGraphs

Maximum number of edges in a simple undirected graph with 10 vertices and 2 connected components?

Your answer:

Show the key