GATE Computer Science Programming and Data Structures Previous Year Questions

#include < stdio.h>  
void foo(int *p, int x){  
    *p=x;  
}  
int main(){  
    int *z;  
    int a = 20, b = 25;  
    z = &a;  
    foo(z,b);  
    printf("%d",a);  
    return 0;  
}  

The output of the given C program is ________. (Answer in integer)

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.

Suppose a Min-Heap $T$ stores $32$ keys. The height of $T$ is ___________. (Answer in integer)

#include < stdio.h>  
int foo(int S[],int size){  
    if(size == 0) return 0;  
    if(size == 1) return 1;  
    if(S[0] != S[1]) return 1+foo(S+1,size-1);  
    return foo(S+1,size-1);  
}  
int main(){   
    int A[]={0,1,2,2,2,0,0,1,1};  
    printf("%d",foo(A,9));  
    return 0;  
}  

The value printed by the given C program is ______ . (Answer in integer)

Let LIST be a datatype for an implementation of linked list defined as follows:

typedef struct list {  
    int data;   
    struct list *next;  
} LIST;  

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.

Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is _______ .
(Answer in integer)

int find (int query, LIST *list) {  
    while (list != NULL){  
        if(list->data == query) return 1;  
        list = list->next;  
    }  
    return 0;  
}  
int main () {  
    ...  ...  ...  
    ptr1=L1; ptr2=L2;  
    while (ptr1->next != NULL){  
        query = ptr1->next->data;  
        if (find (query, L2))  
            ptr1->next = ptr1->next->next;  
        else ptr1 = ptr1->next;  
    }  
    ...  ...  ...  
    return 0;  
}  

Consider the following C program:

#include < stdio.h>  
int gate (int n) {  
    int d, t, newnum, turn;  
    newnum = turn = 0; t=1;  
    while (n>=t) t *= 10;  
    t /=10;  
    while (t>0) {  
        d = n/t;  
        n = n%t;  
        t /= 10;  
        if (turn) newnum = 10*newnum + d;  
        turn = (turn + 1) %2;  
    }  
    return newnum;  
}  
int main () {  
    printf ("%d", gate(14362));  
    return 0;  
}  

The value printed by the given C program is ______ . (Answer in integer)

In a double hashing scheme, h1(k) = k mod 11 and h2(k) = 1 + (k mod 7) are the auxiliary hash functions. The size m of the hash table is 11. The hash function for the i-th probe in the open address table is [h1(k) + i h2(k)] mod m. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24.

The slot at which key 24 gets stored is ________. (Answer in integer)

Consider a binary tree $T$ in which every node has either zero or two children. Let $n>0$ be the number of nodes in $T$.

Which ONE of the following is the number of nodes in $T$ that have exactly two children?

Consider the following C program:

#include <stdio.h> 

void stringcopy(char *, char *);

int main(){

    char a[30] = "@#Hello World!";

    stringcopy(a, a + 2);

    printf("%s\n", a);

    return 0;

}

void stringcopy(char *s, char *t) {

    while(*t)

        *s++ = *t++;

}  

Which ONE of the following will be the output of the program?

int x=126,y=105;  
do {  
    if(x>y) x=x-y;  
    else y=y-x;  
} while(x!=y);

printf("%d",x);  

The output of the given C code segment is _______. (Answer in integer)

Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let T be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of T is ________. (Answer in integer)

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size $n$ of these data structures?

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.

We wish to augment the stack data structure with an $O(1)$ time MIN operation that returns a pointer to the record with smallest key present in the stack

1. without deleting the corresponding record, and
2. without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

Consider the following C program:

#include <stdio.h>

int main(){

    int a;

    int arr[5] = {30,50,10};

    int *ptr;

    ptr = &arr[0] + 1;

    a = *ptr;

    (*ptr)++;

    ptr++;

    printf("%d", a + (*ptr) + arr[1]);

    return 0;

}  

The output of the above program is ________. (Answer in integer)

Consider the following C program:

#include <stdio.h> 

int g(int n) {  
    return (n+10);  
}

int f(int n) {  
    return g(n*2);  
}

int main() {  
    int sum, n;  
    sum=0;  
    for (n=1; n<3; n++)  
        sum += g(f(n));  
    printf ("%d", sum);  
    return 0;  
}  

The output of the given C program is _______. (Answer in integer)