Table of Contents
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;
}
}
