v!p!n
Hello reader,
Here I am posting the questions asked in GATE 2015 COMPUTER SCIENCE (CSE) Exam and the answer key. I am thankful to all my friends who have shared these questions. If you also want to share any question other than posted here feel free to comment that here.
Here I am posting the questions asked in GATE 2015 COMPUTER SCIENCE (CSE) Exam and the answer key. I am thankful to all my friends who have shared these questions. If you also want to share any question other than posted here feel free to comment that here.
:)
Here we go.!!
a.A cookie is a piece of code that has a potential to compromise the security of an Internet user.
b. A cookie gains entry to the user's work area through an HTTP Header.
c. It has expiry date and time.
d. It can be used to track the browsing pattern of a user at a particular site.
a. Any personal information that you give to a Web site, including credit card information, will most likely be stored in a cookie unless you have turned off the cookie feature in your browser.
b.
c. The Expires directive in cookie tells the browser the exact/absolute date and time to delete the cookie
d If the user requests a page of the site for first time the server creates a random string and sends it as a cookie back to the browser together with the requested page;this cookie will automatically be sent by the browser to the server every time a new page from the site is requested;the server stores the URL of the requested page, the date/time of the request, and the cookie in a log file. By analyzing the log file collected in the process it is possible to plot browsing pattern.
Ans: a
2.If a binary tree has 20 leaves, then how many nodes will have two children nodes?
If there are n leaves, there will be (n-1)
Answer is 20-1=19
3. In a typical server in which order the operations- accept, bind, listen and recv - will be executing?
a)listen,bind,accept,recv
b)bind,listen,accept,recv
c)listen,accept,bind,recv
d)accept,listen,bind,recv
bind( ) :to associate the socket with a port on server machine
listen( ) :wait for incoming connections
accept( ):accept the connection request and returns new socket file descriptor
recv( ) : accepts the data from the client.
The order is as in (b):
4. Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds in a cache hit. Suppose while running a program, it was observed that 80% of the processor's read requests result in a cache hit. The average read access time in nanoseconds is :
Ans: effective memory access time = (hit rate * cache access time) + (miss rate * access time for cache miss),
(50x20+5x80)/100=14 ns
5. Find the number of divisors for 2100?
To find the number of positive integral divisors, write the number as a product of prime numbers. Add one to exponent value of each prime number and multiply them together .
Read the method in detail here.
Given number 2100 can be represented as 2100=2*3*5*7*2*5=2^2 * 3 * 5^2* 7
Total number of divisors= (2+1)*(1+1)*(2+1)*(1+1)= 3*2*3*2= 36
6. Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
a) Reflexive and symmetric but not transitive
b) Neither Reflexive nor symmetric but transitive
c) Symmetric but not reflexive, not transitive
d) Reflexive but not symmetric, not transitive
Ans c
#Given relation is symmetric for all integers. eg: 7R21 means 21R7
#Given relation cannot be reflexive as a and b should be distinct numbers.
#Given relation may not be transitive Eg: 7R21 and 21 R 3 are true but 7R3 is false.
7. What will the following code print if input is given as ABCD EFGH
void foo(char *a)
{
if(*a && *a != ' ')
foo(a+1);
putchar(*a);
}
a. ABCD EFGH
b. ABCD
c. EFGH
d. DCBA
Ans d
8. Match the following
A. Lexical analysis i. Graph coloring
B. Parsing ii. DFA minimization
C. Register allocation iii. Post order traversal
D. Expression evaluation iv. production tree
Solution:
A -ii B- iv C-i D-iii
9. In a bank transaction scenario, read(x); x:=x-50; write(x); ready(y); y:=y+50; write(y);. The restriction such that the sum of x and y should always be a constant will come under which property?
a. Atomicity
b. Consistency
c. Isolation
d. Durability
Ans: b
10. In an unordered list of numbers find the complexity of an algorithm to search for an element which is neither maximum nor minimum.
a. Θ(n logn)
b. Θ( n)
c. Θ(log n)
d. Θ(1)
Ans: d
We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as Θ(1)
Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20Pick any three elements from given liar. Let the three elements be 10, 20 and 7.
Using 3 comparisons, we can find that the middle element is 10
11. Consider the statements:
S1: If a candidate is corrupted, he will not be elected.
S2: If a candidate is kind, he will be elected.
Which of the conclusions is TRUE?
a. If a candidate is corrupted he will be kind.
b. If a candidate is not corrupted he is not kind.
c. If a candidate is kind, he is not corrupted.
d. If a candidate is not kind he is not corrupted.
Ans : c
12. Find the largest Eigen value for the matrix
[4 5
2 1]
Ans: (4-x)(1-x)-5*2=0
x^2-5x-6=0
Possible value of x are 3,-2,6, and -1.
Thus Maximum value is 6
13. Which among the following should not be discussed in SRS?
a. User Interface issues.
b. Non functional requirements.
c. Design specifications.
d. Interface with third party software.
Ans : c
14. A system has 6 resources and N processes . Each process can demand for 2 resources n maximum. For what value of n deadlock will definitely occur?
a. 1
b. 2
c. 3
d. 4
Ans: Wrong question
15. Which of the following statements are true about Abstract Syntax Tree(AST) and Control Flow graph(CFG)?
a. If N2 is a successor of N1 in AST and CFG the code implementing N2 will always be after the code implementing N1.
b. Neither AST nor CFG will carry a cycle.
c. The maximum number of successors in AST and CFG depends on input program.
d. In AST and CFG each node represents one statement in code.
Ans: c
16. If left and right subtrees of a tree are max heaps, then find the time complexity to convert the tree into heap?
a.Ω(logn)
b. Ω(n)
c.Ω(nlogn)
d. Ω(n^2)
Ans: a
17. A link has a transmission speed of 10^6 bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgment has negligible transmission delay, and that its propagation delay is the same as the data propagation delay. Also assume that the processing delays at nodes are negligible. The efficiency of the stop-and-wait protocol in this setup is exactly 25%. The value of the one-way propagation delay (in milliseconds) is :
Ans: 12
18. Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?
(A) Q1 is in NP, Q2 is NP hard.
(B) Q2 is in NP, Q1 is NP hard.
(C) Both Q1 and Q2 are in NP
(D) Both Q1 and Q2 are NP hard.
Ans: a
19. Consider the function:
int f(n)
{
int x=1,k;
if(n==1)
return x;
for(k=1;k<n;k++)
x=x+f(k)*f(n-k);
return x;
}
What will be the return value for f(5)?
f(1) = 1
f(2)= 1+ 1*1 =2
f(3)=1+1*2=3 ;
3+2*1=5
f(4)= 1+1*5=6
6+2*2=10
10+5*1=15
f(5)= 1+1*15=16
16+2*5=26
26+5*2=36
36+15*1=51
Ans: 51
20.Equation to find duration for software development using COCOMO Model where a,b,c,d
are usual constants:
a. E=a(KLOC)exp(b) D=c(E)exp(d)
b. E=a(KLOC)exp(b) D=c(KLOC)exp(d)
c. E=a exp(b) D=c exp(d)
d. E=c exp(d) D=a exp(b)
Ans:a
21. Find the cardinality of power set of {0 , 1 , 2 , ...., 10}
Ans: Cardinality= 2^(number of elements) =2^11=2048
22. A graph is self complementary if it is isomorphic to its complementary graph. For a self complementary graph of n vertices which of the following is correct?
a. n is a multiple of 4
b. n is odd
c. n is even
d. n is congruent to 0 mod 4 or 1 mod 4
Ans : d
23. Which of the following is correct?
a. Code inspection is done after unit testing is completed.
b. Code walk through and Code inspection are synonymous.
c. Coding standards are evaluated during code inspection
d. Code walk through is done by an independent team.
Ans: a.
Unit testing should be done before Code inspection.
Code inspection and code walk through have many differences. For example, Code inspection is formal, initiated by project team and planned one while walk through is informal, initiated by the author and unplanned.
Code Inspection is done to find and fix mistakes
Code walk throgh is done by the author only
24 Consider a simple check-pointing protocol and the following set of operations in the log.
(start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7);
(checkpoint);
(start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3), (write, T3, z, 7, 2);
If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list?
(A) Undo: T3, T1; Redo: T2
(B) Undo: T3, T1; Redo: T2, T4
(C) Undo: none; Redo: T2, T4, T3, T1
(D) Undo: T3, T1, T4; Redo: T2
Ans: A
In recovery stage, we need not take care of transactions committed before checkpoint.
T2 is committed after checkpoint. Thus redo it.
T1 and T3 are not committed after checkpoint. Thus abort them by undoing
25. If there are ten buckets numbered from 0 to 9 and input values can be in between 0 and 2020, which of the following function can fairly distribute values among buckets?
a. h(i)= i^2 mod 10
b. h(i) = i^3 mod 10
c. h(i) = 11. i^2 mod 10
d. h(i)= 12. i^2 mod 10
Ans: B
26. A grammar is given as :
X0=1X1
X1:= 0X1+ 1X1
X2 := 0X1+ λ
Which of the following regular expressions can correctly represent the grammar?
a. 10(0*+ (10)*)1
b. 10(0*1(10)*)*1
c. 1 (0+10)*1
d. 10(0+10)*1 + 110(0+10)*1
Ans: C
27. Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN. Ethernet frames may carry data up to 1500 bytes (i.e. MTU1500 bytes). Size of UDP header is 8 bytes and size of IP header is 20 bytes. There is no option field in 111 header. How many total number of IP fragments will be transmitted and what will be the contents of offset field in the last fragment?
(A) 6 and 925
(B) 6 and 7400
(C) 7 and 1110
(D) 7 and 8880
Ans: C
28. If a connection has speed of 104560 bits per second and works in TCP connection. If 'α' is the RTT before TCP scaling and 'β' is the window size after TCP scaling then value of α and β will be:
a. 63 ms , 65535 x 2^14
b. 63 ms , 65535 x 2^16
c. 500 ms , 65535 x 2^14
d. 500 ms , 65535 x 2^16
Ans: C
29. The edge which causes graph disconnected on deleting it is called bridge. Which of the following is true about bridge?
a. There will be no bridge in a tree.
b. Bridge can never be a part of a simple cycle.
c. Every edge in a clique having more than 3 nodes is a bridge.
d. If a graph has bridge there will be no cycle in it.
Ans: B
30. A system has memory segments of size 200, 400, 600, 500, 300 and 250
respectively. If the processes of size 357, 210, 468, and 491 are allocated in segments using best fit algorithm, what segments will be left unused?
a. 200 & 300
b. 250 & 300
c. 200 & 400
d. 200 & 250
Ans : A
31. Two operations are performed on given matrix
3 4 45
7 9 105
13 2 195
I . Add third row to second row
II . Subtract third column from first column
then Determinant is:
(I)
3 4 45
20 11 300
13 2 195
(II)
3 4 42
20 11 280
13 2 182
Do the row transform as C3--> C3/14
3 4 3
20 11 20
13 2 13
As C1=C3 Determinant =0
32. Consider a processor with byte-addressable memory. Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes. A stack in the main memory is implemented from memory location (0100)16 and it grows upward. The stack pointer (SP) points to the top element of the stack. The current value of SP is (016E) 16. The CALL instruction is of two words, the first word is the op-code and the second word is the starting address of the subroutine (one word = 2 bytes). The CALL instruction is implemented as follows:
• Store the current value of PC in the stack
• Store the value of PSW register in the stack
• Load the starting address of the subroutine m PC
The content of PC just before the fetch of a CALL instruction is (5FAO) 16. After execution of the CALL instruction, the value of the stack pointer is
(A) (016A) 16 (B) (016C)16 (C) (0170)16 (D) (0172)16
Current value of SP: 016E
PC (2 bytes) will be stored in: 016F and 0170
PSW(2bytes) will be stored in: 0171 and 0172
So after execution of CALL instruction the value of stack pointer is 0172
33.Given two relations: R1(A,B)= {(1,5), (3,7)} and R2(A, C) = {(1 , 7),(4,9)}. R is a relation obtained the doing FULL NATURAL OUTER JOIN between R1 and R2. Find the tuples that cannot be a member of R
a = (1,5,NULL) b = (1,5,9) c = (1,3,7) d = (4,3,9) e = (1,5,7) f= (3,7,NULL) g = (4,NULL,9)
a. a,b,c,d,e not f,g
b. a,b,c,d,e,f,g
c. e,f,g not a,b
d. e
Full natiral outer join of R1 and R2::(1,5,7), (3,7,NULL), (4,NULL,9)
Ans: c
34. Find the minimal number of gates required to implement the function
[D' +AB' +A'C + AC'D +A'C'D]'
Ans: 1
35. Find the minimum number of states in DFA required to represent the regular expression (0+1)*10
Minimal no of states=3 36 )A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is bits.
Ans: 36
37. The number of onto functions (surjective functions) from set X = {1, 2, 3, 4} to set
Y = {a, b, c} is
A function f from X to Y is surjective if every element y in Y has a corresponding element x in X such that f(x) = y.
.In given problem n = 4 and m = 3.
Count the number of partitions of A into m blocks.
The no of partitions of elements 1, 2,3 and 4 of X into 3 blocks is Stirling value S{4,3}=6
Each partition the first block can map to any of the m elements of Y, Total number of mappings will be m!=3!=6
Total number of onto functions= S{n,m}*m!=S{4,3}*3!=6*6=36
38. All possible functions are made between set having 2 and 20 distinct elements respectively. Find the probability of selecting an one to one function:
39. Four branches of a company are located at M,N,O and P. M is north of N at a distance of 4 Km, N is 1 km south east to O, and P is 2 km south to O. what is distance between M to P ?
a. 5.34
b. 6.74
c. 28.5
d. 45.49
Ans: a
40. Which of following statements can be used to find the total weight of 10 poles using following statements.
S1: 1/4th weight of one pole is 5
S2: The total weight of these poles is 160 kg more than the total weight of two poles
a. S1 alone
b. S2 alone
c. either S1 or S2
d. Neither S1 nor S2
Ans C
S1: Total weight= 5/0.25 *10 =200
S2: Total weight=160/8*10 =200
41.Consider a function f(x) = 1 – |x| on –1 ≤ x ≤1. The value of x at which the function
attains a maximum and the maximum value of the function are:
(a) 0, –1
(b) –1, 0
(c) 0, 1
(d) –1, 2
Ans c
42. Let f(x) = x^–(1/3) and A denote the area of the region bounded by f(x) and the X-axis,
when x varies from –1 to 1. Which of the following statements is/are True?
1. f is continuous in [–1, 1]
2. f is not bounded in [–1, 1]
3. A is nonzero and finite
(a) 2 only
(b) 3 only
(c) 2 and 3 only
(d) 1, 2 and 3
The graph for given function is plotted as above.
f is not defined for x<0. Hence it is not continuous in [-1,1]
f is not bounded in [-1,1]
A is nonzero and finite
hence c is answer
43. Consider the three languages given:
L1 : {wxwR| where w R is reversal of w}
L2: {a^m b^n | m≠n where m,n >0}
L3: {a^p b^q c^r | where p,q,r >0}
Which of these is/are regular?
a. L1
b. L3
c. L1 & L3
d. L1 , L2 & L3
44. Which one of the following underline word is correct with reference to sentence
a) Industrialist owns a personnel jet.
b) I daily write my personnel diary.
c) All personnel are given day off.
d) Being religious is a personnel aspect.
Ans c: personnel means "people employed in an organization"
45. Which one of the following word is related to clothes like pair of jeans,shirt,etc
a) fabric
b) textile
c) fiber
d) apparel
a: fabric: cloth produced by weaving
b. textile: a type of cloth
c. Fiber: a thread from which cloth is formed.
d Apparel: clothing
46. Consider the sequence of machine instructions given below::
MUL R5, R0, R1
DIV R6, R2, R3
ADD R7, R5, R6
SUB R8, R7, R4
In the above sequence, R0 to R8 are general purpose registers. In the instructions
shown, the first register stores the result of the operation performed on the second
and the third registers. This sequence of instructions is to be executed in a pipelined
instruction processor with the following 4 stages:
(1) Instruction Fetch and Decode(IF),
(2) Operand Fetch (OF),
(3) Perform Operation (PO)
(4) Write back theResult (WB).
The IF, OF and WB stages take 1 clock cycle each for any instruction.The PO stage takes 1 clock cycle for ADD or SUB instruction, 3 clock cycles for MUL instruction and 5 clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instructions is ___________
Cycle no Operations
========||================
1 IF1 -- -- --
2 IF2 OF1 -- --
3,4,5 IF3 OF2 PO1 --
6,7,8,9,10 IF4 OF3 PO2 WB1
11 -- OF4 PO3 WB2
12 -- --- PO4 WB3
13 -- -- -- WB4
Ans: 13
47. Fill the blanks
we _________ our friend's birthday and we ________ how to make up
a) completely forgot, don't just know
b) forgot completely, don't just know
c) completely forgot, just don't know
d) forgot completely, just don't know
Ans c
48. Calculate distance between S and P
M is 4km north of N
P is 2 km south of O
N is 1km south East of O
a) 5.34
b) 4
c) 28.5
d)6.something
47. If p,q,r,s,t is the arithmetic sequence then which of the following is also an arithmetic sequence
I 2p,2q,2r,2s,2t
II p^2,q^2,r^2,s^2,t^2
III p-3,q-3,r-3,s-3,t-3
a) I & II
b) I & III
c) I only
d) III only
Ans b)
48. In a function integer i,j,k,l
f(i,j,k,l)=max(i,j,k,l)
g(i,j,k,l)=Min(i,j,k,l)
h(i,j,k,l)= remainder of (i*j/k*l) if i*j>k*l or (k*l/i*j) if k*l>i*j
Also a function fgh(i,j,k,l)=f(i,j,k,l) x g(i,j,k,l) x h(i,j,k,l)
compute the value of fg(h(2,5,3,7),4,6,8)
Ans:
fg(h(2,5,3,7),4,6,8)=fg(1,4,6,8)= f(1,4,6,8) * (g(1,4,6,8) =8x1=8
49.The secant method is used to find the root of an equation f(x) = 0. It is started from
two distinct estimates xa and xb for the root. It is an iterative procedure involving
linear interpolation to a root. The iteration stops if f(xb) is very small and then xb
is the solution. The procedure is given below. Observe that there is an expression
which is missing and is marked by? Which is the suitable expression that is to be
put in place of? So that it follows all steps of the secant method?
Secant
Initialize: xa, xb, ε, N // ε = convergence indicator
fb= f(xb)
i = 0
while (i < N and | fb | > ε) do
i = i + 1 // update counter
xt= ? // missing expression for
// intermediate value
xa= xb// reset xa
xb= xt// reset xb
fb= f(xb) // function value at new xb
end while
if |fb| > εthen // loop is terminated with i = N
write “Non-convergence”
else
write “return xb”
end if
(a) xb– (fb– f(xa)) fb/ (xb– xa)
(b) xa– (fa– f(xa)) fa/ (xb– xa)
(c) xb– (fb– xa) fb / (xb – fb(xa)
(d) xa– (xb– xa) fa/ (fb– f (xa))
50.For a given B+ tree of order 1 ,minimum number of nodes to be fetched for a given query
"X greater than or equal to 5 and less than 15"
51. Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50x 10^6 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller's transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512-byte sector of the disk is :
Ans : 6.1
52. The minimum number of JK flipflops required to construct a synchronous counter with the counting sequence (0,0,1,1,2,2,3,3,0,0,......) is:
Ans : 2
53. Out of the following four sentences, select the most suitable sentence with respect to grammar and usage:
a. Since the report lacked needed information, it was of no use to them.
b. The report was useless to them because there were no needed information in it.
c.Since the report did not contain the needed information , it was not real useful to them.
d. Since the report lacked needed information, it would not have been useful to them.
Ans : a
54
