Page 542 - Computer science 868 Class 12
P. 542

8.  When the order in which the nodes are visited is Left, Root, Right, it is ………………… traversal.
                  9.  The post fix notation of  x ∧ y % z is  ………………… .
                 10.  Prefix notation is also called ………………… notation.

                 Answers
                   1.  Linear         2.   push           3.   dynamically        4.  parent           5.   N-1
                   6.  forest         7.   1              8.    in order          9.   xy ∧ z %       10.   polish


              C.  Answer the following questions:
                  1.  Differentiate between Stack and Queue.
                Ans.
                                       Stack                                     Queue
                       i.  The working principle is LIFO.         i.  The working principle is FIFO.
                      ii.  Stack has only one end called top.    ii.  Queue has two ends front and rear.

                      iii.  Push and Pop both take place from top.   iii.  Insertion is done from rear end and deletion from
                                                                  front end.
                  2.  Differentiate between Dequeue  and Circular queue.
                Ans.                  Dequeue                                 Circular Queue

                       i.  Insertion and deletion of items is done from both    i.  Insertion is done from rear end and deletion from
                        the ends.                                 front end.
                      ii.  During  insertion  or deletion, the front and  rear   ii.  During  insertion,  the rear  pointer  increases  by
                        pointers increase or decrease by 1.       rear = (rear + 1)% size and during deletion, the
                                                                  front pointer changes by front = (front + 1 ) % size.
                      iii.  It does not follow FIFO principle.   iii.  It follows FIFO principle.

                  3.  Find (a) post fix and (b) pre fix notations of the following infix form (A/B + C) * (D/(E - F)).
                Ans.                                Postfix

                             Symbol               Stack status            Output
                     (                      (
                     A                      (                      A
                     /                      ( /                    A
                     B                      ( /                    A B
                     +                      ( +                    A B /

                     C                      ( +                    A B / C
                     )                      (+)                    AB / C+
                     *                      *                      A B / C+
                     (                      *(                     A B / C+
                     D                      *(                     A B / C+ D
                     /                      *( /                   A B / C+  D
                     (                      *( / (                 A B / C+  D
                     E                      *( / (                 A  B / C+  D E
                     -                      *( / ( -               A B / C+  D  E
                     F                      *( / ( -               A B / C+ D E F
                     )                      *( / ( -)              A B / C+ D E F -

                     )                      *( / )                 A B / C+ D E F - / *


                540540  Touchpad Computer Science-XII
   537   538   539   540   541   542   543   544   545   546   547