Question 1

**Which one of the following in NOT necessarily a property of a Group?**

A : Commutativity

B : Associativity

C : Existence of inverse for every element

D : Existence of identity

.

Correct answer is : A

Solution :

A group is a set, G, together with an operation that combines any two elements a and b to form another element.

To qualify as a group, the set and operation, must satisfy four requirements known as the group axioms:

* Closure

* Associativity

* Identity element should exist

* Inverse element

Question 2

**What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n >= 2.**

A : 2

B : 3

C : n-1

D : n

.

Correct answer is : A

Solution :

A simple graph with no odd cycles is bipartite graph and a Bipartite graph can be colored using 2 colors

Question 3

**Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?**

A : No two vertices have the same degree

B : At least two vertices have the same degree

C : At least three vertices have the same degree

D : All vertices have the same degree

.

Correct answer is : B

Solution :

Since the graph is simple, there must not be any self loop and parallel edges. Since the graph is connected, the degree of any vertex cannot be 0. Therefore, degree of all vertices should be be from 1 to n-1. So the degree of at least two vertices must be same.

Question 4

**Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?**

A : R is symmetric but NOT antisymmetric

B : R is NOT symmetric but antisymmetric

C : R is both symmetric and antisymmetric

D : R is neither symmetric nor antisymmetric

.

Correct answer is : D

Solution :

R is not symmetric as (x, y) is present, but (y, x) is not present in R. R is also not antisymmetric as both (x, z) and (z, x) are present in R.

Question 5

**(1217)**

_{8}is equivalent toA : (1217)

_{16}

B : (028F)

_{16}

C : (2297)

_{16}

D : (0B17)

_{16}

.

Correct answer is : B

Solution :

(1217)

_{8}= (001 010 001 111)

_{8}= (0010 1000 1111) = (28F)

_{16}

Question 6

**What is the minimum number of gates required to implement the Boolean function (AB+C)if we have to use only 2-input NOR gates?**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Solution :

AB+C = (A+C)(B+C) = ((A+C)' + (B+C)')' So, '3' 2-input NOR gates are required.

Question 7

**A CPU generally handles an interrupt by executing an interrupt service routine**

A : As soon as an interrupt is raised

B : By checking the interrupt register at the end of fetch cycle

C : By checking the interrupt register after finishing the execution of the current instruction

D : By checking the interrupt register at fixed time intervals

.

Correct answer is : C

Solution :

Hardware detects interrupt immediately, but CPU acts only after its current instruction. This is followed to ensure integrity of instructions.

Question 8

**In which one of the following page replacement policies, Belady’s anomaly may occur?**

A : FIFO

B : Optimal

C : LRU

D : MRU

.

Correct answer is : A

Solution :

Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.

Question 9

**The essential content(s) in each entry of a page table is / are**

A : Virtual page number

B : Page frame number

C : Both virtual page number and page frame number

D : Access right information

.

Correct answer is : B

Solution :

A page table entry must contain Page frame number. Virtual page number is typically used as index in page table to get the corresponding page frame number.

Question 10

**What is the number of swaps required to sort n elements using selection sort, in the worst case?**

A : θ (n)

B : θ (n log n)

C : θ (n

^{2})

D : θ (n

^{2}log n)

.

Correct answer is : A

Solution :

Selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading.

Question 11

**S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of**

A : All palindromes

B : All odd length palindromes

C : Strings that begin and end with the same symbol

D : All even length palindromes

.

Correct answer is : B

Solution :

The possible palindrome generated by above grammar can be of odd length only as there is no rule for S -> ε. For example generated palindromes are aba, aaa, bab, ababa, aaaaa, ..

Question 12

**Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm?**

P: Always finds a negative weighted cycle, if one exist s.

Q: Finds whether any negative weighted cycle is reachable from the source.

P: Always finds a negative weighted cycle, if one exist s.

Q: Finds whether any negative weighted cycle is reachable from the source.

A : P only

B : Q only

C : Both P and Q

D : Neither P and Q

.

Correct answer is : B

Solution :

Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.

Question 13

**Let A be a problem that belongs to the class NP. Then which one of the following is TRUE?**

A : There is no polynomial time algorithm for A

B : If A can be solved deterministically in polynomial time,then P = NP

C : If A is NP-hard, then it is NP-complete

D : A may be undecidable

.

Correct answer is : C

Solution :

If a problem is both NP hard and NP, then it is NP Complete.

Question 14

**Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?**

A : The set of all strings containing the substring 00.

B : The set of all strings containing at most two 0’s

C : The set of all strings containing at least two 0’s.

D : The set of all strings that begin and end with either 0 or 1.

.

Correct answer is : C

Solution :

The regular expression has two 0?s surrounded by (0+1)* which means accepted strings must have at least 2 0?s.

Question 15

**Which one of the following is FALSE?**

A : There is unique minimal DFA for every regular language

B : Every NFA can be converted to an equivalent PDA

C : Complement of every context-free language is recursive

D : Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

.

Correct answer is : D

Solution :

Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

Question 16

**How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-bytes?**

A : 8

B : 32

C : 64

D : 128

.

Correct answer is : C

Solution :

We need 256 Kbytes, i.e., 256 x 1024 x 8 bits. We have RAM chips of capacity 32 Kbits = 32 x 1024 bits. (256 * 1024 * 8)/(32 * 1024) = 64

Question 17

**Match all items in Group 1 with correct options from those given in Group 2.**

GROUP 1 | GROUP 2 |

P.Regular expression | 1. Syntax analysis |

Q. Pushdown automata | 2. Code generation |

R. Dataflow analysis | 3. Lexical analysis |

S. Register allocation | 4. Code optimization |

A : P-4. Q-1, R-2, S-3

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

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

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

.

Correct answer is : B

Solution :

Regular expressions are used in syntax analysis. Pushdown automata is related to context free grammar which is related to syntax analysis. Dataflow analysis is done in code optimization. Register allocation is done in code generation.

Question 18

**Output of following program?**

#includeint fun(int n, int *f_p) { int t, f; if (n ≤ 1) { *f_p = 1; return 1; } t = fun(n- 1,f_p); f = t+ * f_p; *f_p = t; return f; } int main() { int x = 15; printf (" %d \n", fun(5, &x)); return 0; }

A : 6

B : 8

C : 14

D : 15

.

Correct answer is : B

Question 19

**The coupling between different modules of a software is categorized as follows:**

I. Content coupling

II. Common coupling

III. Control coupling

IV. Stamp coupling

V. Data coupling

Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:

I. Content coupling

II. Common coupling

III. Control coupling

IV. Stamp coupling

V. Data coupling

Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:

A : I-II-III-IV-V

B : V-IV-III-II-I

C : I-III-V -II-IV

D : IV-II-V-III-I

.

Correct answer is : A

Question 20

**Consider the HTML table definition given below:**

The number of rows in each column and the number of columns in each row are:

The number of rows in each column and the number of columns in each row are:

A : (2, 2, 3) and (2, 3, 2)

B : (2, 2, 3) and (2, 2, 3)

C : (2, 3, 2) and (2, 3, 2)

D : (2, 3, 2) and (2, 2, 3)

.

Correct answer is : C

Question 21

**An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?**

A : 0.453

B : 0.468

C : 0.485

D : 0.487

.

Correct answer is : B

Solution :

Let Xi be the probability that the face value is i.

We can say that X1 + X2 + X3 + X4 + X5 + X6 = 1

It is given that (X1 + X3 + X5) = 0.9*(X2 + X4 + X6)

It is also given that X2 = X4 = X6

Also given that (X4 + X6)/(X4 + X5 + X6) = 0.75

Solving the above equations, we can get X3 as 0.468

Question 22

**For the composition table of a cyclic group shown below**

Which one of the following choices is correct?

Which one of the following choices is correct?

A : a, b are generators

B : b, c are generators

C : c, d are generators

D : d, a are generators

.

Correct answer is : C

Solution :

Check for all:-

a1 = a ,

a2 = a * a = a

a3 = a2 * a = a * a = a

a is not the generator since we are not able to express other members of the group in powers of a

Check for c -

c1 = c

c2 = c * c = b

c3 = c2 * c = b * c = d

c4 = c2 * c2 = b * b = a

We are able to generate all the members of the group from c ,

Hence c is the generator Similarly check for d

Question 23

**Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: G(x): x is a gold ornament S(x): x is a silver ornament P(x): x is precious**

A : ∀ x( P(x) -> (G(x) ∧ S(x) ) )

B : ∀x ( (G(x) ∧ S(x)) -> P(x))

C : ∃x( (G(x) ∧ S(x)) -> P(x)

D : ∀x( (G(x) ∨ S(x)) -> P(x) )

.

Correct answer is : D

Solution :

D represents the correct form. For all x where x is gold ornament or silver ornament, x is precious.

Question 24

**The binary operation c is defined as follows**

Which one of the following is equivalent to P ◊ Q?

Which one of the following is equivalent to P ◊ Q?

A : ¬Q ◊ ¬P

B : P ◊ ¬Q

C : ¬P ◊ Q

D : ¬P ◊ ¬Q

.

Correct answer is : B

Solution :

We can try substituting different values of P and Q. For example P = T and Q = F.

Question 25

**Evalutae the following**

A : 0

B : 1

C : ln 2

D : 1/2 ln 2

.

Correct answer is : D

Solution :

(1-tanx)/(1+tanx) = (cosx - sinx)/(cosx + sinx)

Let cosx + sinx = t (-sinx + cosx)dx = dt (1/t)dt = ln t

=> ln(sinx + cosx) => ln(sin π/4 + cos π/4) => ln(1/√2 + 1/√2) => 1/2 ln 2

Question 26

**Consider the following well-formed formulae:**

I.¬∀ x(P(x))

II. ¬∃ x(P(x))

III. ¬∃ x(¬P(x))

IV. ¬∃x(¬P(x))

Which of the above are equivalent?

I.¬∀ x(P(x))

II. ¬∃ x(P(x))

III. ¬∃ x(¬P(x))

IV. ¬∃x(¬P(x))

Which of the above are equivalent?

A : I and III

B : I and IV

C : II and III

D : II and IV

.

Correct answer is : B

Solution :

According to negation property of universal qualifier and existential quantifier

¬ ∀ ∈ X P(x) ≡ ∃x ∈ X ¬ P(x)

Question 27

**Given the following state table of an FSM with two states A and B, one input and one output**

If the initial state is A=0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output = 1?

If the initial state is A=0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output = 1?

A : 3

B : 4

C : 5

D : 6

.

Correct answer is : A

Solution :

(0, 0) --1--> (0, 1) --0-->(1, 0) --1--> (0, 1) and output 1

Question 28

**Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:**

What is the number of cycles needed to execute the following loop? For (i=1 to 2) {I1; I2; I3; I4;}

What is the number of cycles needed to execute the following loop? For (i=1 to 2) {I1; I2; I3; I4;}

A : 16

B : 23

C : 28

D : 30

.

Correct answer is : B

Question 29

**Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order: 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155. Which one of the following memory block will NOT be in cache if LRU replacement policy is used?**

A : 3

B : 8

C : 129

D : 216

.

Correct answer is : D

Question 30

**Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.**

Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?

Process P1: t=0: requests 2 units of R2 t=1: requests 1 unit of R3 t=3: requests 2 units of R1 t=5: releases 1 unit of R2 and 1 unit of R1. t=7: releases 1 unit of R3 t=8: requests 2 units of R4 t=10: Finishes Process P2: t=0: requests 2 units of R3 t=2: requests 1 unit of R4 t=4: requests 1 unit of R1 t=6: releases 1 unit of R3 t=8: Finishes Process P3: t=0: requests 1 unit of R4 t=2: requests 2 units of R1 t=5: releases 2 units of R1 t=7: requests 1 unit of R2 t=8: requests 1 unit of R3 t=9: Finishes

Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?

A : All processes will finish without any deadlock

B : Only P1 and P2 will be in deadlock.

C : Only P1 and P3 will be in a deadlock.

D : All three processes will be in deadlock

.

Correct answer is : A

Solution :

We can apply the following Deadlock Detection algorithm and see that there is no process waiting indefinitely for a resource. See this for deadlock detection algorithm.

Question 31

**Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?**

A : 95ms

B : 119ms

C : 233ms

D : 276ms

.

Correct answer is : B

Solution :

4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Since shortest seek time first policy is used, head will first move to 34. This move will cause 16*1 ms. After 34, head will move to 20 which will cause 14*1 ms. And so on. So cylinders are accessed in following order 34, 20, 19, 15, 10, 7, 6, 4, 2, 73 and total time will be (16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71)*1 = 119 ms.

Question 32

**In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements.**

I. If a process makes a transition D, it would result in another process making transition A immediately. II. A process P2 in blocked state can make transition E while another process P1 is in running state. III. The OS uses preemptive scheduling. IV. The OS uses non-preemptive scheduling. Which of the above statements are TRUE?

A : I and II

B : I and III

C : II and III

D : II and IV

.

Correct answer is : C

Solution :

I is false. If a process makes a transition D, it would result in another process making transition B, not A. II is true. A process can move to ready state when I/O completes irrespective of other process being in running state or not. III is true because there is a transition from running to ready state. IV is false as the OS uses preemptive scheduling.

Question 33

**The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:**

In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements: I. The above solution to CS problem is deadlock-free II. The solution is starvation free. III. The processes enter CS in FIFO order. IV More than one process can enter CS at the same time. Which of the above statements is TRUE?

void enter_CS(X) { while test-and-set(X) ; } void leave_CS(X) { X = 0; }

In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements: I. The above solution to CS problem is deadlock-free II. The solution is starvation free. III. The processes enter CS in FIFO order. IV More than one process can enter CS at the same time. Which of the above statements is TRUE?

A : I only

B : I and II

C : II and III

D : IV only

.

Correct answer is : A

Solution :

The above solution is a simple test-and-set solution that makes sure that deadlock doesn’t occur, but it doesn’t use any queue to avoid starvation or to have FIFO order.

Question 34

**A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because**

A : It reduces the memory access time to read or write a memory location.

B : It helps to reduce the size of page table needed to implement the virtual address space of a process

C : It is required by the translation lookaside buffer

D : It helps to reduce the number of page faults in page replacement algorithms

.

Correct answer is : B

Solution :

The size of page table may become too big to fit in contiguous space. That is why page tables are typically divided in levels

Question 35

**The running time of an algorithm is represented by the following recurrence relation**

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?

(A) θ (n)

(B) θ (n log n)

(C) θ (n^2)

(D) θ (n^2 log n)

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?

(A) θ (n)

(B) θ (n log n)

(C) θ (n^2)

(D) θ (n^2 log n)

A : A

B : B

C : C

D : D

.

Correct answer is : A

Solution :

T(n) = cn + T(n/3)

= cn + cn/3 + T(n/9)

= cn + cn/3 + cn/9 + T(n/27)

Taking the sum of infinite GP series. The value of T(n) will be less than this sum.

T(n) <= cn(1/(1-1/3))

<= 3cn/2

or we can say

cn <= T(n) <= 3cn/2

Therefore T(n) = θ(n)

This can also be solved using Master Theorem for solving recurrences.

Question 36

**The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash**

A : A

B : B

C : C

D : D

.

Correct answer is : C

Solution :

Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:

linear probing in which the interval between probes is fixed–often at 1.

quadratic probing in which th

Question 37

**What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Solution :

AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees

Question 38

**Consider the following graph.Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?**

A : (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)

B : (b,e)(e,f)(a,c)(f,g)(b,c)(c,d)

C : (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)

D : (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

.

Correct answer is : D

Solution :

In the sequence (b, e) (e, f) (b, c) (a, c) (f, g) (c, d) given option D, the edge (a, c) of weight 4 comes after (b, c) of weight 3. In Kruskal's Minimum Spanning Tree Algorithm, we first sort all edges, then consider edges in sorted order, so a higher weight edge cannot come before a lower weight edge.

Question 39

**In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?**

A : θ (n)

B : θ (n log n)

C : θ (n

^{2})

D : θ (n

^{2}log n)

.

Correct answer is : B

Solution :

Answer(B) The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get θ(nLogn)

Question 40

**Let 1 2 L = L I L , where L1 ∩ L2 are languages as defined below:**

L1 = {a

L2={ a

Then L is

L1 = {a

^{m}b^{m}ca^{n}b^{m}| m,n >= 0 }L2={ a

^{i}b^{j}c^{k}| i,j,k >= 0 }Then L is

A : Not recursive

B : Regular

C : Context free but not regular

D : Recursively enumerable but not context free.

.

Correct answer is : C

Solution :

The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …}

L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }.

Intersection of these two languages is L1 cap L2 = {a

^{k}b

^{k}c | k >= 0} which is context free, but not regular.

Question 41

**The below DFA accepts the set of all strings over {0,1} that**

A : begin either with 0 or 1

B : end with 0

C : end with 00

D : contain the substring 00

.

Correct answer is : C

Question 42

**Which of the following statements are TRUE?**

I. There exist parsing algorithms for some programming languages whose complexities are less than O(n

II. A programming language which allows recursion can be implemented with static storage allocation.

III. No L-attributed definition can be evaluated in The framework of bottom-up parsing.

IV. Code improving transformations can be performed at both source language and intermediate code level.

I. There exist parsing algorithms for some programming languages whose complexities are less than O(n

^{3}).II. A programming language which allows recursion can be implemented with static storage allocation.

III. No L-attributed definition can be evaluated in The framework of bottom-up parsing.

IV. Code improving transformations can be performed at both source language and intermediate code level.

A : I and II

B : I and IV

C : III and IV

D : I,III and IV

.

Correct answer is : B

Solution :

II is false, in recursion, compiler cannot determine the space needed for recursive calls. III is false.

Question 43

**Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below:**

T1 = R1[X] W1[X] W1[Y]

T2 = R2[X] R2[Y] W2[Y]

S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y]

S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y]

S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y]

S4 = R1[X] R2[Y]R2[X]W1[X] W1[Y] W2[Y]

Which of the above schedules are conflict-serializable?

T1 = R1[X] W1[X] W1[Y]

T2 = R2[X] R2[Y] W2[Y]

S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y]

S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y]

S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y]

S4 = R1[X] R2[Y]R2[X]W1[X] W1[Y] W2[Y]

Which of the above schedules are conflict-serializable?

A : S1 and S2

B : S2 and S3

C : S3 only

D : S4 only

.

Correct answer is : B

Solution :

There can be two possible serial schedules T1 T2 and T2 T1. The serial schedule T1 T2 has the following sequence of operations R1[X] W1[X] W1[Y] R2[X] R2[Y] W2[Y] And the schedule T2 T1 has the following sequence of operations. R2[X] R2[Y] W2[Y] R1[X] W1[X] W1[Y] The Schedule S2 is conflict-equivalent to T2 T1 and S3 is conflict-equivalent to T1 T2

Question 44

**The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+-tree is initially empty. 10, 3, 6, 8, 4, 2, 1. The maximum number of times leaf nodes would get split up as a result of these insertions is**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Question 45

**Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database.Which of the following are equivalent ?**

A : I and II

B : I and III

C : II and IV

D : III and IV

.

Correct answer is : A

Solution :

I and II describe the division operator in Relational Algebra and Tuple Relational Calculus respectively.

Question 46

**In the RSA public key cryptosystem, the private and public keys are (e, n) and (d, n) respectively, where n = p*q and p and q are large primes. Besides, n is public and p and q are private. Let M be an integer such that 0 < M < n and f(n) = (p- 1)(q-1). Now consider the following equations.**

I. M’= Me mod n

M = (M’)

II. ed = 1 mod n

III. ed = 1 mod f(n)

IV. M’= M

Which of the above equations correctly represent RSA cryptosystem?

I. M’= Me mod n

M = (M’)

^{d}mod nII. ed = 1 mod n

III. ed = 1 mod f(n)

IV. M’= M

^{e}mod f(n) M = (M’)^{d}mod f(n)Which of the above equations correctly represent RSA cryptosystem?

A : I and II

B : I and III

C : II and IV

D : III and IV

.

Correct answer is : C

Solution :

I is true because below is true in RSA-Cryptosystem.

Encrypted-Text = (Plain-Text)

^{e}mod n

Plain-Text = (Encrypted-Text)

^{d}mod n

III is true because below is true

d

^{-1}= e mod φ(n)

OR ed = 1 mod φ(n)

Question 47

**While opening a TCP connection, the initial sequence number is to be derived using a time-of-day(ToD) clock that keeps running even when the host is down. The low order 32 bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter increments once per millisecond. The maximum packet lifetime is given to be 64s. Which one of the choices given below is closest to the minimum permissible rate at which sequence numbers used for packets of a connection can increase?**

A : 0.015/s

B : 0.064/s

C : 0.135/s

D : 0.327/s

.

Correct answer is : A

Solution :

The maximum packet lifetime is given to be 64 seconds in the question. Thus, a sequence number increments after every 64 seconds. So, minimum permissible rate = 1 / 64 = 0.015 per second

Question 48

**Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?**

A : G(x) contains more than two terms

B : G(x) does not divide 1+x^k, for any k not exceeding the frame length

C : 1+x is a factor of G(x)

D : G(x) has an odd number of terms

.

Correct answer is : C

Solution :

Odd number of bit errors can be detected if G(x) contains (x+1) as a factor. See this for proof.

Question 49

**Which of the following statements are TRUE?**

I. The context diagram should depict The system as a single bubble.

II. External entities should be identified clearly at all levels of DFDs.

III. Control information should not be represented in a DFD.

IV. A data store can be connected either to another data store or to an external entity.

I. The context diagram should depict The system as a single bubble.

II. External entities should be identified clearly at all levels of DFDs.

III. Control information should not be represented in a DFD.

IV. A data store can be connected either to another data store or to an external entity.

A : II and III

B : II and III

C : I and III

D : I,II and III

.

Correct answer is : C

Solution :

The context diagram depict the system as a single bubble. Control information should not represent in DFD.

Question 50

**Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE?**

I. The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph.

II. The cyclomatic complexity of a module is the number of decisions in the module plus one,where a decision is effectively any conditional statement in the module.

III.The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.

I. The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph.

II. The cyclomatic complexity of a module is the number of decisions in the module plus one,where a decision is effectively any conditional statement in the module.

III.The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.

A : I and II

B : II and III

C : I and III

D : I,II and III

.

Correct answer is : B

Solution :

TRUE: The cyclomatic complexity of a module is the number of decisions in the module plus one,where a decision is effectively any conditional statement in the module.

TRUE: The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.

Question 51

**A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c, h, s), where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0th sector is addressed as (0, 0, 0), the 1st sector as (0, 0, 1), and so on The address <400,16,29> corresponds to sector number:**

A : 505035

B : 505036

C : 505037

D : 505038

.

Correct answer is : C

Solution :

Total surfaces are 20 There are 1000 cylinders each cylinder contains 20 tracks in all the surfaces together. Each track contains 63 sectors So the address is 400x20x63 + 16x63 + 29 = 505037

Question 52

**A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c, h, s), where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0th sector is addressed as (0, 0, 0), the 1st sector as (0, 0, 1), and so on The address of the 1039th sector is**

A : (0, 15, 31)

B : (0, 16, 30)

C : (0, 16, 31)

D : (0, 17, 31)

.

Correct answer is : C

Solution :

16*31 + 31 = 1039

Question 53

**A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:**

l(i,j) = 0, if either i=0 or j=0

= expr1, if i,j > 0 and X[i-1] = Y[j-1]

= expr2, if i,j > 0 and X[i-1] != Y[j-1]

Which of the following options is correct?

l(i,j) = 0, if either i=0 or j=0

= expr1, if i,j > 0 and X[i-1] = Y[j-1]

= expr2, if i,j > 0 and X[i-1] != Y[j-1]

Which of the following options is correct?

A : expr1 = l(i-1, j) + 1

B : expr1 = l(i, j-1)

C : expr2 = max(l(i-1, j), l(i, j-1))

D : expr2 = max(l(i-1,j-1),l(i,j))

.

Correct answer is : C

Solution :

In Longest common subsequence problem, there are two cases for X[0..i] and Y[0..j]

1) The last characters of two strings match.

The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]

2) The last characters don't match.

The length of lcs is max of following two lcs values a) LCS of X[0..i-1] and Y[0..j]

b) LCS of X[0..i] and Y[0..j-1]

Question 54

**A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.**

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?

A : All elements L should be initialized to 0 for the values of l(i,j) to be properly computed

B : The values of l(i,j) may be computed in a row major order or column major order of L(M,N)

C : The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N)

D : L[p,q] needs to be computed before L[r,s] if either p < r or q < s

.

Correct answer is : B

Solution :

The value can be computed either in row major or column major order. We can swap the two loops without effecting the output.

Question 55

**Consider the following relational schema:**

Suppliers(

Parts(

Catalog(

Consider the following relational query on the above database:

SELECT S.sname

FROM Suppliers S

WHERE S.sid NOT IN (SELECT C.sid

FROM Catalog C

WHERE C.pid NOT IN (SELECT P.pid

FROM Parts P

WHERE P.color<> 'blue'))

Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?

Suppliers(

__sid:integer__, sname:string, city:string, street:string)Parts(

__pid:integer__, pname:string, color:string)Catalog(

__sid:integer__, pid:integer, cost:real)Consider the following relational query on the above database:

SELECT S.sname

FROM Suppliers S

WHERE S.sid NOT IN (SELECT C.sid

FROM Catalog C

WHERE C.pid NOT IN (SELECT P.pid

FROM Parts P

WHERE P.color<> 'blue'))

Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?

A : Find the names of all suppliers who have supplied a non-blue part.

B : Find the names of all suppliers who have not supplied a non-blue part.

C : Find the names of all suppliers who have supplied only blue parts

D : Find the names of all suppliers who have not supplied only blue parts.

.

Correct answer is : A

Solution :

The subquery “SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’” gives pids of parts which are not blue. The bigger subquery “SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’)” gives sids of all those suppliers who have supplied blue parts. The complete query gives the names of all suppliers who have supplied a non-blue part

Question 56

**Consider the following relational schema:**

Suppliers(

Parts(

Catalog(

Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?

Suppliers(

__sid:integer__, sname:string, city:string, street:string)Parts(

__pid:integer__, pname:string, color:string)Catalog(

__sid:integer__, pid:integer, cost:real)Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?

A : The schema is in BCNF

B : The schema is in BCNF

C : The schema is in 2NF but not in 3NF

D : The schema is not in 2NF

.

Correct answer is : A

Solution :

A relation is in BCNF if for every one of its dependencies X → Y, at least one of the following conditions hold:

X → Y is a trivial functional dependency (Y ⊆ X)

X is a superkey for schema R

Since (sname, city) forms a candidate key, there is no non-tirvial dependency X → Y where X is not a superkey

Question 57

**Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link). What is the minimum number of bits (i) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames**

A : i=2

B : i=3

C : i=4

D : i=5

.

Correct answer is : D

Solution :

Transmission delay for 1 frame = 1000/(10

^{6}) = 1 ms Propagation time = 25 ms The sender can atmost transfer 25 frames before the first frame reaches the destination. The number of bits needed for representing 25 different frames = 5

Question 58

**Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Suppose that the sliding window protocol is used with the sender window size of 2^i where is the number of bits identified in the previous question and acknowledgments are always piggybacked. After sending 2^i frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)**

A : 16ms

B : 18ms

C : 20ms

D : 22ms

.

Correct answer is : B

Solution :

Size of sliding window = 2^5 = 32 Transmission time for a frame = 1ms Total time taken for 32 frames = 32ms The sender cannot receive acknoledgement before round trip time which is 50ms After sending 32 frames, the minimum time the sender will have to wait before starting transmission of the next frame = 50 – 32 = 18

Question 59

**Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?**

A : 25,12,16,13,10,8,14

B : 25,14,13,16,10,8,12

C : 25,14,16,13,10,8,12

D : 25,14,12,13,10,8,16

.

Correct answer is : C

Solution :

A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data. In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.

Question 60

**Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?**

A : 14,13,12,10,8

B : 14,12,13,8,10

C : 14,13,8,12,10

D : 14,13,12,8,10

.

Correct answer is : D

Solution :

For Heap trees, deletion of a node includes following two operations. 1) Replace the root with last element on the last level. 2) Starting from root, heapify the complete tree from top to bottom.. Let us delete the two nodes one by one:

1) Deletion of 25: Replace 25 with 12 12 / / 14 16 / / / / 13 10 8 Since heap property is violated for root (16 is greater than 12), make 16 as root of the tree. 16 / / 14 12 / / / / 13 10 8 2) Deletion of 16: Replace 16 with 8 8 / / 14 12 / / 13 10 Heapify from root to bottom. 14 / / 8 12 / / 13 10 14 / / 13 12 / / 8 10

## Prepjunkie

Home . Contact . About . Disclaimer

Prepjunkie© 2015

Picture Palace Tilak Road Mussoorie, Uttarakhand

contactus@prepjunkie.com

About Prepjunkie PrepJunkie provides comprehensive guidance for entrance exams with well thought of solutions for selected questions, notes, books & much more.