Data Structures and Algorithms | Set 3

Last Updated : 03 Feb, 2023

Following questions have asked in GATE CS exam.

1. Suppose you are given an array s[1…n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence

do, where 1 < k <= n:
  reverse (s, 1, k);
  reverse (s, k + 1, n);
  reverse (s, 1, n);

(GATE CS 2000)

(a) Rotates s left by k positions

(b) Leaves s unchanged

(d) None of the above

Answer: (a) Effect of the above 3 reversals for any k is equivalent to left rotation of the array of size n by k. Please see this post for details. If we rotate an array n times for k = 1 to n, we get the same array back.

2. The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004)

a) queue

b) stack

c) tree

d) list

Answer(b) There are three types of parentheses [ ] { } (). Below is an arbitrary c code segment which has parentheses of all three types.

c

void func(int c, int a[])
{
   return  ((c +2)  + arr[(c-2)]) ; 
}

Stack is a straightforward choice for checking if left and right parentheses are balanced. Here is a algorithm to do the same.

c

/*Return 1 if expression has balanced parentheses */
bool areParenthesesBalanced(expression )
{ 
   for each character in expression
   {
      if(character == ’(’ || character == ’{’ || character == ’[’) 
        push(stack, character);
      if(character == ’)’ || character == ’}’ || character == ’]’) 
      {
         if(isEmpty(stack))  
           return 0; /*We are seeing a right parenthesis  
                       without a left pair*/
 
         /* Pop the top element from stack, if it is not a pair
             bracket of character then there is a mismatch. 
             This will happen for expressions like {(}) */
         else if (! isMatchingPair(pop(stack), character) ) 
           return 0;   
      }
   }
   
   if(isEmpty(stack))
     return 1; /*balanced*/
   else 
     return 0;  /*not balanced*/  
} /* End of function to check parentheses */
 
/* Returns 1 if character1 and character2 are matching left
   and right parentheses */
bool isMatchingPair(character1, character2)
{
   if(character1 == ‘(‘ && character2 == ‘)’)
     return 1;
   else If(character1 == ‘{‘ && character2 == ‘}’)
     return 1;
   else If(character1 == ‘[‘ && character2 == ‘]’)
     return 1;
   else
     return 0;
}

3. Level order traversal of a rooted tree can be done by starting from the root and performing (GATE CS 2004)

a) preorder traversal

b) in-order traversal

c) depth first search

d) breadth first search

Answer(d) See this post for details

4. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i. 9679, 1989, 4199 hash to the same value ii. 1471, 6171 has to the same value iii. All elements hash to the same value iv. Each element hashes to a different value (GATE CS 2004)

a) i only

b) ii only

c) i and ii only

d) iii or iv

Answer (c)

5. Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? (GATE CS 2005)

a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Answer (a) Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.