Programming and Data Structures - Online Test
Q1. You have an array of n elements. Suppose you implement quick sort by always choosing the
central element of the array as the pivot. Then the tightest upper bound for the worst case
performance is
Answer : Option A
Explaination / Solution:
The Worst case time complexity of quick sort is O(n2). This will happen when the elements
of the input array are already in order (ascending or descending), irrespective of position of
pivot element in array.
Q2. Consider the basic block given below.
a = b + c
c = a + d
d = b + c
e = d - b
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above
basic block respectively are
Answer : Option A
Explaination / Solution:
The given basic block can be rewritten as
From above simplification it is visible that e is same as c and final value of a is same as d. So
the final basic block can be written as follows:
The DAG generated for the above basic block in as
Maximum number of modes and edges in above DAG is (6,6)
Q3. Consider the pseudocode given below. The function Dosomething () takes as argument a
pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling
representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
Struct treeNode
{
Treeptr leftMostchild, rightSibiling;
};
Int Dosomething (treeptr tree)
{
int value =0;
if (tree ! = NULL) {
If (tree -> leftMostchild = = NULL)
else
value = Dosomething (tree->leftMostchild);
value = value + Dosometing (tree->rightsibiling);
}
return (value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value
returned by the function corresponds to the
Answer : Option D
Explaination / Solution:
The key to solving such questions is to understand or detect where/by what condition the
value (or the counter) is getting incremented each time.
Here, that condition is if (tree→leftMostchild == Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current nodeas
called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child,
there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Q4. Consider the C function given below. Assume that the array listA contains n (> 0) elements,
sored in ascending order.
int ProcessArray (int * listA, int x, int n)
{
Int 1, j, k;
i = 0;
j = n – 1;
do {
k = (i + j) /2;
if (x < = listA [k])
j = k – 1;
If (listA [k] < = x)
i = k+1;
}while (1 < = j);
If (listA [k] = = x)
return (k) ;
else
return -1;
}
Which one of the following statements about the function ProcessArray is CORRECT?
Answer : Option B
Explaination / Solution:
By the logic of the algorithm it is clear that it is an attempted implementation of
Binary Search. So option C is clearly eliminated. Let us now check for options A and
D.
A good way to do this is to create small dummy examples (arrays) and implement the
algorithm as it is. One may make any array of choice. Running iterations of the
algorithm would indicate that the loop exits when the x is not present. So option A is
wrong. Also, when x is present, the correct index is indeed returned. D is also wrong.
Correct answer is B. It is a correct implementation of Binary Search.
Q5. Consider the following relational schema:
Employee (empId, empName, empDept)
Customer (custId,custName, salesRepId, rating)
SalesRepId is a foreign key referring to empId of the employee relation. Assume that each
employee makes a sale to at least one customer. What does the following query return?
SELECT empName
FROM employee E
WHERE NOT EXISTS (SELECT custId
FROM customer C
WHERE C. salesRepId = E. empId
AND C. rating < > ‘GOOD’)
Answer : Option D
Explaination / Solution:
The outer query will return the value (names of employees) for a tuple in relation E, only if
inner query for that tuple will return no tuple (usage of NOT EXISTS).
The inner query will run for every tuple of outer query. It selects cust-id for an employee e, if
rating of customer is NOT good. Such an employee should not be selected in the output of
outer query.
So the query will return the names of all those employees whose all customers have GOOD
rating.
Q6. Let R be the relation on the set of positive integers such that a aRb if and only if a and b are
distinct and have a common divisor other than 1. Which one of the following statements
about R is true?
Answer : Option D
Explaination / Solution:
R is not reflexive as each element can‟t be related to itself.
R is symmetric
Let a = 3, b = 6 and c = 10 then 3 and 6 have a common division other than 1
6 and 10 have a common division other than 1
but 3 &10 have no common division other than 1
3R6 and 6R10 but
3R10
R is not transitive
Q7. In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the
following is TRUE?
Answer : Option C
Explaination / Solution:
Optional (A) is not true when CFG contains cycle
Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
Q8. Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT
and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with
the above statement?
Answer : Option A
Explaination / Solution:
Q9. In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of
the following statements is true?
Answer : Option B
Explaination / Solution:
Since, every edge in a tree is bridge
(A) is false
Since, every edge in a complete graph
kn (n ≥ 3) is not a bridge (c) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge „e‟ and a cycle of length „3‟
(D) is false
Since, in a cycle every edge is not a bridge
(B) is true
Q10. Which one of the following assertions concerning code inspection and code walkthrough is
true?
Answer : Option A
Explaination / Solution:
No Explaination.
