create stack
push A on to stack
push F on to stack
push X on to stack
pop item from stack
push B on to stack
pop item from stack
pop item from stack.
Solution:
Stack
create stack --> Empty stack
push A on to stack --> A
push F on to stack --> FA
push X on to stack --> XFA
pop item from stack --> FA
push B on to stack --> BFA
pop item from stack --> FA
pop item from stack. --> A
Finally the stack contains A only
Problem 2: Show the state of the stack and the value of each variable after execution of
each of the following statements:
A = 5 B = 3 C = 7
(a) create stack
push A onto stack
push C*C onto stack
pop item from stack and store in B
push B+A onto stack
pop item from stack and store in A
pop item from stack and store in B
(b) create stack
push B onto stack
push C onto stack
push A onto stack
A = B * C
push A+C onto stack
pop item from stack and store in A
pop item from stack and store in B
pop item from stack and store in C
Solution for a:
operation Stack
create stack Empty stack
push A onto stack Push 5 5
push C*C onto stack push 7*7 49 5
pop item from stack and store in B pop 49& B=49 5
push B+A onto stack push 54 54 5
pop item from stack and store in A pop 54& A=54 5
pop item from stack and store in B pop 5 & B=5 Empty stack
Now A=54,B=5 and C=7
Solution for b:
Stack
create stack Empty stack
push B onto stack 3
push C onto stack 7 3
push A onto stack 5 7 3
A = B * C-->A=21
push A+C onto stack -->21+7->28 28 5 7 3
pop item from stack and store in A->A=28 5 7 3
pop item from stack and store in B->B=5 7 3
pop item from stack and store in C->C=7 3
Now A=28,B=5 and C=7
Problem 3:A function f defined on stacks of integers satisfies the following properties. f(∅)= 0 and f(push(S,i))=max(f(S),0)+ i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
(a) 6
(b) 4
(c) 3
(d) 2
Solution:
Initially stack is empty. S->{}. so f(S)=0
Push 2 in to stack S.
f(push(S,2)=f(push({},2)=max(f(S),0)+2=max(0,0)+2=0+2=2
now S->{2} and f(S)=2
push -3 in to Stack S
f(push({2},-3))=max(f(S),0)+(-3)=max(2,0)+(-3)=2-3=-1
now S->{2,-3} and f(s)=-1
push 2 in to stack S
f(push({2,-3},2)=max(-1,0)+2=0+2=2
now S->{2,-3,2} and f(S)=2
push -1 in to stack S
f(push({2,-3,2},-1))=max(2,0)+(-1)=2-1=1
now S->{2,-3,2,-1} and f(S)=1
push 2 in to stack S
f(push({2,-3,2,-1},2))=max(1,0)+2=1+2=3
now S->{2,-3,2,-1,2} and f(S)=3
so finally f(S)=3
Problem 4:Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order on to the stack; the pop operations print out the return value. Which of the following sequences could not occur?
(a) 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7 5 3 2 9 0 1
(c) 2 5 6 7 4 8 9 3 1 0
(d) 4 3 2 1 0 5 6 7 8 9
(e) 1 2 3 4 5 6 9 8 7 0
(f) 0 4 6 5 3 8 1 7 2 9
(g) 1 4 7 9 8 6 5 3 0 2
(h) 2 1 4 3 6 5 8 7 9 0
Solution
Sequence b,f,g couldn't occur
Problem 5:
Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is (GATE CS 2003)
a) n(X+ Y)
b) 3Y + 2X
c) n(X + Y)-X
d) Y + 2X
Solution
Answer is n(X+Y)-X
Problem 6:
The following sequence of operation is performed on a stack push(1),push(2),pop,push(1),push(2),pop,pop,pop,push(2),pop. The sequences of popped out values are
- 2,2,1,2,1
- 2,2,1,1,2
- 2,1,2,2,1
- 2,1,2,2,2
Answer is (2) 2,2,1,1,2
No comments:
Post a Comment