1
GATE CSE 2006
+2
-0.6
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(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( \le 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 \le x \le 2n$$ and $$2m \le y \le n + m$$
B
$$n + m \le x \le 2n$$ and $$2m \le y \le 2n$$
C
$$2m \le x \le 2n$$ and $$2m \le y \le n + m$$
D
$$2m \le x \le 2n$$ and $$2m \le y \le 2n$$
2
GATE CSE 2006
+2
-0.6
The following function computes the value of mCn correctly for all legal values m and n (m≥1,n≥0 and m>n)
int func(int m, int n)
{
if (E) return 1;
else return(func(m -1, n) + func(m - 1, n - 1));
} 
In the above function, which of the following is the correct expression for E?
A
(n = = 0) || (m = = 1)
B
(n = = 0) && (m = = 1)
C
(n = = 0) || (m = = n)
D
(n = = 0) && (m = = n)
3
GATE CSE 2004
+2
-0.6
Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. The postfix expression corresponding to the infix expression a + b×c-d^e^f is
A
abc×+def^^-
B
abc×+de^f^-
C
ab+c×d-e^f^
D
- + a×bc^^def
4
GATE CSE 2004
+2
-0.6
A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following a strings CANNOT be generated using this program?
A
abcd
B
dcba
C