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 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. |
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∝b|b∝c| aB S → ∝S|b S → ∝b b|ab S ∝ → bd b|b
The above grammar is:
Context free | |
Regular | |
Context sensitive | |
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 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)
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 non-deterministic machine M1 there exists an equivalent deterministic machine M2 recognizing the same language“.
M1 is non-deterministic finite automaton | |
M1 is a non-deterministic PDA | |
M1 is a non-deterministic Turing machine | |
For no machine M1 use the above statement true | |
Both A and C |
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.
Out of syllabus. |
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-R, B-P, C-S, D-Q |
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-S, B-R, C-P, D-Q |
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 Turing-machine recognizable | |
It is a context-sensitive language | |
It is a regular language | |
None of the above | |
B, C and D |
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)
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)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Question 22 |
Which one of the following statements is FALSE?
There exist context-free languages such that all the context-free 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 non-deterministic pushdown automata always accept the same set of languages | |
A finite set of string from one alphabet is always a regular language |
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?
TCP guarantees a minimum communication rate | |
TCP ensures in-order 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
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
P-II, Q-III, R-IV, S-I | |
P-IV, Q-III, R-I, S-II | |
P-III, Q-II, R-IV, S-I | |
P-IV, Q-II, R-I, S-III |
Binary search - T(n/2) + 1
Merge sort - T(n) = 2T(n/2)+ cn
Tower of hanoi - T(n) = 2T(n-1) +1