**Ans . **

C

**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.

**Ans . **

D

**Explanation :**f(x) = x

^{2}-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

**Ans . **

C

**Explanation :**Number of reflexive relations is 2

^{n2-n}which is 2^{20}for n = 5

**Ans . **

A

**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.

**Ans . **

A

**Explanation :**

**Ans . **

A

**Explanation :**P = (F87B)

_{16}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)_{16}

**Ans . **

D

**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 */

}

**Ans . **

D

**Explanation :**

**Ans . **

D

**Explanation :**

**Ans . **

D

**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.

**Ans . **

B

**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

**Ans . **

C

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

**Ans . **

D

**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

**Ans . **

D

**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.

**Ans . **

B

**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.

**Ans . **

B

**Explanation :**

**Ans . **

B

**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.

**Ans . **

A

**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

**Ans . **

C

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

**Ans . **

A

**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.

**Ans . **

A

**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.

**Ans . **

D

**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.

**Ans . **

A

**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).

**Ans . **

A

**Explanation :**

**Ans . **

A

**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.

**Ans . **

C

**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.

**Ans . **

B

**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

**Ans . **

C

**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.

**Ans . **

A

**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.

**Ans . **

A

**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.

**Ans . **

D

**Explanation :**T1 checks S1

T2 checks S3

T4 checks S2 and S4

**Ans . **

A

**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.

**Ans . **

D

**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.

**Ans . **

D

**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.

**Ans . **

D

**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).

**Ans . **

C

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

**Ans . **

B

**Explanation :**Circuitous: indirect and lengthy

**Ans . **

D

**Explanation :**25 - (15+ 17-10)

**Ans . **

B

**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.

**Ans . **

D

**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.

**Ans . **

D

**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

**Ans . **

B

**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.