Computer Science Engineering - Online Test
Q1. A hash table of length 10 uses open addressing with hash function h(k)=k
mod 10, and linear probing. After inserting 6 values into an empty hash table,
the table is as shown below 
Which one of the following choices gives a possible order in which the key values
could have been inserted in the table?
Answer : Option C
Explaination / Solution:
No Explaination.
Q2. What is the return value of f (p,p) if the value of p is initialized to 5 before the call? Note
that the first parameter is passed by reference, whereas the second parameter is passed by
value.
int f (int & x, int c) {
c = c - 1;
if (c = 0) return 1;
x = x + 1;
return f (x,c)* x;
}
Answer : Option B
Explaination / Solution:
Q3. Consider the following languages over the alphabet ∑= {a, b,c}
Which of the following are context-free languages ?
I. L1 ∪ L2 II. L1 ∩ L2
Answer : Option A
Explaination / Solution:
Q4. A hash table of length 10 uses open addressing with hash function h(k)=k
mod 10, and linear probing. After inserting 6 values into an empty hash table,
the table is as shown below
How many different insertion sequences of the key values using the same hash
function and linear probing will result in the hash table shown above?
Answer : Option B
Explaination / Solution:
No Explaination.
Q5. A certain computation generates two arrays a and b such that a[i] = f(i) for 0 ≤ i < n and b[i] = g(a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent
processes X and Y such that X computes the array a and Y computes the array b. The
processes employ two binary semaphores R and S, both initialized to zero. The array a is
shared by the two processes. The structures of the processes are shown below.
Pr ocess X; Pr ocess Y;
private i; private i;
for(i = 0; i<n; i++){ for(i = 0; i<n; i++){
a[i] = f(i); EntryY(R, S);
ExitX(R, S); b[i] = g(a[i]);
} }
Which one of the following represents the CORRECT implementations of ExitX and
EntryY?
Answer : Option C
Explaination / Solution:
For computing both the array a[] and b[], first element a[i] should be computed using which
b[i] can be computed. So process X and Y should run in strict alteration manner, starting with
X. This requirement meets with implementation of ExitX and EntryY given in option C.
Q6. Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total
functional from A*
to B*
. We say f is computable if there exists a Turning machine M which
given an input x in A*
, always halts with f(x) on its tape. Let Lf denote the language
{x#f(x)|x∈A*}. Which of the following statements is true:
Answer : Option A
Explaination / Solution:
A TM is recursive iff it halts for every input string (either in accept or reject state).
Here, a computable function is defined in a similar way.
Q7. Consider the following function
int unknown (int n) {
int i, j, k 0;
for (i = n/2; i<=n; i++)
for (j = 2; j<=n; j = j*2)
k = k+n/2;
return(k);
}
The return value of the function is
Answer : Option B
Explaination / Solution:
Q8. Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are nonterminals
G1 : S → aSb|T,T → cT|∈
G2 : S → bSa|T,T → cT|∈
The language L(G1) ∩ L(G2) is
Answer : Option B
Explaination / Solution:
The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals
are:
Q9. The number of elements that can be sorted in Θ(logn) time using heap sort is
Answer : Option A
Explaination / Solution:
After constructing a max-heap in the heap sort , the time to extract maximum element and
then heapifying the heap takes Θ(log n) time by which we could say that Θ(log n) time is
required to correctly place an element in sorted array. If Θ(logn) time is taken to sort using
heap sort, then number of elements that can be sorted is constant which is Θ(1)
Q10. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively
enumerable but not recursive. Which of the following statements is not
necessarily true?
Answer : Option B
Explaination / Solution:
No Explaination.
