DS TEST-3 SHORT ANSWER

QUESTIONS AND ANSWERS:

Q1.What is stack? Explain the algorithm of push() and pop() operation.

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top.

Algorithm of push() and pop() operations:

Push operation

 Algorithm to push an item into stack.
            
    1) IF TOP = MAX   then
    Print “Stack is full”;
    Exit;
    2) Otherwise
    TOP: = TOP + 1;        /*increment TOP*/
    STACK (TOP):= ITEM;
    3) End of IF
    4) Exit

Pop operation

Algorithm to pop an element from stack.

    1) IF TOP = 0 then
        Print “Stack is empty”;
        Exit;
    2) Otherwise
        ITEM: =STACK (TOP);
        TOP:=TOP – 1;
    3) End of IF
    4) Exit

Q2.Define recursion and types of recursion?

Recursion is the process which comes into existence when a function calls a copy of itself to work on a smaller problem. Any function which calls itself is called recursive function, and such function calls are called recursive calls.

Example, sorting, searching, and traversal problem.

Types of recursion:

linear recursion

Tail recursion

Binary recursion

Exponential recursion.

Nested Recursion.

Mutual Recursion.

Q3.Explain tower of hanoi rules and write program.

Tower of Hanoi consists of three pegs or towers with n disks placed one over the other. The objective of the puzzle is to move the stack to another peg following these simple rules. Only one disk can be moved at a time. No disk can be placed on top of the smaller disk.

program:

#include<stdio.h>
#include<conio.h>
int main ()
{
clrscr();
int n;
printf("Enter number of disks required: \n");
scanf ("%d",  &n);
TOH (n, 'A', 'B',' C');
getch();
return 0;
}
void TOH (int n, char src, char spare, char dest)
{
if (n==1)
printf("Move from %c to %c \n", src, dest);

else
{
TOH(n-1, src, dest, spare) ;
TOH(1, src, spare, dest);
TOH(n-1, spare, src, dest);
}
}


Copy

Q4.Algorithm of postfix evaluation: 231*+ 9-

Let the given expression be “2 3 1 * + 9 -“. 

We scan all elements one by one.

1) Scan ‘2’, it’s a number, so push it to stack. Stack contains ‘2’

2) Scan ‘3’, again a number, push it to stack, stack now contains ‘2 3’ (from bottom to top)

3) Scan ‘1’, again a number, push it to stack, stack now contains ‘2 3 1’

4) Scan ‘*’, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 3*1 which results in 3. We push the result ‘3’ to stack. Stack now becomes ‘2 3’.

5) Scan ‘+’, it’s an operator, pop two operands from stack, apply the + operator on operands, we get 3 + 2 which results in 5. We push the result ‘5’ to stack. Stack now becomes ‘5’.

6) Scan ‘9’, it’s a number, we push it to the stack. Stack now becomes ‘5 9’.

7) Scan ‘-‘, it’s an operator, pop two operands from stack, apply the – operator on operands, we get 5 – 9 which results in -4. We push the result ‘-4’ to stack. Stack now becomes ‘-4’.

8) There are no more elements to scan, we return the top element from stack (which is the only element left in stack).

Q5.Algorithm of infix to post fix conversion:(a+b)x(c-d)+e

"COMING SOON" 

NOTE: all answer are explained so before copying just go with answers once. Ping me for any help or support. 

thankyou:)