Ans .

B

1. Explanation :

   Number of entries in page table = 232 / 4Kbyte = 232 / 212 = 220 Size of page table = (No. page table entries)*(Size of an entry) = 220 * 4 bytes = 222 = 4 Megabytes

Ans .

C

1. Explanation :

   The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. By definition, a viable prefix is a prefix of a right sentential form that does not continue past the right end of the rightmost handle of that sentential form. Source http://cse.iitkgp.ac.in/~bivasm/notes/scribe/11CS30001.pdf

Ans .

C

1. Explanation :

   This question is the revision of basics of propositional logic. Conjunction Disjunction of p and q, denoted by p ? q, is the proposition ‘p and q’. The Disjunction p ? q is TRUE when both p and q is TRUE. Disjunction Conjunction of p and q, denoted by p ?q, is the proposition ‘p or q’.The Conjunction p ?q is when anyone of p or q is TRUE. Logical Implication It is a type of relationship between two statements or sentence. Denoted by ‘p ? q’. The conditional statement p ? q is false when p is true and q is false, and true otherwise. i.e. p ? q = ¬p ? q Bi-Condition A bi-conditional statement is a compound statement formed by combining two conditionals under “and.” Bi-conditionals are true when both statements have the exact same truth value. Solution : p?q means both p?q and q?p p?q is equivalent to ?p ? q and q is equivalent to ?q ? p So A and B are fine. D is a different way of writing A p ? q = (p? q) ? (q?p) = (?p ? q) ? (q ? p) [ Since p? q = ?p ? q ] = (?p ? q) ? (?q ? p) = (¬p ? p )? (¬p ?¬q )? (q ?p ) ?(q ?¬q ) (Distributive law) [As ((¬p? p )=0,(q ?¬q )=0) (Complementation) ] (?p ? ?q) ? (p ? q) which is Option (D) Only option which is not equivalent to p?q is option (C). So, option (C) is correct.

Ans .

C

1. Explanation :

   1.TRUE- XML is a structured way of organizing content. 2.FALSE- XML is CASE SENSITIVE whereas HTML is NOT case sensitive. 3.TRUE- XML facilitates User Defined tags whereas HTML has only Pre-Defined tags 4.FALSE- XML tags MUST be closed while HTML tags may NOT be closed.

Ans .

C

1. Explanation :

   A = {5, {6}, {7}} Below is Powerset of A { f, 5, {6}, {7}, {5, {6}}, {5, {7}}, {{6}, {7}}, {5, {6}, {7}} } I is true, as f belongs to Powerset. II is true, as an empty set is a subset of every set. III is true as {5, {6}} belongs to Powerset. IV is false, {5, {6}} is not a subset, but {{5, {6}}} is.

Ans .

A

1. Explanation :

   HTTP may use different TCP connection for different objects of a webpage if non-persistent connections are used. FTP uses two TCP connections, one for data and another control. TELNET and FTP can only use ONE connection at a time.

Ans .

B

1. Explanation :

   LU decomposition (where 'LU' stands for 'lower upper', and also called LU factorization) factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. | 2 2 | = | l11 0 | * | 1 u12 | | 4 9 | | l21 l22 | | 0 1 | l21 * u12 + l22 * 1 = 9 ------ (1) We need to find l21 and u12 l21 * 1 + l22 * 0 = 4 l21 = 4 l11 * U12 + 0 * 1 = 2 l11 = 2 U12 = 1 Putting value of l21 and u12 in (1), we get 4 * 1 + l22 * 1 = 9 l22 = 5

Ans .

B

1. Explanation :

   TCP sequence number of a segment is the byte number of the first byte in the segment. For example, if the segment contains 500 bytes which are from 1000 to 1499, then sequence number of the segment would be 1000 and sequence number of next segment would be 1500. Receiver window changes when TCP data is processed by application layer of receiver side.

Ans .

D

1. Explanation :

   Refer http://en.wikipedia.org/wiki/Ring_counter#Johnson_Counter_.284-bits.29 The four bit Johnson's counter connects the complement of the output of the last shift register to the input of the first register with shift distance=1 i.e 1 bit will shift/cycle It will work as follows: 0000 //Last 0 complemented and fed as input to first register 1000 1100 1110 1111 //Last 1 complemented and fed as input to first register 0111 0011 0001 0000

Ans .

C

1. Explanation :

   In Symmetric Key Cryptography, access of key is with both the parties. It implies every person needs to communicate N-1 other users using different keys i.e 1+2+3...N-2+N-1 This is like number of edges needed in a complete graph with N vertices is N(N-1)/2. Answer is therefore C

Ans .

B

1. Explanation :

   Length and checksum can be modified when IP fragmentation happens. Time To Live is reduced by every router on the route to destination. Only Source Address is what IP address can not change SO B is the answer.

Ans .

B

1. Explanation :

   The time taken by search, insert and delete on a BST is always proportional to height of BST. Height may become O(n) in worst case.

Ans .

C

1. Explanation :

   In Clustered Index, data blocks are stored in a way to match the index. Therefore, only one clustered index can be created on a given database table. Refer https://msdn.microsoft.com/en-IN/library/ms190457.aspx for more details.

Ans .

A

1. Explanation :

   Number of nodes is maximum for a perfect binary tree. A perfect binary tree of height h has 2h+1 - 1 nodes Number of nodes is minimum for a skewed binary tree. A perfect binary tree of height h has h+1 nodes.

Ans .

A

1. Explanation :

   S = 1/1*2 + 1/2*3 + 1/3*4 + ..... + 1/99*100 = (1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + .... + (1/99 - 1/100) = (1 + 1/2 + 1/3 .... 1/99) - (1/2 + 1/3 + 1/4 ... 1/100) = 1 - 1/100 = 99/100 = 0.99

Ans .

C

1. Explanation :

   Below is result of given query. Note that there are only two student names and query prints sum(P.Marks) for every student. Student_Name Marks Raj 310 Rohit 140

Ans .

A

1. Explanation :

   The operation is basically XOR which is both commutative and associative.

Ans .

A

1. Explanation :

   The probability of sending a frame in the first slot without any collision by any of these four stations is sum of following 4 probabilities Probability that S1 sends a frame and no one else does + Probability thatS2 sends a frame and no one else does + Probability thatS3 sends a frame and no one else does + Probability thatS4 sends a frame and no one else does = 0.1 * (1 - 0.2) * (1 - 0.3) *(1 - 0.4) + (1 -0.1) * 0.2 * (1 - 0.3) *(1 - 0.4) + (1 -0.1) * (1 - 0.2) * 0.3 *(1 - 0.4) + (1 -0.1) * (1 - 0.2) * (1 - 0.3) * 0.4 = 0.4404

Ans .

C

1. Explanation :

   In Shortest seek first (SSTF), closest request to the current position of the head, and then services that request next. In SCAN (or Elevator) algorithm, requests are serviced only in the current direction of arm movement until the arm reaches the edge of the disk. When this happens, the direction of the arm reverses, and the requests that were remaining in the opposite direction are serviced, and so on. Given a disk with 100 tracks And Sequence 45, 20, 90, 10, 50, 60, 80, 25, 70. Initial position of the R/W head is on track 50. In SSTF, requests are served as following Next Served Distance Traveled 50 0 45 5 60 15 70 10 80 10 90 10 25 65 20 5 10 10 ----------------------------------- Total Dist = 130 If Simple SCAN is used, requests are served as following Next Served Distance Traveled 50 0 60 10 70 10 80 10 90 10 45 65 [disk arm goes to 100, then to 45] 25 20 20 5 10 10 ----------------------------------- Total Dist = 140 Less Distance traveled in SSTF = 130 - 140 = 10 Therefore, it is not additional but it is less distance traversed by SSTF than SCAN.

Ans .

D

1. Explanation :

   int fun1 (int n) { int i, j, k, p, q = 0; // This loop runs T(n) time for (i = 1; i < n; ++i) { p = 0; // This loop runs T(Log n) times. Refer this for (j=n; j > 1; j=j/2) ++p; // Since above loop runs T(Log n) times, p = T(Log n) // This loop runs T(Log p) times which loglogn for (k=1; k < p; k=k*2) ++q; } return q; } T(n) = n(logn + loglogn) T(n) = n(logn) dominant But please note here we are return q which lies in loglogn so ans should be T(n) = nloglogn Refer this for details.

Ans .

B

1. Explanation :

   The array 40, 30, 20, 10, 15, 16, 17, 8, 4 represents following heap 40 / \ 30 20 / \ / \ 10 15 16 17 / \ 8 4 After insertion of 35, we get 40 / \ 30 20 / \ / \ 10 15 16 17 / \ / 8 4 35 After swapping 35 with 15 and swapping 35 again with 30, we get 40 / \ 35 20 / \ / \ 10 30 16 17 / \ / 8 4 15

Ans .

B

1. Explanation :

   The given pseudo code does following for given x and y which positive integers. 1) It initializes r as x. 2) It repeatedly subtracts y from r until r becomes smaller than y. For every subtraction, it increments count q. 3) Finally r contains remainder, i.e., x%y and q contains ?x/y? See below pseudo code with comments. begin q := 0 // q is going to contain floor(x/y) r := x // r is going to contain x % y // Repeatedly subtract y from x. while r >= y do begin r := r – y q := q + 1 end end

Ans .

D

1. Explanation :

   Number of triplets in L3 = Number of ways in which we can choose 3 elements from 5 with repetition = 5 * 5 * 5 = 125. Now, when we take x = t, then the given condition for L is satisfied for any y and z. Here, y and z can be taken in 5 * 5 = 25 ways. Take x = r, y = p, z = p. Here also, the given condition is satisfied. So, pr > 25 / 125 > 1/5. For x = q, y = r, z = s, the given condition is not satisfied as q ? (r ? s) = q ? p = q, while (q ? r) ? (q ? s) = t ? t = t. So, pr ? 1. Hence D choice.

Ans .

A

1. Explanation :

   x = 2000 Since x is considered as a pointer to an array of 3 integers and an integer takes 4 bytes, value of x + 3 = 2000 + 3*3*4 = 2036 The expression, *(x + 3) also prints same address as x is 2D array. The expression *(x + 2) + 3 = 2000 + 2*3*4 + 3*4 = 2036

Ans .

D

1. Explanation :

The character equation for given matrix is | 1-? 4 | = 0 | b a-?| (1-?)*(a-?) - 4b = 0 Putting ? = -1, => (1 - (-1)) * (a - (-1)) - 4b = 0 => 2a + 2 - 4b = 0 => 2b - a = 1 Putting ? = 7, => (1 - 7) * (a - 7) - 4b = 0 => -6a + 42 - 4b = 0 => 2b + 3a = 21 Solving the above two equations, we get a = 5, b = 3

Ans .

A

1. Explanation :

   
   Initially Q output of D - FF = 1 Initially Q output of JK - FF = 0 Now with the help of present state and next state table we can see what is happening in circuit. Toggle: J = K = 1 Hold : J = K = 0
   
   jk1 We see from table Q output of D-FF is going to next state input of JK-FF and the bits sequence produced is like 110110….. Including initial condition (0) we get output as 0110110110…. Hence answer is (A) part. Another Explanation: Here, it is given that JK flip flop will toggle when J = K = 1 and it will retain the output if J = K = 0. Also, the output of the D flip flop would remain the same as the input. So, we have Initial output : D = 1 JK = 0 After clock 1 : D = 0 (D gets 0 as input from initial output of JK, so output = 0) JK = 1 (J = K = 1 from initial output of D, so output would be toggled from 0 to 1) After clock 2 : D = 1 (D gets 1 as input from previous output of JK, so output = 1) JK = 1 (J = K = 0 from previous output of D, so output would be retained to 1) After clock 3 : D = 1 (D gets 1 as input from previous output of JK, so output = 1) JK = 0 (J = K = 1 from previous output of D, so output would be toggled from 1 to 0) After clock 4 : D = 0 (D gets 0 as input from previous output of JK, so output = 0) JK = 1 (J = K = 1 from previous output of D, so output would be toggled from 0 to 1) After clock 5 : D = 1 (D gets 1 as input from previous output of JK, so output = 1) JK = 1 (J = K = 0 from previous output of D, so output would be retained to 1) Thus, the bit sequence generated at the Q output of the JK flip flop will be 0110110...

Ans .

A

1. Explanation :

   Speedup = ExecutionTimeOld / ExecutionTimeNew ExecutionTimeOld = CPIOld * CycleTimeOld [Here CPI is Cycles Per Instruction] = CPIOld * CycleTimeOld = 4 * 1/2.5 Nanoseconds = 1.6 ns Since there are no stalls, CPUnew can be assumed 1 on average. ExecutionTimeNew = CPInew * CycleTimenew = 1 * 1/2 = 0.5 Speedup = 1.6 / 0.5 = 3.2 Refer http://www.cs.berkeley.edu/~pattrsn/252F96/Lecture2a.pdf for more information on this topic.

Ans .

B

1. Explanation :

   A function is considered as functionally complete if it does not belong to T0,T1,L,M,S which are Property 1: We say that boolean function f preserves zero, if on the 0-input it produces 0. By the 0-input we mean such an input, where every input variable is 0 (this input usually corresponds to the ?rst row of the truth table). We denote the class of zero-preserving boolean functions as T0 and write f ? T0. Property 2: Similarly to T0, we say that boolean function f preserves one, if on 1-input, it produces 1. The 1-input is the input where all the input variables are 1 (this input usually corresponds to the last row of the truth table). We denote the class of one-preserving boolean functions as T1 and write f ? T1. Property 3: We say that boolean function f is linear if one of the following two statements holds for f: For every 1-value of f, the number of 1's in the corresponding input is odd, and for every 0-value of f, the number of 1's in the corresponding input is even. or For every 1-value of f, the number of 1's in the corresponding input is even, and for every 0-value of f, the number of 1's in the corresponding input is odd. If one of these statements holds for f, we say that f is linear1. We denote the class of linear boolean functions with L and write f ? L. Property 4: We say that boolean function f is monotone if for every input, switching any input variable from 0 to 1 can only result in the function’s switching its value from 0 to 1, and never from 1 to 0. We denote the class of monotone boolean functions with M and write f ? M. Property 5: We say that boolean function f(x1,...,xn) is self-dual if f(x1,...,xn) = ¬f(¬x1,...,¬xn). The function on the right in the equality above (the one with negations) is called the dual of f. We will call the class of self-dual boolean functions S and write f ? S. As in our case we can see on giving all i/p to 0 (g )produce 0 so it preserving 0 and can’t be functionally complete. But f is neither preserving 0 nor 1. F is not linear(see defn. of linear above) F is not monotone(see defn. of monotone above) F is not self dual as f(x,y,z) is not equal to –f(-x,-y,-z) So f is functionally complete. Hence ans is (B) part

Ans .

A

1. Explanation :

   The time complexity of insert in unsorted array is O(1), O(Logn) in Min-Heap, O(n) in sorted array and sorted DLL. For unsorted array, we can always insert an element at end and do insert in O(1) time For Min Heap, insertion takes O(Log n) time. Refer Binary Heap operations for details. For sorted array, insert takes O(n) time as we may have to move all elements worst case. For sorted doubly linked list, insert takes O(n) time to find position of element to be inserted. Since number of insertion operations is asymptotically higher, unsorted array is preferred.

Ans .

C

1. Explanation :

   Entity E1. a1 a12 -------- a11 is key Entity E2 a21 a22 -------- a22 is key Entity E3 a31 a32 -------- a31 is key R12 is m:n Relationship between E1 and E2 R12 a11 a22 ------------- (a11, a22) is key. R13 is 1:n Relationship between E1 and E3 R13 a11 a31 ----------- (a11, a31) is key. We need minimum no. of tables. Can we remove any of the above tables without loosing information and keeping the relations in 3NF? We can combine R13 and R12 into one. a11 a31 a22 ------------------ (a11, a31, a22) is key. The relation is still in 3NF as for every functional dependency X -> A, one of the following holds 1) X is a superkey or 2) A-X is prime attribute

Ans .

C

1. Explanation :

   the cyclomatic complexity of a structured program[a] is defined with reference to the control flow graph of the program, a directed graph containing the basic blocks of the program, with an edge between two basic blocks if control may pass from the first to the second. The complexity M is then defined as M = E - N + 2P, where E = the number of edges of the graph. N = the number of nodes of the graph. P = the number of connected components. Source: http://en.wikipedia.org/wiki/Cyclomatic_complexity For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is M = E - N + 2 For the given program, the control flow graph is: q100
   
   E = 13, N = 10. Therefore, E - N + 2 = 5.

Ans .

B

1. Explanation :

   In every cycle, the weight of an edge that is not part of MST must by greater than or equal to weights of other edges which are part of MST. Since all edge weights are distinct, the weight must be greater. So the minimum possible weight of ED is 7, minimum possible weight of CD is 16 and minimum possible weight of AB is 10. Therefore minimum possible sum of weights is 69.

Ans .

B

1. Explanation :

   Let f(x) be the given function. We assume that \[\frac{1}{x} = z\] Differentiating both sides, we get [Tex] \[\frac{-1}{x^2} dx = dz\] Now, accordingly, the lower limit of the integral is \[ z = \frac{1}{\frac{1}{\pi}} = \pi\] and the upper limit for the integral is \[ z = \frac{1}{\frac{2}{\pi}} = \frac{\pi}{2}\] So, the given function now becomes \[ f(x)= - \int_\pi^{\frac{\pi}{2}} cos(z) dz \] \[ f(x)= \int_\frac{\pi}{2}^{\pi} cos(z) dz \] \[f(x) = sin(z) ,\] and the upper limit is p and the lower limit is p/2 So, \[f(x) = sin(\pi) - sin(\frac{\pi}{2})\] \[f(x) = 0 - 1\] \[f(x) = -1\] So, the required answer is -1. [/Tex]

Ans .

D

1. Explanation :

   Note that the given graph is undirected, so an edge (u, v) also means (v, u) is also an edge. Since a shorter path can always be obtained by using edge (u, v) or (v, u), the difference between d(u) and d(v) can not be more than 1.

Ans .

A

1. Explanation :

   3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3 In both FIFO and LRU, we get following after considering 3, 8, 2, 3, 9, 1, 3 8 2 9 1 FIFO 6 replaces 3 8 2 9 1 6 3 replaces 8 2 9 1 6 3 8 replaces 2 9 1 6 3 8 2 replaces 9 1 6 3 8 2 No more page faults LRU 6 replaces 8 3 2 9 1 6 8 replaces 2 3 9 1 6 8 2 replaces 1 3 9 6 8 2 1 replaces 8 3 9 6 2 1

Ans .

A

1. Explanation :

   Seek time (given) = 4ms RPM = 10000 rotation in 1 min [60 sec] So, 1 rotation will be =60/10000 =6ms [rotation speed] Rotation latency= 1/2 * 6ms=3ms # To access a file, total time includes =seek time + rot. latency +transfer time TO calc. transfer time, find transfer rate Transfer rate = bytes on track /rotation speed so, transfer rate = 600*512/6ms =51200 B/ms transfer time= total bytes to be transferred/ transfer rate so, Transfer time =2000*512/51200 = 20ms Given as each sector requires seek tim + rot. latency = 4ms+3ms =7ms Total 2000 sector takes = 2000*7 ms =14000 ms To read entire file ,total time = 14000 + 20(transfer time) = 14020 ms

Ans .

A

1. Explanation :

   Simple Solution One way to solve this is to try for small values and rule out options. a0 = 0 a1 = 0 a2 = 1 ["11"] a3 = 3 ["011", "110", "111"] a4 = 8 ["0011", "0110", "0111", "1101", "1011", "1100", "1110", "1111"] If we check for a3, we can see that only A and C satisfy the value. Among (A) and (C), only (A) satisfies for a4. Another Solution (With Proof) A string of length n (n >= 2) can be formed by following 4 prefixes 1) 11 followed by a string of length n-2 2) 00 followed by a string of length n-2 3) 01 followed by a string of length n-2 4) 10 followed by a string of length n-2 Number 1 has already two consecutive 1's so number of binary strings beginning with number 3 is 2^n-2 as remaining n-2 bits can have any value. Number 2 has two 0's so remaining n-2 bits must have two consecutive 1's. Therefore number of binary strings that can be formed by number 2 is a_n-2. Number 3 and Number 4 together form all strings of length n-1 and two consecutive 1's.

Ans .

C

1. Explanation :

   Live variable analysis is useful in compilers to find variables in each program that may be needed in future. As per the definition given in question, a variable is live if it holds a value that may be needed in the future. In other words, it is used in future before any new assignment.

Ans .

B

1. Explanation :

   In q0 state for '1', a '1' is pushed and for a '0' a '0' is pushed. In q1 state, for a '0' a '1' is popped and for a '1' a '0' is popped. So, the given PDA is accepting all strings of of the form x0x'r or x1x'r or xx'r, where x'r is the reverse of the 1's complement of x. The given string 101100 has 6 letters and we are given 5 letter strings. So, x0 is done, with x = 10110. So, x'r = (01001)r = 10010. Hence option B is correct.

Ans .

B

1. Explanation :

   In DFA M: all strings must end with 'a'. In DFA N: all strings must end with 'b'. So the intersection is empty. For an empty language, only one state is required in DFA. The state is non-accepting and remains on itself for all characters of alphabet.
   

Ans .

B

1. Explanation :

   Transmission or Link speed = 64 kb per sec Propagation Delay = 20 milisec Since stop and wait is used, a packet is sent only when previous one is acknowledged. Let x be size of packet, transmission time = x / 64 milisec Since utilization is at least 50%, minimum possible total time for one packet is twice of transmission delay, which means x/64 * 2 = x/32 x/32 > x/64 + 2*20 x/64 > 40 x > 2560 bits = 320 bytes

Ans .

A

1. Explanation :

   Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, then v - e + f = 2. v -> Number of vertices e -> Number of edges f -> Number of faces As per the question v = 10 And number of edges on each face is three Therefore, 2e = 3f [Note that every edge is shared by 2 faces] Putting above values in v - e + f = 2 10 - e + 2e/3 = 2 e = 3*10 - 6 = 24

Ans .

B

1. Explanation :

   The correct answer is 8. This question was asked as a fill in the blank type question in the exam. Three address code is an intermediate code generated by compilers while optimizing the code. Each three address code instruction can have atmost three operands (constants and variables) combined with an assignment and a binary operator. The point to be noted in three address code is that the variables used on the left hand side (LHS) of the assignment cannot be repeated again in the LHS side. Static single assignment (SSA) is nothing but a refinement of the three address code. So, in this question, we have t1 = r / 3; t2 = t * 5; t3 = u * v; t4 = t3 / w; t5 = q + t1; t6 = t5 + s; t7 = t6 - t2; t8 = t7 + t4; Therefore, we require 8 temporary variables (t1 to t8) to create the three address code in static single assignment form.

Ans .

C

1. Explanation :

   Periods of T1, T2 and T3 are 3ms, 7ms and 20ms Since priority is inverse of period, T1 is the highest priority task, then T2 and finally T3 Every instance of T1 requires 1ms, that of T2 requires 2ms and that of T3 requires 4ms Initially all T1, T2 and T3 are ready to get processor, T1 is preferred Second instances of T1, T2, and T3 shall arrive at 3, 7, and 20 respectively. Third instance of T1, T2 and T3 shall arrive at 6, 14, and 49 respectively. Time-Interval Tasks 0-1 T1 1-2 T2 2-3 T2 3-4 T1 [Second Instance of T1 arrives] 4-5 T3 5-6 T3 6-7 T1 [Third Instance of T1 arrives] [Therefore T3 is preempted] 7-8 T2 [Second instance of T2 arrives] 8-9 T2 9-10 T1 [Fourth Instance of T1 arrives] 10-11 T3 11-12 T3 [First Instance of T3 completed]