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
(c) Reverses all elements of s
(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
bool areParenthesesBalanced(expression )
{
for each character in expression
{
if(character == ’(’ || character == ’{’ || character == ’[’)
push(stack, character);
if(character == ’)’ || character == ’}’ || character == ’]’)
{
if(isEmpty(stack))
return 0;
else if (! isMatchingPair(pop(stack), character) )
return 0;
}
}
if(isEmpty(stack))
return 1;
else
return 0;
}
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.