CBSE Class 12 Computer Science Data Structures Assignment

Short Answer Type Questions :

Question. Convert the following infix expression to its equivalent postfix expression. Showing stack  contents for the conversion
                     (A + B * (C − D)/E)
Answer: Given infix expression is
                     (A + B * (C − D)/E)

Output ABCD −*E/+

Question. Consider the following stack of characters, where STACK is allocated N = 8 memory cells.
                           STACK : A, C, D, F, K, …, …, …
Describe the STACK at the end of the following operations. Here, Pop and Push are algorithms for  deleting and adding an element to the stack.
(i) Pop (STACK, ITEM)      (ii) Pop (STACK, ITEM)
(iii) Push (STACK, L)       (iv) Push (STACK, P)
(v) Pop (STACK, ITEM)    (vi) Push (STACK,R)
(vii) Push (STACK, S)     (viii) Pop (STACK, ITEM)
Answer: The stack contents will be as follows after the operations of stack
(i) STACK : A, C, D, F             (ii) STACK : A, C, D
(K is deleted)                             (F is deleted)
(iii) STACK : A, C, D, L           (iv) STACK: A, C, D, L, P
(L is inserted)                             (P is inserted)
(v) STACK : A, C, D, L            (vi) STACK : A, C, D, L, R
(P is deleted)                               (R is inserted)
(vii) STACK : A, C, D, L, R, S
(S is inserted)
(viii) STACK : A, C, D, L, R
(S is deleted)

Question. Evaluate the following postfix expression using a stack. Show the contents of stack after execution of each operation:
                  10, 40, 25, −, *, 15, 4, *, +
Answer: Given postfix expression is
                  10, 40, 25, −, *, 15, 4, *, +

Output 210

Question. Obtain the postfix notation for the following infix notation of expression showing the contents of the stack and postfix expression formed after each step of conversion:
                 (A * B + (C − D/F))
Answer: Given infix expression is
                 (A * B + (C − D/F))

Output AB*CDF/–+

Question. Evaluate the following postfix notation of expression
                True, False, NOT, AND, True, True, AND, OR
Answer: Given postfix expression is
                True, False, NOT, AND, True, True, AND, OR

Output True

Question. Evaluate the following postfix expression. Show the status of stack after execution of each operation :
              25, 8, 3, −, /, 6, *, 10, +
Answer: Given postfix expression is
              25, 8, 3, −, /, 6, *, 10, +

Output 40

Question. Change the following infix expression into postfix expression :
               ((A + B) * C + D/E − F)
Answer: Given infix expression is
               ((A + B) * C + D/E − F)

Output AB+C*DE/+F–

Question. Evaluate the following postfix notation. Show status of stack after every step of evaluation (i.e. after each operator).
                 True, False, NOT, AND, False, True, OR, AND
Answer: Given postfix expression is
                True, False, NOT, AND, False, True, OR, AND

Output True

Question. Evaluate the following postfix expression. Show the status of stack after execution of each operation :
             20, 10, +, 5, 2, *, −, 10, /
Answer: Given postfix expression is
            20, 10, +, 5, 2, *, −, 10, /

Output 2

Question. Evaluate the following postfix expression using a stack and show the contents of stack after execution of each operation :
                  100, 40, 8, +, 20, 10, −, +, *
Answer: Given postfix expression is
                  100, 40, 8, +, 20, 10, −, +, *

Output 5800

Question. Suppose STACK is allocated 6 memory locations and initially STACK is empty (Top = 0).
Given the output of the program segment.
AAA = 4
BBB = 6
Push (STACK, AAA)
Push (STACK, 4)
Push (STACK, BBB +2)
Push (STACK, AAA + BBB)
Push (STACK, 10)
while (Top>0) :
                Element = STACK. Pop ( )
                print(Element)
Answer: Output
10
10
8
4
4

Question. Evaluate the following postfix expression. Show the status of stack after execution of each operation :
                  10, 20, +, 25, 15, −, *, 30, /
Answer: Given postfix expression is
                  10, 20, +, 25, 15, −, *, 30, /

Output 10

Question. Evaluate the following postfix expression using a stack and show the contents of the stack after execution of each operation :
                      5, 6, 9, +, 80, 5, *, −, /
Answer: Given postfix expression is
                      5, 6, 9, +, 80, 5, *, −, /

Output −1 / 77

Question. What is data structure ? Name any two non-primitive data structures.
Answer: Data structure is a way of storing and organising information in the computer, so that it can be retrieved and used most productively. Two non-primitive data structures are array and linked list. 

Question. Evaluate the following postfix expression. Show the status of stack after execution of each operation.
                  60, 6, /, 5, 2, *, 5, −, +
Answer: Given postfix expression is
                 60, 6, /, 5,2, *, 5, −, +

Output 15

Question. Consider the following sequence of numbers:
1, 2, 3, 4
These are supposed to be operated through a stack to produce the following sequence of numbers:
2, 1, 4, 3
List the Push and Pop operations to get the required output.
Answer: (i) Push (1) (ii) Push (2)
(iii) Pop (2)       (iv) Pop (1)
(v) Push (3)      (vi) Push (4)
(vii) Pop (4)     (viii) Pop (3)

Question. What is the value of the postfix expression?
6 3 2 4 + − *
Answer: Postfix expression is : (6 * (3 − (2 + 4)))
= (6 * (3 − 6))
= (6 * (−3)) = − 18

Question. Evaluate the following postfix expression using stack and show the contents of stack after execution of each expression.
                 120, 45, 20, +, 25, 15, −, +, *
Answer: Given postfix expression is
                 120, 45, 20, +, 25, 15, −, +, *

Output 9000

Question. Write the applications of stack.
Answer: There are some applications of stack are as follows
(i) Infix to postfix conversion using stack.
(ii) Evaluation of postfix expression.
(iii) Reverse a string using stack.
(iv) Implement two stacks in an array.

Question. Use a stack to evaluate the following postfix expression and show the content of the stack after execution of each operation. Do not write any code.  Assume as if you are using Push and Pop member methods of the stack.
                          AB − CD + E * +
(where A = 5, B = 3, C = 5, D = 4 and E = 2)
Answer: Putting the values of the operands, we get the postfix expression as
                        5, 3, −, 5, 4, +, 2, *, +

Output 20

Question. Evaluate the following postfix expression. Show the status of stack after execution of each operation separately.
                    T, F, NOT, AND, T, OR, F, AND
Answer: Given postfix expression is
                    T, F, NOT, AND, T, OR, F, AND

Output F

Question. Evaluate the following postfix expression:
                    20, 10, −, 15, 3, /, +, 5, *
Answer: Given postfix expression is

Output 75

Question. Define any two operations on data structure.
Answer: Two operations on data structure are as follows
(i) Insertion It means addition of a new data element in a data structure.
(ii) Searching It involves searching for the specific data element in a data structure.

Question. Evaluate the following postfix using stack and show the content of the stack after the execution of each.
                 20, 4, +, 3, −, 7, /
Answer: Given postfix expression is
                 20, 4, +, 3, −, 7, /

Output 3

Question. Evaluate the following postfix expression using a stack. Show the contents of stack after execution of each operation.
True, False, True, False, NOT, OR, True, OR, OR, AND
Answer: In the given expression True and False are operands and AND, NOT and OR are operators.

Output True

Long Answer Type Questions :

Question. Find the output of the following code
answer=[]; output=‘’
answer.append(‘T’)
answer.append(‘A’)
answer.append(‘M’)
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
print(‘Result=’,output)
Answer: answer is a blank list and output is a blank string. The three append operatins add T→A→ M into the stack with M at the top. First Pop operation takes out ‘M’ and adds it to ‘ch’ and then ‘output’. Similarly, the subsequent pop operations are popping out ‘A’ and ‘T’ and adding them to output, which is printed as ‘MAT’.
Output Result = MAT

Question. Write the Push operation of stack containing person names. Notice that the name should only accept characters, spaces and period (.) except digits. Assume that Pname is a class instance  attribute.
Answer: 

Question. Change the following infix expression into postfix expression
                    (A + (B*C) −D/ E+C^H
Answer: Given infix expresion is
                   (A + (B*C) −D/ E+C ^H

Output ABC*+DE/− CH^+

Question. Write Push (contents) and Pop (contents) methods in Python to add numbers and remove numbers  considering them to act as Push and Pop operations of stack.
Answer: 

Question. Convert the expression given below from infix to postfix using stack , showing each operation.
                       (A + B/(C * D)-E)
Answer: Given infix expression is
                       (A + B/(C * D)-E)

Output ABCD*/+E−

Question. Explain the different operations possible in a stack.
Answer: The stack provides three major operaions, which are as follows
(i) Push
(ii) Pop
(iii) Traversal
(i) Push Operation Whenever we add any element ‘‘data’’ in the list, then it will be called as ‘Push  operation’ on stack.
Before every Push operation, the value of ‘‘Top’’ is incremented by one and then value is inserted at the  top of the stack.
(ii) Pop Operation Whenever we try to remove elements from the stack, then the operation is called as ‘Pop operation’ on stack.
After every Pop operation, the value of ‘‘Top’’ is decremented by one and then value is deleted from the top of the stack.
(iii) Traversal Operation The traversal operation means traversing through the elements of the stack  starting from the 1st element to the last. It does not involve any modifications to the contents of the  stack.

Question. Evaluate the following postfix expression using stack, showing stack 7 8 2 * 4 / + status after execution of each operation.
Answer: Given postfix expresion is
7 8 2 * 4/+

Output 11

Question. A linear stack called status contains the following information :
(i) Phone number of Employee
(ii) Name of Employee
Write the following methods to perform given operations on the stack status :
(i) Push_element ( ) To Push an object containing Phone number of Employee and Name of Employee into the stack.
(ii) Pop_element ( ) To Pop an object from the stack and to release the memory.
Answer: