Question 1

**Consider the following two statements about the function f(x)=|x|**

P. f(x) is continuous for all real values of x

Q. f(x) is differentiable for all real values of x

Which of the following is TRUE?

P. f(x) is continuous for all real values of x

Q. f(x) is differentiable for all real values of x

Which of the following is TRUE?

A : P is true and Q is false

B : P is false and Q is true

C : Both P and Q are true

D : Both P and Q are false

.

Correct answer is : A

Question 2

**Let S be a set of nelements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:**

A : n and n

B : n

^{2}and n

C : n

^{2}and 0

D : n and 1

.

Correct answer is : B

Question 3

**What is the maximum number of different Boolean functions involving n Boolean variables?**

A : n

^{2}

B : 2

^{n}

C : 2

^{2n}

D : 2

^{n2}

.

Correct answer is : C

Solution :

No of inputs sequences possible for a n variable Boolean function = 2n

Each input sequence can give either T or F as output ( 2 possible values )

So, Total no of Boolean functions are -

X2X2X2X2X2X.............X2X2X2X2X2X2

<-------------------- 2

^{n}Times -------------->

2

^{2n}

Question 4

**Let G be the non-planar graph with the minimum possible number of edges. Then G has**

A : 9 edges and 5 vertices

B : 9 edges and 6 vertices

C : 10 edges and 5 vertices

D : 10 edges and 6 vertices

.

Correct answer is : B

Solution :

For a simple, connected, planar graph with v vertices and e edges, the following simple conditions hold: If v ? 3 then e ? 3v ? 6;

Question 5

**Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?**

A : 1 2 3 4 5 6

B : 1 3 2 4 5 6

C : 1 3 2 4 6 5

D : 3 2 4 1 6 5

.

Correct answer is : D

Solution :

1 appears after 2 and 3 which is not possible in Topological Sorting.

Question 6

**Which of the following problems is undecidable?**

A : Membership problem for CFGs

B : Ambiguity problem for CFGs.

C : Finiteness problem for FSAs

D : Equivalence problem for FSAs

.

Correct answer is : B

Solution :

Ambiguity problem for CFGs are not decidable.

Question 7

**Which of the following is TRUE?**

A : Every subset of a regular set is regular

B : Every finite subset of a non-regular set is regular

C : The union of two non-regular sets is not regular.

D : Infinite union of finite sets is regular

.

Correct answer is : B

Question 8

**How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?**

A : 7

B : 8

C : 9

D : 10

.

Correct answer is : C

Question 9

**Consider the following Boolean function of four variables: f(w,x,y,z) = ∑ (1,3,4,6,9,11,12,14) The function is:**

A : independent of one variable

B : independent of two variable

C : independent of three variable

D : independent of all variable

.

Correct answer is : B

Question 10

**Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields arerespectively:**

A : 9,6,5

B : 7,7,6

C : 7,5,8

D : 9,5,6

.

Correct answer is : C

Question 11

**Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:**

A : 256 Mbyte, 19 bits

B : 256 Mbyte, 28 bits

C : 512 Mbyte, 20 bits

D : 64 Mbyte, 28 bits

.

Correct answer is : A

Solution :

Capacity of the disk = 16 surfaces X 128 tracks X 256 sectors X 512 bytes = 256 Mbytes.

To calculate number of bits required to access a sector, we need to know total number of sectors. Total number of sectors = 16 surfaces X 128 tracks X 256 sectors = 2^19

So the number of bits required to access a sector is 19.

Question 12

**The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:**

A : 2

^{h}-1

B : 2

^{h-1}-1

C : 2

^{h+1}-1

D : 2

^{h+1}

.

Correct answer is : C

Solution :

Maximum number of nodes will be there for a complete tree. Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + .... 2^h = 2^(h+1) - 1

Question 13

**The maximum number of binary trees that can be formed with three unlabeled nodes is:**

A : 1

B : 5

C : 4

D : 3

.

Correct answer is : B

Solution :

O / O O (i) O / O / O (ii) O / O O (iii) O O O

Question 14

**Which of the following sorting algorithms has the lowest worst-case complexity?**

A : Merge sort

B : Bubble sort

C : Quick sort

D : Selection sort

.

Correct answer is : A

Solution :

Worst case complexities for the above sorting algorithms are as follows:

Merge Sort - nLogn

Bubble Sort - n^2

Quick Sort - n^2

Selection Sort - n^2

Question 15

**Consider the following segment of C-code:**

int j, n;

j = 1;

while (j <= n)

j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

int j, n;

j = 1;

while (j <= n)

j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

A : ceil(log n) +2

B : n

C : ceil(log n)

D : floor(log n) +1

.

Correct answer is : A

Solution :

We can see it by taking few examples like n = 1, n = 3, etc.

For example, for n=5 we have the following (4) comparisons:

------------------------

1 <= 5 (T)

2 <= 5 (T)

4 <= 5 (T)

8 <= 5 (F)

------------------------

CEIL(log_2 n)+2 = CEIL(log_2 5) + 2 = CEIL(2.3) + 2 = 3 + 2 = 5

Question 16

**Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.**

A : P 3 Q 2 R 1

B : P 1 Q 2 R 3

C : P 2 Q 3 R 1

D : P 1 Q 3 R 2

.

Correct answer is : A

Solution :

Gang scheduling for parallel systems that schedules related threads or processes to run simultaneously on different processors.

Rate monotonic scheduling is used in real-time operating systems with a static-priority scheduling class. The static priorities are assigned on the basis of the cycle duration of the job: the shorter the cycle duration is, the higher is the jobs priority.

Fair Share Scheduling is a scheduling strategy in which the CPU usage is equally distributed among system

Question 17

**Consider the following statements about user level threads and kernel level threads. Which one of the following statement is FALSE?**

A : Context switch time is longer for kernel level threads than for user level threads.

B : User level threads do not need any hardware support.

C : Related kernel level threads can be scheduled on different processors in a multi-processor system.

D : Blocking one kernel level thread blocks all related threads.

.

Correct answer is : D

Solution :

Since kernel level threads are managed by kernel, blocking one thread doesnt cause all related threads to block. Its a problem with user level threads.

Kernel Threads:

Advantages: Because kernel has full knowledge of all threads, Scheduler may decide to give more time to a process having large number of threads than process having small number of threads.

Kernel-level threads are especially good for applications that frequently block.

Disadvantages: The kernel-level threads are slow and inefficient. For instance, threads operations are hundreds of times slower than that of user-level threads.

Since kernel must manage and schedule threads as well as processes. It require a full thread control block (TCB) for each thread to maintain information about threads. As a result there is significant overhead and increased in kernel complexity.

User Threads:

Advantages:

The most obvious advantage of this technique is that a user-level threads package can be implemented on an Operating System that does not support threads.

User-level threads does not require modification to operating systems. Simple Representation: Each thread is represented simply by a PC, registers, stack and a small control block, all stored in the user process address space.

Simple Management: This simply means that creating a thread, switching between threads and synchronization between threads can all be done without intervention of the kernel.

Fast and Efficient: Thread switching is not much more expensive than a procedure call.

Disadvantages:

User-Level threads are not a perfect solution as with everything else, they are a trade off. Since, User-Level threads are invisible to the OS they are not well integrated with the OS. As a result, Os can make poor decisions like scheduling a process with idle threads, blocking a process whose thread initiated an I/O even though the process has other threads that can run and unscheduling a process with a thread holding a lock. Solving this requires communication between between kernel and user-level thread manager.

There is a lack of coordination between threads and operating system kernel. Therefore, process as whole gets one time slice irrespect of whether process has one thread or 1000 threads within. It is up to each thread to relinquish control to other threads.

User-level threads requires non-blocking systems call i.e., a multithreaded kernel. Otherwise, entire process will blocked in the kernel, even if there are runable threads left in the processes. For example, if one thread causes a page fault, the process blocks.

Question 18

**Which one of the following is a top-down parser?**

A : Recursive descent parser.

B : Operator precedence parser.

C : An LR(k) parser.

D : An LALR(k) parser.

.

Correct answer is : A

Solution :

Recursive Descent parsing is LL(1) parsing which is top down parsing.

Question 19

**In Ethernet when Manchester encoding is used, the bit rate is:**

A : Half the baud rate.

B : Twice the baud rate.

C : Same as the baud rate.

D : None of the above

.

Correct answer is : A

Solution :

In Manchester encoding, the bitrate is half of the baud rate.

Question 20

**Which one of the following uses UDP as the transport protocol?**

A : HTTP

B : Telnet

C : DNS

D : SMTP

.

Correct answer is : C

Solution :

DNS uses UDP as the transport protocol

Question 21

**How many different non-isomorphic Abelian groups of order 4 are there**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Question 22

**Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement:**

Not every graph is connected?

Not every graph is connected?

A : A

B : B

C : C

D : D

.

Correct answer is : D

Solution :

We need to find out first order logic sentence that DOES NOT represent the statement:

Not every graph is connected

Option B says 'There exist some x such that x is a graph AND not connected'

So B is right option.

Option A and option C are same G(x)-->C(x) can also be written as ~G(x) or C(x), and they are the correct representation.

Option C says: There exists a graph and graph is not connected, which is equivalent to given sentence.

Option D: Every x which

Question 23

**Which of the following graphs has an Eulerian circuit?**

A : Any k-regular graph where kis an even number

B : A complete graph on 90 vertices

C : The complement of a cycle on 25 vertices

D : None of the above

.

Correct answer is : C

Solution :

A graph has Eulerian Circuit if following conditions are true.

a) All vertices with non-zero degree are connected. We dont care about vertices with zero degree because they dont belong to Eulerian Cycle or Path (we only consider all edges). .b) All vertices have even degree. Let us analyze all options. A) Any k-regular graph where k is an even number. is not Eulerian as a k regular graph may not be connected (property b is true, but a may not) B) A complete graph on 90 vertices is not Eulerian because all vertices have degree as 89 (property b is false) C) The complement of a cycle on 25 vertices is Eulerian. In a cycle of 25 vertices, all vertices have degree as 2. In complement graph, all vertices would have degree as 22 and graph would be connected.

Question 24

**Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3 , ..,20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?**

A : 1/2

B : 1/10

C : 9!/10!

D : None of the above

.

Correct answer is : D

Question 25

**Let A be a 4 x 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue of**

[A I]

[I A]

where I is the 4 x 4 identity matrix?

[A I]

[I A]

where I is the 4 x 4 identity matrix?

A : -5

B : -7

C : 2

D : 1

.

Correct answer is : C

Question 26

A : A

B : B

C : C

D : D

.

Correct answer is : C

Question 27

**Consider the set of (column) vectors defined by**

X = { x ∈ R

X = { x ∈ R

^{3}| x1+x2+x3=0 , where x^{T}= [x1,x2,x3]^{T}.of the following is TRUE?A : { [1,-1,0]

^{T}, [1,0,-1]

^{T}} is a basis for the subspace X.

B : { [1,-1,0]

^{T}, [1,0,-1]

^{T}} is a linearly independent set, but it does not span

C : X is not a subspace of R

^{3}

D : None of the above

.

Correct answer is : B

Question 28

**Consider the series X**

^{n+1}= X^{n}/ 2 + 98 X^{n}, X^{0}= 0.5 obtained from the Newton-Raphson method. The series converges toA : 1.5

B : √2

C : 1.6

D : 1.4

.

Correct answer is : A

Question 29

**A minimum state deterministic finite automaton accepting the language L={W | W ε {0,1} *, number of 0s and 1s in are divisible by 3 and 5, respectively} has**

A : 15 states

B : 11 states

C : 10 states

D : 9 states

.

Correct answer is : A

Question 30

**The language L= {0**

^{i}21^{i}| i≥0 } over the alphabet {0,1, 2} is:A : not recursive

B : is recursive and is a deterministic CFL

C : is a regular language

D : is not a deterministic CFL but a CFL

.

Correct answer is : B

Question 31

**Which of the following languages is regular?**

A : {ww

^{R}| w ∈ {0,1}

^{+}}

B : {ww

^{R}x | x,w ∈ {0,1}

^{+}}

C : {wxw

^{R}| x,w ∈ {0,1}

^{+}}

D : {xww

^{R}| x,w ∈ {0,1}

^{+}}

.

Correct answer is : C

Question 32

**Let f(w, x, y, z) = Σ(0, 4, 5, 7, 8, 9, 13, 15). Which of the following expressions are NOT equivalent to f?**

A : x'y'z' + w'xy' + wy'z + xz

B : w'y'z' + wx'y' + xz

C : w'y'z' + wx'y' + xyz + xy'z

D : x'y'z' + wx'y' + w'y

.

Correct answer is : D

Question 33

**Define the connective * for the Boolean variables X and Y as: X * Y = XY + X' Y'. Let Z = X * Y.**

Consider the following expressions P, Q and R.

π P: X = Y*Z

Q: Y = X*Z

R: X*Y*Z=1

Which of the following is TRUE?

Consider the following expressions P, Q and R.

π P: X = Y*Z

Q: Y = X*Z

R: X*Y*Z=1

Which of the following is TRUE?

A : Only P and Q are valid

B : Only Q and R are valid

C : Only P and R are valid

D : All P,Q,R are valid

.

Correct answer is : D

Question 34

**Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?**

A : 2

^{n}line to 1 line

B : 2

^{n+1}line to 1 line

C : 2

^{n-1}line to 1 line

D : 2

^{n-2}line to 1 line

.

Correct answer is : C

Question 35

**In a look-ahead carry generator, the carry generate function Gi and the carry propagate function Pi for inputs Ai and Bi are given by:**

Pi = Ai ⊕ Bi and Gi = Ai Bi

The expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by:

Si = Pi ⊕ Ci and Ci+1 = Gi + PiCi , where C0 is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all Pi and Gi are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs are respectively:

Pi = Ai ⊕ Bi and Gi = Ai Bi

The expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by:

Si = Pi ⊕ Ci and Ci+1 = Gi + PiCi , where C0 is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all Pi and Gi are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs are respectively:

A : 6,3

B : 10,4

C : 6,4

D : 10,5

.

Correct answer is : B

Question 36

**The control signal functions of a 4-bit binary counter are given below (where X is dont care) The counter is connected as follows:**

Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:

Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:

A : 0,3,4

B : 0,3,4,5

C : 0,1,2,3,4

D : 0,1,2,3,4,5

.

Correct answer is : C

Solution :

when A1 and A3 both are 1 it again goes to 0000. SO initially starts with 0000 then move till 4 then starts again

Question 37

**Consider a pipelined processor with the following four stages:**

IF: Instruction Fetch

ID: Instruction Decode and Operand Fetch

EX: Execute

WB: Write Back

The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage dependson the instruction. The ADD and SUB instructions need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?

IF: Instruction Fetch

ID: Instruction Decode and Operand Fetch

EX: Execute

WB: Write Back

The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage dependson the instruction. The ADD and SUB instructions need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?

A : 7

B : 8

C : 10

D : 14

.

Correct answer is : B

Question 38

**The following postfix expression with single digit operands is evaluated using a stack:**

8 2 3 ^ / 2 3 * + 5 1 * -

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

8 2 3 ^ / 2 3 * + 5 1 * -

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

A : 6,1

B : 5,7

C : 3,2

D : 1,5

.

Correct answer is : A

Question 39

**The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:**

A : d e b f g c a

B : e d b g f c a

C : e d b f g c a

D : d e f g b c a

.

Correct answer is : A

Solution :

Below is the given tree. a / / b c / / / / d e f g

Question 40

**Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that _ denotes an empty location in the table.**

A : 8, _, _, _, _, _, 10

B : 1, 8, 10, _, _, _, 3

C : 1, _, _, _, _, _,3

D : 1, 10, 8, _, _, _, 3

.

Correct answer is : B

Solution :

Let us put values 1, 3, 8, 10 in the hash of size 7.

Initially, hash table is empty

- - - - - - -

0 1 2 3 4 5 6

The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0

1 - - - - - -

0 1 2 3 4 5 6

The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6

1 - - - - - 3

0 1 2 3 4 5 6

The value o

Question 41

**In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by**

A : Dijkstras algorithm starting from S

B : Warshalls algorithm

C : Performing a DFS starting from S

D : Performing a BFS starting from S

.

Correct answer is : D

Solution :

* Time Comlexity of the Dijkstras algorithm is O(|V|^2 + E)

* Time Comlexity of the Warshalls algorithm is O(|V|^3)

* DFS cannot be used for finding shortest paths

* BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

Question 42

**Consider the following C function, what is the output?**

int f(int n)

{

static int r = 0;

if (n <= 0)

return 1;

if (n > 3)

{

r = n;

return f(n-2)+2;

}

return f(n-1)+r;

}

int main()

{

printf("%d", f(5));

}

int f(int n)

{

static int r = 0;

if (n <= 0)

return 1;

if (n > 3)

{

r = n;

return f(n-2)+2;

}

return f(n-1)+r;

}

int main()

{

printf("%d", f(5));

}

A : 5

B : 7

C : 9

D : 18

.

Correct answer is : D

Question 43

**A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?**

A : 3

B : 4

C : 5

D : 6

.

Correct answer is : C

Solution :

For an n-ary tree where each node has n children or no children, following relation holds

L = (n-1)*I + 1

Where L is the number of leaf nodes and I is the number of internal nodes.

Let us find out the value of n for the given data.

L = 41 , I = 10

41 = 10*(n-1) + 1

(n-1) = 4

n = 5

Question 44

**In the following C function, let n >= m.**

int gcd(n,m)

{

if (n%m ==0) return m;

n = n%m;

return gcd(m,n);

}

How many recursive calls are made by this function?

int gcd(n,m)

{

if (n%m ==0) return m;

n = n%m;

return gcd(m,n);

}

How many recursive calls are made by this function?

A : θ (n)

B : ω(n)

C : θ (loglogn)

D : θ (sqrt(n))

.

Correct answer is : A

Solution :

Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).

Question 45

**What is the time complexity of the following recursive function:**

int DoSomething (int n)

{

if (n <= 2)

return 1;

else

return (DoSomething (floor(sqrt(n))) + n);

}

int DoSomething (int n)

{

if (n <= 2)

return 1;

else

return (DoSomething (floor(sqrt(n))) + n);

}

A : θ (n)

B : θ (n log n)

C : θ (logn)

D : θ (loglog n)

.

Correct answer is : D

Solution :

Recursive relation for the DoSomething() is

T(n) = T(√n) + C1 if n > 2

We have ignored the floor() part as it doesnt matter here if its a floor or ceiling.

Let n = 2^m, T(n) = T(2^m)

Let T(2^m) = S(m)

From the above two, T(n) = S(m)

S(m) = S(m/2) + C1 /* This is simply binary search recursion*/

S(m) = O(logm)

= O(loglogn) /* Since n = 2^m */

Now, let us go back to the original recursive functio

Question 46

**Consider the following C program segment where CellNode represents a node in a binary tree:**

struct CellNode

{

struct CellNOde *leftChild;

int element;

struct CellNode *rightChild;

};

int GetValue(struct CellNode *ptr)

{

int value = 0;

if (ptr != NULL)

{

if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))

value = 1;

else

value = value + GetValue(ptr->leftChild) + GetVal

struct CellNode

{

struct CellNOde *leftChild;

int element;

struct CellNode *rightChild;

};

int GetValue(struct CellNode *ptr)

{

int value = 0;

if (ptr != NULL)

{

if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))

value = 1;

else

value = value + GetValue(ptr->leftChild) + GetVal

A : the number of nodes in the tree

B : the number of internal nodes in the tree

C : the number of leaf nodes in the tree

D : the height of the tree

.

Correct answer is : C

Question 47

**Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:**

A : θ (logn)

B : θ (loglogn)

C : θ (n)

D : θ (n logn)

.

Correct answer is : B

Solution :

The height of a Max Heap is ?(logn). If we perform binary search for finding the correct position then we need to do ?(LogLogn) comparisons.

Question 48

**Which of the following is TRUE about formulae in Conjunctive Normal Form?**

A : For any formula, there is a truth assignment for which at least half the clauses evaluate to true.

B : For any formula, there is a truth assignment for which all the clauses evaluate to true

C : There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate t

D : None of the above

.

Correct answer is : B

Question 49

**Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?**

A : There is a minimum spanning tree containing e.

B : If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have

C : Every minimum spanning tree has an edge of weight w

D : e is present in every minimum spanning tree

.

Correct answer is : D

Solution :

(A), (B) and (C) are correct.

(D) is incorrect as there may be many edges of wight w in the graph and e may not be picked up in some of the minimum spanning trees.

Question 50

**An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?**

A : At least 2n - c comparisons, for some constant c, are needed.

B : At most 1.5n - 2 comparisons are needed

C : At least nLog2n comparisons are needed

D : None of the above

.

Correct answer is : B

Question 51

**Consider the following C code segment:**

int IsPrime(n)

{

int i,n;

for(i=2;i<=sqrt(n);i++)

if(n%i == 0)

{printf(Not Prime\n); return 0;}

return 1;

}

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

int IsPrime(n)

{

int i,n;

for(i=2;i<=sqrt(n);i++)

if(n%i == 0)

{printf(Not Prime\n); return 0;}

return 1;

}

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

A : T(n) = O(sqrt(n)) and T(n) = Ω(sqrt(n))

B : T(n) = O(sqrt(n)) and T(n) = Ω(1)

C : T(n) = O(n) and T(n) = Ω(sqrt(n))

D : None of the above

.

Correct answer is : B

Solution :

Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.

The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) = Ω(1)

Question 52

**Consider the grammar with non-terminals N = {S,C,S1 },terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:**

S --> iCtSS1|a

S1 --> eS|?

C --> b

The grammar is NOT LL(1) because:

S --> iCtSS1|a

S1 --> eS|?

C --> b

The grammar is NOT LL(1) because:

A : it is left recursive

B : it is right recursive

C : it is amiguous

D : it is not context free

.

Correct answer is : C

Question 53

**Consider the following two statements:**

P: Every regular grammar is LL(1)

Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

P: Every regular grammar is LL(1)

Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

A : Both P and Q are true

B : P is true and Q is false

C : P is false and Q is true

D : Both P and Q are false

.

Correct answer is : C

Solution :

A regular grammar can also be ambiguous also

For example, consider the following grammar,

S -> aA/a

A -> aA/Ε

In above grammar, string 'a' has two leftmost derivations.

(1) S -> aA

S->a (using A->?)

(2) S -> a

And LL(1) parses only unambiguous grammar,

so statement P is False.

Statement Q is true is for every regular set, we can have a regular

grammar which is unambiguous so it can be parse by LR parser.

Question 54

**In a simplified computer the instructions are:**

The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:

t1=a+b

t2=c+d

t3=e-t2

t4=t1-t3

Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:

t1=a+b

t2=c+d

t3=e-t2

t4=t1-t3

Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

A : 2

B : 3

C : 5

D : 6

.

Correct answer is : B

Question 55

**An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:**

What is the total waiting time for process P2?

What is the total waiting time for process P2?

A : 5

B : 15

C : 40

D : 55

.

Correct answer is : C

Solution :

At time 0, P1 is the only process, P1 runs for 15 time units.

At time 15, P2 arrives, but P1 has the shortest remaining time. So P1 continues for 5 more time units.

At time 20, P2 is the only process. So it runs for 10 time units

At time 30, P3 is the shortest remaining time process. So it runs for 10 time units

At time 40, P2 runs as it is the only process. P2 runs for 5 time units.

At time 45, P3 arrives, but P2 has the shortest remaining time. So P2 continues for 10 m

Question 56

**A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:**

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.

Q:Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.

Q:Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

A : Both P and Q are true, and Q is the reason for P

B : Both P and Q are true, but Q is not the reason for P.

C : P is false, but Q is true

D : Both P and Q are false

.

Correct answer is : B

Solution :

P is true. Increasing the number of page frames allocated to process may increases the no. of page faults .

Q is also true, but Q is not the reason for-P as Beladys Anomaly occurs for some specific patterns of page references.

Question 57

**A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?**

A : P0

B : P1

C : P2

D : None of the above, since the system is in a deadlock

.

Correct answer is : C

Solution :

Once all resources (5, 4 and 3 instances of X, Y and Z respectively) are allocated, 0, 1 and 2 instances of X, Y and Z are left. Only needs of P1 can be satisfied. So P1 can finish its execution first. Once P1 is done, it releases 2, 1 and 3 units of X, Y and Z respectively. Among P0 and P2, needs of P0 can only be satisfied. So P0 finishes its execution. Finally, P2 finishes its execution.

Question 58

**Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?**

A : It does not ensure mutual exclusion

B : It does not ensure bounded waiting

C : It requires that processes enter the critical section in strict alternation.

D : It does not prevent deadlocks, but ensures mutual exclusion.

.

Correct answer is : D

Solution :

The above synchronization constructs dont prevent deadlock. When both wants1 and wants2 become true, both P1 and P2 stuck forever in their while loops waiting for each other to finish.

Question 59

**Information about a collection of students is given by the relation studinfo(studId, name, sex). The relation enroll(studId, courseId) gives which student has enrolled for (or taken) that course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?**

π

π

_{courseid}(( π_{studid}( σ_{sex="female"}(studInfo)) * π_{courseId}(enroll) - enroll )A : Courses in which all the female students are enrolled

B : Courses in which a proper subset of female students are enrolled.

C : Courses in which only male students are enrolled

D : None of the above

.

Correct answer is : B

Solution :

The expression given in question does following steps in sequence.

a) Select studids of all female students and selects all courseids of all courses.

b) Then the query does a Cartesian Product of the above select two columns from different tables.

c) Finally it subtracts enroll table from the result of above step (b). This will remove all the (studid, courseid) pairs which are present in enroll table.

Question 60

**Consider the relation employee(name, sex, supervisorName) with name as the key. supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?**

{ e.name | employee(e) ∧ (∀x) [ ¬employee(x) ∨ x.supervisorName ≠ e.name ∨ x.sex = "male" ] }

{ e.name | employee(e) ∧ (∀x) [ ¬employee(x) ∨ x.supervisorName ≠ e.name ∨ x.sex = "male" ] }

A : Names of employees with a male supervisor.

B : Names of employees with no immediate male subordinates.

C : Names of employees with no immediate female subordinates.

D : Names of employees with a female supervisor.

.

Correct answer is : C

Solution :

The query selects all those employees whose immediate subordinate is male. In other words, it selects names of employees with no immediate female subordinates

Question 61

**Consider the table employee(empId, name, department, salary) and the two queries Q1 ,Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?**

Q1 : Select e.empId

From employee e

Where not exists

(Select * From employee s where s.department = 5 and s.salary >=e.salary)

Q2 :

Select e.empId

From employee e

Where e.salary > Any

(Select distinct salary From employee s Where s.department = 5)

Q1 : Select e.empId

From employee e

Where not exists

(Select * From employee s where s.department = 5 and s.salary >=e.salary)

Q2 :

Select e.empId

From employee e

Where e.salary > Any

(Select distinct salary From employee s Where s.department = 5)

A : Q1 is the correct query

B : Q2 is the correct query

C : Both Q1 and Q2 produce the same answer

D : Neither Q1 nor Q2 is the correct query

.

Correct answer is : D

Solution :

Consider the following example table.

empid name department salary

1 a 4 90k

2 b 5 30k

3 c 5 50k

4 d 5 80k

Q1 will give empid 1

Q2 will give empid 1, 3, 4

But the correct answer is 4

Question 62

**Which one of the following statements if FALSE?**

A : Any relation with two attributes is in BCNF

B : A relation in which every key has only one attribute is in 2NF

C : A prime attribute can be transitively dependent on a key in a 3 NF relation.

D : A prime attribute can be transitively dependent on a key in a BCNF relation.

.

Correct answer is : D

Question 63

**The order of a leaf node in a tree B+ tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?**

A : 63

B : 64

C : 67

D : 68

.

Correct answer is : A

Solution :

Disk Block size = 1024 bytes

Data Record Pointer size, r = 7 bytes

Value size, V = 9 bytes

Disk Block ptr, P = 6 bytes

Let order of leaf be m. A leaf node in B+ tree contains at most m record pointers, at most m values, and one disk block pointer. r*m + V*m + p <= 1024 16m <= 1018 m =< 63

Question 64

**Consider the following schedules involving two transactions. Which one of the following statements is TRUE?**

S1 : r1(X);r1(Y);r2(X);r2(Y);w2(Y);w1(x)

S2 : r1(X);r2(X);r2(Y);w2(Y);r1(Y);w1(X)

S1 : r1(X);r1(Y);r2(X);r2(Y);w2(Y);w1(x)

S2 : r1(X);r2(X);r2(Y);w2(Y);r1(Y);w1(X)

A : Both S1 and S2 are conflict serializable.

B : S1 is conflict serializable and S2 is not conflict serializable.

C : S1 is not conflict serializable and S2 is conflict serializable

D : Both S1 and S2 are not conflict serializable.

.

Correct answer is : C

Solution :

S1 is not conflict serializable, but S2 is conflict serializable

Schedule S1 T1 T2 --------------------- r1(X) r1(Y) r2(X) r2(Y) w2(Y) w1(X) The schedule is neither conflict equivalent to T1T2, nor T2T1. Schedule S2 T1 T2 --------------------- r1(X) r2(X) r2(Y) w2(Y) r1(Y) w1(X)

The schedule is conflict equivalent to

Question 65

**There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?**

A : (1-p)

^{n-1}

B : np(1-p)

^{n-1}

C : p(1-p)

^{n-1}

D : 1-(1-p)

^{n-1}

.

Correct answer is : B

Solution :

The probability that a particular station transmits and no body else transmits = p*(1-p)^(n-1)

The probability that any station can transmit = n*(probability that a particular station transmits) = n*p*(1-p)^(n-1).

Question 66

**In a token ring network the transmission speed is 10^7 bps and the propagation speed is 200 metres/micro second. The 1-bit delay in this network is equivalent to:**

A : 500 metres of cable.

B : 200 metres of cable.

C : 20 metres of cable.

D : 50 metres of cable.

.

Correct answer is : C

Solution :

Transmission delay for 1 bit t = 1/(10^7) = 0.1 micro seconds. 200 meters can be traveled in 1 micro second. Therefore, in 0.1 micro seconds, 20 meters can be traveled.

Question 67

**The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?**

A : 62 subnets and 262142 hosts

B : 64 subnets and 262142 hosts

C : 62 subnets and 1022 hosts

D : 64 subnets and 1024 hosts

.

Correct answer is : C

Solution :

Maximum number of subnets = 2^6-2 =62.

Note that 2 is subtracted from 2^6. The RFC 950 specification reserves the subnet values consisting of all zeros (see above) and all ones (broadcast), reducing the number of available subnets by two.

Maximum number of hosts is 2^10-2 = 1022.

2 is subtracted for Number of hosts is also. The address with all bits as 1 is reserved as broadcast address and address with all host id bits as 0 is used as network address of subnet.

In genera

Question 68

**The message 11001001 is to be transmitted using the CRC polynomial x^3 + 1 to protect it from errors. The message that should be transmitted is:**

A : 11001001000

B : 11001001011

C : 11001010

D : 110010010011

.

Correct answer is : B

Solution :

The polynomial x^3+1 corresponds to divisor is 1001.

11001001 000 <--- input right padded by 3 bits 1001 <--- divisor 01011001 000 <---- XOR of the above 2 1001 <--- divisor 00010001 000 1001 00000011 000 10 01 00000001 010 1 001 00000000 011 <------- remainder (3 bits)

After dividing the given message 11001001 by 1001, we get the remainder as 011 which is the CRC. The transmitted data is, message + CRC which is 11001001 011.

Question 69

**The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocolis used, is:**

A : A

B : B

C : C

D : D

.

Correct answer is : C

Solution :

Distance between stations = L KM

Propogation delay per KM = t seconds

Total propagation delay = Lt seconds

Frame size = k bits

Channel capacity = R bits/second

Transmission Time = k/R

Let n be the window size.

UtiliZation = n/(1+2a) where a = Propagation time / transmission time

= n/[1 + 2LtR/k]

= nk/(2LtR+k)

For maximum utilization: nk = 2LtR + k

Therefore, n = (2LtR+k)/k

Question 70

**Match the following:**

A : P 2 Q 1 R 3 S 5

B : P 1 Q 4 R 2 S 3

C : P 1 Q 4 R 2 S 5

D : P 2 Q 4 R 1 S 3

.

Correct answer is : B

Solution :

SMTP is an application layer protocol used for e-mail transmission.

TCP is a core transport layer protocol.

BGP is a network layer protocol backing the core routing decisions on the Internet

PPP is a data link layer protocol commonly used in establishing a direct connection between two networking nodes.

Question 71

**Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.**

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal. Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is:

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal. Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is:

A : 10

B : 11

C : 20

D : 21

.

Correct answer is : D

Question 72

**Consider the data given in above question. Assume that the memory is word addressable. After the execution of this program, the content of memory location 2010 is:**

A : 100

B : 101

C : 102

D : 110

.

Correct answer is : A

Question 73

**Consider the data given in above questions. Assume that the memory is byte addressable and the word size is 32 bits. If an interrupt occurs during the execution of the instruction INC R3, what return address will be pushed on to the stack?**

A : 1005

B : 1020

C : 1024

D : 1040

.

Correct answer is : C

Question 74

**Consider the following Finite State Automaton. The language accepted by this automaton is given by the regular expression**

A : b* ab* ab* ab*

B : (a+b)*

C : b*a(a+b)*

D : b*ab*ab*

.

Correct answer is : C

Question 75

**Consider the following Finite State Automaton:**

The minimum state automaton equivalent to the above FSA has the following number of states

The minimum state automaton equivalent to the above FSA has the following number of states

A : 1

B : 2

C : 3

D : 4

.

Correct answer is : B

Question 76

**Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?**

A : 0, 10, 110, 1110, 11110, 11111

B : 11, 10, 011, 010, 001, 000

C : 11, 10, 01, 001, 0001, 0000

D : 110, 100, 010, 000, 001, 111

.

Correct answer is : A

Solution :

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 1 / / 1/2 a(1/2) / / 1/4 b(1/4) / / 1/8 c(1/8) / /

Question 77

**Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?**

A : 3

B : 2.1875

C : 2.25

D : 1.19375

.

Correct answer is : D

Solution :

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 1 / / 1/2 a(1/2) / / 1/4 b(1/4) / / 1/8 c(1/8) / /

Question 78

**Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b}as the terminal alphabet, S as the start symbol and the following set of production rules:**

Which of the following strings is generated by the grammar?

Which of the following strings is generated by the grammar?

A : aaaabb

B : aabbbb

C : aabbab

D : abbbba

.

Correct answer is : C

Solution :

The grammar accepts strings with equal number of a's and b's. Option C is the only option which has equal a's and b's.

Question 79

**For the correct answer strings to above question, how many derivation trees are there?**

A : 1

B : 2

C : 3

D : 4

.

Correct answer is : B

Question 80

**Consider a machine with a byte addressable main memory of 10**

^{16}bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 ื 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses. How many data cache misses will occur iA : 40

B : 50

C : 56

D : 59

.

Correct answer is : C

Question 81

**Consider a machine with a byte addressable main memory of 1016 bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 ื 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.Which of the following lines of the data cache will**

A : line 4 to line 11

B : line 4 to line 12

C : line 0 to line 7

D : line 0 to line 8

.

Correct answer is : A

Question 82

**A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 If optimal page replacement policy is used, how many page faults occur for the above reference string?**

A : 7

B : 8

C : 9

D : 10

.

Correct answer is : A

Question 83

**A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1. how many more page faults occur with LRU than with the optimal page replacement policy? (Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement.)**

A : 0

B : 1

C : 2

D : 3

.

Correct answer is : C

Question 84

**Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0, 0)**

A : 20C10

B : 2

^{20}

C : 2

^{10}

D : None of the above

.

Correct answer is : A

Question 85

**Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?**

A : 2

^{9}

B : 2

^{19}

C : 8C4 * 11C4

D : 20C10 - (8C4 * 11C5)

.

Correct answer is : D

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