Question 1

**Evaluate the following**

A : 1

B : -1

C : INF

D : -INF

.

Correct answer is : A

Question 2

**If P, Q, R are subsets of the universal set U, then (P ∩ Q ∩ R) U (P` ∩ Q ∩ R) U Q` U R`**

A : Q` U R`

B : P U Q` U R`

C : P` U Q` U R`

D : U

.

Correct answer is : D

Solution :

(P ∩ Q ∩ R) ∪ (P` ∩ Q ∩ R) ∪ (Q` ∩ R`) where ` denotes complement

(P` ∪ P) ∩ ((Q ∩ R) ∪ (Q` ∪ R`))

U ∩ ((Q ∩ R) ∪ (Q ∪ R`))

U ∩ U

= U

Question 3

**The following system of equations has a unique solution. The only possible value(s) for α is/are**

A : 0

B : Either 0 or 1

C : any real number

D : any real number other than 5

.

Correct answer is : D

Solution :

Augment the given matrix as

1 1 2 | 1

1 2 3 | 2

1 4 a | 4

Apply R2 <- R2 - R1 and R3 <- R3 - R1

1 1 2 | 1

0 1 1 | 1

0 3 a-2 | 3

Apply R3 <- R3 - 3R2

1 1 2 | 1

0 1 1 | 1

0 0 a-5 | 0

So for the system of equations to have a unique solution,

a - 5 != 0

or

a != 5

or

a = R - {5}

Question 4

**In the IEEE floating point representation, the hexadecimal value 0 × 00000000 corresponds to**

A : the normalized value 2

^{-127}

B : the normalized value 2

^{-126}

C : the normalized value +0

D : the special value +0

.

Correct answer is : D

Solution :

Exponent = All zero

Fraction = All zero

Number = Positive or negative zero

Question 5

**In the Karnaugh map shown below, X denotes a don't care term. What is the minimal form of the function represented by the Karnaugh map?**

A : b`d` + a`d`

B : a`b`+b`d`+a`bd`

C : b`d`+a`bd`

D : a`b`+b`d`+a`d`

.

Correct answer is : A

Question 6

**Let r denote number system radix. The only value(s) of r that satisfy the equation √(121**

_{r}) = 11_{r}is/areA : decimal 10

B : decimal 11

C : decimal 10 and 11

D : any value >2

.

Correct answer is : D

Question 7

**Given f1, f3 and f in canonical sum of products form (in decimal) for the circuit then f2 is**

A : &sum (4,6)

B : &sum (4,8)

C : &sum (6,8)

D : &sum (4,6,8)

.

Correct answer is : C

Question 8

**Which of the following is true for the language { a**

^{p}| p is prime }A : It is not accepted by a Turing Machine

B : It is regular but not context-free

C : It is context-free but not regular

D : It is neither regular nor context-free, but accepted by a Turing machine

.

Correct answer is : D

Question 9

**Which of the following are decidable?**

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

A : I and II

B : I and IV

C : II and III

D : II and IV

.

Correct answer is : B

Question 10

**Which of the following describes a handle (as applicable to LR-parsing) appropriately?**

A : It is the position in a sentential form where the next shift or reduce operation will occur

B : It is non-terminal whose production will be used for reduction in the next step

C : It is a production that may be used for reduction in a future step along with a position in the sent

D : It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found

.

Correct answer is : D

Question 11

**Some code optimizations are carried out on the intermediate code because**

A : they enhance the portability of the compiler to other target processors

B : program analysis is more accurate on intermediate code than on machine code

C : the information from dataflow analysis cannot otherwise be used for optimization

D : the information from the front end cannot otherwise be used for optimization

.

Correct answer is : A

Question 12

**If L and L' are recursively enumerable, then L is**

A : regular

B : context-free

C : context-sensitive

D : recursive

.

Correct answer is : D

Solution :

If L is recursively enumerable, then L' is recursively enumerable if and only if L is also recursive.

Question 13

**What is the maximum size of data that the application layer can pass on to the TCP layer below?**

A : Any size

B : 2

^{16}bytes - size of TCP header

C : 2

^{16}bytes

D : 1500 bytes

.

Correct answer is : A

Solution :

The default TCP Maximum Segment Size is 536. Where a host wishes to set the maximum segment size to a value other than the default, the maximum segment size is specified as a TCP option, initially in the TCP SYN packet during the TCP handshake. Because the maximum segment size parameter is controlled by a TCP option, a host can change the value in any later segment.

Question 14

**Which of the following tuple relational calculus expression(s) is/are equivalent to**

∀t ∈ r( P(t) ) ?

∀t ∈ r( P(t) ) ?

A : I only

B : II only

C : III only

D : III and IV only

.

Correct answer is : C

Question 15

**A clustering index is defined on the fields which are of type**

A : non-key and ordering

B : non-key and non-ordering

C : key and ordering

D : key and non-ordering

.

Correct answer is : A

Solution :

A clustering index determines how rows are physically ordered.

Question 16

**Which of the following system calls results in the sending of SYN packets?**

A : socket

B : bind

C : listen

D : connect

.

Correct answer is : D

Solution :

socket() creates a new socket of a certain socket type, identified by an integer number, and allocates system resources to it.

bind() is typically used on the server side, and associates a socket with a socket address structure, i.e. a specified local port number and IP address.

listen() is used on the server side, and causes a bound TCP socket to enter listening state.

connect() is used on the client side, and assigns a free local port number to a socket. In case of a TCP socket, it it causes an attempt to establish a new TCP connection. When connect() is called by client, following three way handshake happens to establish the connection in TCP. 1) The client requests a connection by sending a SYN (synchronize) message to the server. 2) The server acknowledges this request by sending SYN-ACK back to the client. 3) The client responds with an ACK, and the connection is established.

Question 17

**The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is**

A : MNOPQR

B : NQMPOR

C : QMNPRO

D : QMNPOR

.

Correct answer is : C

Question 18

**Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?**

a = ( x > y ) ? (( x > z ) ? x : z) : (( y > z ) ? y : z )

a = ( x > y ) ? (( x > z ) ? x : z) : (( y > z ) ? y : z )

A : x = 3, y = 4, z = 2

B : x = 6, y = 5, z = 3

C : x = 6, y = 3, z = 5

D : x = 5, y = 4, z = 5

.

Correct answer is : A

Solution :

The given expression assigns maximum among three elements (x, y and z) to a.

Question 19

**The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity**

A : θ (n)

B : θ (m)

C : θ (m+n)

D : θ (mn)

.

Correct answer is : C

Solution :

Number of connected components in undirected graph can simply calculated by doing a BFS or DFS. The best possible time complexity of BFS and DFS is O(m + n).

Question 20

**The data blocks of a very large file in the Unix file system are allocated using**

A : contiguous allocation

B : linked allocation

C : indexed allocation

D : an extension of indexed allocation

.

Correct answer is : D

Question 21

**The minimum number of equal length subintervals needed to approximate to an accuracy of at least 1/3 * 10**

^{-6}using the trapezoidal rule isA : 1000e

B : 1000

C : 100e

D : 100

.

Correct answer is : A

Question 22

**The Newton-Raphson iteration x**

_{n+1}= 1/2(x_{n}+ R/x_{n}) can be used to compute the.A : square of R

B : reciprocal of R

C : square root of R

D : logarithm of R

.

Correct answer is : C

Solution :

According to Newton-Raphson method,

x

_{n+1}= x

_{n}- f(x

_{n}) / f`(x

_{n})

So we try to bring given equation in above form. Given equation is :

x

_{n+1}= x

_{n}/2 + R/(2x

_{n})

= x

_{n}- x

_{n}/2 + R/(2x

_{n})

= x

_{n}- (x

_{n}

^{2}- R2)/(2x

_{n})

So clearly f(x) = x2 - R, so root of f(x) means x2 - R = 0 i.e. we are trying to find square root of R. So option (C) is corr

Question 23

**Which of the following statements is true for every planar graph on n vertices?**

A : The graph is connected

B : The graph is Eulerian

C : The graph has a vertex-cover of size at most 3n/4

D : The graph has a independent set of size at least n/3

.

Correct answer is : C

Solution :

A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A) FALSE: A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B) FALSE: An Eulerian Graph may or may not be planar. An undirected graph is eulerian if all vertices have even degree.

Question 24

A : P=Q-k

B : P=Q+k

C : P=Q

D : P=Q+2k

.

Correct answer is : A

Question 25

**A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x**

^{4}- 16x^{3}+ 24x^{2}+ 37A : 0

B : 1

C : 2

D : 3

.

Correct answer is : B

Solution :

f(x)=3x

^{4}- 16x

^{3}+ 24x

^{2}+ 37

f`(x)=12x

^{3}- 48x

^{2}+ 48x

f``(x)= 36x

^{2}- 96x + 48

f`(x) = 0 => 12x (x

^{2}- 4x + 4) = 12x (x-2)

^{2}

f`(x) is negative for all x< 0 and positive for all x > 0

=> f(x) is decreasing to the left of zero and increasing to the right of zero

=> f(x) has only one minimum (extrema) at x = 0

Question 26

**If P, Q, R are Boolean variables, then (P + Q')(PQ' + PR)(P'R' + Q') simplifies**

A : PQ`

B : PR`

C : PQ` + R

D : PR` + Q

.

Correct answer is : A

Solution :

(P + Q`)(P.Q` + P.R)(P`.R` + Q`)

=(P + Q)(P.Q + P.R.Q`)

=(P + Q)(P.Q + P.R.Q`)

=(P + Q)(P.Q`) => pQ`

Question 27

**Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?**

A : 0.24

B : 0.36

C : 0.4

D : 0.6

.

Correct answer is : C

Question 28

**How many of the following matrices have an eigenvalue 1?**

A : 1

B : 2

C : 3

D : 4

.

Correct answer is : A

Question 29

**Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown If P(X <=-1) = P(Y >-2). the standard deviation of Y is**

A : 3

B : 2

C : sqrt(2)

D : 1

.

Correct answer is : A

Solution :

X(1,4), Y(-1,Δ

P(X <= -1)Z = -1-1/2 = -1

=P(Z <= -1)= P(Z >= 1) = 0.5 - P(0 < Z < 1)

=0.5 - 0.3413 = 0.1587

if Δ = 3,then P(Z >= 2),Z = 2+1/3 = 1

=P(Z >= 1) = 0.1587

Question 30

**Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following: Each finite state automaton has an equivalent pushdown automaton.**

A : A

B : B

C : C

D : D

.

Correct answer is : A

Question 31

**For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to**

A : non-uniform distribution of requests

B : arm starting and stopping inertia

C : higher capacity of tracks on the periphery of the platter

D : use of unfair arm scheduling policies

.

Correct answer is : B

Question 32

**Which of the following is/are true of the auto-increment addressing mode?**

I. It is useful in creating self-relocating code.

II. If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation.

III.The amount of increment depends on the size of the data item accessed.

I. It is useful in creating self-relocating code.

II. If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation.

III.The amount of increment depends on the size of the data item accessed.

A : I only

B : II only

C : III only

D : II and III only

.

Correct answer is : C

Question 33

**P and Q are two propositions. Which of the following logical expressions are equivalent?**

I. P ∨ ~Q

II. ~(~P ∧ Q)

III. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~Q)

IV.(P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)

I. P ∨ ~Q

II. ~(~P ∧ Q)

III. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~Q)

IV.(P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)

A : Only I and II

B : Only I,II and III

C : Only I,II and IV

D : All of I,II,III and IV

.

Correct answer is : B

Solution :

I and II are same by Demorgan's law The IIIrd can be simplified to P ∨ ~P is always true.

Question 34

**Which of the following must be true for the RFE (Return from Exception) instruction on a general purpose processor?**

I. It must be a trap instruction

II. It must be a privileged instruction

III. An exception cannot be allowed to occur during execution of an RFE instruction

I. It must be a trap instruction

II. It must be a privileged instruction

III. An exception cannot be allowed to occur during execution of an RFE instruction

A : I only

B : II only

C : I and II only

D : I,II and III only

.

Correct answer is : D

Solution :

RFE (Return From Exception) is a privileged trap instruction that is executed when exception occurs, so an exception is not allowed to execute. (D) is the correct option.

Question 35

**For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary?**

I. L1 must be a write-through cache

II. L2 must be a write-through cache

III. The associativity of L2 must be greater than that of L1

IV. The L2 cache must be at least as large as the L1 cache

I. L1 must be a write-through cache

II. L2 must be a write-through cache

III. The associativity of L2 must be greater than that of L1

IV. The L2 cache must be at least as large as the L1 cache

A : IV only

B : I and IV only

C : I,III and IV only

D : I,II,III and IV

.

Correct answer is : A

Solution :

L1 and L2 cache are placed between CPV & they can be both write through cache but not necessary. Associativity doesn't matter. L2 cache must be at least as large as L1 cache, since all the words in L1 are also is L2.

Question 36

**Which of the following are NOT true in a pipelined processor?**

I. Bypassing can handle all RAW hazards.

II. Register renaming can eliminate all register carried WAR hazards.

III. Control hazard penalties can be eliminated by dynamic branch prediction.

I. Bypassing can handle all RAW hazards.

II. Register renaming can eliminate all register carried WAR hazards.

III. Control hazard penalties can be eliminated by dynamic branch prediction.

A : I and II only

B : I and III only

C : II and III only

D : I, II and III

.

Correct answer is : D

Solution :

i) In a Pipelined processor bypassing can’t handle all the raw hazards. A read after write (RAW) data hazard refers to a situation where an instruction refers to a result that has not yet been calculated or retrieved. This can occur because even though an instruction is executed after a previous instruction, the previous instruction has not been completely processed through the pipeline.Consider when any instruction depends on the result of LOAD instruction, now LOAD updates register value at Memory Access Stage (MA), so data will not be available directly on Execute stage. ii) WAR(Write After Read ) A write after read (WAR) data hazard represents a problem with concurrent execution. Register carried WAR does not have register renaming as proper solution because If programs refrained from reusing registers immediately, there would be no need for register renaming.

Question 37

**The use of multiple register windows with overlap causes a reduction in the number of memory accesses for**

I. Function locals and parameters

II. Register saves and restores

III. Instruction fetches

I. Function locals and parameters

II. Register saves and restores

III. Instruction fetches

A : I only

B : II only

C : III only

D : I,II and III

.

Correct answer is : B

Question 38

**In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is**

A : before effective address calculation has started

B : during effective address calculation

C : after effective address calculation has completed

D : after data cache lookup has completed

.

Correct answer is : B

Question 39

**Consider the following functions:**

f(n) = 2

g(n) = n!

h(n) = n

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

f(n) = 2

^{n}g(n) = n!

h(n) = n

^{logn}Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

A : f(n) = O(g(n)); g(n) = O(h(n))

B : f(n) = Ω (g(n)); g(n) = O(h(n))

C : g(n) = O(f(n)); h(n) = O(f(n))

D : h(n) = O(f(n)); g(n) = Ω(f(n))

.

Correct answer is : D

Solution :

According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) ) We can easily see above order by taking logs of the given 3 functions

Question 40

**The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is**

A : θ (n)

B : θ (log n)

C : θ (log*n)

D : 1

.

Correct answer is : B

Question 41

**A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?**

A : 3

B : 4

C : 5

D : 6

.

Correct answer is : C

Question 42

**G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?**

A : For every subset of k vertices, the induced subgraph has at most 2k-2 edges

B : The minimum cut in G has at least two edges

C : There are two edge-disjoint paths between every pair to vertices

D : There are two vertex-disjoint paths between every pair of vertices

.

Correct answer is : D

Solution :

Counter for option D is as follows. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by using these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex.

Question 43

**Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then**

A : T(n) <= 2T(n/5) + n

B : T(n) <= T(n/5) + T(4n/5) + n

C : T(n) <= 2T(4n/5) + n

D : T(n) <= 2T(n/2) + n

.

Correct answer is : B

Solution :

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

Question 44

**The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?**

A : X[i, j] = X[i - 1, j] V X[i, j -ai]

B : X[i, j] = X[i - 1, j] V X[i - 1, j - ai]

C : X[i, j] = X[i - 1, j] /\ X[i, j - ai]

D : X[i, j] = X[i - 1, j] /\ X[i -1, j - ai]

.

Correct answer is : B

Solution :

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

Question 45

**Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to**

A : only vertex a

B : only vertices a, e, f, g, h

C : only vertices a, b, c, d

D : all the vertices

.

Correct answer is : D

Solution :

Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.

Question 46

**You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?**

A : O(log n)

B : O(n)

C : O(n log n)

D : none of the above, as the tree cannot be uniquely determined

.

Correct answer is : B

Question 47

**We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is**

A : θ (log n)

B : θ (n)

C : θ (n logn)

D : θ (n

^{2})

.

Correct answer is : B

Question 48

**Which of the following statements is false?**

A : Every NFA can be converted to an equivalent DFA

B : Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machin

C : Every regular language is also a context-free language

D : Every subset of a recursively enumerable set is recursive

.

Correct answer is : D

Question 49

**Given below are two finite state automata (? indicates the start state and F indicates a final state)Which of the following represents the product automaton Z×Y?**

A : A

B : B

C : C

D : D

.

Correct answer is : A

Question 50

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

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa

II. All ε productions can be removed from any context-free grammar by suitable transformations

III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular

IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa

II. All ε productions can be removed from any context-free grammar by suitable transformations

III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular

IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

A : I,II,III and IV

B : II,III and IV only

C : I,III and IV only

D : I,II and IV only

.

Correct answer is : C

Question 51

**Match the following:**

A : E - P, F - R, G - Q, H - S

B : E - R, F - P, G - S, H - Q

C : E - R, F - P, G - Q, H - S

D : E - P, F - R, G - S, H - Q

.

Correct answer is : C

Question 52

**Match the following NFAs with the regular expressions they correspond to**

1. ε + 0(01*1 + 00) * 01*

2. ε + 0(10 *1 + 00) * 0

3. ε + 0(10 *1 + 10) *1

4. ε + 0(10 *1 + 10) *10 *

1. ε + 0(01*1 + 00) * 01*

2. ε + 0(10 *1 + 00) * 0

3. ε + 0(10 *1 + 10) *1

4. ε + 0(10 *1 + 10) *10 *

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

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

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

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

.

Correct answer is : C

Question 53

**Which of the following are regular sets?**

I. { a

II. { a

III. { a

IV. {xcy x, y ε{a,b} *}

I. { a

^{n}b^{2m}|n >=0,m >= 0}II. { a

^{n}b^{m}|n = 2m }III. { a

^{n}b^{m}|n ≠ m}IV. {xcy x, y ε{a,b} *}

A : I and IV only

B : I and III only

C : I only

D : IV only

.

Correct answer is : A

Solution :

We can write DFA for both I and IV.

Question 54

**Which of the following are true?**

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic storage allocation

IV. Nesting of procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic storage allocation

IV. Nesting of procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

A : II and V only

B : I,III and IV only

C : I,II and V only

D : II,III and V only

.

Correct answer is : A

Question 55

**An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if**

A : the SLR(1) parser for G has S-R conflicts

B : the LR(1) parser for G has S-R conflicts

C : the LR(0) parser for G has S-R conflicts

D : the LALR(1) parser for G has reduce-reduce conflicts

.

Correct answer is : B

Question 56

**In the slow start phase of the TCP congestion control algorithm, the size of the congestion window**

A : does not increase

B : increases linearly

C : increases quadractically

D : increases exponentially

.

Correct answer is : D

Solution :

Although the name is slow start, during the slow start phase, window size is increased by the number of segments acknowledged, which means window size grows exponentially. This happens until either an acknowledgment is not received for some segment or a predetermined threshold value is reached.

Question 57

**If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?**

A : 1022

B : 1023

C : 2046

D : 2047

.

Correct answer is : C

Solution :

The binary representation of subnet mask is 11111111.11111111.11111000.00000000. There are 21 bits set in subnet. So 11 (32-21) bits are left for host ids. Total possible values of host ids is 2^11 = 2048. Out of these 2048 values, 2 addresses are reserved. 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 general, the number of addresses usable for addressing specific hosts in each network is always 2

Question 58

**A computer on a 10Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits. What is the maximum duration for which the computer can transmit at the full 10Mbps?**

A : 1.6 seconds

B : 2 seconds

C : 5 seconds

D : 8 seconds

.

Correct answer is : B

Solution :

New tokens are added at the rate of r bytes/sec which is

2Mbps in the given question.

Capacity of the token bucket (b) = 16 Mbits

Maximum possible transmission rate (M) = 10Mbps

So the maximum burst time = b/(M-r) = 16/(10-2) = 2 seconds

Question 59

**A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket(), a bind() and a listen() system call in that order, following which it is preempted. Subsequently, the client process P executes a socket() system call followed by connect() system call to connect to the server process S. The server process has not executed any accept() system call. Which one of the following events could take place?**

A : connect () system call returns successfully

B : connect () system call blocks

C : connect () system call returns an error

D : connect () system call results in a core dump

.

Correct answer is : C

Solution :

Since accept() call is not executed then connect () gets no response for a time stamp to wait & then return no response server error.

Question 60

**What is printed by the following C program?**

int f(int x, int *py, int **ppz)

{

int y, z;

**ppz += 1;

z = **ppz;

*py += 2;

y = *py;

x += 3;

return x + y + z;

}

void main()

{

int c, *b, **a;

c = 4;

b = &c;

a = &b;

printf( "%d", f(c,b,a));

getchar();

}

int f(int x, int *py, int **ppz)

{

int y, z;

**ppz += 1;

z = **ppz;

*py += 2;

y = *py;

x += 3;

return x + y + z;

}

void main()

{

int c, *b, **a;

c = 4;

b = &c;

a = &b;

printf( "%d", f(c,b,a));

getchar();

}

A : 18

B : 19

C : 21

D : 22

.

Correct answer is : B

Solution :

/* Explanation for the answer */

/*below line changes value of c to 5. Note that x remains unaffected by this change as x is a copy of c and address of x is different from c*/

**ppz += 1

/* z is changed to 5*/

z = **ppz;

/* changes c to 7, x is not changed */

*py += 2;

/* y is changed to 7*/

y = *py;

/* x is incremented by 3 */

x += 3;

/* return 7 + 7 + 5*/

return x + y + z;

Question 61

**Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.**

void reverse(void)

{

int c;

if (?1) reverse();

?2

}

int main()

{

printf ("Enter Text ") ;

printf ("\n") ;

reverse();

printf ("\n") ;

}

void reverse(void)

{

int c;

if (?1) reverse();

?2

}

int main()

{

printf ("Enter Text ") ;

printf ("\n") ;

reverse();

printf ("\n") ;

}

A : ?1 is (getchar() != ’\n’)

?2 is getchar(c);

B : ?1 is (c = getchar() ) != ’\n’)

?2 is getchar(c);

C : ?1 is (c != ’\n’)

?2 is putchar(c);

D : ?1 is ((c = getchar()) != ’\n’)

?2 is putchar(c);

.

Correct answer is : D

Solution :

getchar() is used to get the input character from the user and putchar() to print the entered character, but before printing reverse is called again and again until ‘ ’ is entered. When ‘ ’ is entered the functions from the function stack run putchar() statements one by one. Therefore, last entered character is printed first.

Question 62

**The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?**

struct node { int value; struct node *next; }; void rearrange(struct node *list) { struct node *p, * q; int temp; if ((!list) || !list->next) return; p = list; q = list->next; while(q) { temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0; } }

A : 1,2,3,4,5,6,7

B : 2,1,4,3,6,5,7

C : 1,3,2,5,4,7,6

D : 2,3,4,5,6,7,1

.

Correct answer is : B

Solution :

The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

Question 63

**The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:**

P(s) : s = s - 1; if (s < 0) then wait; V(s) : s = s + 1; if (s <= 0) then wakeup a process waiting on s; Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores Xb and Yb are used to implement the semaphore operations P(s) and V(s) as follows: P(s) : Pb(Xb); s = s - 1; if (s < 0) { Vb(Xb) ; Pb(Yb) ; } else Vb(Xb); V(s) : Pb(Xb) ; s = s + 1; if (s <= 0) Vb(Yb) ; Vb(Xb) ; The initial values of Xb and Yb are respectively

A : 0 and 0

B : 0 and 1

C : 1 and 0

D : 1 and 1

.

Correct answer is : C

Solution :

Both P(s) and V(s) operations are perform Pb(xb) as first step. If Xb is 0, then all processes executing these operations will be blocked. Therefore, Xb must be 1.

If Yb is 1, it may become possible that two processes can execute P(s) one after other (implying 2 processes in critical section). Consider the case when s = 1, y = 1. So Yb must be 0.

Question 64

**Which of the following statements about synchronous and asynchronous I/O is NOT true?**

A : An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O

B : In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of the I/O

C : A process making a synchronous I/O call waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O

D : In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O

.

Correct answer is : A

Solution :

In both Synchronous and Asynchronous, an interrupt is generated on completion of I/O. In Synchronous, interrupt is generated to wake up the process waiting for I/O. In Asynchronous, interrupt is generated to inform the process that the I/O is complete and it can process the data from the I/O operation.

Question 65

**Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?**

A : In deadlock prevention, the request for resources is always granted if the resulting state is safe

B : In deadlock avoidance, the request for resources is always granted if the result state is safe

C : Deadlock avoidance is less restrictive than deadlock prevention

D : Deadlock avoidance requires knowledge of resource requirements a priori

.

Correct answer is : A

Solution :

Deadlock prevention scheme handles deadlock by making sure that one of the four necessary conditions don't occur. In deadlock prevention, the request for a resource may not be granted even if the resulting state is safe.

Question 66

**A process executes the following code**

for (i = 0; i < n; i++) fork();

The total number of child processes created is

for (i = 0; i < n; i++) fork();

The total number of child processes created is

A : n

B : 2^n-1

C : 2^n

D : 2^(n+1) -1

.

Correct answer is : B

Solution :

F0 // There will be 1 child process created by first fork / F1 F1 // There will be 2 child processes created by second fork / / F2 F2 F2 F2 // There will be 4 child processes created by third fork / / / / ............... // and so onIf we sum all levels of above tree for i = 0 to n-1, we get 2^n - 1. So there will be 2^n – 1 child processes.

Question 67

**A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows • Bits 30-31 are used to index into the first level page table • Bits 21-29 are used to index into the second level page table • Bits 12-20 are used to index into the third level page table, and • Bits 0-11 are used as offset within the page The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively.**

A : 20, 20 and 20

B : 24, 24 and 24

C : 24, 24 and 20

D : 25, 25 and 24

.

Correct answer is : D

Solution :

Virtual address size = 32 bits

Physical address size = 36 bits

Physical memory size = 2^36 bytes

Page frame size = 4K bytes = 2^12 bytes

No. of bits required to access physical memory frame = 36 - 12 = 24

So in third level of page table, 24 bits are required to access an entry.

9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes. So size of second level page table is (2^9)*4 = 2^11 bytes.

It means there are (2^36)/(2^11) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. Similarly, the third page table needs 25 bits to address it.

Question 68

A : Only I and II

B : Only I and III

C : Only I,II and III

D : Only I, III and IV

.

Correct answer is : D

Solution :

In I, Ps from natural join of R and S are selected.

In III, all Ps from intersection of (P, Q) pairs present in R and S.

IV is also equivalent to III because (R – (R – S)) = R ∩ S.

II is not equivalent as it may also include Ps where Qs are not same in R and S.

Question 69

**Consider the following relational schemes for a library database: Book (Title, Author, Catalog_no, Publisher, Year, Price) Collection (Title, Author, Catalog_no) with in the following functional dependencies:**

I. Title Author --> Catalog_no

II. Catalog_no --> Title Author Publisher Year

III. Publisher Title Year --> Price

Assume {Author, Title} is the key for both schemes. Which of the following statements is true?

I. Title Author --> Catalog_no

II. Catalog_no --> Title Author Publisher Year

III. Publisher Title Year --> Price

Assume {Author, Title} is the key for both schemes. Which of the following statements is true?

A : Both Book and Collection are in BCNF

B : Both Book and Collection are in 3NF only

C : Book is in 2NF and Collection is in 3NF

D : Both Book and Collection are in 2NF only

.

Correct answer is : C

Solution :

Table Collection is in BCNF as there is only one functional dependency “Title Author –> Catalog_no” and {Author, Title} is key for collection. Book is not in BCNF because Catalog_no is not a key and there is a functional dependency “Catalog_no –> Title Author Publisher Year”. Book is not in 3NF because non-prime attributes (Publisher Year) are transitively dependent on key [Title, Author]. Book is in 2NF because every non-prime attribute of the table is either dependent on the key [Title, Author], or on another non prime attribute.

Question 70

**Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multi-level index scheme is used to store the secondary index, the number of first-level and second-level blocks in the multi-level index are**

A : 8 and 0

B : 128 and 6

C : 256 and 4

D : 512 and 5

.

Correct answer is : C

Question 71

**Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes.**

double ARR[1024][1024];

int i,j;

/* initialize array ARR to 0.0 */

for(i=0;i<1024;i++)

for(j=0;j<1024;j++)

ARR[i][j]=0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

The total size of the tags in the cache directory is

double ARR[1024][1024];

int i,j;

/* initialize array ARR to 0.0 */

for(i=0;i<1024;i++)

for(j=0;j<1024;j++)

ARR[i][j]=0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

The total size of the tags in the cache directory is

A : 32 bits

B : 34 bits

C : 64 bits

D : 68 bits

.

Correct answer is : B

Question 72

**Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes.**

double ARR[1024][1024];

int i,j;

/* initialize array ARR to 0.0 */

for(i=0;i<1024;i++)

for(j=0;j<1024;j++)

ARR[i][j]=0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

Which of the following array elements has the same cache index as ARR [0] [0]?

double ARR[1024][1024];

int i,j;

/* initialize array ARR to 0.0 */

for(i=0;i<1024;i++)

for(j=0;j<1024;j++)

ARR[i][j]=0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

Which of the following array elements has the same cache index as ARR [0] [0]?

A : ARR [0] [4]

B : ARR [4] [0]

C : ARR [0] [5]

D : ARR [5] [0]

.

Correct answer is : B

Question 73

**Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes.**

double ARR[1024][1024];

int i,j;

/* initialize array ARR to 0.0 */

for(i=0;i<1024;i++)

for(j=0;j<1024;j++)

ARR[i][j]=0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

The cache hit ratio for this initialization loop is

double ARR[1024][1024];

int i,j;

/* initialize array ARR to 0.0 */

for(i=0;i<1024;i++)

for(j=0;j<1024;j++)

ARR[i][j]=0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

The cache hit ratio for this initialization loop is

A : 0%

B : 25%

C : 50%

D : 75%

.

Correct answer is : C

Question 74

**Consider the following C program**

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

return (2*f1(n-1) + 3*f1(n-2));

}

int f2(int n)

{

int i;

int X[N], Y[N], Z[N] ;

X[0] = Y[0] = Z[0] = 0;

X[1] = 1; Y[1] = 2;

Z[1] = 3;

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

{

X[i] = Y[i-1] + Z[i-2];

Y[i] = 2*X[i];

Z[i] = 3*X[i];

}

return X[n] ;

}

The running time of f1(n) and f2(n) are

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

return (2*f1(n-1) + 3*f1(n-2));

}

int f2(int n)

{

int i;

int X[N], Y[N], Z[N] ;

X[0] = Y[0] = Z[0] = 0;

X[1] = 1; Y[1] = 2;

Z[1] = 3;

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

{

X[i] = Y[i-1] + Z[i-2];

Y[i] = 2*X[i];

Z[i] = 3*X[i];

}

return X[n] ;

}

The running time of f1(n) and f2(n) are

A : θ (n) and θ (n)

B : θ (2

^{n}) and θ (n)

C : θ (n) and θ (2

^{n})

D : θ (2

^{n}) and θ (2

^{n})

.

Correct answer is : B

Solution :

For f1(), let T(n) be the function for time complexity.

T(n) = T(n-1) + T(n-2)

Above recursion is a standard one for Fibonacci Numbers. After solving the recursion, we get

T(n) = 1/sqrt(5)[(1 + sqrt(5))/2]^n - 1/sqrt(5)[(1 - sqrt(5))/2]^n

Above recursion can also be written as ?(1.618.^n)

In f2(), there is a single loop, so time complexity is ?(n)

Among all the 4 given choices, (B) looks closest.

Question 75

**Consider the following C program**

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

return (2*f1(n-1) + 3*f1(n-2));

}

int f2(int n)

{

int i;

int X[N], Y[N], Z[N] ;

X[0] = Y[0] = Z[0] = 0;

X[1] = 1; Y[1] = 2;

Z[1] = 3;

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

{

X[i] = Y[i-1] + Z[i-2];

Y[i] = 2*X[i];

Z[i] = 3*X[i];

}

return X[n] ;

}

f1(8) and f2(8) return the values

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

return (2*f1(n-1) + 3*f1(n-2));

}

int f2(int n)

{

int i;

int X[N], Y[N], Z[N] ;

X[0] = Y[0] = Z[0] = 0;

X[1] = 1; Y[1] = 2;

Z[1] = 3;

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

{

X[i] = Y[i-1] + Z[i-2];

Y[i] = 2*X[i];

Z[i] = 3*X[i];

}

return X[n] ;

}

f1(8) and f2(8) return the values

A : 1661 and 1640

B : 59 and 59

C : 1640 and 1640

D : 1640 and 1661

.

Correct answer is : C

Solution :

Both functions perform same operation, so output is same, means either (B) or (C) is correct.

f1(2) = 2*f1(1) + 3*f1(0) = 2

f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7

f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20

f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61

We can skip after this as the only remaining choice is (C)

f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182

f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547

f1(8) = 2*f1(7) +

Question 76

**Delayed branching can help in the handling of control hazards. For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false,**

A : the instruction following the conditional branch instruction in memory is executed

B : the first instruction in the fall through path is executed

C : the first instruction in the taken path is executed

D : the branch takes longer to execute than any other instruction

.

Correct answer is : D

Question 77

**Delayed branching can help in the handling of control hazards The following code is to run on a pipelined processor with one branch delay slot:**

I1: ADD R2 <- R7+R8

I2 : SUB R4 <- R5-R6

I3 : ADD R1 <- R2+R3

I4 : STORE Memory [R4] <- [R1]

BRANCH to Label if R1== 0

Which of the instructions I1, I2, I3 or I4 can legitimately occupy the delay slot without any other program modification?

I1: ADD R2 <- R7+R8

I2 : SUB R4 <- R5-R6

I3 : ADD R1 <- R2+R3

I4 : STORE Memory [R4] <- [R1]

BRANCH to Label if R1== 0

Which of the instructions I1, I2, I3 or I4 can legitimately occupy the delay slot without any other program modification?

A : I1

B : I2

C : I3

D : I4

.

Correct answer is : D

Question 78

**Let xn denote the number of binary strings of length n that contain noconsecutive 0s. Which of the following recurrences does Xn satisfy?**

A : x

_{n}= 2x

_{n-1}

B : x

_{n}=x

_{floor(n/2)}+1

C : x

_{n}=x

_{floor(n/2)}+n

D : x

_{n}=x

_{n-1}+x

_{n-2}

.

Correct answer is : D

Question 79

**Let xn denote the number of binary strings of length n that contain noconsecutive 0s.The value of X5 is**

A : 5

B : 7

C : 8

D : 16

.

Correct answer is : C

Solution :

Since, X(n) = X(n - 1) + X(n - 2)

X5 = X4 + X3

X4 = X3 + X2 = 5 + 3 = 8

Therefore, X5 = 8 + 5 = 13

Question 80

**The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?**

A : X[i, j] = X[i - 1, j] V X[i, j -ai]

B : X[i, j] = X[i - 1, j] V X[i - 1, j - ai]

C : X[i, j] = X[i - 1, j] V X[i, j - ai]

D : X[i, j] = X[i - 1, j] V X[i -1, j - ai]

.

Correct answer is : B

Solution :

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

Question 81

**The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W? Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?**

A : X[1, W]

B : X[n, 0]

C : X[n, W]

D : X[n-1, n]

.

Correct answer is : C

Solution :

If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.

Question 82

**Consider the following ER diagram. The minimum number of tables needed to represent M, N, P, R1, R2 is**

A : 2

B : 3

C : 4

D : 5

.

Correct answer is : B

Solution :

Answer is B, i.e, 3 minimum tables. M, P are strong entities hence they must be represented by separate tables. Many-to-one and one-to-many relationship sets that are total on the many-side can be represented by adding an extra attribute to the “many” side, containing the primary key of the “one” side. ( This way no extra table will be needed for Relationship sets ) M table is modified to include primary key of P side(i.e. P1). N is weak entity, and is modified to include primary key of P (i.e, P1). Therefore there would be minimum of 3 tables with schema given below : M ( M1, M2, M3, P1) P ( P1, P2 ) N ( P1, N1, N2 ) Note: This modification of a table in the case of one-many or many-one to include relationship set at the many side works well, but only in the case when the relationship set doesn't have its own attributes. If the relationship set has its own attribute then we need to make a separate table for the relationship set also.

Question 83

**Consider the following ER diagram.Which of the following is a correct attribute set for one of the tables for the correct answer to the above question?**

A : {M1, M2, M3, P1}

B : {M1, P1, N1, N2}

C : {M1, P1, N1}

D : {M1, P1}

.

Correct answer is : A

Question 84

**Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.**

1. f(int Y[10], int x) {

2. int i, j, k;

3. i = 0; j = 9;

4. do {

5. k = (i + j) /2;

6. if( Y[k] < x) i = k; else j = k;

7. } while(Y[k] != x && i < j);

8. if(Y[k] == x) printf ("x is in the array ") ;

9. else printf (" x is not in the array ") ;

10. } On which of the following contents of Y and x does the program fail?

1. f(int Y[10], int x) {

2. int i, j, k;

3. i = 0; j = 9;

4. do {

5. k = (i + j) /2;

6. if( Y[k] < x) i = k; else j = k;

7. } while(Y[k] != x && i < j);

8. if(Y[k] == x) printf ("x is in the array ") ;

9. else printf (" x is not in the array ") ;

10. } On which of the following contents of Y and x does the program fail?

A : Y is [1 2 3 4 5 6 7 8 9 10] and x < 10

B : Y is [1 3 5 7 9 11 13 15 17 19] and x < 1

C : Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

D : Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

.

Correct answer is : C

Solution :

(C) The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

Question 85

**Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.**

1. f(int Y[10], int x) {

2. int i, j, k;

3. i = 0; j = 9;

4. do {

5. k = (i + j) /2;

6. if( Y[k] < x) i = k; else j = k;

7. } while(Y[k] != x && i < j);

8. if(Y[k] == x) printf ("x is in the array ") ;

9. else printf (" x is not in the array ") ;

10. }

the correction needed in the program to make it work properly is

1. f(int Y[10], int x) {

2. int i, j, k;

3. i = 0; j = 9;

4. do {

5. k = (i + j) /2;

6. if( Y[k] < x) i = k; else j = k;

7. } while(Y[k] != x && i < j);

8. if(Y[k] == x) printf ("x is in the array ") ;

9. else printf (" x is not in the array ") ;

10. }

the correction needed in the program to make it work properly is

A : Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;

B : Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;

C : Change line 6 to: if (Y[k] <= x) i = k; else j = k;

D : Change line 7 to: } while ((Y[k] == x) && (i < j));

.

Correct answer is : A

Solution :

Below is the corrected function

f(int Y[10], int x) { int i, j, k; i = 0; j = 9; do { k = (i + j) /2; if( Y[k] < x) i = k + 1; else j = k – 1; } while(Y[k] != x && i < j); if(Y[k] == x) printf ('x is in the array '); else printf ('x is not in the array ') ; }

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