GATE CSE 2017 PYQ

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum spanning tree of G is always uni

Match the algorithms with their time complexities:

Which one of the following in-place sorting algorithms needs the minimum number of swaps?

Consider the following table: Match the algorithms to the design paradigms they are based on.

A message is made up entirely of characters from the set X= {P,Q,R,S,T}. The table of probabilities for each of the characters is shown below: If a message of 100 characters over X is encoded using Hu

Which of the following algorithms solves the all pair shortest path problem?

The number of swappings needed to sort the numbers 8 , 22, 7, 9, 31, 5, 13 in ascending order using bubble sort is

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

Consider the recurrence function Then T(n) in terms of notation is

Consider the following functions from positive integers to real numbers: . The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum spanning tree of G is always uni

Consider the following C function int fun (int n) { int i, j; for (i = 1; i < = n; i++) { for (j = 1 ; j < n ; j+=i) { printf ("%d %d , i, j ) ; } } } Asymptotic Notation of fun in terms of notation i

The recurrence relation that arises in relation with the complexity of binary search is:

Consider the following grammar: stmt if expr then expr else expr; stmt| expr term relop term|term term id|number if a|b|c number [0-9] where relop is a relational operate (e.g ,...), refers to the emp

Consider the expression ( a-1)* (((b + c) / 3) + d)) . Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architect

The output of a lexical analyzer is

Match the following according to input (from the left column) to the complier phase (in the right column) that processes it.

Consider the following intermediate program in three address code p= a -b q= p *c p= u * v q= p + q Which one of the following corresponds to a static single assignment form of the above code?

If there are n devices (nodes) in a network, what is the number of cable links required for a fully connected mesh and a star topology respectively

Which protocol suite designed by IETF to provide security for a packet at the Internet layer?

The default subnet mask for a class B network can be

Physical topology of FDDI is?

Which of the following protocol is used for transferring electronic mail messages from one machine to another?

What is WPA?

Which media access control protocol is used by IEEE 802.11 wireless LAN?

The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is _________.

Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connectional and a FIN segment is sent to the TCP

In a RSA cryptosystem a participant A uses two prime numbers p=13 and q=17 to generate her public and private keys. If the public key of A is 35. Then the private key of A is __________.

Consider a binary code that consists of only four valid code words as given below: 00000,01011,10101,11110 Let the minimum Hamming distance of the code be p and the maximum number of erroneous bits th

A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place. I. S can launch a bi

Pretty Good Privacy (PGP) is used in:

The values of parameters for the Stop-and-Wait ARQ protocol are as given below: Bit rate of the transmission channel = 1Mbps Propagation delay from sender to receiver = 0.75 ms Time to process a frame

MD5 is a widely used hash function for producing hash value of

Match with the suitable one:

Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the following statements

Consider two hosts X and Y, connected by a single direct link of rate bits/sec . The distance between the two hosts is 10,000 km and the propagation speed along the link is 2x m/sec . Host X sends a f

Consider the following statements about the routing protocols, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network. I. RIP uses distance vector routing II. RIP pa

In networking terminology UTP means

A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses as the generator polynomial to generate the check bits. In this network, the message 01011011

An Ethernet frame that is less than the IEEE 802.3 minimum length of 64 octets is called

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 th

The most appropriate matching for the following pairs:

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 c

Instructions execution in a processor is divided into 5 stages. Instruction Fetch (IF), Instruction Decode (ID) , Operand Fetch (OF), Execute (EX), and Write Back (WB), These stages take 5,4,20, 10 an

The read access times and the hit ratios for different caches in a memory hierarchy are as given below. The read access time of main memory is 90 nanoseconds. Assume that the caches use the referred w

In a two-level cache system, the access times of and caches are 1 and 8 clock cycles, respectively. The miss penalty from L2 cache to main memory is 18 clock cycles . The miss rate of cache is twice t

Which interrupt in 8085 Microprocessor is unmaskable?

How many 128x8 bit RAMs are required to design 32Kx32 bit RAM?

A cache memory needs an access time of 30 ns and main memory 150 ns, what is average access time of CPU (assume hit ratio = 80%)?

SATA is the abbreviation of

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 d

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 expe

Consider a machine with a byte addressable main memory of bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this machine. The size of th

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

Consider the following tables T1 and T2. In table T1, P is the primary key and Q is the foreign key referencing R in table T2 with ondelete cascade and on-update cascade. In table T2, R is the primary

Two transactions are given as: where denotes a read operation by transaction on a variable V and denotes a write operations by transaction on a variable V. The total number of conflict serializable sc

A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in th

Consider a database that has the relation schemas EMP(EmpId, EmpName, DepId) and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following qu

What is the output of the following SQL query? select count(*) from ((select Employee, Department from Overtime_allowance) natural join (select Department, OT_allowance from Overtime_allowance) as T);

In a tree, if the search -key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then maximum order of the tree is _______________.

What does a data dictionary will identify?

Which of the following concurrency control protocol ensures both conflict and free from deadlock? ,

Which of these is characteristic of RAID 5?

Which symbol denote derived attributes in ER Model?

An ER model of a database consists of entity types A and B. These are connected by a relationship R which does not have its own attribute. Under which one of the following conditions, can the relation

In a database system, unique time stamps are assigned to each transaction using Lamport's logical clock . Let TS( ) and TS( ) be the timestamps of transactions and respectively. Besides, holds a lock

ACID properties of a transactions are

Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below. The output of executing the SQL query is _____

The following functional dependencies hold true for the relational schema R{V,W,X,Y,Z}: V W VW X Y VX Y Z Which of the following is irreducible equivalent for this set of functional dependencies ?

Consider the following database table named top_scorer. Consider the following SQL query: The number of tuples returned by the above SQL query is ___________.

Consider a database that has the relation schema CR (StudentName, CourseName). An instance of the schema CR is as given below. The following query is made on the database The number of rows in T2 is _

When two 8-bit numbers and in 2's complement representation (with and as the least significant bits ) are added using a ripple-carry Combinational Circuit, the sum bits obtained are and the carry bits

Advantage of synchronous sequential circuits over asynchronous one is :

Given f(w,x,y,z) = (0,1,2,3,7,8,10) + (5,6,11,15), where d represents the don't care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w,x,y,z) ?

Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flop is connected to the input of the T flip-flop and the output of the T flip-flop is connected to the

What is the minimum number of two-input NAND gates used to perform the function of two-input OR gate?

The 2-input XOR has a high output only when the input values are

The n-bit fixed-point representation of an unsigned real number real X uses f bits for the fraction part. Let i=n-f. The range of decimal values for X in this representation is

If w, x, y, z are Boolean variables, then which one of the following is INCORRECT ?

The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

Consider the Karnaugh map given below, where x represents "don't care" and blank represents 0. Assume for all inputs (a, b, c, d) the respective complements are also available. The above logic is impl

is equivalent to

When two n-bit binary numbers are added the sum will contain at the most

The next state table of a 2-bit saturating up-counter is given below. The counter is built as a synchronous sequential circuit using T flip-flops. The expression for are

Given the following binary number in 32-bit (single precision) IEEE-754 format: 00111110011011010000000000000000 The decimal value closest to this floating- point number is

If A is a skew symmetric matrix then is

If and , then the constants R and S are, respectively

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be

Consider a quadratic equation with coefficients in a base b. The solutions of this equation in the same base b are x = 5 and x = 6. Then b = ___________.

Let be scalars, not all zero, such that where are column vectors in . Consider the set of linear equations Ax = b where A= and b= . The set of equations has

Let A be nxn real valued square symmetric matrix of rank 2 with . Consider the following statements. (I) One eigen value must be in [-5, 5] (II) The eigen value with the largest magnitude must be stri

Let and be any two arbitrary events, then, which one of the following is TRUE?

Using Newton-Raphson method, a root correct to 3 decimal places of

G is undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.

Which one of the following Boolean expressions is NOT a tautology?

Consider the first-order logic sentence . Assuming non-empty logical domains, which of the sentences below are implied by F? I. II. III. IV.

Let p, q, and r be propositions and the expression (p q) r be a contradiction. Then, the expression (r p) q is

For any discrete random variable X, with probability mass function and , define the polynomial function . For a certain discrete random variable Y, there exists a scalar [0,1] such that . The expectat

The value of

If a random variable X has a Poisson distribution with mean 5, then the expectation equals ______________.

The symmetric difference of sets A={1,2,3,4,5,6,7,8} and B={1,3,5,6,7,8,9} is:

Let u and v be two vectors in whose Euclidean norms satisfy ||u||=2|| v|| . What is the value of such that w=u+ v bisects the angle between u and v ?

The statement is logically equivalent to which of the statements below? I. II. III. IV.

Let and be two matrices. Then the rank of P +Q is _____________.

If the ordinary generating function of a sequence then is equal to ______.

Let X be a Gaussian random variable mean 0 and variance . Let Y=max(X, 0) where max (a,b) is the maximum of a and b. The median of Y is ____________.

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______________.

Consider the set X={a, b,c,d,e} under the partial ordering R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}. The Hasse diagram of the partial order (X, R) is shown bel

Let p, q, r denote the statements "It is raining ," It is cold", and " It is pleasant," respectively. Then the statement "It is not raining and it is pleasant, and it is not pleasant only if it is rai

P and Q are considering to apply for a job. The probability that P applies for the job is 1/4. The probability that P applies for the job given that Q applies for the job is 1/2 , and the probability

If the characteristics polynomial of 3x3 matrix M over R ( the set of real numbers) is , and one eigenvalue of M is 2, then the largest among the absolute values of the eigenvalues of M is ________.

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.

Which of the following is/are shared by all the threads in a process ? I. Program counter II. Stack III. Address space IV. Registers

A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: Which of the following best describes current state of the system ?

Given reference to the following pages by a program 0,9,0,1,8,1,8,7,8,7,1,2,8,2,7,8,2,3,8,3 How many page faults will occur if the program has three page frames available to it and uses an optimal rep

Wha is the output of the following program? main() { int a = 10; if(fork()) == 0)) a++; printf("%d ",a); }

What problem is solved by Dijikstra banker' algorithm?

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU burst (in milliseconds) as given below: If the pre-emptive shortest remaining time first scheduling algorith

In a file allocation system, which of the following allocation schemes(s) can be used if no external fragmentation is allowed? I. Contiguous II. Linked III. Indexed

Threads of a process share

Consider the set of processes with arrival time (in milliseconds). CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time. Th

The Linux command mknod myfifo b 4 16

Mutual exclusion problem occurs

Recall that Belady's anomaly is that the pages-fault rate may increase as the number of allocated frames increases. Now consider the following statements: S1: Random page replacement algorithm (where

A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentr

A critical region

At a particular time the value of counting semaphore is 10. It will become 7 after:

Consider the disk system with 100 cylinders. The request to access the cylinders occur in the following sequence. 4, 37, 10,7,19,73,2,15,6,20 Assuming the head is currently at cylinder 50 what is the

Given two statements Insertion of an element should be done at the last node of the circular list Deletion of an element should be done at the last node of the circular list

Consider the following C Program. #include #include #int main ( ) { char* c = "GATECSIT2017"; char* p = c; printf("%d", (int) strlen (c+2[p]-6[p]-1)); return 0; } The output of the program is ________

What will be the output of the following C code? #include main() { int i; for(i=0;i<5;i++) { int i=10; printf("%d" , i); i++; } return 0; }

Choose the equivalent prefix form of the following expression

In a doubly linked list the number of pointers affected for an insertion operation will be

Which of the following data structure is useful in traversing a given graph by breadth first search?

Consider the following function void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } In order to exchange the values of two variables x and y.

Consider the C code fragment given below. typedef struct node { int data; node* next ; } node; void join (node* m, node* n) { node* p=n ; while (p->next ! =NULL){ p = p -> next ; } p-> next = m; } Ass

Consider the following snippet of a C program. Assume that swap (&x, &y) exchanges the contents of x and y. int main ( ) { int array[]={3,5,1,4,6,2}; int done =0 ; int i ; while (done = = 0) { done =

Consider the following two functions. The output printed when fun1(5) is called is

We use malloc and calloc for:

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.

What does the following program do when the input is unsigned 16 bit integer? #include main(){ unsigned int num; int i; scanf("%u", &num); for(i=0;i<16;i++){ printf("%d", (num < < i&1 < < 15)?1:0); }

Consider the following C program. #include int main ( ) { int m = 10; int n, n1; n = ++m; n1 = m++; n--; --n1; n-=n1; printf ("%d", n) ; return 0; } The output of the program is ______________.

What is the output of the C++ program? #include using namespace std; void square(int *x){ *x = (*x)++ * (*x); } void square(int *x, int *y){ *x = (*x) * --(*y); } int main() { int number = 30; square(

What does the following C-statement declare? int (*f) (int * );

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 best data structure to check whether an arithmetic expression has balanced parenthesis is a:

What is the output of the following program? #include int tmp=20; main() { printf("%d", tmp); func(); printf("%d", tmp); } func() { static int tmp=10; printf("%d", tmp); }

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 ", len); } vo

The pre-order transversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x, y, q and r are all unsigned int. while (r >= y) { r = r - y; q = q +1; } Which of th

If the post order traversal gives ab -cd * + then the label of the nodes 1,2,3.. will be

Consider the following function implemented in C: void printxy (int x, int y) { int *ptr ; x = 0; ptr = &x; y = * ptr; * ptr = l; print f ("%d, %d," x, y); } The output of invoking printxy (1,1) is

Consider the following C code: # include lt stdio.h > int * assignval (int *x, int val) { *x = val; return x; } void main ( ) { int * x= malloc (sizeof (int)); if (NULL = = x) return; x = assignval (x

A circular queue has been implemented using a single linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and

The output of executing the following C program is ________. # include int total (int v) { while (v) { static int count + = v & 1; v>> = 1; } return count; } void main ( ) { static int x = 0; int i =

Consider the C functions foo and bar given below: int foo (int val ) { int x = 0; while (val > 0) { x = x + foo(val--); } return val ; } int bar (int val ) { int x = 0; while (val > 0) { x = x + bar(v

Consider the following expression grammar G: E E-T|T T T+F|F F (E)|id Which of the following grammars is not left recursive, but is equivalent to G?

Consider the following languages is a prime number} Which of the following are CORRECT ? I. is context-free but not regular. II. is not context-free. III. is not context-free but recursive. IV. is det

Let denote that transition function and denote the extended transition function of the - NFA whose transition table is given below: Then is ____

If L and P are two recursively enumerable languages then they are not closed under

Consider the following languages over the alphabet . Let and Which of the following are context-free languages ? I. II.

The minimum possible number of states of a deterministic automaton that accepts the regular language is ____

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L (M) be the language accepted by a Turning machine M. Which of the fo

Given the following statements S1 : Every context-sensitive language L is recursive S2 : There exists a recursive language that is not context-sensitive Which statements are true?

If G is grammar with productions where S is the start variable, then which one of the following is not generated by G?

In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If and denote the sets of letters and digits respectively, which of the following e

Consider the language L given by the regular expression (a+b )* b (a+b ) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automation (DFA) accepting L is

Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-terminals The language is

Consider the following grammar. P xQRS Q yz|z R w| S y What is FOLLOW (Q) ?

Which of the following statements about parser is/are CORRECT? I. Canonical LR is more powerful than SLR. II. SLR is more powerful than LALR III. SLR is more powerful than Canonical LR.

Consider the following context-free grammar over the alphabet = {a,b,c} with S as the start symbol. S abScT|abcT T bT|b Which one of the following represents the language generated by the above gramma

Let be any two context free languages and R be any regular language. Then which of the following is/are CORRECT ? I. is context - free II. is context - free III. is context - free IV. is context - fre

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B*. We say f is computable if there exists a Turning machine M which given an input

Identify the language generated by the following grammar, where S is start variable. S XY X aX|a Y aYb|

Which one of the following is FALSE?