GATE PYQ

GATE CSE 2017 SET-1

Q1.
Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC- relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to the address of the next instruction in the program sequence. Consider the following instruction sequence. If the target of the branch instruction is i, then the decimal value of the Offset is __________

Q2.
Consider the C struct defined below: struct data { int marks [100] ; char grade; int cnumber; }; struct data student; The base address of student is available in register R1. The field student.grade can be accessed efficiently using

Q3.
Consider the following C program. #include #include void printlength (char s, char t) { unsigned int c = 0; int len = ((strlen(s) - strlen (t)) > c) ? strlen(s): strlen(t); printf ("%d\n", len); } void main ( ) { char x = "abc"; char y ="defgh"; printlength (x,y); Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int. The output of the program is _____________.

Q4.
Consider the following C code: # include int * assignval (int x, int val) { x = val; return x; } void main ( ) { int * x= malloc (sizeof (int)); if (NULL = = x) return; x = assignval (x,0); if(x) { x=(int ) malloc (sizeof (int)); if (NULL = = x) return; x = assignval (x, 10); } printf("%d\n", x); free (x); } The code suffers from which one of the following problems:

Q5.
Let A be an array of 31 numbers consisting of sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index i that A[i] is 1 by probing the minimum numbers of locations in A. The worst case number of probes performed by an optimal algorithm is _____________.

Q6.
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are : Note: The height of a tree with a single node is 0.

Q7.
Consider the following functions from positive integers to real numbers: 10,\sqrt{n},n, log_{2}n,\frac{100}{n}. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

Q8.
Consider a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache 0.1, the L2 cache experiences, on average, 7 misses per 1000 instructions. The miss rate of L2 expressed correct to two decimal places is ___________.

Q9.
A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ______bits.

Q10.
Consider a 2-way set associative cache with 256 blocks and uses LRU replacement, Initially the cache is empty. Conflict misses are those misses which occur due the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks. (0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129) is repeated 10 times. The number of conflict misses experienced by the cache is ___________.