Data Structures and Algorithms | Set 17

Last Updated : 27 Mar, 2017

Following questions have been asked in GATE CS 2006 exam.

1. An implementation of a queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x) { 
   push (S1, x); 
} 
  
void delete(Q){ 
   if(stack-empty(S2)) then  
      if(stack-empty(S1)) then { 
          print(“Q is empty”); 
          return; 
      } 
      else while (!(stack-empty(S1))){ 
          x=pop(S1); 
          push(S2,x); 
      } 
   x=pop(S2); 
} 

Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
(A) n+m <= x < 2n and 2m <= y <= n+m (B) n+m <= x < 2n and 2m<= y <= 2n (C) 2m <= x < 2n and 2m <= y <= n+m (D) 2m <= x <2n and 2m <= y <= 2n Answer(A) The order in which insert and delete operations are performed matters here. The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.

The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())

2. Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
(A) (a—b),(d—f),(b—f),(d—c),(d—e)
(B) (a—b),(d—f),(d—c),(b—f),(d—e)
(C) (d—f),(a—b),(d—c),(b—f),(d—e)
(D) (d—f),(a—b),(b—f),(d—e),(d—c)

Answer (D)
The edge (d-e) cannot be considered before (d-c) in Kruskal’s minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.

3. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
(A) Θ(n)
(B) Θ(nlogn)
(C) Θ(n^2)
(D) Θ(n^3)

Answer (B)
If median is always used as pivot, then recursion remains T(n) = 2T(n/2) + cn for all the cases where cn is combined time for median finding and partition. So, worst case time complexity of this quick sort becomes Θ(nlogn). In practical implementations, however, this variant is considerably slower on average (see http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting)

Please write comments if you find any of the answers/explanations incorrect, or you want to share more information about the topics discussed above.