GATE 2014 [Set3]
Question 1 
While trying to collect(I) an envelope from under the table(II), Mr. X fell down (III) and was losing consciousness (IV) Which one of the above underlined parts of the sentence is NOT appropriate?
I  
II  
III  
IV 
Question 2 
If she _____________ how to calibrate the instrument, she ______________ done the experiment.
knows, will have  
knew, had  
had known, could have  
should have known, would have 
Rule: If + past perfect then result to be perfect conditional (or) perfect continuous condition.
Then answer is Option C.
Question 3 
Choose the word that is opposite in meaning to the word “coherent”.
sticky  
wellconnected  
rambling  
friendly 
Rambling = lengthy and confused (or) inconsequential
Question 4 
Which number does not belong in the series below?
2, 5, 10, 17, 26, 37, 50, 64
17  
37  
64  
26 
2 = 1^{2}+1
5 = 2^{2}+1
10 = 3^{2}+1
17 = 4^{2}+1
26 = 5^{2}+1
37 = 6^{2}+1
50 = 7^{2}+1
64 = 8^{2}+0
64 does not belong to the series.
Question 5 
The table below has questionwise data on the performance of students in an examination. The marks for each question are also listed. There is no negative or partial marking in the examination.
What is the average of the marks obtained by the class in the examination?
1.34  
1.74  
3.02  
3.91 
Total marks obtained = (21×2)+(15×3)+(23×2) = 133
Average marks = 133/44 = 3.02
Question 6 
A dance programme is scheduled for 10.00 a.m. Some students are participating in the programme and they need to come an hour earlier than the start of the event. These students should be accompanied by a parent. Other students and parents should come in time for the programme. The instruction you think that is appropriate for this is
Students should come at 9.00 a.m. and parents should come at 10.00 a.m.  
Participating students should come at 9.00 a.m. accompanied by a parent, and other parents and students should come by 10.00 a.m.  
Students who are not participating should come by 10.00 a.m. and they should not bring their parents. Participating students should come at 9.00 a.m.  
Participating students should come before 9.00 a.m. Parents who accompany them should come at 9.00 a.m. All others should come at 10.00 a.m. 
→ All other students and parents should come in time for the programme i.e. 10.00 am.
→ Option B is correct answer.
→ In option D, they gave, all other should come at 10.00 am that includes student's parents, staff and all others. So this is not correct option.
Question 7 
By the beginning of the 20^{th} century, several hypotheses were being proposed, suggesting a paradigm shift in our understanding of the universe. However, the clinching evidence was provided by experimental measurements of the position of a star which was directly behind our sun.
Which of the following inference(s) may be drawn from the above passage?
 (i) Our understanding of the universe changes based on the positions of stars
(ii) Paradigm shifts usually occur at the beginning of centuries
(iii) Stars are important objects in the universe
(iv) Experimental evidence was important in confirming this paradigm shift
(i), (ii) and (iv)  
(iii) only  
(i) and (iv)  
(iv) only 
(i) is incorrect as it generalizes the experimental evidence of the star and assumes it to be always true, which may not be the case every time.
(ii) and (iii) is anyway wrong.
Hence, answer is option (D).
Question 8 
The Gross Domestic Product (GDP) in Rupees grew at 7% during 20122013. For international comparison, the GDP is compared in US Dollars (USD) after conversion based on the market exchange rate. During the period 20122013 the exchange rate for the USD increased from Rs. 50/ USD to Rs. 60/ USD. India’s GDP in USD during the period 20122013
increased by 5%  
decreased by 13%  
decreased by 20%  
decreased by 11% 
GDP in rupees = x
GDP in dollars = x/50
Increase in GDP in rupees = 7%
∴ New GDP in rupees = 1.07x
New GDP in dollars = 1.07x/60
Change = ((1.07x/60)  (x/50))/(x/50) = 6.5/60 = 10.83%
As it is negative, the value has decreased.
GDP in VSD has decreased by 11%.
Question 9 
The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students in 2011 and 2012 is equal, what is the ratio of male students in 2012 to male students in 2011?
1:1  
2:1  
1.5:1  
2.5:1 
Male to female students ratio in 2011 = 1 : 1
Male to female students ratio in 2012 = 1.5 : 1 = 3 : 2
⇒ M_{1}/F_{1} = 1:1
M_{1} = F_{1}  (1)
⇒ M_{2}/F_{2} = 1:1
2M_{2} = 3F_{2}  (2)
Given,
F_{1} = F_{2}  (3) From (1) & (2)
M_{1}/M_{2} = F_{1}/(3F_{2}/2) = 2F_{1}/3F_{2}
But from (3)
M_{1}/M_{2} = 2/3
We need to find
M_{2} : M_{1} = 3 : 2 = 1.5 : 1
Question 10 
Consider the equation: (7526)_{8}  (Y)_{8 } = (4364)_{8}, where (X)_{N} stands for X to the base N. Find Y.
1634  
1737  
3142  
3162 
⇒ 1/8 = (7526)_{8}  (4364)_{8}
Base 8 ⇒ 0 to 7 digits
When you are borrowing you will add the value of the base, hence 2 becomes (2+8) = 10
Y = 3142
Question 11 
Consider the following statements:
P: Good mobile phones are not cheap Q: Cheap mobile phones are not good L: P implies Q M: Q implies P N: P is equivalent to Q
Which one of the following about L, M, and N is CORRECT?
Only L is TRUE.  
Only M is TRUE.  
Only N is TRUE.  
L, M and N are TRUE. 
So, given statement can be sub divided such that we can utilize the negation of this atomic statements.
Suppose, X is Good mobile and Y is cheap then
P: (Good(x) → ~cheap(x)) → (~good(x) ∨ ~cheap(x))
Q: cheap(x) → ¬good(x) ⟺ ((¬cheap(x) ∨ good(x)) ⟺ ¬good(x) ∨ ¬cheap(x))
All these are contra positive.
All L, M, N are true.
Question 12 
Let X and Y be finite sets and f: X→Y be a function. Which one of the following statements is TRUE?
For any subsets A and B of X, f(A ∪ B) = f(A)+f(B)  
For any subsets A and B of X, f(A ∩ B) = f(A) ∩ f(B)  
For any subsets A and B of X, f(A ∩ B) = min{ f(A),f(B)}  
For any subsets S and T of Y, f^{ 1} (S ∩ T) = f^{ 1} (S) ∩ f^{ 1} (T) 
We need to consider subsets of 'x', which are A & B (A, B can have common elements are exclusive).
Similarly S, T are subsets of 'y'.
To be a function, each element should be mapped with only one element.
(a) f(A∪B) = f(A)+f(B)
{a,b,c}∪{c,d,e} = {a,b,c} + {c,d,e}
{a,b,c,d,e} = 3+3
5 = 6 FALSE
(d) To get inverse, the function should be oneone & onto.
The above diagram fulfills it. So we can proceed with inverse.
f^{1} (S∩T ) = f^{1} (S)∩f^{1} (T)
f^{1} (c) = f^{1} ({a,b,c})∩f^{1} ({c,d,e})
2 = {1,2,3}∩{2,4,5}
2 = 2 TRUE
Question 13 
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4. The size of L is __________.
5  
6  
7  
8 
So, 15 is divided by {1, 3, 5, 15}.
As minimum is 4 and total is 15, we eliminate 1,3,15.
Answer is 5.
Question 14 
Which one of the following statements is TRUE about every n × n matrix with only real eigenvalues?
If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative.  
If the trace of the matrix is positive, all its eigenvalues are positive.  
If the determinant of the matrix is positive, all its eigenvalues are positive.  
If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive. 
• The product of the n eigenvalues of A is the same as the determinant of A. •
A: Yes, for sum to be negative there should be atleast one negative number.
B: There can be one small negative number and remaining positive, where sum is positive.
C: Product of two negative numbers is positive. So, there no need of all positive eigen values.
D: There is no need for all eigen values to be positive, as product of two negative numbers is positive.
Question 15 
If V_{1} and V_{2} are 4dimensional subspace of a 6dimensional vector space V, then the smallest possible dimension of V_{1}∩V_{2} is ______.
2  
3  
4  
5 
For eg: a two dimensional vector space have x, y axis. For dimensional vector space, it have x, y, z axis.
In the same manner, 6 dimensional vector space has x, y, z, p, q, r (assume).
Any subspace of it, with 4 dimensional subspace consists any 4 of the above. Then their intersection will be atmost 2.
[{x,y,z,p} ∩ {r,q,p,z}] = #2
V_{1} ∩ V_{2} = V_{1} + V_{2}  V_{1} ∪ V_{2} = 4 + 4 + (6) = 2
Question 16 
If , then the value of k is equal to ________.
4  
5  
6  
7 
We have xSinx,
We can observe that it is positive from 0 to π and negative in π to 2π.
To get positive value from π to 2π we put ‘‘ sign in the (π, 2π)
Question 17 
Consider the following minterm expression for F:
F(P,Q,R,S) = Σ0,2,5,7,8,10,13,15
The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sumofproducts form for F is:
Question 18 
Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.
f (x, y, a, b) { if (x is 1) y = a; else y = b; }
Which one of the following digital logic blocks is the most suitable for implementing this function?
Full adder  
Priority encoder  
Multiplexor  
Flipflop 
x is the select line, I_{0} is 'b' and I_{1} is a.
The output line, y = xa + x’b
Question 19 
Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency.

P1: Fourstage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns.
P2: Fourstage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns.
P3: Fivestage pipeline with stage latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns.
P4: Fivestage pipeline with stage latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock frequency?
P1  
P2  
P3  
P4 
So CP_{P1} = Max(1,2,2,1) = 2ns
CP_{P2} = Max(1,1.5,1.5,1.5) = 1.5ns
CP_{P3} = Max(0.5,1,1,0.6,1) = 1ns
CP_{P4} = Max(0.5,0.5,1,1,1.1)=1.1ns
As frequency ∝ 1/C.P, so least clock period will give the highest peak clock frequency.
So, f_{P3} = 1/1ns = 1GHz
Question 20 
Let A be a square matrix of size n x n. Consider the following program. What is the expected output?
C = 100 for i = 1 to n do for j = 1 to n do { Temp = A[i][j] + C A[i][j] = A[j][i] A[j][i] = Temp  C } for i = 1 to n do for j = 1 to n do Output(A[i][j]);
The matrix A itself  
Transpose of the matrix A  
Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A  
None of the above 
For first row iteration, it get swapped and becomes
For second row iteration, it comes to the original position
=A
So, it is the same matrix A.
Question 21 
The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X^{5} + 4X^{3} + 6X + 5 for a given value of X, using only one temporary variable is ________.
7  
8  
9  
10 
P(X) = x^{5}+4x^{3}+6x+5
= x(x^{4}+4x^{2}+6)+5
= x(x(x^{3}+4x)+6)+5
= x(x(x(x^{2}+4))+6)+5
= x(x(x(x(x)+4))+6)+5
4 multiplications & 3 additions.
4 + 3 = 7
Question 22 
Consider the following rooted tree with the vertex labeled P as t he root:
The order in which the nodes are visited during inorder traversal is
SQPTRWUV  
SQPTUWRV  
SQPTWUVR  
SQPTRUWV 
Inorder Traversal: Left, Root, Middle, Right.
So, during inorder traversal whenever we visit the node second time then print it.
So, output will be,
S Q P T R W U V
Question 23 
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
19  
20  
21  
22 
Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.
Question 24 
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
O(n^{2})  
O(n log n)  
Θ(n logn)  
O(n^{3}) 
Question 25 
The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________.
a*b*(ba)*a*
3  
4  
5  
6 
{ϵ, a, b, aa, ab, ba, bb}
Let’s check all the string of length 3.
The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}
But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).
Question 26 
Let Σ be a finite nonempty alphabet and let 2^{Σ*} be the power set of Σ*. Which one of the following is TRUE?
Both 2^{Σ*} and Σ* are countable  
2^{Σ*} is countable and Σ* is uncountable  
2^{Σ*} is uncountable and Σ* is countable  
Both 2^{Σ*} and Σ* are uncountable 
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2^{Σ*} is uncountable, it has been already proved by using Diagonalization method.
Question 27 
One of the purposes of using intermediate code in compilers is to
make parsing and semantic analysis simpler.  
improve error recovery and error reporting.  
increase the chances of reusing the machineindependent code optimizer in other compilers.  
improve the register allocation. 
Question 28 
Which of the following statements are CORRECT?

1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
1 and 2 only  
2 and 3 only  
3 and 4 only  
1 and 3 only 
Question 29 
In the context of modular software design, which one of the following combinations is desirable?
High cohesion and high coupling  
High cohesion and low coupling  
Low cohesion and high coupling  
Low cohesion and low coupling 
Cohesion is a measure of internal strength within a module, whereas coupling is a measure of inter dependency among the modules. So in the context of modular software design there should be high cohesion and low coupling.
Question 30 
A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?
4, 7, 6, 1, 7, 6, 1, 2, 7, 2
6  
7  
8  
9 
Question 31 
What is the optimized version of the relation algebra expression π_{A1}(π_{A2}(σ_{F1}(σ_{F2}(r)))), where A1, A2 are sets of attributes in with A1 ⊂ A2 and F1, F2 are Boolean expressions based on the attributes in r?
π_{A1} (σ_{(F1∧F2)} (r))  
π_{A1} (σ_{(F1∨F2)} (r))  
π_{A2} (σ_{(F1∧F2)} (r))  
π_{A2} (σ_{(F1∨F2)} (r)) 
Two Selects with Boolean expression can be combined into one select with AND of two Boolean expressions.
Question 32 
A prime attribute of a relation scheme is an attribute that appears
in all candidate keys of R.  
in some candidate key of R.  
in a foreign key of R.  
only in the primary key of R . 
Ex: AB, BC, CD are candidate keys of R(ABCD). In the FDs set one attribute may not be part of all the FDs.
Question 33 
In the following pairs of OSI protocol layer/sublayer and its functionality, the INCORRECT pair is
Network layer and Routing  
Data Link Layer and Bit synchronization  
Transport layer and Endtoend process communication  
Medium Access Control sublayer and Channel sharing 
(b) Bit Synchronization is always handled by Physical Layer of OSI model but not Data Link Layer. So Option (b) is INCORRECT.
(c) End – to – End Process Communication is handled by Transport Layer. So Option (c) is CORRECT.
(d) MAC sub layer have 3 types of protocols (Random, Controlled and Channelized Access).
Question 34 
A bitstuffing based framing protocol uses an 8bit delimiter pattern of 01111110. If the output bitstring after stuffing is 01111100101, then the input bitstring is
0111110100  
0111110101  
0111111101  
0111111111 
Output Bit string after stuffing is 01111100101.
Question 35 
Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP v4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D?
(i) TTL (ii) Checksum (iii) Fragment Offset
(i) only  
(i) and (ii) only  
(i) and (ii) only  
(i), (ii) and (iii) 
Question 36 
The identifier of the output interface on which this packet will be forwarded is ______.
1  
2  
3  
4 
Question 37 
Every host in an IPv4 network has a 1second resolution realtime clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a 50bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?
256  
257  
258  
259 
1000 unique Ids ⇒ 1Sec
2^{18} unique Ids ⇒ 2^{18}/1000 = 28 = 256
Question 38 
An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fields in the header of the third IP fragment generated by the router for this packet are
MF bit: 0, Datagram Length: 1444; Offset: 370  
MF bit: 1, Datagram Length: 1424; Offset: 185  
MF bit: 1, Datagram Length: 1500; Offset: 370  
MF bit: 0, Datagram Length: 1424; Offset: 2960 
So Datagram with data 4404 byte fragmented into 3 fragments.
Question 39 
Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.
T1: r1(X); r1(Z); w1(X); w1(Z) T2: r2(Y); r2(Z); w2(Z) T3: r3(Y); r3(X); w3(Y) S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z) S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?
Only S1 is conflictserializable.  
Only S2 is conflictserializable.  
Both S1 and S2 are conflictserializable.  
Neither S1 nor S2 is conflictserializable. 
No cycle, so schedule S1 is conflict serializable.
S2:
There is a cycle, so S2 is not conflict serializable.
Question 40 
Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation.
employee (empId, empName, empAge) dependent(depId, eId, depName, depAge)
Consider the following relational algebra query:
^{∏}_{empId}^{(employee)∏}_{empId}^{(employee}^{⋈}(empId = eID)∧(empAge ≤ depAge)^{dependent)}
The above query evaluates to the set of empIds of employees whose age is greater than that of
some dependent.  
all dependents.  
some of his/her dependents.  
all of his/her dependents. 
Question 41 
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
7  
8  
9  
10 
Question 42 
An operating system uses shortest remaining time first scheduling algorithm for preemptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):
The average waiting time (in milliseconds) of the processes is
5.5  
5.6  
5.7  
5.8 
WT  Waiting Time
CT  Completion Time
TAT  Turn Around Time
TAT = CT  AT < br> WT = TAT  BT
Gantt chart using Shortest remaining time first,
Avg. WT = 15+0+3+4/4 = 22/4 = 5.5
Question 43 
Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.
122  
123  
124  
125 
= 10 + 0.4 × 80 + 80
= 10 + 32 + 80
= 122 ms
Question 44 
Consider the basic block given below.
a = b + c c = a + d d = b + c e = d  b a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are
6 and 6  
8 and 10  
9 and 12  
4 and 4 
c = a + d
d = b + c
e = d  b = b + c  b = c
a = d  b + b = d
So, DAG representation of above basic block respectively,
So, number of nodes = 6 &
number of edges = 6
Question 45 
Which one of the following problems is undecidable?
Deciding if a given contextfree grammar is ambiguous.  
Deciding if a given string is generated by a given contextfree grammar.  
Deciding if the language generated by a given contextfree grammar is empty.  
Deciding if the language generated by a given contextfree grammar is finite. 
We have a membership algorithm which decides that whether a given string is generated by a given contextfree grammar. Similarly, the problems, whether the language generated by a given contextfree grammar is empty and the language generated by a given contextfree grammar is finite are decidable.
Question 46 
Consider the following languages over the alphabet Σ = {0,1,c}:
 L_{1} = {0^{n}1^{n}  n≥0}
L_{2} = {w^{c}w^{r}  w∈{0,1}*}
L_{3} = {ww^{r}  w∈{0,1}*}
Here, w^{r} is the reverse of the string . Which of these languages are deterministic Contextfree languages?
None of the languages  
Only L_{1}  
Only L_{1} and L_{2}  
All the three languages 
But in L_{3}, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L_{3} is not possible. It can be accepted by NPDA only, so L_{3} is CFL but not DCFL.
Question 47 
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a prespecified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y),T(z)). Then the value of the product yz is _____.
150  
151  
152  
153 
Now, it is given that
T(9) = 1 + min(T(y),T(z))
where,
T(y) = steps from y to 100
T(z) = steps from z to 100
where y and z are two possible values that can be reached from 9.
One number that can be reached from 9 is 10. Another no. is 15, the shortcut path from 9, as given in the question.
∴ The value of 'y' and 'z' are 10 and 15.
So, y × z = 10 × 15 = 150
Question 48 
Consider the decision problem 2CNFSAT defined as follows:
 {ΦΦ is a satisfiable propositional formula in CNF with atmost two literals per clause}
For example, is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
NPComplete.  
solvable in polynomial time by reduction to directed graph reachability.  
solvable in constant time since any input instance is satisfiable.  
NPhard, but not NPcomplete. 
Question 49 
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n + m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is ____.
110  
111  
112  
113 
1. n_{1} is the smallest number greater than or equal to L and there is no predecessor n_{1}' of >n_{1} such that n_{1}' is equal to n_{1}.
2. n_{2}2' of n_{2} such that is equal to n_{2}.
Since there are m elements between n_{1} and n_{2}, it takes ‘m’ time to add all elements between n_{1} and n_{2}.
So time complexity is O(log n+m)
So the given expression becomes O(n^{0}log'n+m'log^{0}n)
And a+10b+100c+1000d = 0+10*1+100*1+1000*1 = 10+100 = 110
Because a=0, b=1, c=1 and d=0
Question 50 
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
(97×97×97)/100^{3}  
(99×98×97)/100^{3}  
(97×96×95)/100^{3}  
(97×96×95)/(3!×100^{3}) 
They are picked with equal probability of Hash function since it is uniform hashing.
So to avoid the first 3 slots to be unfilled
= 97/100*97/100*97/100 =((97*97*97))⁄100^{3}
Question 51 
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChildrightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree>leftMostChild == NULL) value = 1; else value = DoSomething(tree>leftMostChild); value = value + DoSomething(tree>rightSibling); } return(value); }
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
number of internal nodes in the tree.  
height of the tree.  
number of nodes without a right sibling in the tree.  
number of leaf nodes in the tree. 
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the subtree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Question 52 
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n1; do { k = (i+j)/2; if (x <= listA[k]) j = k1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return 1; }
Which one of the following statements about the function ProcessArray is CORRECT?
It will run into an infinite loop when x is not in listA.  
It is an implementation of binary search.  
It will always find the maximum element in listA.  
It will return −1 even when x is present in listA. 
k = (i+j)/2;
where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.
So it is an implementation of Binary search.
Question 53 
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.
1.54  
1.55  
1.56  
1.57 
Instruction Fetch (IF),
instruction decode and register fetch (ID/RF),
Instruction execution (EX),
Memory access (MEM),
and register writeback (WB)
P old design:
With stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns
Cycle time = MAX(1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns) = 2.2nsec
Branch penalty = 31 = 2 because the next instruction pointer at the end of the EX stage(which is 3rd stage) in the old design
AVG instruction execution time is
P = T_{avg} = (1+no. of stalls*branch penalty)*cycle time
= (1+0.20*2)2.2
P = 3.08 nsec
Q new design:
ID/RF stage is split into three stages (ID, RF1, RF2) each of latency (2.2)/3 ns = 0.73ns.
The EX stage is split into two stages (EX1, EX2) each of latency 1 ns.
The new design has a total of eight pipeline stages.
Time of stages in new design = {1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns}
Cycle time = MAX(1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns) = 1nsec
Branch penalty = 61 = 5 because the next instruction pointer at the end of the EX2 stage(which is 6th stage) in the new design.
AVG instruction execution time is
Q = T_{avg} = (1+no. of stalls*branch penality)*cycle time
= (1+0.20*5)1
Q = 2 nsec
Therefore, P/Q = 3.08/2 = 1.54
Question 54 
The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10 nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. The cache hitratio is 0.9. The average memory access time (in nanoseconds) in executing the sequence of instructions is __________.
1.68  
1.69  
1.70  
1.71 
= 200 instructions (operations)
Time taken for fetching 100 instructions (equivalent to read) = 90*1ns + 10*5ns = 140ns
Memory operand Read operations = 90% (60)*1ns + 10% (60) × 5ns = 54ns + 30 ns = 84ns
Memory operands Write operations time = 90% (40)*2ns + 10% (40)*10ns
= 72ns + 40ns = 112ns
Total time taken for executing 200 instructions = 140 + 84 + 112 = 336ns
∴ Average memory access time = 336 ns/200 = 1.68ns
Question 55 
The above synchronous sequential circuit built using JK flipflops is initialized with Q2Q1Q0 = 000. The state sequence for this circuit for the next 3 clock cycles is
001, 010, 011  
111, 110, 101  
100, 110, 111  
100, 011, 001 
Question 56 
With respect to the numerical evaluation of the definite integral , where a and b are given, which of the following statements is/are TRUE?
I) The value of obtained using the trapezoidal rule is always greater than or equal to the exact value of the definite integral.
II) The value of obtained using the Simpson’s rule is always equal to the exact value of the definite integral.
I only  
II only  
Both I and II  
Neither I nor II 
Question 57 
The value of the integral given below is
2π  
π  
π  
2π 
Question 58 
Let S be a sample space and two mutually exclusive events A and B be such that A∪B = S. If P(∙) denotes the probability of the event, the maximum value of P(A)P(B) is __________.
0.25  
0.26  
0.27  
0.28 
P(A∪B) = P(A) + P(B) + P(A∩B) = 1 →①
But, as A and B are mutually exclusive events
P(A∩B) = 0
∴ P(A∪B) = P(A) + P(B) = 1 →②
Arithmetic mean of two numbers ≥ Geometric mean of those two numbers
(P(A)+P(B))/2 ≥ √(P(A)∙P(B))
1/2 ≥ √(P(A)∙P(B)) (∵from ②)
Squaring on both sides
1/4 ≥ P(A)∙P(B)
P(A)∙P(B) ≤ 1/4
∴ Maximum value of P(A)P(B) = 1/4 = 0.25
Question 59 
Consider the set of all functions f: {0,1, … ,2014} → {0,1, … ,2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements:
 P. For each such function it must be the case that for every i, f(i) = i.
Q. For each such function it must be the case that for some i, f(i) = i.
R. Each such function must be onto.
Which one of the following is CORRECT?
P, Q and R are true  
Only Q and R are true  
Only P and Q are true  
Only R is true 
So f(i)should be resulting only {0, 1, …2014}
So, every element in range has a result value to domain. This is onto. (Option R is correct)
We have ‘2015’ elements in domain.
So atleast one element can have f(i) = i,
so option ‘Q’ is also True.
∴ Q, R are correct.
Question 60 
There are two elements x, y in a group (G,∗) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that
x * x = y * y = x * y * x = y * x * y * x = e
where e is the identity element. The maximum number of elements in such a group is ________.
4  
5  
6  
7 
a*a^{1} = e
1. x*x = e So x^{1} is x ⇒ x is element of Group
2. y*y = e So y^{1} = y ⇒ y is element of Group
4. (y*x)*(y*x) = x*y*y*x = x*x*e = e So (y*x)^{1} = (y*x)
In ③, ④
x*y, y*x has same inverse, there should be unique inverse for each element.
x*y = y*x (even with cumulative law, we can conclude)
So {x, y, e, x*y} are element of Group.
Question 61 
If G is a forest with n vertices and k connected components, how many edges does G have?
⌊n/k⌋  
⌈n/k⌉  
n–k  
nk+1 
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: nk = 0 edges.
Option 4: nk+1 = 1 edge, which is false.
Question 62 
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
In any planar embedding, the number of faces is at least n/2 + 2  
In any planar embedding, the number of faces is less than n/2 + 2  
There is a planar embedding in which the number of faces is less than n/2 + 2  
There is a planar embedding in which the number of faces is at most n/(δ+1) 
v – e + f = 2 →①
Point ① degree of each vertex is minimum ‘3’.
3×n ≥ 2e
e ≤ 3n/2
From ① :
n3n/2+f = 2 ⇒
Question 63 
The CORRECT formula for the sentence, “not all rainy days are cold” is
∀d (Rainy(d) ∧∼Cold(d))  
∀d (∼Rainy(d) → Cold(d))  
∃d (∼Rainy(d) → Cold(d))  
∃d (Rainy(d) ∧∼Cold(d)) 
= ∼[∀rainy days are cold]
= ∼[∀ days (rainy days ⇒ cold days]
= ∃ days[∼(cold days ∨ ∼rainy days)]
= ∃ days[rainy days ∧ ∼cold days]
Question 64 
Consider the following relational schema:
employee(empId, empName, empDept) customer(custId, custName, salesRepId, rating)
salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?
SELECT empName FROM employee E WHERE NOT EXISTS (SELECT custId FROM customer C WHERE C.salesRepId = E.empId AND C.rating <> `GOOD`);
Names of all the employees with at least one of their customers having a ‘GOOD’ rating.  
Names of all the employees with at most one of their customers having a ‘GOOD’ rating.  
Names of all the employees with none of their customers having a ‘GOOD’ rating.  
Names of all the employees with all their customers having a ‘GOOD’ rating. 
The inner query i.e., ② represents all customers having other than ‘GOOD’ while the entire query represents name of all employees with all their customers having a ‘good rating’.
Question 65 
Let ⊕ denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q:
F(P,Q) = ((1⊕P)⊕(P⊕Q))⊕((P⊕Q)⊕(Q⊕0))
The equivalent expression for F is
P+Q  
P⨁Q  
⊕ is associative i.e P ⊕ (Q ⊕ R) = (P⊕Q) ⊕ R.
P ⊕ P = 0, 1 ⊕ P = P’ and 0 ⊕ Q = Q
(1 ⊕ P) ⊕ ((P ⊕ Q) ⊕ (P ⊕ Q)) ⊕ (Q ⊕ 0)
= P’⊕ (0) ⊕ Q
= P’ ⊕ Q
= (P ⊕ Q)’