# Important Questions for CBSE Class 12 Computer Science (C) Chapter 9 Linked List, Stack and Queue

## CBSE Class 12 Computer Science (C++) Chapter 9 Linked List, Stack and Queue Important Questions – Free PDF Download

Free PDF download of Important Questions for CBSE Class 12 Computer Science (C++) Chapter 9 Linked List, Stack and Queue prepared by expert Computer Science (C++) teachers from latest edition of CBSE(NCERT) books, On CoolGyan.Org to score more marks in CBSE board examination.

## CBSE Class 12 Computer Science (C++) Important Questions Chapter 9 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
"; 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
"; F=F->Next; delete Temp; if(F==NULL) R=NULL; } else cout<<"
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<<"
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<<"
"<<temp->city; temp = temp->l ink; } } void main() { int choice; queue QUEUE; char opt="Y"; do { cout<<"
l.Insertion in queue"; cout<<"
2.Deletion from queue"; cout<<"
3.Traversal of queue"; cout<<"
4.Exit from queue"; cout<<"
Enter your choice from above(1,2,3,4)"; cin<<choice; switch(choice) { case 1: do { QUEUE.add_Q(); cout<<"
do you want to add more elements<Y/N>?"; cin>>opt; } while(toupper(opt)=="Y"); break; case 2: do { QUEUE.del_Q(); cout<<"
do 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; } }