GATE Computer Science Numerical 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)

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is ______. (Answer in integer)

int main()  
{  
   int x=0, i=0;  
   scanf("%d",&x);  
   for(i=0; i<20; i++)  
   {  
       x = x+20;  
       printf("%d\n",x);  
   }  
   return 0;  
}   

A computer system supports a logical address space of $2^{32}$ bytes. It uses two-level hierarchical paging with a page size of $4096$ bytes. A logical address is divided into a $b$-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of b is __________ . (Answer in integer)

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the “hit rate” for L1 cache is 90% while the processor is accessing the data from L1 cache. Whereas, for the second level (L2) cache, the “hit rate” is 80% and the “miss penalty” for transferring data from L2 cache to L1 cache is 10 ns. The “miss penalty” for the data to be transferred from main memory to L2 cache is 100 ns.

Then the average memory access time in this system in nanoseconds is __________ . (rounded off to one decimal place)

Consider the following database tables of a sports league.

player(pid,pname,age) team(tid,tname,city,cid)
coach(cid,cname) members(pid,tid)

An instance of the table and an SQL query are given.

SELECT MIN(P.age)
FROM player P
WHERE P.pid IN (
SELECT M.pid
FROM team T, coach C, members M
WHERE C.cname = 'Mark'
AND T.cid = C.cid
AND M.tid = T.tid
)

The value returned by the given SQL query 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)

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)

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is _______. (Answer in integer)

The pseudocode of a function fun() is given below:

fun(int $A[0,\ldots,n-1]$) {  
    for i = 0 to n-2  
        for j = 0 to n-i-2  
            if ($A[j] > A[j+1]$)  
                then swap A[j] and A[j+1]   
}  

Let $A[0,\dots ,29]$ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with $A[0,\dots ,29]$ as argument, is ________. (Answer in integer)

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = $2^{10}$ and 1M = $2^{20}$. The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)

Consider a finite state machine (FSM) with one input X and one output f, represented by the given state transition table. The minimum number of states required to realize this FSM is _______. (Answer in integer)

The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ________ . (answer in integer)

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:

The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.

A process accesses the pages in the following order of page numbers:

$1,3,2,4,2,3,1,2,4,3,1,4$.

If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ________. (Answer in integer)

The following two signed 2's complement numbers (multiplicand M and multiplier Q) are being multiplied using Booth's algorithm:

M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010

The total number of addition and subtraction operations to be performed is ________. (Answer in integer)

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)

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is ________ . (Answer in integer)

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is _______. (Answer in integer)

1001: i = 1  
1002: j = 1  
1003: t1 = 10*i  
1004: t2 = t1+j  
1005: t3 = 8*t2  
1006: t4 = t3-88  
1007: a[t4] = 0.0  
1008: j = j+1  
1009: if j <= 10 goto 1003  
1010: i = i+1  
1011: if i <= 10 goto 1002  
1012: i = 1  
1013: t5 = i-1  
1014: t6 = 88*t5  
1015: a[t6] = 1.0  
1016: i = i+1  
1017: if i <= 10 goto 1013  

#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)

Suppose a message of size 15000 bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum transmission unit (MTU) as shown in the figure, including IP header. The number of fragments that will be delivered to the destination 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;  
}