GATE CS 2010

Q1.

Let G = (V,E) be a graph. Define f(G) = summation of d id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with f(S) = f(T),then

|S| = 2|T|

|S| = |T|-1

|S| = |T|

|S| = |T|+1

Ans .

Explanation :
The expression f(G) is basically sum of all degrees in a tree. For example, in the following tree, the sum is 3 + 1 + 1 + 1. Now the questions is, if sum of degrees in trees are same, then what is the relationship between number of vertices present in both trees? The answer is, f(G) and f(T) is same for two trees, then the trees have same number of vertices. It can be proved by induction. Let it be true for n vertices. If we add a vertex, then the new vertex (if it is not the first node) increases degree by 2, it doesn't matter where we add it. For example, try to add a new vertex say 'e' at different places in above example tee.

Q2.

Newton-Raphson method is used to compute a root of the equation x²-13=0 with 3.5 as the initial value. The approximation after one iteration is

3.575

3.676

3.667

3.607

Ans .

Explanation :
f(x) = x²-13
f'(x) = 2x
Applying the above formula, we get
Next x = 3.5 - (3.5*3.5 - 13)/2*3.5
Next x = 3.607

Q3.

What is the possible number of reflexive relations on a set of 5 elements?

2¹⁰

2¹⁵

2²⁰

2²⁵

Ans .

Explanation :
Number of reflexive relations is 2^n²-n which is 2²⁰ for n = 5

Q4.

Consider the set S = {1, w, w2}, where w and w² are cube roots of unity. If * denotes the multiplication operation, the structure (S, *) forms

A group

A ring

An integral domain

A field

Ans .

Explanation :
A group is a set of elements together with an operation that combines any two of its elements to form a third element also in the set while satisfying four conditions called the group axioms, namely closure, associativity, identity and invertibility.

Q5.

The minterm expansion of f(P, Q, R) = PQ + QR' + PR' is

m2 + m4 + m6 + m7

m0 + m1 + m3 + m5

m0 + m1 + m6 + m7

m2 + m3 + m4 + m5

Ans .

Explanation :

Q6.

P is a 16-bit signed integer. The 2's complement representation of P is (F87B)₁₆.The 2's complement representation of 8*P

(C3D8)₁₆

(187B)₁₆

(F878)₁₆

(987B)₁₆

Ans .

Explanation :
P = (F87B)₁₆ is -1111 1000 0111 1011 in bianry Note that most significant bit in the binary representation is 1, which implies that the number is negative. To get the value of the number perform the 2's complement of the number. We get P as -1925 and 8P as -15400 Since 8P is also negative, we need to find 2's complement of it (-15400) Binary of 15400 = 0011 1100 0010 1000 2's Complement = 1100 0011 1101 1000 = (C3D8)₁₆

Q7.

The Boolean expression for the output 'f' of the multiplexer shown below is

(P(XOR)Q(XOR)R)'

P(XOR)Q(XOR)R

(P+Q+R)'

P+Q+R

Ans .

Explanation :
See below comments for explanation.
/* p points to i and q points to j */
void f(int *p, int *q)
{
p = q; /* p also points to j now */
*p = 2; /* Value of j is changed to 2 now */
}

Q8.

What does the following program print?
#include
void f(int *p, int *q)
{
p = q;
*p = 2;
}
int i = 0, j = 1;
int main()
{
f(&i, &j);
printf("%d %d \n", i, j);
getchar();
return 0;
}

2 2

2 1

0 1

0 2

Ans .

Explanation :

Q9.

Two alternative packages A and B are available for processing a database having 10k records.Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

Ans .

Explanation :

Q10.

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

(n-1)/2

n-1

Ans .

Explanation :
It is mentioned that each node has odd number of descendants including node itself, so all nodes must have even number of descendants 0, 2, 4 so on. Which means each node should have either 0 or 2 children. So there will be no node with 1 child. Hence 0 is answer.

Q11.

Which data structure in a compiler is used for managing information about variables and their attributes?

Abstract syntax tree

Symbol table

Semantic stack

Parse Table

Ans .

Explanation :
Symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier in a program's source code is associated with information relating to its declaration or appearance in the source, such as its type, scope level and sometimes its location

Q12.

Which languages necessarily need heap allocation in the runtime environment?

Those that support recursion

Those that use dynamic scoping

Those that allow dynamic data structures

Those that use global variables

Ans .

Explanation :
Heap allocation is needed for dynamic data structures like tree, linked list, etc.

Q13.

One of the header fields in an IP datagram is the Time to Live(TTL)field.Which of the following statements best explains the need for this field?

It can be used to prioritize packets

It can be used to reduce delays

It can be used to optimize throughput

It can be used to prevent packet looping

Ans .

Explanation :
Time to Live can be thought as an upper bound on the time that an IP datagram can exist in the network. The purpose of the TTL field is to avoid a situation in which an undeliverable datagram keeps circulating

Q14.

Which one of the following is not a client server application?

Internet chat

Web browsing

E-mail

ping

Ans .

Explanation :
Ping is not a client server application. Ping is a computer network administration utility used to test the reachability of a host on an Internet Protocol (IP). In ping, there is no server that provides a service.

Q15.

Ans .

Explanation :
A) Always True
(Recursively enumerable - Recursive ) is
Recursively enumerable
B) Not always true
L1 - L3 = L1 intersection ( Complement L3 )
L1 is recursive , L3 is recursively enumerable
but not recursive Recursively enumerable languages
are NOT closed under complement.
C) and D) Always true Recursively enumerable languages
are closed under intersection and union.

Q16.

Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

Ans .

Explanation :

Q17.

Which of the following concurrency control protocols ensure both conflict serialzability and freedom from deadlock? I. 2-phase locking II. Time-stamp ordering

I only

II only

Both I and II

Neither I nor II

Ans .

Explanation :
2 Phase Locking (2PL) is a concurrency control method that guarantees serializability. The protocol utilizes locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction’s life. 2PL may be lead to deadlocks that result from the mutual blocking of two or more transactions. See the following situation, neither T3 nor T4 can make progress. Timestamp-based concurrency control algorithm is a non-lock concurrency control method. In Timestamp based method, deadlock cannot occur as no transaction ever waits.

Q18.

The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?

Ans .

Explanation :
Cyclomatic Complexity of module = Number of decision points + 1
Number of decision points in A = 10 - 1 = 9
Number of decision points in B = 10 - 1 = 9
Cyclomatic Complexity of the integration = Number of decision points + 1
= (9 + 9) + 1
= 19

Q19.

P-3, Q-2, R-4, S-1

P-2, Q-3, R-1, S-4

P-3, Q-2, R-1, S-4

P-2, Q-3, R-4, S-1

Ans .

Explanation :
Module Development and Integration is clearly implementation work Performance Tuning is clearly maintenance work Domain Analysis is clearly Requirements Capture

Q20.

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.
Method Used by P1
while (S1 == S2) ;
Critica1 Section
S1 = S2;

Method Used by P2
while (S1 != S2) ;
Critica1 Section
S2 = not (S1);
Which one of the following statements describes the properties achieved?

Mutual exclusion but not progress

Progress but not mutual exclusion

Neither mutual exclusion nor progress

Both mutual exclusion and progress

Ans .

Explanation :
Mutual Exclusion: A way of making sure that if one process is using a shared modifiable data, the other processes will be excluded from doing the same thing. while one process executes the shared variable, all other processes desiring to do so at the same time moment should be kept waiting; when that process has finished executing the shared variable, one of the processes waiting; while that process has finished executing the shared variable, one of the processes waiting to do so should be allowed to proceed. In this fashion, each process executing the shared data (variables) excludes all others from doing so simultaneously. This is called Mutual Exclusion. Progress Requirement: If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. Solution: It can be easily observed that the Mutual Exclusion requirement is satisfied by the above solution, P1 can enter critical section only if S1 is not equal to S2, and P2 can enter critical section only if S1 is equal to S2. But here Progress Requirement is not satisfied. Suppose when s1=1 and s2=0 and process p1 is not interested to enter into critical section but p2 want to enter critical section. P2 is not able to enter critical section in this as only when p1 finishes execution, then only p2 can enter (then only s1 = s2 condition be satisfied). Progress will not be satisfied when any process which is not interested to enter into the critical section will not allow other interested process to enter into the critical section.

Q21.

A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?

196

192

197

195

Ans .

Explanation :
Access to 100 pages will cause 100 page faults. When these pages are accessed in reverse order, the first four accesses will not cause page fault. All other access to pages will cause page faults. So total number of page faults will be 100 + 96.

Q22.

Which of the following statements are true?
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time

I only

I and III only

II and III only

I, II and III

Ans .

Explanation :
I) Shortest remaining time first scheduling is a pre-emptive version of shortest job scheduling. In SRTF, job with the shortest CPU burst will be scheduled first. Because of this process, It may cause starvation as shorter processes may keep coming and a long CPU burst process never gets CPU. II) Pre-emptive just means a process before completing its execution is stopped and other process can start execution. The stopped process can later come back and continue from where it was stopped. In pre-emptive scheduling, suppose process P1 is executing in CPU and after some time process P2 with high priority then P1 will arrive in ready queue then p1 is pre-empted and p2 will brought into CPU for execution. In this way if process which is arriving in ready queue is of higher priority then p1, then p1 is always pre-empted and it may possible that it suffer from starvation. III) round robin will give better response time then FCFS ,in FCFS when process is executing ,it executed up to its complete burst time, but in round robin it will execute up to time quantum. So Round Robin Scheduling improves response time as all processes get CPU after a specified time. So, I,II,III are true which is option (D). Option (D) is correct answer.

Q23.

Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process.This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?

pq + (1 - p)(1 - q)

(1 - q) p

(1 - p) q

Ans .

Explanation :
A computer can be declared faulty in two cases
1) It is actually faulty and correctly declared so (p*q)
2) Not faulty and incorrectly declared (1-p)*(1-q).

Q24.

What is the probability that divisor of 1099 is a multiple of 1096?

1/625

4/625

12/625

16/625

Ans .

Explanation :

Q25.

The program below uses six temporary variables a, b, c, d, e, f.
a = 1
b = 10
c = 20
d = a+b
e = c+d
f = c+e
b = c+e
e = b+f
d = 5+e
return d+f
Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

Ans .

Explanation :
All of the given expressions use at-most 3 variables, so we never nee more than 3 registers. See http://en.wikipedia.org/wiki/Register_allocation It requires minimum 3 registers. Principle of Register Allocation : If a variable needs to be allocated to a register, the system checks for any free register available, if it finds one, it allocates. If there is no free register, then it checks for a register that contains a dead variable ( a variable whose value is not going to be used in future ), and if it finds one then it allocates. Otherwise it goes for Spilling ( it checks for a register whose value is needed after the longest time, saves its value into the memory, and then use that register for current allocation, later when the old value of the register is needed, the system gets it from the memory where it was saved and allocate it in any register which is available ). But here we should not apply spilling as directed in the question. Let's allocate the registers for the variables. a = 1 ( let's say register R1 is allocated for variable 'a' ) b = 10 ( R2 for 'b' , because value of 'a' is going to be used in the future, hence can not replace variable of 'a' by that of 'b' in R1) c = 20 ( R3 for 'c', because values of 'a' and 'b' are going to be used in the future, hence can not replace variable 'a' or 'b' by 'c' in R1 or R2 respectively) d = a+b ( now, 'd' can be assigned to R1 because R1 contains dead variable which is 'a' and it is so called because it is not going to be used in future, i.e. no subsequent expression uses the value of variable 'a') e = c+d ( 'e' can be assigned to R1, because currently R1 contains value of varibale 'd' which is not going to be used in the subsequent expression.) Note: an already calculated value of a variable is used only by READ operation ( not WRITE), hence we have to see only on the RHS side of the subsequent expressions that whether the variable is going to be used or not. f = c+e ( ' f ' can be assigned to R2, because vaule of 'b' in register R2 is not going to be used in subsequent expressions, hence R2 can be used to allocate for ' f ' replacing 'b' ) b = c+e ( ' b ' can be assigned to R3, because value of 'c' in R3 is not being used later ) e = b+f ( here 'e' is already in R1, so no allocation here, direct assignment ) d = 5+e ( 'd' can be assigned to either R1 or R3, because values in both are not used further, let's assign in R1 ) return d+f ( no allocation here, simply contents of registers R1 and R2 are added and returned) hence we need only 3 registers, R1 R2 and R3.

Q26.

The grammar S -> aSa | bS | c is

LL(1) but not LR(1)

LR(1)but not LR(1)

Both LL(1)and LR(1)

Neither LL(1)nor LR(1)

Ans .

Explanation :
First(aSa) = a
First(bS) = b
First(c) = c
All are mutually disjoint i.e no common terminal between them, the given grammar is LL(1). As the grammar is LL(1) so it will also be LR(1) as LR parsers are more powerful then LL(1) parsers. and all LL(1) grammar are also LR(1) So option C is correct.

Q27.

Let L={w |in (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

(0*10*1)*

0*(10*10*)*

0*(10*1*)*0*

0*1(10*1)*10*

Ans .

Explanation :
Option (A) is incorrect because it cannot accept "110" Option (C) is incorrect because it accept a string with single 1. Option (D) is incorrect because it cannot accept 11101

Q28.

Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

n-1

n+1

2n-1

Ans .

Explanation :
We need minimum n+1 states to build NFA that accepts all substrings of a binary string. For example, following NFA accepts all substrings of "010" and it has 4 states.

Q29.

Consider the following schedule for transactions T1, T2 and T3: Which one of the schedules below is the correct serialization of the above?

T1->>T3->>T2

T2->>T1->>T3

T2->>T3->>T1

T3->>T1->>T2

Ans .

Explanation :
T1 can complete before T2 and T3 as there is no conflict between Write(X) of T1 and the operations in T2 and T3 which occur before Write(X) of T1 in the above diagram. T3 should can complete before T2 as the Read(Y) of T3 doesn’t conflict with Read(Y) of T2. Similarly, Write(X) of T3 doesn’t conflict with Read(Y) and Write(Y) operations of T2. Another way to solve this question is to create a dependency graph and topologically sort the dependency graph. After topologically sorting, we can see the sequence T1, T3, T2.

Q30.

Which of the following functional dependencies hold for relations R(A, B, C) and S(B, D, E):
B -> A
A -> C
The relation R contains 200 tuples and the rel ation S contains 100 tuples. What is the maximum number of tuples possible in the natural join of R and S (R natural join S)

100

200

300

2000

Ans .

Explanation :
From the given set of functional dependencies, it can be observed that B is a candidate key of R. So all 200 values of B must be unique in R. There is no functional dependency given for S. To get the maximum number of tuples in output, there can be two possibilities for S.
1) All 100 values of B in S are same and there is an entry in R that matches with this value. In this case, we get 100 tuples in output.
2) All 100 values of B in S are different and these values are present in R also. In this case also, we get 100 tuples.

Q31.

The following program is to be tested for statement coverage:
begin
if (a== b) {S1; exit;}
else if (c== d) {S2;]
else {S3; exit;}
S4;
end
The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given. T1 : a, b, c and d are all equal T2 : a, b, c and d are all distinct T3 : a = b and c != d T4 : a != b and c = d Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?

T1, T2, T3

T2, T4

T3, T4

T1, T2, T4

Ans .

Explanation :
T1 checks S1
T2 checks S3
T4 checks S2 and S4

Q32.

The following program consists of 3 concurrent processes and 3 binary semaphores.The semaphores are initialized as S0 = 1, S1 = 0, S2 = 0.How many times will process P0 print '0'?

At least twice

Exactly twice

Exactly thrice

Exactly once

Ans .

Explanation :
Initially only P0 can go inside the while loop as S0 = 1, S1 = 0, S2 = 0. P0 first prints '0' then, after releasing S1 and S2, either P1 or P2 will execute and release S0. So 0 is printed again.

Q33.

Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same netmask N. Which of the values of N given below should not be used if A and B should belong to the same network?

255.255.255.0

255.255.255.128

255.255.255.192

255.255.255.224

Ans .

Explanation :
The last octets of IP addresses of A and B are 113 (01110001) and 91 (01011011). The netmask in option (D) has first three bits set in last octet. If netmask has first 3 bits set, then these bits nmust be same in A and B, but that is not the case. In simple words, we can say option (D) is not a valid netmask because doing binary ‘&’ of it with addresses of A and B doesn’t give the same network address. It must be same address as A and B are on same network.

Q34.

Consider the data from above question. When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?

222 nanoseconds

888 nanoseconds

902 nanoseconds

968 nanoseconds

Ans .

Explanation :
Access time from main memory is 200. So total time to access is is 200+20 nanoseconds Similarly for L1 cache to access from L2 cache is 20+2 nanoseconds So total time is 4*(220 + 22) = 968 nanoseconds.

Q35.

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

Ans .

Explanation :
To get the minimum spanning tree with vertex 0 as leaf, first remove 0th row and 0th column and then get the minimum spanning tree (MST) of the remaining graph. Once we have MST of the remaining graph, connect the MST to vertex 0 with the edge with minimum weight (we have two options as there are two 1s in 0th row).

Q36.

Choose the most appropriate word from the options given below to the complete the following sentence: His rather casual remarks on politics ___________ his lack of seriousness about the subject.

masked

belied

betrayed

suppressed

Ans .

Explanation :
There should be word like showed or revealed or betrayed.

Q37.

Which of the following options is closest in meaning to the word Circuitous.

cyclic

indirect

confusing

crooked

Ans .

Explanation :
Circuitous: indirect and lengthy

Q38.

25 persons are in a room. 15 of them play hockey, 17 of them play football and 10 of them play both hockey and football. Then the number of persons playing neither hockey nor football is:>

Ans .

Explanation :
25 - (15+ 17-10)

Q39.

Hari(H), Gita(G), Irfan(I) and Saira(S) are siblings (i.e., brothers and sisters). All were born on 1st January. The age difference between any two successive siblings (that is born one after another) is less than 3 years. Given the following facts:
i. Hari's age + Gita's age > Irfan's age + Saira's age
ii. The age difference between Gita and Saira is 1 year. However Gita is not the oldest and Saira is not the youngest. iii. There are no twins.
In what order were they born (oldest first)?

HSIG

SGHI

IGSH

IHSG

Ans .

Explanation :
H + G > I + S G - S = 1 OR S - G = 1 G is not the oldest and S is not the youngest. We need to try all options one by one.

Q40.

Modern warfare has changed from large scale clashes of armies to suppression of civilian populations. Chemical agents that do their work silently appear to be suited to such warfare; and regretfully, there exist people in military establishments who think that chemical agents are useful tools for their cause. Which of the following statements best sums up the meaning of the above passage:

Modern warfare has resulted in civil strife.

Chemical agents are useful in modern warfare.

Use of chemical agents in warfare would be undesirable

People in military establishments like to use chemical agents in war.

Ans .

Explanation :
Civil Strife means civil disorder, a term used to describe unrest caused by a group of people, which is not true in the light of the given passage. So, A is not the correct option. B is incorrect because there is no fact in the data justifying the usefulness of chemical agents for warfare. C is also incorrect because it is mentioned in the second line that chemical agents appear to be suited for such warfare, which implies that they are desirable. It is mentioned in the last line that there exist people in military establishments who think that chemical agents are useful for warfare, which makes D correct.

Q41.

5 skilled workers can build a wall in 20 days: 8 semi-skilled workers can build a wall in 25 days; 10 unskilled workers can build a wall in 30 days. If a team has 2 skilled, 6 semi-skilled and 5 unskilled workers, how long will it take to build the wall?

Ans .

Explanation :
5 skilled workers can build a wall in 20 days 1 skilled worker can build the same wall in 100 days Capacity of each skilled worker is 1/100 8 semi-skilled workers can build a wall in 25 days 1 semi-skilled worker can build the same wall in 200 days Capacity of each semi-skilled worker is 1/200 Capacity of 1 unskilled worker is 1/300 Capacity of 2 skilled + 6 semi-skilled + 5 unskilled workers is 2(1/100) + 6(1/200) + 5/300 = 1/15

Q42.

Given digits 2, 2, 3, 3, 3, 4, 4, 4, 4 how many distinct 4 digit numbers greater than 3000 can be formed?

Ans .

Explanation :
First digit is either 3 or 4. We'll consider each case separately: (1) First digit is 3: Then the rest of the numbers must come from the list: 2, 2, 3, 3, 4, 4, 4, 4 Therefore we may choose any 3-digit sequence except 222 and 333 for the rest of the digits. This shows there are 3*3*3 - 2 = 25 numbers in this case. (2) First digit is 4: Then the rest of the numbers must come from the list 2, 2, 3, 3, 3, 4, 4, 4 Therefore we may choose any 3-digit sequence except 222 for the rest of the digits. This shows there are 3*3*3 - 1 = 26 numbers in this case. Now, the total number is just 25 + 26 = 51.

upscfever.com

Journey of a Thousand Miles begins with One Click!!!

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments