Computer Science Engineering - Online Test
Q1. Consider the following routing table at an IP router:
For each IP address in Group I identify the correct choice of the next hop from Group II using
the entries from the routing table above.
Answer : Option A
Explaination / Solution:
No Explaination.
Q2. Consider two relations R1(A,B) with the tuples (1.5), (3,7) and R2 (A,C) = (1,7), (4,9).
Assume that R(A,B,C) is the full natural outer join of R1 and R2 . Consider the following
tuples of the form (A,B,C): a = (1.5,null), b = (1,null,7) c = (3,null,9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9).
Which one of the following statements is correct?
Answer : Option C
Explaination / Solution:
Q3. A graph is self-complementary if it is isomorphic to its complement For all self-complementary
graphs on n vertices, n is
Answer : Option D
Explaination / Solution:
An n vertex self complementary graph has exactly half number of edges of the complete
graph i.e., n(n-1)/4 edges. Since n(n-1) must be divisible by 4 , n must be congruent to 0 or
1 module 4.
Q4. If f(x) = 2x7 + 3x - 5 which of the following is a factor of f(x)?
Answer : Option B
Explaination / Solution:
from the option (b0 substitute x=1 in
2x7 + 3x - 5 = 0
2(1)7 + 3(1) - 5 = 0
5-5 = 0
So (x - 1) is a factor of f (x)
Q5. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are
performed efficiently. Which one of the following statements is CORRECT (n refers to the
number of items in the queue)?
Answer : Option A
Explaination / Solution:
No Explaination.
Q6. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Answer : Option D
Explaination / Solution:
Merge sort θ(n log n) in all the cases
Quick sort θ(n log n) best case and θ(n2) worst cases
Insertion sort θ(n)best case R θ(n2) worst case
Q7. Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
Answer : Option A
Explaination / Solution:
No Explaination.
Q8. The following function computes the maximum value contained in an integer array p[ ] of size
n (n >= 1).
int max(int *p, int n) {
int a=0, b=n-1;
while ( _________ ) {
if (p[a] <= p[b]) { a = a+1; }
else { b = b-1; }
}
return p[a];
}
The missing loop condition is
Answer : Option D
Explaination / Solution:
When a=b then P[a] will have the maximum value of the array
Q9. What will be the output of the following pseudo-code when parameters are passed by
reference and dynamic scoping is assumed?
a=3;
void n(x) {x = x * a; print(x);}
void m(y) {a = 1; a = y - a; n(a); print(a);}
void main() {m(a);}
Answer : Option D
Explaination / Solution:
Dynamic scoping looks for the definition of free variable in the reverse order of calling
sequence.
Q10. An operator delete (i) for a binary heap data structure is to be designed to delete the item in
the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of
the array. If the heap tree has depth d (number of edges on the path from the root to the
farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal
of the element?
Answer : Option B
Explaination / Solution:
Time complexity of heapification is O (height) =O(d)
