## 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 _______.
 A 12 B 13 C 14 D 15
Algorithms       General       GATE 2014(Set-01)
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
 Question 2
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.
 A 148 B 149 C 150 D 151
Algorithms       General       GATE 2014(Set-01)
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;`
`}`
 A maximum possible sum of elements in any sub-array of array E. B maximum element in any sub-array of array E. C sum of the maximum elements in all possible sub-arrays of array E. D the sum of all the elements in the array E.
Data-Structures       General       GATE 2014(Set-01)
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.
 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 ___.
 A 6 B 7 C 8 D 9
Compiler-Design       General       Gate 2014 Set -02
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.
 A 1 and 2 only B 2 and 3 only C 3 and 4 only D 1 and 3 only
Compiler-Design       General       Gate 2014 Set -03
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 (n3) C : O (nm) D : O (n + m)
 A 1→ C, 2 → A, 3 → B, 4 → D B 1→ B, 2 → D, 3 → C, 4 → A C 1→ C, 2 → D, 3 → A, 4 → B D 1→ B, 2 → A, 3 → C, 4 → D
Algorithms       General       Gate 2005-IT
Question 6 Explanation:
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
 Question 7
Which of the following statements is true?
 A ROM is a Read/Write memory B PC points to the last instruction that was executed C Stack works on the principle of LIFO D All instructions affect the flags
Operating-Systems       General       Gate-1995
Question 7 Explanation:
We know that stack works on the principle of LIFO.
 Question 8
The principle of locality justifies the use of
 A interrupts B DMA C Polling D Cache Memory
Computer-Organization       General       Gate-1995
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.
 Question 9

 A Context free B Regular C Context sensitive D LR(k)
Theory-of-Computation       General       Gate-1995
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).
 Question 10

 A I and II B II and III C I and IV D I and III
Algorithms       General       Gate-1995
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.
 Question 11
Which one of the following statements is true?
 A Macro definitions cannot appear within other macro definitions in assembly language programs B Overlaying is used to run a program which is longer than the address space of computer C Virtual memory can be used to accommodate a program which is longer than the address space of a computer D It is not possible to write interrupt service routines in a high level language
Computer-Organization       General       Gate-1994
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

 A Out of syllabus.
Engineering-Mathematics       General       Gate-1994
Question 12 Explanation:
(i) - (b), (ii) - (c), (iii) - (d), (iv) - (a)
 Question 13

 A (i) - (d), (ii) - (a), (iii) - (b), (iv) - (c)
Compiler-Design       General       Gate-1994
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.
 Question 14

 A Out of syllabus.
Computer-Organization       General       Gate-1994
Question 14 Explanation:
(i) - (a), (ii) - (b), (iii) - (d), (iv) - (c)
 Question 15

 A True B False
Database-Management-System       General       Gate-1994
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:
 A text editor B assembler C linker D loader E none of the above
Compiler-Design       General       Gate-1993
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

 A M1 is non-deterministic finite automaton B M1 is a non-deterministic PDA C M1 is a non-deterministic Turing machine D For no machine M1 use the above statement true E Both A and C
Theory-of-Computation       General       Gate-1992
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.
 Question 18

 A Out of syllabus.
Computer-Networks       General       Gate-1991
 Question 19

 A A-R, B-P, C-S, D-Q
Operating-Systems       General       Gate-1991
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.
 Question 20

 A A-S, B-R, C-P, D-Q
Algorithms       General       Gate-1991
 Question 21

 A It could be undecidable B It is Turing-machine recognizable C It is a context-sensitive language D It is a regular language E None of the above F B, C and D
Theory-of-Computation       General       Gate-1991
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.
There are 21 questions to complete.