## General

 Question 1

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-1]
Question 1 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 2

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-1]
Question 2 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 3

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-2]
Question 3 Explanation:  Question 4

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-3]
Question 4 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 5

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed

```void find_and_replace(char *A, char *oldc, char *newc) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}```

The procedure is tested with the following four test cases

```(1) oldc = "abc", newc = "dab" (2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda" (4) oldc = "abc", newc = "bac" ```

The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

 A Only one B Only two C Only three D All four
Computer-Organization       General       GATE 2013
Question 5 Explanation:
void find_and_replace (char *A, char *oldc, char *newc)
{
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] = = oldc[j])
A[i] = newc[j];
}
The procedure is tested with the following four test cases.
1. oldc = “abc”, newc = ”dab”
2. oldc = “cde”, newc = ”bcd”
3. oldc = “bca”, newc = ”cda”
4. oldc = “abc”, newc = ”bac”
Given input string of length 5 consisting of a, b, c, d, e, duplicates allowed. Similarly for (4), we done 2 replacements for A with element newc & newc.
Updating the newc value with another newc value is called as a flaw here. Hence 2 flaws.
 Question 6

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 6 Explanation:
We know that stack works on the principle of LIFO.
 Question 7

The principle of locality justifies the use of

 A interrupts B DMA C Polling D Cache Memory
Computer-Organization       General       GATE 1995
Question 7 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 8

Consider a grammar with the following productions

```S → a∝b|b∝c| aB
S → ∝S|b
S → ∝b b|ab
S ∝ → bd b|b ```

The above grammar is:

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

Which of the following statements is true?

I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is O(n2)
 A I and II B II and III C I and IV D I and III
Algorithms       General       GATE 1995
Question 9 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. Finding 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 iterative one in terms of performance.
 Question 10

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 10 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 11

Match the following items A (i) - (b), (ii) - (c), (iii) - (d), (iv) - (a)
Engineering-Mathematics       General       GATE 1994
Question 11 Explanation:
Note: Out of syllabus.
 Question 12

Match the following items A (i) - (d), (ii) - (a), (iii) - (b), (iv) - (c)
Compiler-Design       General       GATE 1994
Question 12 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 UNIX operating 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 13

Match the following items A (i) - (a), (ii) - (b), (iii) - (d), (iv) - (c)
Computer-Organization       General       GATE 1994
Question 13 Explanation:
Note: Out of syllabus.
 Question 14

State True or False with reason
Logical data independence is easier to achieve than physical data independence

 A True B False
Database-Management-System       General       GATE 1994
Question 14 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 15

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 15 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 16

In which of the cases stated below is the following statement true?

` “For every non-deterministic machine M1 there exists an equivalent deterministic machine M2 recognizing the same language“.  `
 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 16 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 17

Match the pairs in the following questions by writing the corresponding letters only.

```(A) IEEE 488    (P) specifies the interface for connecting a single device
(B) IEEE 796    (Q) specifies the bus standard for connecting a computer to
other devices including CPU’s
(C) IEEE 696    (R) specifies the standard for an instrumentation bus
(D) RS232-C     (S) specifies the bus standard for the “backplane” bus called
multibus.
```
 A Out of syllabus.
Computer-Networks       General       GATE 1991
 Question 18

Match the pairs in the following questions by writing the corresponding letters only.

```(A) Buddy system     (P) Run-time type specification
(B) Interpretation   (Q) Segmentation
(C) Pointer type     (R) Memory allocation
(D) Virtual memory   (S) Garbage collection```
 A A-R, B-P, C-S, D-Q
Operating-Systems       General       GATE 1991
Question 18 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 19

Match the pairs in the following questions by writing the corresponding letters only.

```(A) The number distinct binary trees with n nodes       (P) n!/2
(B) The number of binary strings of length of 2n        (Q) (3n/n)
with an equal number of 0’s and 1’s
(C) The number of even permutations of n objects        (R) (2n/n)
(D) The number of binary strings of length 6m which     (S) 1/n+1(2n/n)
are palindromes with 2n 0’s.```
 A A-S, B-R, C-P, D-Q
Algorithms       General       GATE 1991
 Question 20

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which one of the following is the strongest correct statement about a finite language over some finite alphabet ∑?

 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 20 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.
 Question 21

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       A: O ( m log n)
2. Kruskal’s algorithm          B: O (n3)
3. Floyd-Warshall algorithm     C: O (nm)
4. Topological sorting	        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 21 Explanation:
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
 Question 22

Which one of the following statements is FALSE?

 A There exist context-free languages such that all the context-free grammars generating them are ambiguous B An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it C Both deterministic and non-deterministic pushdown automata always accept the same set of languages D A finite set of string from one alphabet is always a regular language
Theory-of-Computation       General       GATE 2004-IT
Question 22 Explanation:
Deterministic automata can be able to recognize all the deterministic context-free languages.
But non-deterministic ones can recognize all context-free languages.
So, option C is false.
 Question 23

Which one of the following statements is FALSE?

 A TCP guarantees a minimum communication rate B TCP ensures in-order delivery C TCP reacts to congestion by reducing sender window size D TCP employs retransmission to compensate for packet loss
Computer-Networks       General       GATE 2004-IT
Question 23 Explanation:
Option B:
Sequence numbers can allow receivers to discard duplicate packets and properly sequence reordered packets.
Option C:
If the congestion is deleted, the transmitter decreases the transmission rate by a multiplicative factor.
Option D:
Acknowledgement allows the sender to determine when to retransmit lost packets.
 Question 24

Which one of the following statements is FALSE?

 A HTTP runs over TCP B HTTP describes the structure of web pages C HTTP allows information to be stored in a URL D HTTP can be used to test the validity of a hypertext link
Computer-Networks       General       GATE 2004-IT
Question 24 Explanation:
Note: Out of syllabus.
 Question 25

A serial transmission T1 uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for each character. A synchronous transmission T2 uses 3 eight bit sync characters followed by 30 eight bit information characters. If the bit rate is 1200 bits/second in both cases, what are the transfer rates of T1 and T2?

 A 100 characters/sec, 153 characters/sec B 80 characters/sec, 136 characters/sec C 100 characters/sec, 136 characters/sec D 80 characters/sec, 153 characters/sec
Computer-Networks       General       GATE 2004-IT
Question 25 Explanation:
T1: 1 char = (8 + 2 + 1 + 1) = 12 bits
Transfer rate = 1200/12 = 100 char/sec
T2: Transfer character in bits = 24 + 240 = 264 bits
In 264 = 30 characters
Then in 1200 = ? 264/30 = 1200/x
x = 136.3 char/sec
So, correct option is (C).
 Question 26

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

```RECURSIVE ALGORITHM		  RECURRENCE RELATION
P. Binary search	      I. T(n) = T(n-k) + T(k) + cn
Q. Merge sort	             II. T(n) = 2T(n-1) + 1
R. Quick sort	            III. T(n) = 2T(n/2) + cn
S. Tower of Hanoi	     IV. T(n) = T(n/2) + 1 ```
 A P-II, Q-III, R-IV, S-I B P-IV, Q-III, R-I, S-II C P-III, Q-II, R-IV, S-I D P-IV, Q-II, R-I, S-III
Algorithms       General       GATE 2004-IT
Question 26 Explanation:
Quick sort - T(n) = T(n-k) + T(k) + cn
Binary search - T(n/2) + 1
Merge sort - T(n) = 2T(n/2)+ cn
Tower of hanoi - T(n) = 2T(n-1) +1
There are 26 questions to complete.