Programming and Data Structures - Online Test
Q1. K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs?
Answer : Option B
Explaination / Solution:
Both K4 and Q3 are planar
Q2. A max-heap is a heap where the value of each parent is greater than or equal to
the value of its children. Which of the following is a max-heap?
Answer : Option B
Explaination / Solution:
Heap is a complete binary tree
Q3. Which of the given options provides the increasing order of asymptotic
complexityoffunctions f1,f2,f3 and f4?
Answer : Option A
Explaination / Solution:
Q4. 
The following is comment written for a C function
/* This function computes the roots of a quadratic equation
a.x^2+b.x+c=0. The function stores two real roots
in *root1 and *root2 and returns the status of validity of
roots. It handles four different kinds of cases.
(i) When coefficient a is zero irrespective of discriminant
(ii) When discriminant is positive
(iii) When discrimanant is zero
(iv) When discrimanant is negative
Only in cases (ii) and (iii), the stored roots are valid.
Otherwise 0 is stored in the roots. the function returns 0 when
the roots are valid and -1 otherwise.
The functin also ensures root1>=root2.
int get_QuadRoots (float a, float b, float c, float *root1, float *root2) ;
*/
A software test engineer is assigned the job of doing black box testing. He comes
up with the following test cases, many of which are redundant.
Which one of the following options provide the set of non-redundant tests using
equivalence class partitioning approach from input perspective for black box
testing?
Answer : Option C
Explaination / Solution:
T1 and T2 checking same condition a = 0 hence, any one of T1 and T2 is
redundant.
T3, T4: in both case discriminant (D)= b2 − 4ac = 0 . Hence any one of it is
redundant.
T5 : D>0
T6 : D<0
Q5. Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of the operator ↑ . Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?
Answer : Option B
Explaination / Solution:
7 ↓ 3 ↑ 4 ↑ 3 ↓ 2
7 ↓ 3 ↑ (4 ↑ 3) ↓ 2 as ↑ is right associative
7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
(7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Q6. We are given a set of n distinct elements and an unlabeled binary tree with n
nodes. In how many ways can we populate the tree with the given set so that it
becomes a binary search tree?
Answer : Option D
Explaination / Solution:
No Explaination.
Q7. Consider evaluating the following expression tree on a machine with load-store
architecture in which memory can be accessed only through load and store
instructions. The variables a, b, c, d and e are initially stored in memory. The
binary operators used in this expression tree can be evaluated by the machine
only when the operands are in registers. The instructions produce result only in a
register. If no intermediate results can be stored in memory, what is the
minimum number of registers needed to evaluate this expression?
Answer : Option D
Explaination / Solution:
Total 3 Registers are required minimum
Q8. An undirected graph G(V,E) contains n ( n > 2 ) nodes named v1, v2,....vn . Two
nodes vi, vj are connected if and only if 0 < |i − j| ≤ 2. Each edge (vi ,vj ) is
assigned a weight i + j. A sample graph with n = 4 is shown below
What will be the cost of the minimum spanning tree (MST) of such a graph with n
nodes?
Answer : Option B
Explaination / Solution:
No Explaination.
Q9. An undirected graph G(V,E) contains n ( n > 2 ) nodes named v1, v2,....vn . Two nodes vi, vj are connected if and only if 0 < |i − j| ≤ 2. Each edge (vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below
The length of the path from v5 to v6 in the MST of previous question with n = 10
is
Answer : Option C
Explaination / Solution:
12 + 8 + 4 + 3 + 6 + 10 = 31
Q10. Consider a network with five nodes, N1 to N5, as shown below
The net work uses a Distance Vector Routing protocol. Once the routes have
stabilized, the distance vectors at different nodes are as following
N1 : (0, 1, 7, 8, 4)
N2 : (1, 0, 6, 7, 3)
N3 : (7, 6, 0, 2, 6)
N4 : (8, 7, 2, 0, 4)
N5 : (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to
nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric
and the cost is identical in both directions. In each round, all nodes exchange
their distance vectors with their respective neighbors. Then all nodes update their
distance vectors. In between two rounds, any change in cost of a link will cause
the two incident nodes to change only that entry in their distance vectors
The cost of link N2-N3 reduces to 2 in (both directions). After the next round of
updates, what will be the new distance vector at node, N3?
Answer : Option A
Explaination / Solution:
