General
Question 1 
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is __________.
148  
149  
150  
151 
(∵ 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; }
maximum possible sum of elements in any subarray of array E.  
maximum element in any subarray of array E.  
sum of the maximum elements in all possible subarrays of array E.  
the sum of all the elements in the 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 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 _______.
6  
7  
8  
9 
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.
1 and 2 only  
2 and 3 only  
3 and 4 only  
1 and 3 only 
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?
Only one  
Only two  
Only three  
All four 
{
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[0] with element newc[0] & newc[1].
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?
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 
The principle of locality justifies the use of
interrupts  
DMA  
Polling  
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 8 
Consider a grammar with the following productions
S → a∝bb∝c aB S → ∝Sb S → ∝b bab S ∝ → bd bb
The above grammar is:
Context free  
Regular  
Context sensitive  
LR(k) 
Because LHS must be single nonterminal 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(n^{2})
I and II  
II and III  
I and IV  
I and III 
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?
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 
Match the following items
(i)  (b), (ii)  (c), (iii)  (d), (iv)  (a) 
Question 12 
Match the following items
(i)  (d), (ii)  (a), (iii)  (b), (iv)  (c) 
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
(i)  (a), (ii)  (b), (iii)  (d), (iv)  (c) 
Question 14 
State True or False with reason
Logical data independence is easier to achieve than physical data independence
True  
False 
Question 15 
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 
In which of the cases stated below is the following statement true?
“For every nondeterministic machine M_{1} there exists an equivalent deterministic machine M_{2} recognizing the same language“.
M_{1} is nondeterministic finite automaton  
M_{1} is a nondeterministic PDA  
M_{1} is a nondeterministic Turing machine  
For no machine M_{1} use the above statement true  
Both A and C 
For every NPDA there does not exist a deterministic PDA.
Every nondeterministic 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) RS232C (S) specifies the bus standard for the “backplane” bus called multibus.
Out of syllabus. 
Question 18 
Match the pairs in the following questions by writing the corresponding letters only.
(A) Buddy system (P) Runtime type specification (B) Interpretation (Q) Segmentation (C) Pointer type (R) Memory allocation (D) Virtual memory (S) Garbage collection
AR, BP, CS, DQ 
BP
CS
DQ
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.
AS, BR, CP, DQ 
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 ∑?
It could be undecidable  
It is Turingmachine recognizable  
It is a contextsensitive language  
It is a regular language  
None of the above  
B, C and D 
And, regular language ⊂ contextfree ⊂ contextsensitive ⊂ 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. BellmanFord algorithm A: O ( m log n) 2. Kruskal’s algorithm B: O (n^{3}) 3. FloydWarshall algorithm C: O (nm) 4. Topological sorting 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 
Krushkal's algorithm → O(m log n)
FloydWarshall algorithm → O(n^{3})
Topological sorting → O(n+m)
Question 22 
Which one of the following statements is FALSE?
There exist contextfree languages such that all the contextfree grammars generating them are ambiguous  
An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it  
Both deterministic and nondeterministic pushdown automata always accept the same set of languages  
A finite set of string from one alphabet is always a regular language 
But nondeterministic ones can recognize all contextfree languages.
So, option C is false.
Question 23 
Which one of the following statements is FALSE?
TCP guarantees a minimum communication rate  
TCP ensures inorder delivery  
TCP reacts to congestion by reducing sender window size  
TCP employs retransmission to compensate for packet loss

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?
HTTP runs over TCP  
HTTP describes the structure of web pages  
HTTP allows information to be stored in a URL  
HTTP can be used to test the validity of a hypertext link 
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?
100 characters/sec, 153 characters/sec  
80 characters/sec, 136 characters/sec  
100 characters/sec, 136 characters/sec  
80 characters/sec, 153 characters/sec 
Transfer rate = 1200/12 = 100 char/sec
T_{2}: 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(nk) + T(k) + cn Q. Merge sort II. T(n) = 2T(n1) + 1 R. Quick sort III. T(n) = 2T(n/2) + cn S. Tower of Hanoi IV. T(n) = T(n/2) + 1
PII, QIII, RIV, SI  
PIV, QIII, RI, SII  
PIII, QII, RIV, SI  
PIV, QII, RI, SIII 
Binary search  T(n/2) + 1
Merge sort  T(n) = 2T(n/2)+ cn
Tower of hanoi  T(n) = 2T(n1) +1