Programming and Data Structures - Online Test
Q1. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n
elements. Assume that the insertion and deletion operations are carried out using REAR and
FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions
to detect queue full and queue empty are
Answer : Option A
Explaination / Solution:
The counter example for the condition full : REAR = FRONT is
Initially when the Queue is empty REAR=FRONT=0 by which the above full condition is satisfied which is false
The counter example for the condition full : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=3, so after inserting one element REAR=1 and FRONT=0, at this point the condition full above is satisfied, but still there is place for one more element in Queue, so this condition is also false
The counter example for the condition empty : (REAR+1)mod n = FRONT is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
The counter example for the condition empty : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
Q2. Let G be a weighted graph with edge weights greater than one and G’ be the graph
constructed by squaring the weights of edges in G. Let T and T’ be the minimum spanning
trees of G and G’ respectively, with total weights t and t’. Which of the following statements
is TRUE?
Answer : Option D
Explaination / Solution:
Graph G is counter example for options (B) and (C) and Graph G1 is counter example for
option (A)
Q3. Consider the following transactions with data items P and Q initialized to zero:
T1 : read (P) ;
read (Q) ;
if P = 0 then Q : = Q + 1 ;
write (Q).
T2 : read (Q) ;
read (P)
if Q = 0 then P : = P + 1 ;
write (P).
Any non-serial interleaving of T1 and T2 for concurrent execution leads to
Answer : Option B
Explaination / Solution:
Let S be a non-serial schedule, without loss of generality assume that T1 has started earlier
than T2. The first instruction of T1 is read(P) and the last instruction of T2 is write(P), so the
precedence graph for S has an edge from T1 to T2, now since S is a non-serial schedule the
first instruction of T2(read(Q)) should be executed before last instruction of T1(write(Q)) and
since read and write are conflicting operations, the precedence graph for S also contains an
edge from T2 to T1, So we will have a cycle in the precedence graph which implies that any
non serial schedule with T1 as the earliest transaction will not be conflict serializable.
In a similar way we can show that if T2 is the earliest transaction then also the schedule is not
conflict serializable.
Q4. Consider an undirected random graph of eight vertices. The probability that there is an edge
between a pair of vertices is ½. What is the expected number of unordered cycles of length
three?
Answer : Option C
Explaination / Solution:
P(edge) = 1/2
Number of ways we can choose the vertices out of 8 is 
(Three edges in each cycle)
Expected number of unordered cycles of length 3 = 
Q5. Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
Answer : Option C
Explaination / Solution:
Q: Sum of degrees of all vertices = 2 × (number of edges)
Q6.
Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time
algorithm to solve A.
Answer : Option A
Explaination / Solution:
1. Cycle detection using DFS: O(V + E) = O(V2)and it is polynomial problem
2. Every P-problem is NP(since P ⊂ NP)
3. NP-complete ∈ NP
Hence, NP-complete can be solved in non-deterministic polynomial time
Q7. Which one of the following is the tightest upper bound that represents the time complexity of
inserting an object into a binary search tree of n nodes?
Answer : Option C
Explaination / Solution:
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n)
Q8. Which one of the following is the tightest upper bound that represents the number of swaps
required to sort n numbers using selection sort?
Answer : Option B
Explaination / Solution:
No Explaination.
Q9. In the following truth table, V = 1 if and only if the input is valid
What function does the truth table represent?
Answer : Option A
Explaination / Solution:
4 to 2 priority encoder.
Q10.
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter
MultiDequeue (Q) {
m = k
while (Q is not empty) and (m > 0) {
Dequeue (Q)
m = m - 1
}
}
What is the worst case time complexity of a sequence of n queue operations on an initially
empty queue?
Answer : Option A
Explaination / Solution:
No Explaination.
