## General

Question 1 |

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______.

12 | |

13 | |

14 | |

15 |

Question 1 Explanation:

Bags: 1 2 3 4 5

No. of coins picked: 1 2 4 8 16

There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.

Let there be x number of 10gm coins and y number of 11gm coins.

So, 10x + 11y = 323 ------ (1)

And we also know that total number of coins picked is

1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,

= 31 ------ (2)

Solving equation (1) and (2), we get

y = 13

Means total there are 13 coins of 11gm.

Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.

So product of labelled bag number = 1×3×4 = 12

No. of coins picked: 1 2 4 8 16

There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.

Let there be x number of 10gm coins and y number of 11gm coins.

So, 10x + 11y = 323 ------ (1)

And we also know that total number of coins picked is

1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,

= 31 ------ (2)

Solving equation (1) and (2), we get

y = 13

Means total there are 13 coins of 11gm.

Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.

So product of labelled bag number = 1×3×4 = 12

Question 2 |

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

148 | |

149 | |

150 | |

151 |

Question 2 Explanation:

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is 3n/2 – 2 = 148. (∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)

Question 3 |

Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the

`int`

`MyX(`

`int`

`*E, unsigned `

`int`

`size)`

`{`

` `

`int`

`Y = 0;`

` `

`int`

`Z;`

` `

`int`

`i, j, k;`

` `

`for`

`(i = 0; i < size; i++)`

` `

`Y = Y + E[i];`

` `

`for`

`(i = 0; i < size; i++)`

` `

`for`

`(j = i; j < size; j++)`

` `

`{`

` `

`Z = 0;`

` `

`for`

`(k = i; k <= j; k++)`

` `

`Z = Z + E[k];`

` `

`if`

`(Z > Y)`

` `

`Y = Z;`

` `

`}`

` `

`return`

`Y;`

`}`

maximum possible sum of elements in any sub-array of array E. | |

maximum element in any sub-array of array E. | |

sum of the maximum elements in all possible sub-arrays of array E. | |

the sum of all the elements in the array E. |

Question 3 Explanation:

Y=0

for (i=0; i
Y=Y+E[i] // E is an array, this statement calculates the sum of elements of the array E and stores it in Y.

for (i=0; i
for(j=i; j
{

Z=0;

for(k=i; k<=j; k++)

Z=Z+E[k];

// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].

Store the current sum in Z.

If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.

for (i=0; i

for (i=0; i

Z=0;

for(k=i; k<=j; k++)

Z=Z+E[k];

// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].

Store the current sum in Z.

If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.

Question 4 |

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.

6 | |

7 | |

8 | |

9 |

Question 4 Explanation:

Question 5 |

Which of the following statements are CORRECT?
1)Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2)Automatic garbage collection is essential to implement recursion.
3)Dynamic allocation of activation records is essential to implement recursion.
4)Both heap and stack are essential to implement recursion.

1 and 2 only | |

2 and 3 only | |

3 and 4 only | |

1 and 3 only |

Question 5 Explanation:

The statement, static allocation of all data areas by a compiler makes it impossible to implement recursion is true, as recursion requires memory allocation at run time, so it requires dynamic allocation of memory. Hence, Dynamic allocation of activation records is essential to implement recursion is also a true statement.

Question 6 |

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

1. Bellman-Ford algorithm 2. Kruskal’s algorithm 3. Floyd-Warshall algorithm 4. Topological sorting | A : O ( m log n)
B : O (n^{3})
C : O (nm)
D : O (n + m) |

1→ C, 2 → A, 3 → B, 4 → D | |

1→ B, 2 → D, 3 → C, 4 → A | |

1→ C, 2 → D, 3 → A, 4 → B | |

1→ B, 2 → A, 3 → C, 4 → D |

Question 6 Explanation:

Bellman-ford algorithm → O(nm)

Krushkal's algorithm → O(m log n)

Floyd-Warshall algorithm → O(n

Topological sorting → O(n+m)

Krushkal's algorithm → O(m log n)

Floyd-Warshall algorithm → O(n

^{3})Topological sorting → O(n+m)

Question 7 |

Which of the following statements is true?

ROM is a Read/Write memory | |

PC points to the last instruction that was executed | |

Stack works on the principle of LIFO | |

All instructions affect the flags |

Question 7 Explanation:

We know that stack works on the principle of LIFO.

Question 8 |

The principle of locality justifies the use of

interrupts | |

DMA | |

Polling | |

Cache Memory |

Question 8 Explanation:

The locality of reference is also known as principle of locality.

→ The things which are used more frequently those are stored in locality of reference.

→ For this purpose we use the cache memory.

→ The things which are used more frequently those are stored in locality of reference.

→ For this purpose we use the cache memory.

Question 9 |

Context free | |

Regular | |

Context sensitive | |

LR(k) |

Question 9 Explanation:

S ∝→ [violates context free]

Because LHS must be single non-terminal symbol.

S ∝→ b [violates CSG]

→ Length of RHS production must be atleast same as that of LHS.

Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.

Ex: [A → αβa]

A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).

So, answer is (D) i.e., LR(k).

Because LHS must be single non-terminal symbol.

S ∝→ b [violates CSG]

→ Length of RHS production must be atleast same as that of LHS.

Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.

Ex: [A → αβa]

A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).

So, answer is (D) i.e., LR(k).

Question 10 |

I and II | |

II and III | |

I and IV | |

I and III |

Question 10 Explanation:

Binary search using linked list is not efficient as it will not give O(log n), because we will not be able to find the mid in constant time. Fnding mid in linked list takes O(n) time.

Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind ietrative one in terms of performance.

Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind ietrative one in terms of performance.

Question 11 |

Which one of the following statements is true?

Macro definitions cannot appear within other macro definitions in assembly language programs | |

Overlaying is used to run a program which is longer than the address space of computer | |

Virtual memory can be used to accommodate a program which is longer than the address space of a computer | |

It is not possible to write interrupt service routines in a high level language |

Question 11 Explanation:

A macro body can also have further macro definitions. However, these nested macro definitions aren't valid until the enclosing macro has been expanded. That means enclosing macro must have been called before the macros can be called.

Question 12 |

Out of syllabus. |

Question 12 Explanation:

(i) - (b), (ii) - (c), (iii) - (d), (iv) - (a)

Question 13 |

(i) - (d), (ii) - (a), (iii) - (b), (iv) - (c) |

Question 13 Explanation:

Backus Normal Form (BNF) is a notation technique for context free grammars, often used to describe the syntax of languages used in computing.

Yacc (Yet Another Compiler- Compiler) is a computer program for the UNIXoperating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.

Yacc (Yet Another Compiler- Compiler) is a computer program for the UNIXoperating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.

Question 14 |

Out of syllabus. |

Question 14 Explanation:

(i) - (a), (ii) - (b), (iii) - (d), (iv) - (c)

Question 15 |

True | |

False |

Question 15 Explanation:

Logical data independence is more difficult to achieve than physical data independence, since application programs are heavily dependent on the logical structure of the data that they access.

Question 16 |

A part of the system software, which under all circumstances must reside in the main memory, is:

text editor | |

assembler | |

linker | |

loader
| |

none of the above |

Question 16 Explanation:

In a program the loader that can loads the object of the program from secondary memory into the main memory to execute the corresponding program. Then the loader is to be resides in the main memory.

Question 17 |

M _{1} is non-deterministic finite automaton | |

M _{1} is a non-deterministic PDA | |

M _{1} is a non-deterministic Turing machine | |

For no machine M _{1} use the above statement true | |

Both A and C |

Question 17 Explanation:

For every NFA there exists a DFA.

For every NPDA there does not exist a deterministic PDA.

Every non-deterministic TM has an equivalent deterministic TM.

For every NPDA there does not exist a deterministic PDA.

Every non-deterministic TM has an equivalent deterministic TM.

Question 19 |

A-R, B-P, C-S, D-Q |

Question 19 Explanation:

A-R

B-P

C-S

D-Q

Buddy system: The buddy system is a technique to allocate the memory by dividing the memory into partitions to try to satisfy a memory request as suitably as possible.

Interpretation: Runtime.

Pointer type: Garbage collector dereference the dangling pointer.

Virtual memory: Segmentation.

B-P

C-S

D-Q

Buddy system: The buddy system is a technique to allocate the memory by dividing the memory into partitions to try to satisfy a memory request as suitably as possible.

Interpretation: Runtime.

Pointer type: Garbage collector dereference the dangling pointer.

Virtual memory: Segmentation.

Question 21 |

It could be undecidable | |

It is Turing-machine recognizable | |

It is a context-sensitive language | |

It is a regular language | |

None of the above | |

B, C and D |

Question 21 Explanation:

(B), (C) and (D) are true. But the strongest answer would be (D), a regular language. Because every finite language is a regular language.

And, regular language ⊂ context-free ⊂ context-sensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.

And, regular language ⊂ context-free ⊂ context-sensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.

There are 21 questions to complete.