GATE CSE 2018 PYQ

Which of the following is application of Breath First Search on the graph?

Of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?

Consider the following undirected graph G: Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.

The running time of an algorithm is given by: Then what should be the relation between , so that the order of the algorithm is constant?

Assume that multiplying a matrix G1 of dimension pxq with another matrix G2 of dimension pxq requires pqr scalar multiplications. Computing the product of n matrices G1G2G3...Gn can be done by parenth

Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respe

Consider the weights and values of items listed below. Note that there is only one unit of each item. The task is to pick a subset of these items such that their total weight is no more than 11 Kgs an

Given two sorted list of size m and n respectively. The number of comparisons needed the worst case by the merge sort algorithm will be:

Which of the following comparisons between static and dynamic type checking incorrect?

Which of the following comment about peep-hole optimization is true?

A particular BNF definition for a "word is given by the following rules. :: = I I :: = I :: = I :: = a I b I c I ......I Y I Z :: = 0 I 1 I 2 I ......I 9 Which of the following lexical entries can be

C onsider the following parse tree for the expression a#b d#e#f, involving two binary operators $ and #. Which one of the following is correct for the given parse tree?

A lexical analyzer uses the following patterns to recognize three tokens over the alphabet {a,b,c}. Note that 'x?' means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the toke

Which one of the following statements is FALSE?

StationA uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 ms and the bottleneck bandwidth on the path between A and B

Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium

Consider an IP packet with a length of 4,500 bytes that includes a 20-byte IPv4 header and a 40-byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum Transmission Unit (MT

________ can detect burst error of length less than or equal to degree of the polynomial and detects burst errors that affect odd number of bits.

Consider the following statements regarding the slow start phase of the TCP congestion control algorithm. Note that stands for the TCP congestion window and MSS denotes the Maximum Segment Size. (i) T

Assuming that for a given network layer implementation, connection establishment overhead is 100 bytes and disconnection overhead is 28 bytes. What would be the minimum size of the packet the transpor

Match the following:

Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (= bits-per-second). The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closest in

In cryptography, the following uses transposition ciphers and the keyword is LAYER. Encrypt the following message. (Spaces are omitted during encrypton) WELCOME TO NETWORK SECURITY!

Avalanche effect in cryptography

Which one of the following algorithm is not used in asymmetric key cryptography?

What is one advantage of setting up a DMZ (Demilitarized Zone) with two firewalls?

Of the following, which best characterizes computers that use memory-mapped I/O?

A particular disk unit uses a bit string to record the occupancy or vacancy of its tracks, with 0 denoting vacant and 1 for occupied. A 32-bit segment of this string has hexadecimal value D4FE2003. Th

A processor has 16 integer registers (R0, R1,...,R15) and 64 floating point registers (F0, F1,...,F63). It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2,

A 32-bit wide main memory unit with a capacity of 1 GB is built using 256M x 4-bit DRAM chips. The number of rows of memory cells in the DRAM chip is . The time taken to perform one refresh operation

A data driven machine is one that executes an instruction if the needed data is available. The physical ordering of the code listing does not dictate the course of execution. Consider the following ps

The following are some events that occur after a device controller issues an interrupt while process L is under execution. (P) The processor pushes the process status of L onto the control stack. (Q)

A byte addressable computer has a memory capacity of and can perform operations. An instruction involving 3 operands and one operator needs maximum of:

Micro program is:

Consider the following processor design characteristics. I. Register-to-register arithmetic operations only II. Fixed-length instruction format III. Hardwired control unit Which of the characteristics

For a multi-processor architecture, in which protocol a write transaction is forwarded to only those processors that are known to possess a copy of newly altered cache line?

The size of the physical address space of a processor is bytes. The word length is bytes. The capacity of cache memory is Bytes. The size of each cache block is words. For a K-way set-associative cach

A particular parallel program computation requires 100 sec when executed on a single processor, if 40% of this computation is inherently sequential (i.e. will not benefit from additional processors),

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF an

Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys. Which one of the relatio

For a database relation R(a,b,c,d) where the domain of a,b,c and d include only atomic value, only the following functions dependencies and those that can be inferred from them hold a c b d The relati

Given relations R(w,x) and S(y,z), the result of SELECT DISTINCT w,x FROM R,S is guaranteed to be same as R, if

The set of attributes X will be fully functionally dependent on the set of attributes Y if the following conditions are satisfied.

in a file which contains 1 million records and the order of the tree is 100, then what is the maximum number of nodes to be accessed if B+ tree index is used?

In E-R model, Y is the dominant entity and X is subordinate entity

Consider the set of relations given below and the SQL query that follows: Students: (Roll_number, Name, Date_of_birth ) Coursed: (Course_number, Course_name, Instructor ) Grades: (Roll_number, Course_

Immunity of the external schemas (or application programs) to changes in the conceptual scheme is referred to as:

Which of the following is dense index?

Considering the following table in a relational database : According to the data shown in the table, which of the following could be a candidate key of the table?

In an Entity-Relationship (ER) model, suppose R is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in R and that the cardinality of E1 is grea

Consider the following two tables and four queries in SQL. Which one of the queries above is certain to have an output that is a superset of the outputs of the other three queries?

Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query Let LOJ denote the natural left outer-join operation. Assume that r

Let us assume that transaction T1 has arrived before transaction T2. Consider the schedule s=r1(A);r2(B):w2(A);w1(B) Which of the following is true?

Given the value of radix r is

Any set of Boolean operation that is sufficient to represent all Boolean expression is said to be complete. Which of the following is not complete ?

In the diagram above, the inverter (NOT gate) and the AND-gates labeled 1 and 2 have delays of 9, 10 and 12 nanoseconds (ns), respectively. Wire delays are negligible. For certain values a and c, toge

A computer uses ternary system instead of the traditional systen, An n bit string in the binary system will occupy

Consider the unsigned 8-bit fixed point binary Number System below, where the position of the binary point is between . Assume is the most significant bit. Some of the decimal numbers listed below can

If a variable can take only integral values from 0 to n, where n is an integer, then the variable can be represented as a bit-field whose width is (the log in the answer are to the base 2, and means t

Consider the minterm list form of a Boolean function F given below. Here, m denotes a minterm and d denotes a don't care term. The number of essential prime implicants of the function F is ______.

Let and denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?

Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. The number of states in the state transition diagram of this circuit that have

The chromatic number of the following graph is _______.

Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (G), medium (M) and low (L). Let P( ) denote the probability that Guwahati has high temperature. Similarly, P( ) and P(

Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is ________.

A class of 30 students occupy a classroom containing 5 rows of seats, with 8 seats in each row. If the students seat themselves at random, the probability that sixth seat in the fifth row will be empt

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

Which one of the following is a closed form expression for the generating function of the sequence , where for all n = 0, 1, 2,...?

Consider a matrix P whose only eigenvectors are the multiples of . Consider the following statements. (I) P does not have an inverse (II) P has a repeated eigenvalue (III) P cannot be diagonalized Whi

Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obta

The value of correct to three decimal places (assuming that = 3.14 ) is

The domain of the function is:

Which of the following is application of Breath First Search on the graph?

(G,*) is an abelian group. Then

Consider the first-order logic sentence where is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose has a model with a un

The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer and a value K, determine if there is a subset of the given set with sum equa

Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respe

Two people, P and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until t

Let N be the set of natural numbers. Consider the following sets. P: Set of Rational numbers (positive and negative) Q: Set of functions from {0, 1} to N R: Set of functions from N to {0, 1} S: Set of

The number of edges in a regular graph of degree: d and n vertices is:

Consider a matrix Note that denotes the transpose of v. The largest eigenvalue of A is _____.

In multi-programmed systems, it is advantageous if some programs such as editors and compilers can be shared by several users. Which of the following must be true of multi-programmed systems in order

Determine the number of page faults when references to pages occur in the order 1,2,4,5,2,1,2,4. Assume that the main memory can accommodate 3 pages and the main memory already has the pages 1 and 2,

In a system, there are three types of resources: E, F and G. Four processes execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Ma

Procedures P1 and P2 have a producer-consumer relationship, communicating by the use of a set of shared buffers. P1 : repeat Obtain an empty buffer Fill it Return a full buffer forever P2: repeat Obta

Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a t

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and

Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, ... , 199), and 256 sectors per track (numbered as 0, 1, ... , 255). The following 6 disk requests

A computer has 1000K of main memory. The jobs arrive and finish in the following sequence. Job 1 requiring 200 K arrives Job 2 requiring 350 K arrives Job 3 requiring 300 K arrives Job 1 finishes Job

The difference between a named pipe and a regular file in Unix is that

Consider a system having m resources of the same type. These resources are shared by 3 processes A,B,C, which have peak time demands of 3,4,6 respectively. The minimum value of m that ensures that dea

Disk requests come to a disk driver for cylinders in the order 10, 22, 20, 2, 40, 6 and 38 at a time when the disk drive is reading from cylinder 20. The seek time is 6 ms/cylinder. The total seek tim

The following C program: { fork(); fork(); printf("yes"); } If we execute this core segment, how many times the string yes will be printed?

The Operating System of a computer may periodically collect all the free memory space to form contiguous block of free space. This is called:

Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operatio

Consider the following program written in pseudo-code. Assume that x and y are integers. Count(x,y) { if (y != 1){ if (x != 1) { print("*"); Count(x/2, y); } else { y = y-1; Count(1024, y); } } } The

A hash table with 10 buckets with one slot pet per bucket is depicted here. The symbols, S1 to S7 are initially entered using a hashing function with linear probing. The maximum number of comparisons

Given a binary-max heap. The elements are stored in an arrays as 25,14,16,13,10,8,12. What is the content of the array after two delete operations?

Consider the following C program: main() { float sum= 0.0, j=1.0,i=2.0; while(i/j>0.001){ j=j+1; sum=sum+i/j; printf("%f/n", sum); } }

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.

Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?

A language with string manipulation facilities uses the following operations. head(s)- returns the first character of the string s tails(s)- returns all but the first character of the string s concat(

Consider the following C program. #include 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

A doubly linked list is declared as: struct Node { int Value; struct Node *Fwd; struct Node *Bwd; }; Where Fwd and Bwd represent forward and backward link to the adjacent elements of the list. Which o

What is the output of tho following program? main(){ int x=2, y=5; if(x < y) return (x=x+y); else printf("z1"); printf("z2"); }

Assume A and B are non-zero positive integers. The following code segment: while(A!=B){ if(A > B) A -= B; else B -= A; } cout << A; // printing the value of A

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be i

Consider the following C++ program int a (int m) {return ++m;} int b(int&m) {return ++m;} int{char &m} {return ++m;} void main() { int p = 0, q=0, r = 0; p += a(b(p)) ; q+= b(a(q);) r+=a(c(r)); cout <

Consider the following C code segment int f(int x) { if(x<1) return 1; else return (f(x-1) + g(x)); } int g(int x) { if(x<2) return 2; else return (f(x-1) + g(x/2)); } Of the following, which best des

The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any

Consider the following C code. Assume that unsigned long int type length is 64 bits. unsigned long int fun(unsigned long int n){ unsigned long int i, j = 0, sum = 0; for (i = n; i > 1; i = i/2) j++; f

Consider the following program { int x=1; printf("%d",(*char(char*)&x)); } Assuming required header files are included and if the machine in which this program is executed is little endian, then the o

Consider the following C code segment: #include main() { int i, j, x; scanf("%d", &x); i=1; j=1; while (i<10) { j =j*i; i= i+1; if(i==x) break; } } For the program fragment above, which of the followi

An array A consists of n integers in locations A[0],A[1],...A[n-1]. It is required to shift the elements of the array cyclically to the left by k places, where . An incomplete algorithm for doing this

Consider the following C program: #include int counter = 0; int calc (int a, int b) { int c; counter++; if (b==3) return (a*a*a); else { c = calc(a, b/3); return (c*c*c); } } int main (){ calc(4, 81);

Consider the following declaration : structaddr { char city[10]; char street[30]; int pin; }; struct { char name[30]; int gender; struct addr locate; } person, *kd = &person; Then can be used instead

Consider the following C program: #include void fun1(char *s1, char *s2){ char *tmp; tmp = s1; s1 = s2; s2 = tmp; } void fun2(char **s1, char **s2){ char *tmp; tmp = *s1; *s1 = *s2; *s2 = tmp; } int m

Consider the following languages: I. II. III. IV. Which of the languages above are context-free?

Choose the correct statement -

CFG (Context Free Grammar) is not closed under:

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

A CFG (Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form or . Let G be a CFG in CNF. To derive a string of terminals of length x, the number of p

Given a language L, define as follows: for all The order of a language L is defined as the smallest k such that . Consider the language L1 (over alphabet 0) accepted by the following automaton. The or

Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. (I) For an unrestricted grammar G and a string w, whether w L(G)

The FSM (Finite State Machine) machine pictured in the figure above

The set of all recursively enumerable languages is