Information Technology - Online Test
Q1. A subsequence of a given sequence is just the given sequence with some elements (possibly none or
all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of
X and Y starting from 0.
The values of l(i, j) could be obtained by dynamic programming based on the correct recursive
definition of l(i, j) of the form given above, using an array L[M, N], where M = m + 1 and N = n + 1,
such that L[i, j] = l(i, j).
Which of the following statements would be TRUE regarding the dynamic programming solution for
the recursive definition of l(i, j)?
Answer : Option B
Explaination / Solution:
No Explaination.
Q2. An algorithm to find the length of the longest monotonically increasing sequence
of numbers in an array A[0 : n - 1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting
at index i in the array
Initialize Ln-1 =1
For all i such that 0 ≤ i ≤ n − 2
Finally the length of the longest monotonically increasing sequence is max (L0, L1,....,Ln-1). Which of the following statements is TRUE?
Answer : Option A
Explaination / Solution:
No Explaination.
Q3. Consider a relational table r with sufficient number of records, having attributes
A1, A2,…, An and let 1 ≤ p ≤ n. Two queries Q1 and Q2 are given below.
The database can be configured to do ordered indexing on Ap or hashing on Ap.
Which of the following statements is TRUE?
Answer : Option C
Explaination / Solution:
No Explaination.
Q4. An 8KB direct mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor generates 32-bit addresses. The cache controller maintains the tag information for each cache block comprising of the following.
1 Valid bit
1 Modified bit
As many bits as the minimum needed to identify the memory block mapped in the cache.
What is the total size of memory needed at the cache controller to store metadata (tags) for the cache?
Answer : Option D
Explaination / Solution:
Required answer =256 × (19 + 2) = 5376 bits
Q5. Consider the following recursive C function that takes two arguments
unsigned int foo unsigned int n, unsigned int r {
if (n > 0) return (n%r) + foo (n / r, r ));
else return 0;
}
What is the return value of the function foo when it is called as foo (345, 10) ?
Answer : Option B
Explaination / Solution:
Q6. Consider the following circuit involving three D-type flip-flops used in a certain
type of counter configuration.
If all the flip-flops were reset to 0 at power on, what is the total number of
distinct outputs (states) represented by PQR generated by the counter?
Answer : Option C
Explaination / Solution:
So Total number of distinct outputs is 4
Q7. Consider a source computer (S) transmitting a file of size 106 bits to a destination computer
(D) over a network of two routers (R1 and R2) and three links (L1, L2, and L3). L1 connects S
to R1; L2 connects R1 to R2; and L3 connects R2 to D. Let each link be of length 100km.
Assume signals travel over each line at a speed of 108 meters per second. Assume that the
link bandwidth on each link is 1Mbps. Let the file be broken down into 1000 packets each of
size 1000 bits. Find the total sum of transmission and propagation delays in transmitting the
file from S to D?
Answer : Option A
Explaination / Solution:
No Explaination.
Q8. Let G=(V, E) be a graph. Define 
where id is the number of
vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T), then
where id is the number of
vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T), then
Answer : Option D
Explaination / Solution:
No Explaination.
Q9. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The
time taken for a single refresh operation is 100 nanoseconds. The time required
to perform one refresh operation on all the cells in the memory unit is
Answer : Option B
Explaination / Solution:
No Explaination.
Q10. Let P be a regular language and Q be a context free language such that Q ⊆ P.
(For example, let P be the language represented by the regular expression p*q*
and Q be {pn qn | n ∈ N}). Then which of the following is ALWAYS regular?
Answer : Option C
Explaination / Solution:
Σ* − P is the complement of P so it is always regular,
since regular languages are closed under complementation
