GATE CSE 2014 Set 2
View Questions

GATE CSE

1
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
T(1) = 2T (n/2) + log n
2
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
3
Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.
4
The number of distinct minimum spanning trees for the weighted graph below is ________ GATE CSE 2014 Set 2 Algorithms - Greedy Method Question 15 English
5
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
6
For a C program accessing X[ i ] [ j ] [ k ], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.
t0 = i * 1024 
t1 = j * 32 
t2 = k * 4 
t3 = t1 + t0 
t4 = t3 + t2 
t5 = X[t4] 
Which one of the following statements about the source code for the C program is CORRECT?
7

Consider the grammar defined by the following production rules, with two operators * and +

$$\eqalign{ & S \to T*P \cr & T \to U\,|\,T*U \cr & P \to Q + P\,|\,Q \cr & Q \to id \cr & U \to id \cr} $$

Which one of the following is TRUE?

8
In the diagram shown below, L1 is an Ethernet LAN and L2 is a Token-Ring LAN. An IP packet originates from sender S and traverses to R, as shown. The links within each ISP and across the two ISPs, are all point-to-point’ optical links. The initial value of the TTL field is 32. The maximum possible value of the TTL field when R receives the datagram is ____________. GATE CSE 2014 Set 2 Computer Networks - Lan Technologies and Wi-Fi Question 16 English
9
Consider the store and forward packet switched network given below. Assume that the bandwidth of each link is 106 bytes/sec. A user on host A sends a file of size 103 bytes to host B through routers R1 and R2 in three different ways. In the first case a single packet containing the complete file is transmitted from A to B. In the second case, the file is split into 10 equal parts, and these packets are transmitted from A to B. In the third case, the file is split into 20 equal parts and these packets are sent from A to B. Each packet contains 100 bytes of header information along with the user data. Consider only transmission time and ignore processing, queuing and propagation delays. Also assume that there are no errors during transmission. Let T1, T2 and T3 be the times taken to transmit the file in the first, second and third case respectively. Which one of the following is CORRECT? GATE CSE 2014 Set 2 Computer Networks - Data Link Layer and Switching Question 11 English
10
An IP machine Q has a path to another IP machine H via three IP routers R1, R2, and R3.

Q—R1—R2—R3—H

H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Session layer encryption is used, with DES as the shared key encryption protocol. Consider the following four pieces of information:

$$[I1]$$ The URL of the file downloaded by Q
$$[I2]$$ The TCP port numbers at Q and H
$$[I3]$$ The IP addresses of Q and H
$$[I4]$$ The link layer addresses of Q and H

Which of $$[I1]$$, $$[I2]$$, $$[I3]$$, and $$[I4]$$ can an intruder learn through sniffing at R2 alone?
11
Which one of the following is TRUE about the interior gateway routing protocols – Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)?
12
Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?
13
A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from a HTTP server S. The static HTML page has exactly one static embedded image which is also at S. Assuming no caching, which one of the following is correct about the HTML webpage loading (including the embedded image)?
14
A $$4$$-way set-associative cache memory unit with a capacity of $$16KB$$ is built using a block size of $$8$$ words. The word length is $$32$$ bits. The size of the physical address space is $$4$$ $$GB.$$ The number of bit for the TAG field is ____________.
15
In designing a computer’s cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?
16
If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?
17
Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $$100$$ nanoseconds ($$ns$$) by the data, address, and control signals. During the same $$100$$ $$ns$$, and for $$500$$ $$ns$$ thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $$1$$ millisecond is ____________.
18
The value of a float type variable is represented using the single-precision $$32$$-bit floating point format of $$IEEE-754$$ standard that uses $$1$$ bit for sign, $$8$$ bits for biased exponent and $$23$$ bits for mantissa. $$A$$ float type variable $$X$$ is assigned the decimal value of $$−14.25.$$ The representation of $$X$$ in hexadecimal notation is
19
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___. GATE CSE 2014 Set 2 Data Structures - Trees Question 31 English
20
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
21
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?
22
SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below:
Select * from R where a in (select S.a from S)
23
Consider a join (relation algebra) between relations r(R)and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R)) < size(s(S)), the join will have fewer number of disk block accesses if
24
Consider the following schedule S of transactions T1, T2, T3, T4: GATE CSE 2014 Set 2 Database Management System - Transactions and Concurrency Question 18 English
25
Given an instance of the STUDENTS relation as shown below: GATE CSE 2014 Set 2 Database Management System - Er Diagrams Question 14 English

For (StudentName, StudentAge) to be a key for this instance, the value $$X$$ should NOT be equal to ________.

26
The maximum number of superkeys for the relation schema $$R(E, F, G, H)$$ with $$E$$ as key is ______.
27
Consider the equation $${\left( {123} \right)_5} = {\left( {x8} \right)_y}$$ with $$x$$ and $$y$$ as unknown. The number of possible solutions is _________.
28
The dual of a Boolean function $$F\left( {{x_1},{x_2},\,....,\,{x_n},\, + , \cdot ,'} \right),$$ written as $${F^D}$$, is the same expression as that of $$F$$ with $$+$$ and $$ \cdot $$ swapped. $$F$$ is said to be self-dual if $$F = {F^D} \cdot $$. The number of self-dual functions with $$n$$ Boolean variables is
29
Let $$k = {2^n}.$$ A circuit is built by giving the output of an ݊$$n$$-bit binary counter as input to an $$n$$-to-$${2^n}$$ bit decoder. This circuit is equivalent to a
30
The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functinal be denoted by p. Then 100p = __________________.
31
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is _______________
32
Which one of the following Boolean expressions is NOT A tautology?
33
Consider the following relation on subsets of the set S integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two setss is in U.

Consider the following two statements:
S1 There is a subset of S that is larger than every other subset. S2: There is a subset of S that is smaller than every other subset.
Which one of the following is CORRECT?

34
If the matrix A is such that $$$A = \left[ {\matrix{ 2 \cr { - 4} \cr 7 \cr } } \right]\,\,\left[ {\matrix{ 1 & 9 & 5 \cr } } \right]$$$ then the determinant of A is equal to _________.
35
The number of distinct positive integral factors of 2014 is _______ .
36
A cycle on $$n$$ vertices is isomorphic to its complement. The value of $$n$$ is __________.
37
The product of the non-zero eigenvalues of
the matrix $$\left[ {\matrix{ 1 & 0 & 0 & 0 & 1 \cr 0 & 1 & 1 & 1 & 0 \cr 0 & 1 & 1 & 1 & 0 \cr 0 & 1 & 1 & 1 & 0 \cr 1 & 0 & 0 & 0 & 1 \cr } } \right]$$ is ____ .
38
Each of the nine words in the sentence "The Quick brown fox jumps over the lazy dog" is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is ______________. (Then answer should be rounded to one decimal place.)
39
A computer has twenty physical page frames which contain pages numbered $$101$$ through $$120.$$ Now a program accesses the pages numbered $$1, 2, …, 100$$ in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?
40
A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is $$4$$ bytes in size. Given a $$100\,\, \times \,\,{10^6}$$ bytes disk on which the file system is stored and data block size is $${10^3}$$ bytes, the maximum size of a file that can be stored on this disk in units of $${10^6}$$ bytes is __________.
41
Consider the procedure below for the Producer-Consumer problem which uses semaphores:
semaphore n = 0;
semaphore s = 1;
void producer()
{
    while(true)
    {
     produce();
     semWait(s);
     addToBuffer();
     semSignal(s);
     semSignal(n);
    }
}
void consumer()
{
   while(true)
   {
    semWait(s);
    semWait(n);
    removeFromBuffer();
    semSignal(s);
    consume();
   }
}
Which one of the following is TRUE?
42
Three processes $$A, B$$ and $$C$$ each execute a loop of $$100$$ iterations. In each iteration of the loop, a process performs a single computation that requires $${t_c}\,\,CPU$$ milliseconds and then initiates a single $${\rm I}/O$$ operation that lasts for $${t_{io}}$$ milliseconds. It is assumed that the computer where the processes execute has sufficient number of $${\rm I}/O$$ devices and the $$OS$$ of the computer assigns different $${\rm I}/O$$ devices to each process. Also, the scheduling overhead of the $$OS$$ is negligible. The processes have the following characteristics:
Process id tc tio
A 100 ms 500 ms
B 350 ms 500 ms
C 200 ms 500 ms

The processes $$A, B,$$ and $$C$$ are started at times $$0, 5$$ and $$10$$ milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of $$50$$ milliseconds. The time in milliseconds at which process $$C$$ would complete its first $${\rm I}/O$$ operation is __________.

43
Consider the function func shown below:
int func(int num) 

{
         int count = 0;
         while(num)
         {
                count++;
                num >>= 1;
         }
  return (count);
}

The value returned by func(435) is _________.
44
Suppose n and p are unsigned int variables in a C program. We wish to set p to $${}^n{C_3}$$. If n is large, which one of the following statements is most likely to set p correctly?
45
Which one of the following is NOT performed during compilation?
46
Consider the following function
double f (double x) {
    if ( abs (x * x – 3) < 0. 01) return x;
    else return f (x / 2 + 1.5/x);
}
Give a value q (to 2 decimals) such that f(q) will return q:______.
47
Consider the C function given below.
int f(int j)
{
    static int i = 50;
    int k;
    if (i == j)
    {
        printf("something");
        k = f(i);
        return 0;
    }
    else return 0;
}
Which one of the following is TRUE?
48
Which one of the following is TRUE?
49
Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$
Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machine that accepts a string of length $$\left. {2014} \right\}.$$ Then, $$L$$ is
50
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_2} = \left\{ {w \in \left\{ {0,\,\,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(000)'s$$ as $$(111)'s$$$$\left. \, \right\}$$. Which one of the following is TRUE?
51
If $${L_1} = \left\{ {{a^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$ and $${L_2} = \left\{ {{b^n}\left| {n \ge \left. 0 \right\}} \right.} \right.,$$ consider
$$\left. {\rm I} \right)$$ $$\,\,\,{L_{1 \bullet }}{L_2}$$ is a regular language
$$\left. {\rm II} \right)$$ $$\,\,\,{L_{1 \bullet }}{L_2} = \left\{ {{a^n}{b^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$
Which one of the following is CORRECT?
52
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_2} = \left\{ {w \in \left\{ {0,\,\,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(000)'s$$ as $$(111)'s$$$$\left. \, \right\}$$. Which one of the following is TRUE?
53
Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12