Question 1

**What does the following C-statement declare?**

int ( * f) (int * ) ;

int ( * f) (int * ) ;

A : A function that takes an integer pointer as argument and returns an integer.

B : A function that takes an integer as argument and returns an integer pointer.

C : A pointer to a function that takes an integer pointer as argument and returns an integer.

D : A function that takes an integer pointer as argument and returns a function pointer

.

Correct answer is : C

Question 2

**An Abstract Data Type (ADT) is:**

A : Same as an abstract class

B : A data type that cannot be instantiated

C : A data type type for which only the operations defined on it can be used, but none else

D : All of the above

.

Correct answer is : C

Solution :

An abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

Question 3

**A common property of logic programming languages and functional languages is:**

A : both are procedural languages

B : both are based on λ -calculus

C : both are declarative

D : both use Horn-clauses

.

Correct answer is : C

Question 4

**Which one of the following are essential features of an object-oriented programming language?**

(i) Abstraction and encapsulatoin

(ii) Strictly-typedness

(iii) Type-safe property coupled with sub-type rule

(iv) Polymorphism in the presence of inheritance

(i) Abstraction and encapsulatoin

(ii) Strictly-typedness

(iii) Type-safe property coupled with sub-type rule

(iv) Polymorphism in the presence of inheritance

A : (i) and (ii) only

B : (i) and (iv) only

C : (i),(ii) and (iv) only

D : (i),(iii) and (iv) only

.

Correct answer is : B

Solution :

Abstraction, Encapsulation, Polymorphism and Inheritance are the essential features of a OOP Language

Question 5

**A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?**

A : An array of 50 numbers

B : An array of 100 numbers

C : An array of 500 numbers

D : A dynamically allocated array of 550 numbers

.

Correct answer is : A

Solution :

An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value

Question 6

**An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose**

(i) diagonal elements are 0's, and

(ii) non-diagonal elements are l's.

Which one of the following is TRUE?

(i) diagonal elements are 0's, and

(ii) non-diagonal elements are l's.

Which one of the following is TRUE?

A : Graph G has no minimum spanning tree (MST)

B : Graph G has a unique MST of cost n-1

C : Graph G has multiple distinct MSTs, each of cost n-1

D : Graph G has multiple spanning trees of different costs

.

Correct answer is : C

Solution :

If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1.

Question 7

**The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be**

A : O(n)

B : O(n logn)

C : O(n

^{3/2})

D : O(n

^{3})

.

Correct answer is : D

Solution :

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node othe

Question 8

**Let A, B and C be non-empty sets and let X = (A - B) - C and Y = (A - C) - (B - C). Which one of the following is TRUE?**

A : X = Y

B : X ⊂ Y

C : Y ⊃ X

D : None of the above

.

Correct answer is : A

Solution :

We can solve it by making Venn diagram

Question 9

**The following is the Hasse diagram of the poset [{a, b, c, d, e}, <].The poset is**

A : not a lattice

B : a lattice but not a distributive lattice

C : a distributive lattice but not a Boolean algebra

D : a Boolean algebra

.

Correct answer is : C

Question 10

**Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is**

A : 6

B : 8

C : 9

D : 13

.

Correct answer is : B

Solution :

We can apply Euler's Formula of planar graphs. The formula is v - e + f = 2.

Question 11

**Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is**

A : 12

B : 8

C : less than 8

D : more than 12

.

Correct answer is : A

Solution :

The number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set.

Question 12

**Let f(x) be the continuous probability density function of a random variable X. The probability that a < X <= b, is**

A : f(b-a)

B : f(b) - f(a)

C : D :

.

Correct answer is : C

Question 13

**The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively**

A : 3 and 13

B : 2 and 11

C : 4 and 13

D : 8 and 14

.

Correct answer is : C

Question 14

**The grammar A → AA | (A) | e is not suitable for predictive-parsing because the grammar is**

A : ambiguous

B : left-recursive

C : right-recursive

D : an operator-grammar

.

Correct answer is : B

Question 15

**Consider the following circuit.**

Which of the following is true?

Which of the following is true?

A : f is independent of X

B : f is independent of Y

C : f is independent of Z

D : None of X, Y, Z is redundant

.

Correct answer is : A

Question 16

**The range of integers that can be represented by an n bit 2's complement number system is**

A : -2

^{n-1}to (2

^{n-1 -1)}

B : -(2

^{n-1}-1) to (2

^{n-1 -1)}

C : -2

^{n-1}to 2

^{n-1}

D : -(2

^{n-1}+1 ) to (2

^{n-1 +1)}

.

Correct answer is : A

Solution :

For example, signed char is 8 bits, we can store from -128 to 127 using sign char

Question 17

**The hexadecimal representation of 657**

_{8}isA : 1AF

B : D78

C : D71

D : 32F

.

Correct answer is : A

Solution :

We can first convert to Binary, we get 110 101 111. Then convert binary to base 16, we get 1AF (0001 1010 1111).

Question 18

**The switching expression corresponding to f(A, B, C, D) = ∑ (1, 4, 5, 9, 11, 12) is**

A : BC'D' + A'C'D + AB'D

B : ABC' + ACD + B'C'D

C : ACD' + A'BC' + AC'D'

D : A'BD + ACD' + BCD'

.

Correct answer is : A

Question 19

**Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?**

A : Neither vectored interrupt nor multiple interrupting devices are possible.

B : Vectored interrupts are not possible but multiple interrupting devices are possible.

C : Vectored interrupts and multiple interrupting devices are both possible

D : Vectored interrupt is possible but multiple interrupting devices are not possible.

.

Correct answer is : B

Question 20

**Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?**

A : I/O protection is ensured by operating system routine (s)

B : I/O protection is ensured by a hardware trap

C : I/O protection is ensured during system configuration

D : I/O protection is not possible

.

Correct answer is : A

Solution :

User applications are not allowed to perform I/O in user mode - All I/O requests are handled through system calls that must be performed in kernel mode.

Question 21

**What is the swap space in the disk used for?**

A : Saving temporary html pages

B : Saving process data

C : Storing the super-block

D : Storing device drivers

.

Correct answer is : B

Solution :

Swap space is typically used to store process data.

Question 22

**Increasing the RAM of a computer typically improves performance because:**

A : Virtual memory increases

B : Larger RAMs are faster

C : Fewer page faults occur

D : Fewer segmentation faults occur

.

Correct answer is : C

Solution :

When RAM size is bigger, the page table would have more entries of pages, hence less number of page faults.

Question 23

**Packets of the same session may be routed through different paths in**

A : TCP, but not UDP

B : TCP and UDP

C : UDP, but not TCP

D : Neither TCP, nor UDP

.

Correct answer is : B

Solution :

Packet is the Network layer Protocol Data Unit (PDU). TCP and UDP are Transport layer protocols. Packets of same session may be routed through different routes. Most networks don’t use static routing, but use some form of adaptive routing where the paths used to route two packets for same session may be different due to congestion on some link, or some other reason.

Question 24

**The address resolution protocol (ARP) is used for**

A : Finding the IP address from the DNS

B : Finding the IP address of the default gateway

C : Finding the IP address that corresponds to a MAC address

D : Finding the MAC address that corresponds to an IP address

.

Correct answer is : D

Solution :

Address Resolution Protocol (ARP) is a request and reply protocol used to find MAC address from IP address.

Question 25

**The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:**

A : 2

^{n}

B : 2

^{n-1}

C : 2

^{n}-1

D : 2

^{n-2}

.

Correct answer is : B

Solution :

In Selective Reject (or Selective Repeat), maximum size of window must be half of the maximum sequence number.

Question 26

**In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges. Why is the spanning tree algorithm used for bridge-routing?**

A : For shortest path routing between LANs

B : For avoiding loops in the routing paths

C : For fault tolerance

D : For minimizing collisions

.

Correct answer is : B

Solution :

The main idea for using Spanning Trees is to avoid loops.

Question 27

**An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be**

A : 255.255.0.0

B : 255.255.64.0

C : 255.255.128.0

D : 255.255.252.0

.

Correct answer is : D

Solution :

The size of network ID is 16 bit in class B networks. So bits after 16th bit must be used to create 64 departments. Total 6 bits are needed to identify 64 different departments. Therefore, subnet mask will be 255.255.252.0.

Question 28

**Which one of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?**

A : Database relations have a large number of records

B : Database relations are sorted on the primary key

C : B+ -trees require less memory than binary search trees

D : Data transfer from disks is in blocks

.

Correct answer is : D

Question 29

**Which one of the following statements about normal forms is FALSE?**

A : BCNF is stricter than 3NF

B : Lossless, dependency-preserving decomposition into 3NF is always possible

C : Lossless, dependency-preserving decomposition into BCNF is always possible

D : Any relation with two attributes is in BCNF

.

Correct answer is : C

Solution :

It is not always possible to decompose a table in BCNF and preserve dependencies. For example, a set of functional dependencies {AB –> C, C –> B} cannot be decomposed in BCNF. See this for more details.

Question 30

**Let r be a relation instance with schema R = (A, B, C, D). We define r1 = π**

_{A, B, C}(r) and r2 = π_{A.D}(r). Let s = r1 * r2 where * denotes natural join. Given that the decomposition of r into r1 and r2 is lossy, which one of the following is TRUE?A : s ⊂ r

B : r ∪ s = r

C : r ⊂ s

D : r * s = s

.

Correct answer is : C

Solution :

Consider the following example with lossy decomposition of r into r1 and r2. We can see that r is a subset of s.

Table r A B C D --------------------------- 1 10 100 1000 1 20 200 1000 1 20 200 1001 Table r1 A B C ------------------ 1 10 100 1 20 200 Table r2 A D ----------- 1 1000 1 1001 Table s (natural join of r1 and r2) A B C D -----

Question 31

**Consider the following C-program:**

void foo(int n, int sum)

{

int k = 0, j = 0;

if (n == 0) return;

k = n % 10;

j = n / 10;

sum = sum + k;

foo (j, sum);

printf ("%d,", k);

}

int main ()

{

int a = 2048, sum = 0;

foo (a, sum);

printf ("%d\n", sum);

getchar();

}

What does the above program print?

void foo(int n, int sum)

{

int k = 0, j = 0;

if (n == 0) return;

k = n % 10;

j = n / 10;

sum = sum + k;

foo (j, sum);

printf ("%d,", k);

}

int main ()

{

int a = 2048, sum = 0;

foo (a, sum);

printf ("%d\n", sum);

getchar();

}

What does the above program print?

A : 8, 4, 0, 2, 14

B : 8, 4, 0, 2, 0

C : 2, 0, 4, 8, 14

D : 2, 0, 4, 8, 0

.

Correct answer is : D

Solution :

sum has no use in foo(), it is there just to confuse. Function foo() just prints all digits of a number. In main, there is one more printf statement after foo(), so one more 0 is printed after all digits of n.

Question 32

**Consider the following C-program:**

double foo (double); /* Line 1 */

int main()

{

double da, db;

// input da

db = foo(da);

}

double foo(double a)

{

return a;

}

The above code compiled without any error or warning. If Line 1 is deleted, the above code will show:

double foo (double); /* Line 1 */

int main()

{

double da, db;

// input da

db = foo(da);

}

double foo(double a)

{

return a;

}

The above code compiled without any error or warning. If Line 1 is deleted, the above code will show:

A : no compile warning or error

B : some compiler-warnings not leading to unintended results

C : some compiler-warnings due to type-mismatch eventually leading to unintended results

D : compiler errors

.

Correct answer is : D

Question 33

**Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?**

A : 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

B : 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

C : 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

D : 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

.

Correct answer is : A

Solution :

Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.

Question 34

**A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:**

A : 10, 8, 7, 5, 3, 2, 1

B : 10, 8, 7, 2, 3, 1, 5

C : 10, 8, 7, 1, 2, 3, 5

D : 10, 8, 7, 3, 2, 1, 5

.

Correct answer is : D

Solution :

Original Max-Heap is:

10 / \ 8 5 / \ 3 2After Insertion of 1.

10 / \ 8 5 / \ / 3 2 1After Insertion of 7.

10 / \ 8 7 / \ / \ 3 2 1 5

Question 35

**How many distinct binary search trees can be created out of 4 distinct keys?**

A : 5

B : 14

C : 24

D : 42

.

Correct answer is : B

Question 36

**In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is A**

A : nk

B : (n - 1)k + 1

C : n(k - 1) + 1

D : n(k - 1)

.

Correct answer is : C

Solution :

We can easily verify the above relation by taking some example binary trees.

Question 37

**Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?**

A : T(n) = O(n

^{2})

B : T(n) = θ(n log n)

C : T(n) = Ω(n

^{2})

D : T(n) = O(n log n)

.

Correct answer is : C

Solution :

The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).

T(n) = θ(nLogn)

By definition of Big O notation, we can say.

θ(nLogn) = O(nLogn) = O(n^2)

θ(nLogn) ca be equal to Ω (n) or Ω (nLogn), but not Ω (n^2)

Question 38

**Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:**

A : O(| V |

^{2})

B : O (| E | + | V | log | V |)

C : O (| V | log | V |)

D : O ((| E | + | V |) log | V |)

.

Correct answer is : D

Question 39

**Suppose there are ⌈ log n ⌉ sorted lists of ⌊ n/log n ⌋ elements each. The time complexity of producing a sorted list of all these elements is : (Hint : Use a heap data structure)**

A : O(n log log n)

B : θ (n log n)

C : Ω (n log n)

D : Ω (n3/2)

.

Correct answer is : A

Solution :

We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.

x = n/Logn y = Logn We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

Question 40

**Let P, Q and R be three atomic prepositional assertions. Let X denote (P v Q) → R and Y denote (P → R) v (Q → R). Which one of the following is a tautology?**

A : X = Y

B : X → Y

C : Y → X

D : ¬ Y → X

.

Correct answer is : B

Question 41

**What is the first order predicate calculus statement equivalent to the following?**

Every teacher is liked by some student

Every teacher is liked by some student

A : ∀(x) [teacher (x) → ∃ (y) [student (y) → likes (y, x)]]

B : ∀ (x) [teacher (x) → ∃ (y) [student (y) ^ likes (y, x)]]

C : ∃ (y) ∀ (x) [teacher (x) → [student (y) ^ likes (y, x)]]

D : ∀ (x) [teacher (x) ^ ∃ (y) [student (y) → likes (y, x)]]

.

Correct answer is : B

Question 42

**Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?**

A : R ∪ S, R ∩ S are both equivalence relations

B : R ∪ S is an equivalence relation

C : R ∩ S is an equivalence relation

D : Neither R ∪ S nor R ∩ S is an equivalence relation

.

Correct answer is : C

Question 43

**Let f: B → C and g: A → B be two functions and let h = f o g. Given that h is an onto function. Which one of the following is TRUE?**

A : f and g should both be onto functions.

B : f should be onto but g need not be onto

C : g should be onto but f need not be onto

D : both f and g need not be onto

.

Correct answer is : B

Question 44

**What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that "a = c mod 3" and "b = d mod 5"**

A : 4

B : 6

C : 16

D : 24

.

Correct answer is : C

Question 45

**Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?**

A : P3 is decidable if P1 is reducible to P3

B : P3 is undecidable if P3 is reducible to P2

C : P3 is undecidable if P2 is reducible to P3

D : P3 is decidable if P3 is reducible to P2's complement

.

Correct answer is : C

Question 46

**Consider the set H of all 3 × 3 matrices of the type given below where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication operation, the set H is**

A : a group

B : a monoid but not a group

C : a semigroup but not a monoid

D : neither a group nor a semigroup

.

Correct answer is : C

Question 47

**Which one of the following graphs is NOT planar?**

A : G1

B : G2

C : G3

D : G4

.

Correct answer is : A

Solution :

A graph is planar if it can be redrawn in a plane without any crossing edges. G1 is a typical example of nonplanar graphs.

Question 48

**Consider the following system of equations in three real variables xl, x2 and x3**

2x1 - x2 + 3x3 = 1

3x1- 2x2 + 5x3 = 2

-x1 + 4x2 + x3 = 3

This system of equations has

2x1 - x2 + 3x3 = 1

3x1- 2x2 + 5x3 = 2

-x1 + 4x2 + x3 = 3

This system of equations has

A : no solution

B : a unique solution

C : more than one but a finite number of solutions

D : an infinite number of solutions

.

Correct answer is : B

Solution :

The determinant value of following matrix is non-zero, therefore we have a unique solution.

2 -1 3

3 -2 5

-1 4 1

Question 49

**What are the eigenvalues of the following 2 × 2 matrix?**

A : -1 and 1

B : 1 and 6

C : 2 and 5

D : 4 and -1

.

Correct answer is : B

Solution :

The eigenvalues of A are precisely the real numbers ? that satisfy the equation det(A - λ I) = 0. Let us find determinant value of A - &lambda I;

2-λ -1 -4 5-λ

Solve the equations and get the correct answer

Question 50

**Let G(x) = the function given below , where |x| <1 . What is g(i)?**

A : i

B : i+1

C : 2i

D : 2

^{i}

.

Correct answer is : B

Solution :

B is the correct option. Let us put values

S = 1 + 2x + 3x2 + 4x3 + ..........

Sx = x + 2x2 + 3x3 + ..........

S - Sx = 1 + x + x2 + x3 + ....

S - Sx = 1/(1 - x) [sum of infinite GP series with ratio < 1 is a/(1-r)]

S = 1/(1 - x)

^{2}

Question 51

**Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows:**

(i) Select a box

(ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

(i) Select a box

(ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

A : 4/19

B : 5/19

C : 2/9

D : 19/30

.

Correct answer is : A

Solution :

The probability of selecting a red ball =

(1/3) * (2/5) + (2/3) * (3/4) = 2/15 + 1/2

= 19/30 [Let it be P1]

Probability of selecting a red ball from box P =

(1/3) * (2/5) = 2/15 [Let it be P2]

Given that a ball selected in the above process is a red ball, the probability that it came from the box P is

= P1/P2 = (2/15) / (19/30) = 4/19

Question 52

**A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is**

A : 1/2

^{n}

B : 1-(1/n)

C : 1/n!

D : 1-(1/2

^{n})

.

Correct answer is : D

Solution :

The probability that the two strings are identical is

(1/2) * (1/2) * ..... * (1/2) (n times) which is 1/2

^{n}

The probability for not identical is 1 - (1/2

^{n})

Question 53

**Consider the machine M: The language recognized by M is:**

A : {w ∈ {a, b}* / every a in w is followed by exactly two b's}

B : {w ∈ {a, b}* every a in w is followed by at least two b’}

C : {w ∈ {a, b}* w contains the substring 'abb'}

D : {w ∈ {a, b}* w does not contain 'aa' as a substring}

.

Correct answer is : B

Solution :

We can try some sample strings like aba, abbbb, abbbabbb

Question 54

**Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?**

A : Df ⊂ Nf and Dp ⊂ Np

B : Df ⊂ Nf and Dp = Np

C : Df = Nf and Dp = Np

D : Df = Nf and Dp ⊂ Np

.

Correct answer is : D

Solution :

Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design. Deterministic context-free languages (DCFL) are a proper subset of context-free languages. Non-deterministic finite automata and Deterministic finite automata, both accept same set of languages as NFAs can be translated to equivalent DFAs using the subset construction algorithm.

Question 55

**Consider the languages:**

L1 = {a

L2 = {a

Which one of the following statements is FALSE?

L1 = {a

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

^{n}b^{m}c^{m}| n, m > 0}Which one of the following statements is FALSE?

A : L1 ∩ L2 is a context-free language

B : L1 U L2 is a context-free language

C : L1 and L2 are context-free language

D : L1 ∩ L2 is a context sensitive language

.

Correct answer is : A

Solution :

L1 and L2 are context free languages. See this for closure properties.

Question 56

**Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?**

L1' --> Complement of L1

L2' --> Complement of L2

L1' --> Complement of L1

L2' --> Complement of L2

A : L1' is recursive and L2' is recursively enumerable

B : L1' is recursive and L2' is not recursively enumerable

C : L1' and L2' are recursively enumerable

D : L1' is recursively enumerable and L2' is recursive

.

Correct answer is : B

Solution :

Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. Recursive Languages are closed under complementation, but recursively enumerable are not closed under complementation. If a languages L is recursively enumerable, then the complement of it is recursively enumerable if and only if L is also recursive. Since L2 is recursively enumerable, but

Question 57

**Consider the languages:**

L1 = {ww

L2 = {w#w

L3 = {ww | w ∈ (0, 1}*)

Which one of the following is TRUE?

L1 = {ww

^{R}|w ∈ {0, 1}*}L2 = {w#w

^{R}| w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)

Which one of the following is TRUE?

A : L1 is a deterministic CFL

B : L2 is a deterministic CFL

C : L3 is a CFL, but not a deterministic CFL

D : L3 is a deterministic CFL

.

Correct answer is : B

Question 58

**Consider the following two problems on undirected graphs**

α : Given G(V, E), does G have an independent set of size | V | - 4?

β : Given G(V, E), does G have an independent set of size 5?

Which one of the following is TRUE?

α : Given G(V, E), does G have an independent set of size | V | - 4?

β : Given G(V, E), does G have an independent set of size 5?

Which one of the following is TRUE?

A : α is in P and β is NP-complete

B : α is NP-complete and β is in P

C : Both α and β are NP-complete

D : Both α and β are in P

.

Correct answer is : C

Solution :

Graph independent set decision problem is NP Complete.

Question 59

**Consider the grammar**

E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-sentential form of the reduction are

E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-sentential form of the reduction are

A : n, E + n and E + n × n

B : n, E + n and E + E × n

C : n, n + n and n + n × n

D : n, E + n and E × n

.

Correct answer is : D

Solution :

E -> E + n {Applying E -> E + n }

-> E + E * n {Applying E -> E * n }

-> E + n * n {Applying E -> n }

-> n + n * n {Applying E -> n }

Question 60

**Consider the grammar**

S → (S) | a

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good

S → (S) | a

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good

A : n1 < n2 < n3

B : n1 = n3 < n2

C : n1 = n3 = n2

D : n1 >= n3 >= n2

.

Correct answer is : B

Question 61

**Consider line number 3 of the following C- program.**

int main ( ) { /* Line 1 */

int I, N; /* Line 2 */

fro (I = 0, I < N, I++); /* Line 3 */

}

Identify the compiler's response about this line while creating the object-module

int main ( ) { /* Line 1 */

int I, N; /* Line 2 */

fro (I = 0, I < N, I++); /* Line 3 */

}

Identify the compiler's response about this line while creating the object-module

A : No compilation error

B : Only a lexical error

C : Only syntactic errors

D : Both lexical and syntactic errors

.

Correct answer is : C

Solution :

Note that there is 'fro' instead of 'for'. This is not a lexical error as lexical analysis typically involves Tokenization.

Question 62

**Consider the following circuit involving a positive edge triggered D FF and the following timing diagram. Let Ai represent the logic level on the line a in the i-th clock period.Let A¢ represent the complement of A. the correct output sequence on Y over the clock periods 1 through 5 is:**

A : A0 Al A1' A3 A4

B : A0 Al A2' A3 A4

C : Al A2 A2' A3 A4

D : Al A2' A3 A4 A5'

.

Correct answer is : A

Question 63

**The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE?**

A : It computes 1's complement of the input number

B : It computes 2's complement of the input number

C : It increments the input number

D : It decrements the input number

.

Correct answer is : B

Question 64

**Consider the following circuit.The flip-flops are positive edge triggered D FFs. Each state is designated as a two bit string Q0Q1. Let the initial state be 00. The state transition sequence is:**

A : A

B : B

C : C

D : D

.

Correct answer is : D

Question 65

**Consider a three word machine instruction**

ADD A[R0], @ B

The first operand (destination) "A [R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@ B" uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand). The number of memory cycles needed during the execution cycle of the instruction is

ADD A[R0], @ B

The first operand (destination) "A [R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@ B" uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand). The number of memory cycles needed during the execution cycle of the instruction is

A : 3

B : 4

C : 5

D : 6

.

Correct answer is : B

Solution :

In Indexed addressing mode, the base address is already in the instruction i.e A and to fetch the index data from R0 no memory access is required because it's a register So to fetch the operand only 1 memory cycle is required. Indirect Addressing mode requires 2 memory cycles only

Question 66

**Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side.**

A : (1, c), (2, b), (3, a)

B : (1, a), (2, c), (3, b)

C : (1, b), (2, c), (3, a)

D : (1, a), (2, b), (3, c)

.

Correct answer is : C

Question 67

**Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively**

A : 10,17

B : 10,22

C : 15,17

D : 5,17

.

Correct answer is : A

Question 68

**A 5 stage pipelined CPU has the following sequence of stages: What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I1 ?**

A : 8

B : 10

C : 12

D : 15

.

Correct answer is : A

Question 69

**A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred byte-wise. Let the interrupt overhead be 4 msec. The byte transfer time between the device interface register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under program controlled mode?**

A : 15

B : 25

C : 35

D : 45

.

Correct answer is : B

Solution :

In programmed I/O, CPU does continuous polling,

To transfer 10KB CPU polls for 1 sec = 10^6 micro-sec of processing

In interrupt mode CPU is interrupted on completion of io ,

To transfer 10 KB CPU does 4 micro-sec of processing.

Gain = 10^6 / 4 = 25000

250000 for 10000 bytes and 25 for 1 bytes.

Question 70

**Consider a disk drive with the following specifications: 16 surfaces, 512 tracks/surface, 512 sectors/track, 1 KB/sector, rotation speed 3000 rpm. The disk is operated in cycle stealing mode whereby whenever one byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a 4 byte word from the memory in each DMA cycle. Memory cycle time is 40 nsec. The maximum percentage of time that the CPU gets blocked during DMA operation is:**

A : 10

B : 25

C : 40

D : 50

.

Correct answer is : B

Solution :

Time takes for 1 rotation = 60/3000 It reads 512*1024 Bytes in one rotation. Time taken to read 4 bytes = 153 ns 153 is approximately 4 cycles (160ns) Percentage of time CPU gets blocked = 40*100/160 = 25

Question 71

**Suppose n processes, P1, …. Pn share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process Pi is Si, where Si > 0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?**

A : A

B : B

C : C

D : D

.

Correct answer is : C

Solution :

In the extreme condition, all processes acquire Si-1 resources and need 1 more resource. So opion c must be true to make sure that deadlock never occurs.

Question 72

**Consider the following code fragment:**

if (fork() == 0)

{

a = a + 5; printf(“%d,%d\n”, a, &a);

}

else { a = a –5; printf(“%d, %d\n”, a, &a);

} Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?

if (fork() == 0)

{

a = a + 5; printf(“%d,%d\n”, a, &a);

}

else { a = a –5; printf(“%d, %d\n”, a, &a);

} Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?

A : u = x + 10 and v = y

B : u = x + 10 and v != y

C : u + 10 = x and v = y

D : u + 10 = x and v != y

.

Correct answer is : C

Solution :

fork() returns 0 in child process and process ID of child process in parent process.

In Child (x), a = a + 5

In Parent (u), a = a – 5;

Therefore x = u + 10.

The physical addresses of ‘a’ in parent and child must be different. But our program accesses virtual addresses (assuming we are running on an OS that uses virtual memory). The child process gets an exact copy of parent process and virtual address of ‘a’ doesn’t change in child process. Therefore, we get same addresses in

Question 73

**In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is:**

A : 4

B : 5

C : 6

D : 7

.

Correct answer is : D

Question 74

**Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 ms. The minimum frame size is**

A : 94

B : 416

C : 464

D : 512

.

Correct answer is : C

Solution :

Transmission Speed = 10Mbps.

Round trip propagation delay = 46.4 ms

The minimum frame size = (Round Trip Propagation Delay) * (Transmission Speed) = 10*(10^6)*46.4*(10^-3) = 464 * 10^3 = 464 Kbit

Question 75

**Let E1 and E2 be two entities in an E/R diagram with simple single-valued attributes. R1 and R2 are two relationships between E1 and E2, where R1 is one-to-many and R2 is many-to-many. R1 and R2 do not have any attributes of their own. What is the minimum number of tables required to represent this situation in the relational model?**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Solution :

The answer is B, i.e minimum 3 tables. Strong entities E1 and E2 are represented as separate tables. In addition to that many-to-many relationships(R2) must be converted as seperate table by having primary keys of E1 and E2 as foreign keys. One-to-many relaionship (R1) must be transferred to 'many' side table(i.e. E2) by having primary key of one side(E1) as foreign key( this way we need not to make a seperate table for R1). Let relation schema be E1(a1,a2) and E2( b1,b2). Relation E1( a1 is the

Question 76

**The following table has two attributes A and C where A is the primary key and C is the foreign key referencing A with on-delete cascade.**

A C

-----

2 4

3 4

4 3

5 2

7 2

9 5

6 4

The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:

A C

-----

2 4

3 4

4 3

5 2

7 2

9 5

6 4

The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:

A : (3,4) and (6,4)

B : (5,2) and (7,2)

C : (5,2), (7,2) and (9,5)

D : (3,4), (4,3) and (6,4)

.

Correct answer is : C

Solution :

When (2,4) is deleted. Since C is a foreign key referring A with delete on cascade, all entries with value 2 in C must be deleted. So (5, 2) and (7, 2) are deleted. As a result of this 5 and 7 are deleted from A which causes (9, 5) to be deleted.

Question 77

**The relation book (title, price) contains the titles and prices of different books. Assuming that no two books have the same price, what does the following SQL query list?**

select title

from book as B

where (select count(*)

from book as T

where T.price > B.price) < 5

select title

from book as B

where (select count(*)

from book as T

where T.price > B.price) < 5

A : Titles of the four most expensive books

B : Title of the fifth most inexpensive book

C : Title of the fifth most expensive bookTitles of the five most expensive books

D : Titles of the five most expensive books

.

Correct answer is : D

Solution :

When a subquery uses values from outer query, the subquery is called correlated subquery. The correlated subquery is evaluated once for each row processed by the outer query. The outer query selects all titles from book table. For every selected book, the subquery returns count of those books which are more expensive than the selected book. The where clause of outer query will be true for 5 most expensive book. For example count (*) will be 0 for the most expensive book and count(*) will be 1 f

Question 78

**Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold: {A–>B, BC–>D, E–>C, D–>A}. What are the candidate keys of R?**

A : AE, BE

B : AE, BE, DE

C : AEH, BEH, BCH

D : AEH, BEH, DEH

.

Correct answer is : D

Solution :

A set of attributes S is candidate key of relation R if the closure of S is all attributes of R and there is no subset of S whose closure is all attributes of R.

Closure of AEH, i.e. AEH+ = {ABCDEH}

Closure of BEH, i.e. BEH+ = {ABCDEH}

Closure of DEH, i.e. DEH+ = {ABCDEH}

Question 79

**Consider the following data path of a CPU.The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation - the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR The instruction "add R0, R1" has the register transfer interpretation R0 < = R0 + R1. The minimum number of clock cycles needed for execution cycle of this instruction is.**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Solution :

Minimum number of clock cycles (execution only) = 3

1) load Y

2) input R1, add

3) output to R1

Question 80

**The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation - the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR 79. The instruction "call Rn, sub" is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is**

Rn < = PC + 1;

PC < = M[PC];

The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:

Rn < = PC + 1;

PC < = M[PC];

The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Solution :

One cycle to increment PC, one cycle to load PC into MAR, one cycle to fetch memory content and load into PC.

Question 81

**Consider the following C-function:**

The space complexity of the above function is:

double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } }

The space complexity of the above function is:

A : O(1)

B : O(n)

C : O(n!)

D : O(n

^{n})

.

Correct answer is : B

Solution :

Note that the function foo() is recursive. Space complexity is O(n) as there can be at most O(n) active functions (function call frames) at a time.

Question 82

**Consider the following C-function:**

Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be

double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } }

Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be

A : O(1)

B : O(n)

C : O(n!)

D : O(n

^{n})

.

Correct answer is : B

Solution :

Space complexity now is also O(n). We would need an array of size O(n). The space required for recursive calls would be O(1) as the values would be taken from stored array rather than making function calls again and again.

Question 83

**Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y The edge e must definitely belong to:**

A : the minimum weighted spanning tree of G

B : the weighted shortest path from s to t

C : each path from s to t

D : the weighted longest path from s to t

.

Correct answer is : A

Solution :

This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge.

Question 84

**Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum weight amongst all those edges that have one vertex in X and one vertex in Y.**

A : a path from s to t in the minimum weighted spanning tree

B : a weighted shortest path from s to t

C : an Euler walk from s to t

D : a Hamiltonian path from s to t

.

Correct answer is : B

Question 85

**Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.**

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

A : It detects recursion and eliminates recursion

B : It detects reduce-reduce conflict, and resolves

C : It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action

D : It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action

.

Correct answer is : C

Question 86

**Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.**

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

A : Equal precedence and left associativity; expression is evaluated to 7

B : Equal precedence and right associativity; expression is evaluated to 9

C : Precedence of '×' is higher than that of '+', and both operators are left associative; expression is

D : Precedence of '+' is higher than that of '×', and both operators are left associative; expression is

.

Correct answer is : A

Question 87

**We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.Are all tasks completed in the schedule that gives maximum profit?**

A : All tasks are completed

B : T1 and T6 are left out

C : T1 and T8 are left out

D : T4 and T6 are left out

.

Correct answer is : D

Solution :

Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3

To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1

Question 88

**We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.**

What is the maximum profit earned?

What is the maximum profit earned?

A : 147

B : 165

C : 167

D : 175

.

Correct answer is : A

Solution :

Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3

To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1. We get the maximum profit as 23 + 20 + 25 + 18 + 30 + 16 + 15 = 147

Question 89

**Consider the following floating point format.Mantissa is a pure fraction in sign-magnitude form. The decimal number 0.239 × 2**

^{13}has the following hexadecimal representation (without normalization and rounding off :A : 0D24

B : 0D4D

C : 4D0D

D : 4D3D

.

Correct answer is : D

Question 90

**Consider the following floating point format.Mantissa is a pure fraction in sign-magnitude form. The normalized representation for the above format is specified as follows. The mantissa has an implicit 1 preceding the binary (radix) point. Assume that only 0's are padded in while shifting a field. The normalized representation of the above number (0.239 × 2**

^{13}) is:A : 0A20

B : 1134

C : 4DD0

D : 4AE8

.

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.