Important Questions for Class 12 Computer Science (C++) – Linked List, Stack and Queue

Important Questions for Class 12 Computer Science (C++) – Linked List, Stack and Queue

Topic – 1
Linked List and Stack
Previous years Examination Questions
2 Marks Questions

Question 1:
Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion:
P/(Q-R)*S + T All India 2016
Аnswer:

Question 2:
Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion.
A/(B + Q*D-E Delhi 2016
Аnswer:

Question 3:
Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion.
P/(Q+(R-T)*U All India (C) 2016
Аnswer:

Question 4:
Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion:
(U* V+ R/ (S-T)) All India 2015
Аnswer:

Question 5:
Convert the following infix expression to its equivalent postfix expression, showing the stack contents for each step of conversion.
(X/Y+U*(V-W)) Delhi 2015
Аnswer:

Question 6:
Evaluate the following postfix expression. Show the. status of stack after execution of each operation separately:
F, T, NOT, AND, F, OR, T, AND Delhi 2014
Аnswer:

Question 7:
Evaluate the following postfix expression. Show the status of stack after execution of each operation separately:
T, F, NOT, AND, T, OR, F, AND All India 2014
Аnswer:

Question 8:
Evaluate the following postfix expression: (show status of stack after each operation)
100,40,8,/,20,10,-,+,* All India (C) 2014
Аnswer:

Question 9:
Evaluate the following postfix expression. Show the status of stack after execution of each operation:
5, 2, *, 50, 5, /, 5, -, + All India 2013
Аnswer:

Question 10:
Evaluate the following postfix expression. Show the status of stack after execution of each operation:
60, 6, /, 5, 2, *, 5, -, + Delhi 2013
Аnswer:

Question 11:
Evaluate the following postfix expression using a stack and show the contents of stack after execution of each operation:
5, 3, 2, *, 4, 2, /, -, * Delhi 2013C
Аnswer:

Question 12:
Evaluate the following postfix notation. Show status of stack after every step of evaluation (i.e. after each operator):
False, NOT, True, AND, True, False, OR, AND Delhi 2012
Аnswer:

Question 13:
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 All India 2012
Аnswer:

Question 14:
Evaluate the following postfix notation of expression:
50, 60, +, 20, 10, – ,* Delhi 2011
Аnswer:

Question 15:
Evaluate the following postfix notation of expression:
True, False, NOT, AND, True, True, AND, OR All india 2011
Аnswer:

Question 16:
Evaluate the following postfix notation of expression:
False, True, NOT, OR, True, False, AND, OR Delhi 2010
Аnswer:

Question 17:
Evaluate the following postfix notation of expression. Show the status of stack after each operation:
True, False, NOT, OR, False, True, OR, AND All India 2010
Аnswer:

Question 18:
Convert the following infix expression to its equivalent postfix expression.
Showing stack contents for the conversion:
(X – Y/(Z+U)*V) Delhi 2009
Аnswer:

Question 19:
Convert the following infix expression to its equivalent postfix expression.
Showing stack contents for the conversion:
(A + B* (C-D) IE) All India 2009
Аnswer:

4 Marks Questions

Question 20:
Write the definition of a member function PUSH( ) in C++, to add a new book in a dynamic stack of BOOKS considering the following code is already included in the program: All India 2015

struct BOOKS 
{
char ISBN[20], TITLE[80];
BOOKS *Link;
};
class STACK 
{
BOOKS *Top; 
public:
STACK() {Top=NULL;} 
void PUSH(); 
void POP();
∼STACK();
 };

Аnswer:

void STACK::PUSH()
{
BOOKS *b = new BOOKS; 
cout<<"Enter ISBN number"; 
cin>>b->ISBN; 
cout<<"Enter TITLE"; 
gets(b—>TITLE); 
if(TOP == NULL)
{
TOP = b;
}
else
{
b->Link = TOP; 
TOP = b;
}
}

Question 21:
Write the definition of a member function Pop( ) in C++, to delete a book from a dynamic stack of TEXTBOOKS considering the following code is already included in the program. Delhi 2015

struct TEXTBOOKS
{
char ISBN[20]; 
char TITLE[80]; 
TEXTBOOKS *Link;
};
class STACK 
{
TEXTBOOKS *Top; 
public:
STACK(){Top=NULL;} 
void Push(); 
void Pop();
∼STACKC);
};

Аnswer:

void STACK::Pop()
{
if(Top! = NULL)
{
TEXTBOOKS *Temp = Top;
Top = Top->Link; 
delete Temp; 
}
else
cout<<"Stack empty";
}

Question 22:
Write a function POPBOOK( ) in C++ to perform delete operation from a dynamic stack, which contains Bno and Title. Consider the following definition of NODE, while writing your C++ code. Delhi 2014

struct NODE
{
int Bno;
char Title[20];
NODE *Link;
};

Аnswer:

void P0PB00K(N0DE *top)
{
cout<<:Deleting the top element from stack\n"; 
cout<<"Book No:"<<top->Bno<<endl; 
cout<<"BookTitle:"<<top->Title<<endl;
NODE *temp = top;
top = top->Link; 
delete(temp);
}

Question 23:
Write a function PUSHBOOK( ) in C++ to perform insert operation on a dynamic stack, which contains Book_no and Book_Title. Consider the following definition of NODE, while writing your C++ code. All India 2014

struct NODE 
{
char Book_No; 
char Book_Title[20]:
NODE *Next:
};

Аnswer:

void PUSHBOOK(NODE *top)
{
NODE *NEW = new NODE; 
cout<<"Enter the Book Number:"; 
cin>>NEW->Book_No; 
cout<<"Enter the Book Title:"; 
gets(NEW->Book_Titie);
NEW->Next = NULL; 
if(top == NULL)
top = NEW; 
else 
{
NEW->Next = top; 
top = NEW;
}
}

Question 24:
Write a complete program in C++ to implement a dynamically allocated stack containing names of Countries. Delhi 2010
Аnswer:

The program is:
#include<iostream.h>
#include<stdio.h>
struct Node
{ 
char Country[30];
Node *Link;
};
class Stack 
{
Node *Top; 
public:
Stack(){Top = NULL;} 
void Push(); 
void Pop();
void Display();
∼Stack();
};
void Stack :: Push()
{
Node *Temp = new Node; 
gets(Temp->Country); 
Temp->Link = Top;
Top = Temp;
}
void Stack :: Pop()
{
if(Top!=NULL) 
{
Node *Temp = Top;
Top = Top->Link; 
delete Temp;
}
else
cout<<"Stack empty";
}
void Stack :: Display()
{
Node *Temp = Top; 
while(Temp!= NULL)
cout<<Temp->Country<<endl; 
Temp = Temp->Link;
Stack :: ∼Stack()
{
while(Top!=NULL)
{
Node *Temp = Top;
Top = Top->Link; 
delete Temp;
}
}
void main()
{
Stack ST; 
char ch; 
do 
{
cout<<"Choose any one P/O/D/Q"; /* displaying choices P - Push,0 - Pop, D-Display, Q-Exit */ 
cin>>ch; 
switch(ch)
{
case 'P':ST.Push(); 
break;
case '0':ST.Pop(); 
break;
case 'D':ST.Display();
}
}
while(ch!='Q');
}

Topic – 2
Queue
Previous years Examination Questions
4 Marks Questions

Question 1:
Write the definition of a member function DELETE( ) for a class QUEUE in C++, to remove a product from a dynamically allocated Queue of products considering the following code is already written as a part of the program. All India 2016

struct PRODUCT 
{
int PID; 
char PNAME[20];
PRODUCT *Next;
};
class QUEUE 
{
PRODUCT *R,*F; 
public:
QUEUE(){R=NULL;F=NULL;} 
void INSERT(); 
void DELETE();
∼QUEUE();
};

Аnswer:

void QUEUE :: DELETE() 
{
if(F!=NULL)
{
PRODUCT *Temp=F;
cout<<F->data<<"deleted\n";
F=F->Next; 
delete Temp;
if(F==NULL)  
R=NULL;
}
else
cout<<"\n Queue is Empty":
}

Question 2:
Write the definition of a member function INSERT( ) for a class QUEUE in C++, to insert an ITEM in a dynamically allocated Queue of items considering the following code is already written as a part of the program. Delhi 2016

struct ITEM 
{
int INO; 
char INAME[20];
ITEM *Link; 
};
class QUEUE 
{
ITEM *R, *F; 
public:
QUEUE() {R=NULL; F=NULL;} 
void INSERT(); 
void DELETE();
∼QUEUE();
};

Аnswer:

void QUEUE :: INSERT!)
{ 
ITEM *temp=new ITEM;
cout<<"\n Enter Item no & Item name:";
cin>>temp->INO; 
gets(temp->IName);
temp->Next = Null;
if(R==Null)
{
R = temp;
F = temp; 
}
else
{
R->Next = temp;
R = temp;
}
}

Question 3:
Write the definition of a member function INSERT! ) in C++, to add a new passenger detail in a dynamic queue of PASSENGERS considering the following code is already existing in the program. All India 2015

struct PASSENGERS
{
char PID[20]; NAME[80];
PASSENGERS *Next;
};
class QUEUE
{
PASSENGERS *Rear, *Front; 
public:  
QUEUE() {Rear=NULL; Front=NULL}
void INSERT(); 
void DELETE();
∼QUEUE();
};

Аnswer:

void QUEUE ::INSERT()
{
PASSENGERS * P = new PASSENGERS; 
cout<<"Enter PID"; 
cin>>P->PID; 
cout<<"Enter Name”; 
gets(p->Name);
P->Next = NULL;
if(Rear == NULL)
{
Front = Rear = P;
}
else 
{
Rear->Next = P;
Rear = P;
}
}

Question 4:
Write a function QDELETE( ) in C++ to perform delete operation in a Linked Queue, which contains Passenger number and Passenger name. Consider the following definition of node in the code. All India 2013

struct node 
{
long int Pno; 
char Pname[20]; 
node *Link;
};

Аnswer:

void QDELETE()
{
if(Front == NULL) 
{
cout<<"Queue is empty"; 
exit(0);
}
else
{
node *temp = front; 
cout<<"Passenger Information"; 
cout<<Front->Pno; 
cout<<Front->Pname;
Front=Front->Link; 
delete temp;
}
}

Question 5:
Write a function QINSERT( ) in C++ to perform insert operation on a linked queue, which contains client number and client name. Consider the following definition of NODE in the code of QINSERT ( ). Delhi 2013

struct NODE 
{
long int Cno;    //Client number
char Cname[20];    //Client name
NODE *Next;
};

Аnswer:

void QINSERT()
{
NODE *P = new Node;
cout<<"Enter the Client Number and Name:";
cin>>P- Cno;
gets(P->Cname) ;
P->Next=NULL;
if((front ~ NULL)&&(rear == NULL))
{
front=rear=P;
}
else
{
rear->Next = P; 
rear = P;
}
}

Question 6:
Given the necessary declaration of linked implemented Queue containing players information (as defined in the following definition of Node). Also, write a user defined function in C++ to delete one Player’s information from the Queue.
Delhi 2013C

struct Node 
{
int PlayerNo; 
char PIayerName[20];
Node *Link;
};

Аnswer:

void Delete_NODE()
{
NODE *P;
if(front == Null)
cout<<”Queue is empty";
else if(front == rear) 
{
P = front;
cout<<"Deleted Node information is"; 
cout<<P->PlayerNo; 
puts(p->PlayerName); 
front = rear = NULL; 
delete P;
}
else
{
P = front;
cout<<"Deleted Node information is"; 
cout<<P->PlayerNo; 
puts(P->PlayerName); 
front = front->Link; 
delete P;
}
}

Question 7:
Write a function in C++ to perform insert operation in a dynamic queue containing DVD’s information (represented with the help of an array of structure DVD). Delhi 2012

struct DVD 
{
long No; 
char title[20];
DVD *Link;
};

Аnswer:

void Insert()
{
DVD *p = new DVD; 
cout<<"Enter the DVD number and Title";
cin<<p->No; 
gets(p->title);
p->Link = NULL; 
if((front — NULL) && (rear == NULL))
{
front - rear = p;
}
else
{
rear->Link = p; 
rear = p;
}
}

Question 8:
Write a function in C++ to perform insert operation in a static circular queue containing book’s information (represented with the help of an array of structure BOOK). All India 2012

struct BOOK  
{ 
long AccNo; //Book account number 
char Title[20]; //Book Title
};

Аnswer:

void circularQueInsert(BOOK B[], int Front, int Rear, int Max)
{
if((Rear=Max-l && Front ==0)||(Front == Rear +1))
{
cout<<"Circular Queue is full"; 
exit(O);
}
else if(Front == -1 && Rear == -1)
{
Front = Rear = 0;
}
else if(Rear = Max -1 && Front >0)
{
Rear = 0;
}
else
Rear = Rear+1; 
cout<<"Enter book account number and title"; 
cin>>B[Rear].AccNo; 
gets(B[Rear].Title);
}

Question 9:
Write a function in C++ to perform insert operation on a dynamically allocated queue containing passenger details as given in the following definition of NODE; Delhi 2011

struct NODE 
{
long Pno; //Passenger Number 
char Pname[20]; //Passenger Name 
NODE *Link;
};

Аnswer:

void Enter()
{
NODE *nptr=new NODE;
nptr->Link = NULL;
cout<<"Enter name and number for new passenger";
gets(nptr->Pname); 
cin>>nptr->Pno; 
if(rear == NULL)
{
front = rear = nptr;
}
else
{
rear->Link = nptr; 
rear = nptr;
}
}

Question 10:
Write a function in C++ to perform delete operation on a dynamically allocated queue containing passenger details as given in the following definition of NODE: All India 2011

struct NODE 
{
long Mno; //Member Number 
char Mname[20]; //Member Name 
NODE *Link;
};

Аnswer:

void remove(NODE *front)
{
NODE *nptr; 
if(front == NULL) 
{
cout<<"Queue is empty";
}
else 
{
nptr = front; 
front = front->Link; 
if(front == NULL) 
rear = NULL; 
delete nptr;
}

Question 11:
Write a complete program in C++ to implement a dynamically allocated queue containing names of cities. All India 2010
Аnswer:

#include<iostream.h>
#include<string.h> 
struct Node 
{
char city[30];
Node *link;
};
class queue 
{
Node *front, *rear; 
public:
queue() {front=rear=NULL;} 
void add_Q();    //add queue
void del_Q();    //delete queue
void show_Q();    //show queue
};
void queue :: add_Q()
{
Node *temp = new Node; 
char ct[30]; 
cout<<"Enter city"; 
gets(ct);
strcpy(temp->city,ct); 
temp->link = NULL; 
if(rear == NULL)
front = rear = temp; 
else
{
rear->link = temp; 
rear = temp;
}
}
void queue :: del_Q()
{
Node *temp; 
char ct[20]; 
if(front == NULL)
{
cout<<”queue is empty";
}
else   
{
temp = front; 
front = front->link; 
strcpy(ct, temp->city); 
cout<<"Deleted values are"<<ct; 
delete temp;
}
if(front == NULL)
rear = front;
}
void queue :: show_Q()
{
Node *temp = front; 
cout<<"The queue elements are"; 
while(temp!=NULL)
{
cout<<"\n"<<temp->city; 
temp = temp->l ink;
}
}
void main()
{
int choice; 
queue QUEUE; 
char opt='Y'; 
do 
{
cout<<"\nMain Menu"; 
cout<<"\nl.Insertion in queue"; 
cout<<"\n2.Deletion from queue"; 
cout<<"\n3.Traversal of queue"; 
cout<<"\n4.Exit from queue"; 
cout<<"\nEnter your choice from above(1,2,3,4)"; 
cin<<choice; 
switch(choice)
{
case 1: 
do 
{
QUEUE.add_Q(); 
cout<<"\ndo you want to add more elements<Y/N>?"; 
cin>>opt;
}
while(toupper(opt)=='Y'); 
break; 
case 2: 
do 
{
QUEUE.del_Q(); 
cout<<"\ndo you want to delete more elements<Y/N>?";
cin>>opt;
}
whi1e(toupper(opt)== 'Y'); 
break; 
case 3:
QUEUE.show_Q(); 
break; 
case 4; 
exit(0);
}
}
while(choice!=4);
}

Question 12:
Write a function QUEINS( ) in C++ to insert an element in a dynamically allocated queue containing nodes of the following given structure: Delhi 2009

struct Node
{
int Pid;     //Product Id
char Pname[20];   //Product Name 
Node *Next; 
};

Аnswer:

void QUEINS(Node *rear, int val, char valid)
{
Node *temp=new Node; 
temp->Pid = val; 
strcpy(temp->Pname,val1); 
temp->Next = NULL; 
if(rear == NULL)
rear = front = temp; 
else
{
rear->Next = temp; 
rear = temp;
}
}

Question 13:
Write a function QUEDEL( ) in C++ to display and delete an element in a dynamically allocated queue containing nodes of the following given structure: All India 2009

struct Node 
{
int Itemno; 
char Itemname[30];
Node *Link;
};

Аnswer:

void QUEDEL(Node *front)
{
Node *temp; 
if(front == NULL)
cout<<"Queue is Empty"; 
else
{
temp = front; 
cout<<"deleted item="; 
cout<<front->Itemno; 
cout<<front->Itemname; 
front = front->Link; 
if(front == NULL) 
rear = NULL; 
delete temp;
}
}