Programming and Data Structures — GATE Previous Year Questions

The following C function takes a singly linked list of integers as a parameter and rearranges the elements of the list. The list is created with the integers 1, 2, 3, 4, 5, 6, 7 in that order, and rearrange is called with a pointer to the first node.

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

void rearrange(struct node *list) {
    struct node *p, *q;
    int temp;
    if (!list || !list->next) return;
    p = list;
    q = list->next;
    while (q) {
        temp = p->value;
        p->value = q->value;
        q->value = temp;
        p = q->next;
        q = p ? p->next : 0;
    }
}

What will be the contents of the list after the function completes execution?

Postorder traversal of a given binary search tree T produces the following sequence of keys:

10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

The maximum number of binary trees that can be formed with three unlabelled nodes is:

The following postfix expression with single-digit operands is evaluated using a stack:

8 2 3 ^ / 2 3 * + 5 1 * -

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

The following C function takes a singly linked list as an input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node {
    int value;
    struct node *next;
} Node;

Node *move_to_front(Node *head) {
    Node *p, *q;
    if ((head == NULL) || (head->next == NULL))
        return head;
    q = NULL;
    p = head;
    while (p->next != NULL) {
        q = p;
        p = p->next;
    }
    _______________________________
    return head;
}

Choose the correct alternative to replace the blank line.

Consider the following function:

int f(int n) {
    static int r = 0;
    if (n <= 0) return 1;
    if (n > 3) {
        r = n;
        return f(n - 2) + 2;
    }
    return f(n - 1) + r;
}

What is the value of f(5)?

Consider the following function written in C:

int f(int n) {
    static int i = 1;
    if (n >= 5) return n;
    n = n + i;
    i++;
    return f(n);
}

The value returned by f(1) is ______.

Consider a max-heap stored in an array using the usual level-order (breadth-first) representation:

40, 30, 20, 10, 15, 16, 17, 8, 4

The value 35 is now inserted into this heap. After the insertion, the array representing the heap is:

Consider the following C program:

void f(int, short);

void main() {
    int i = 100;
    short s = 12;
    short *p = &s;
    __________ ;   /* call to f() */
}

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

Consider the following C program:

#include <stdio.h>

int *A, stkTop;

int stkFunc(int opcode, int val) {
    static int size = 0, stkTop = 0;
    switch (opcode) {
        case -1: size = val; break;
        case  0: if (stkTop < size) A[stkTop++] = val; break;
        default: if (stkTop) return A[--stkTop];
    }
    return -1;
}

int main() {
    int B[20];
    A = B;
    stkTop = -1;
    stkFunc(-1, 10);
    stkFunc(0, 5);
    stkFunc(0, 10);
    printf("%d\n", stkFunc(1, 0) + stkFunc(1, 0));
    return 0;
}

The value printed by the program is ______.

Consider the following C program:

#include <stdio.h>

struct Ournode {
    char x, y, z;
};

int main() {
    struct Ournode p = {'1', '0', 'a' + 2};
    struct Ournode *q = &p;
    printf("%c, %c", *((char *)q + 1), *((char *)q + 2));
    return 0;
}

The output of this program is:

Consider the following C program:

#include <stdio.h>

int jumble(int x, int y) {
    x = 2 * x + y;
    return x;
}

int main() {
    int x = 2, y = 5;
    y = jumble(y, x);
    x = jumble(y, x);
    printf("%d\n", x);
    return 0;
}

The value printed by the program is ______.