UNIT 7

TOPICS TO BE COVERED IN THIS UNIT:

1. Introduction to data structures
2. Singly linked lists
3. Doubly linked lists
4. Circular list
5. Representing stacks and queues in C using arrays and linked lists
6. Infix to post fix conversion
7. Postfix expression evaluation

Tutorial-1

1. Explain the algorithm to insert a node before a specified node in doubly linked list.


2. For storing the sorted data on which often insert and deletion operations are performed, the following data structure is better
   1. Array
   2. queue
   3. linked-list
   4. doubly linked-list


3. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list could be used?
   1. Singly linked list
   2. Doubly linked list
   3. Circularly doubly linked list
   4. Array implementation of list


4. Which of the following programming languages features require a stack-base allocation
   1. pointer
   2. Block-structure
   3. recursion
   4. dynamic scoping


5. Stacks can not be used to
   1. evaluate an arithmetic expression in postfix form
   2. implement recursion
   3. convert a given arithmetic expression in infix form to is equivalent postfix form
   4. allocates resources (like CPU) by the operating system


6. Declare a queue of integers. Write functions
   1. To insert an element in to queue
   2. To delete an element from queue

Tutorial-2

1. An item that is read as input can be either pushed to a stack or latter popped and printed, or printed directly. Which of the following will be the output if the input is the sequence of items-1,2,3,4,5?
   1. 3,4,5,1,2
   2. 3,4,5,2,1
   3. 1,5,2,3,4
   4. 5,4,3,2


2. Stack is useful for _ _ _ _ _ _ _
   1. radix sort
   2. breadth first search
   3. recursion
   4. quick sort


3. A stack is has the entries a,b,c,(with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of stack B can only be printed. In this arrangement, which of the following permutations a,b,c is not possible?
   1. b a c
   2. b c a
   3. c a b
   4. a b c


4. Write an algorithm to insert an element in the linked list at the following positions:
   1. After a specified element
   2. At the end of a list.


5. Which of the following is essential for converting an infix expression to postfix form efficiently?
   1. An operator stack
   2. An operand stack
   3. An operator stack and an operand stack
   4. A parse tree


6. The postfix equivalent of the prefix * + a b - c d is
   1. ab + cd - *
   2. ab cd + - *
   3. ab + cd * -
   4. ab + - cd *


7. The postfix expression for the infix expression A + B* (C+D) / F + D*E is:
   1. AB + CD + F / D + E*
   2. ABCD + * F / + DE*
   3. A*B + CD / F*DE ++
   4. A+ BCD / F* DE ++


8. A telephone system which places cells to a particular number on hold can best represented by
   1. queue
   2. stack
   3. linked-list
   4. variable

Tutorial-3

1. The infix form of the postfix expression ABC-/D*E+ is
   1. A/B-C*D+E
   2. A-B/C*D+E
   3. (A-B)/C*D+E
   4. A/(B-C)*D+E


2. The equivalent of (a+b^c^d)*(e+f/d) in the post fix notation is
   1. aab+c^d^e &fd/
   2. abcd^+^efd/+*
   3. abcdefd/+*^^+
   4. abcd^^+efd/+*


3. If the sequence of operations push(1),push(2) ,pop, push(1),push(2),pop, pop, pop, push(2),pop,
   are performed on a stack, the sequence of popped out values are
   1. 2,2,1,1,2
   2. 2,2,1,2,2
   3. 2,1,2,2,1
   4. 2,1,2,2,2


4. The disadvantage of the queue is
   1. when the item is deleted, the space for that item is not claimed
   2. when the item is deleted, the space for that item is claimed
   3. a non destructive
   4. increases the memory space


5. As the items from a queue get deleted, the space for item is not reclaimed in queue. This problem is solved by
   1. circular queue
   2. stack
   3. linked list
   4. doubly linked list


6. Queue can be used to implement
   1. radix sort
   2. quick sort
   3. recursion
   4. depth first search


7. A queue of characters currently contained a, b, c, d.
   What would be the contents of queue after the following operation DELETE, ADD W, ADD X, DELETE, ADD Y
   1. A, B, C, W, Y
   2. C, D, W, X, Y
   3. W, Y, X, C, D
   4. A, B, C, D, W


8. Give an algorithm to reverse a singly linked circular list in place.

Beginner problems

1. Imagine we have empty stack S, draw the pictures of each stack after the following operation.
   • push(20);
   • push(40);
   • push(30);
   • push(50);
   • pop( );
   • pop( );


2. Imagine we have empty queue Q, draw the pictures of each queue after the following operation.
   • Q_insert(20);
   • Q_insert(30);
   • Q_insert(50);
   • Q_insert(30);
   • Q_del();
   • Q_del();
   • Q_del();


3. Convert the following infix expressions into postfix expressions.
   1. X-Y+Z*W
   2. X+Y-X/W
   3. A/E*B-H+E/C*G
   4. W+X/T*T*Y/Z


4. What is value of the each of the following postfix expressions after evaluation?
   1. 1 2 4 3 + - *
   2. 1 2 5 4 3 / * + -
   3. 3 4 2 4 / * -
   4. 4 5 8 6 + - *


5. Imagine we have a general list shown in fig-1, show what happen if we apply the following statements to this general list.
   • list1=list1->link;
   • list1=list1->link;


6. Imagine we have a general list shown in fig-1, show what happen if we apply the following statements to this general list.
   • list2=list1;
   • list2->info=30;
   • list2=list2->link;

Intermediate problems

1. What would happen if we execute the following code?

     int main()
   	{
    	      int i,j, arr[5];
    	      for(i=0;i<5;i++)
    	      scanf("%d",&arr[i]);
    	      i=  - - i  -  i++
          	      for(j=i;j<5;j++)
                 printf("%4d",arr[j]);
      	}
    

2. Consider the fig-1, what would happen if we apply the following statements to two lists?

   	 temp=list1;
         	 while(temp->link!=NULL)
             {
               temp=temp->link;
               if(temp->info==40)
               break;
             }
            temp->link=list2;
          

3. Consider the fig-1, what would happen if we apply the following statements to two lists?

         temp= list2;
         while (temp->link!=NULL)
              {
                temp=temp->link;
                if(temp->info==50)
                  {
                    temp->link=list1;
                     break;
                   }
              }
         temp=list2
         while(temp->link!=NULL)
                 {
                      printf("%3d",temp->info);
                       temp=temp->link;
                 }
      

4. Consider the figure -1
   What happens if we apply the following code to two lists?

           temp= list1;
           while (temp->link!=NULL)
                 temp=temp->link;
           temp->link=list2;
   

Advanced problems

1. What would happen if we execute the following code?

       int main()
   	   {
    	     int top=-1, arr[5];
             arr[++top]=20;
   		arr[++top]=40;
   		arr[++top]=60;
   		arr[++top]=80;
             top--;
             top--;
   		while(top>=0)        
               printf("%4d",arr[top--]);
             }           
   

2. What would happen if we execute the following code? 
      int main()
   	{
         		int front=0,rear=0, arr[5];
            	arr[rear++]=20;
   		arr[rear++]=40;
   		arr[rear++]=60;
   		arr[rear++]=80;
             front++;
             while(frontlink=NULL;
                 temp1->info=20;
                 temp=temp1;
                 temp2=(int  *)malloc(sizeof(struct node));
                 temp2->link=NULL;
                 temp2->info=30;
                 temp1->link=temp2;
                 temp3=(in  *)malloc(sizeof(struct node));
                 temp3->link=NULL;
                 temp3->info=40;
                 temp2->link=temp3;
                 while(temp->link!=NULL)
                      {
                          printf("%3d",temp->info);
   		             temp=temp->link;
                        }
              }
   

3. What would happen if the following statements are executed, and draw the picture of each of the operation?
   	struct node 
                {
    	       int info;
                  struct node *link;
                };
            int main()
             {
                 struct node *temp=NULL,*temp1,*temp2,*temp3;
                 temp1=(int *)malloc(sizeof(struct node));
                 temp1->link=NULL;
                 temp1->info=20;
                 temp2=(int  *)malloc(sizeof(struct node));
                 temp2->link=NULL;
                 temp2->info=30;
                 temp3=(int  *)malloc(sizeof(struct node));
                 temp3->link=NULL;
                 temp3->info=40;
                 temp=teamp3
                 temp3->link=temp2;
                 temp2->link=temp1;
                 while(temp->link!=NULL)
                      {
                          printf("%3d",temp->info);
   		             temp=temp->link;
                        }
            }
   

4. Write a function stack_concate() that concatenates contents of one stack on top of another stack using arrays.


5. Write a function queue_concate() that concatenates contents of one queue at the end of another queue using arrays.


6. What would happen if the following statements are executed, and draw the picture of each of the operation?

   	struct node
               {
                 struct  node *left;
   		    int info;
                 struct node *right;
               }
   	int main()
   	       {
       	        struct node *temp=NULL,*temp1,*temp2;
                 	temp1=(int *)malloc(sizeof(struct node));
                	temp1->left=NULL;
                   temp1->right=NULL;
                   temp1->info=20;
                   temp=temp1;
                	temp2=(int  *)malloc(sizeof(struct node));
                 	temp2->left=NULL;
   		temp2->right=NULL;
                 	temp2->info=30;
                 	temp1->right=temp2;
                   temp2->left=temp1;
                	
                 	while(temp->link!=NULL)
                        {
                           printf("%3d",temp->info);
   			        temp=temp->link;
                        }
                  printf("%3d",temp->info);
                   
                  }
   

This Page Is Designed By krishna Chaitanya