Contents
Chapterwise Question Bank CBSE Class 12 Computer Science (C++) – Linked List and Stack
Exam Practice
Short Answer Type Questions [2/3 Marks]
Question 1:
Evaluate the following postfix expression. Show the status of stack after execution of each operation separately. All India 2014
T, F, NOT, AND, T, OR, F, AND
Answer:
Given Postfix Expression is:
T, F, NOT, AND, T, OR, F, AND
Output F
Question 2:
Evaluate the following postfix expression. Show the status of stack after execution of each operation. Dehli 2013
60, 6, /, 5, 2, *, 5, -, +
Answer:
Output 15
Question 3:
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
Answer:
Output True
Question 4:
Evaluate the following postfix notation of expression:
50, 60, +, 20, 10, - , *
Delhi 2011
Answer:
Output 1100
Question 5:
Evaluate the following postfix notation of expression:
True, False, NOT, AND, True, True, AND, OR
All India 2011
Answer:
Output True
Question 6:
Evaluate the following postfix notation of expression (Show status of stack after each operation).
False, True, NOT, OR, True, False, AND, OR
Delhi 2010
Answer:
Output False
Question 7:
Convert the folio wing infix expression to its equivalent postfix expression. Showing stack contents for the conversion
(A + B*(C-D)/E).
All India 2009
Answer:
Let us rewrite like:
(A + B*(C-D)/E)
Output ABCD-*E/
Question 8:
Evaluate the following postfix notation of expression:
4,10,5,+,*,15,3,/,-
Delhi 2008
Answer:
Output 55
Question 9:
Evaluate the following postfix notation of expression:
25, 8, 3, -, /, 6, *, 10, +
Answer:
Output 40
Question 10:
Evaluate the following postfix notation of expression:
10, 20, +, 25, 15, -, *, 30,/
Answer:
Output 10
Question 11:
Evaluate the following postfix notation of expression:
20, 10, +, 5, 2, *, 10, /
Answer:
Output 2
Question 12:
Obtain the postfix notation for the following infix notation of expression showing the contents of the stack and postfix expression formed after each step of conversion.
A * B + (C - D/F)
Answer:
Let us rewrite like (A*B+(C-D/F))
Output AB*CDF/-+
Question 13:
Evaluate the following postfix expression using stack and show the contents of stack after execution of each expression.
120, 45, 20, +, 25, 15, — , + , k
Answer:
Output 9000
Question 14:
Use a stack to evaluate the following postfix expression and show the content of the stack after execution of each operation. Don’t write any code. Assume as if you are using push and pop member functions of the stack.
AB — CD + E * + (where A=5, B=3, 05, D=4 and E-2)
Answer:
Putting the values of the operands, we get the postfix expression as:
5, 3,-, 5, 4,+, 2, *, +
Output 20
Question 15:
Change the following infix expression into postfix expression:
(A + B)*C + D/E - F
Answer:
Let us rewrite like ((A+B)*C + D/E-F)
Output AB+C*DE/+F-
Question 16:
Why are parentheses needed to specify the order of operations in infix expressions but not in postfix expressions?
Answer:
Main advantage of using postfix or prefix expression is that parentheses are not required to enclose the operations. So, the problem of nesting of expression is removed. Every operator in a postfix or prefix expression is placed according to its precedence. Therefore, no ambiguity exists in interpreting arithmetic expressions.
Question 17:
List the disadvantage(s) of implementing stack as array. Describe means for overcoming the problems.
Answer:
Array is a static data structure, so it can not be enlarged or shrinked at the runtime for insertion and deletion of elements.
If we don’t know how many elements are to be inserted and deleted, we can not use array implementation of stack. To overcome this problem we can use linked implementation of stack.
Question 18:
Evaluate the following postfix expression using a stack and show the contents of stack after execution of each operation:
100, 40, 8, +, 20, 10, -, +, *
Answer:
The stack operation is:
Output 5800
Question 19:
Evaluate the following postfix expression using a stack and show the contents of the stack after execution of each operation:
5, 6, 9, +, 80, 5,*,-, /
Answer:
The stack operation is:
Output -1/77
Question 20:
Evaluate the following postfix expression using a stack. Show the contents of stack after execution of each operation.
TRUE, FALSE, TRUE, FALSE, NOT, OR, TRUE, OR, OR, AND
Answer:
In the given expression true and false arc operands and AND, NOT and OR are operators.
Output TRUE
Question 21:
Evaluate the following postfix expression showing the status of stack after execution of each step:
10, 40, +, 8, 2, +, *, 10, -
Answer:
The stack operation is:
Output 490
Question 22:
The following figure show a linked list in memory. HOTS
List the colours in the sequence indicated above.
Answer:
BLUE, BLACK, BROWN.
Question 23:
Consider the following sequence of numbers: HOTS
1, 2, 3, 4
These are supposed to be operated through a stack to produce the following sequence of numbers:
2, 1, 4, 3
List the push and pop operations to get the required output.
Answer:
(i) push (1) (ii) push (2)
(iii) pop (2) (iv)pop(1)
(v) push (3) (vi) push (4)
(vii) pop (4) (viii) pop (3)
Question 24:
convert the following infix expression into postfix expression using stack and show the status stack after every step
(((A + B) - C) * (D - E))
Answer:
The stack operation is:
Hence, the postfix notation is AB+C-DE-*
Question 25:
Consider the following stack of characters, where STACK is allocated N= 8 memory cells.
STACK: A, C, D, F, K,
Describe the STACK at the end of the following operations. Here, POP and PUSH are algorithms for deleting and adding an element to the stack.
(a) POP (STACK, ITEM);
(b) POP (STACK, ITEM);
(c) PUSH (STACK, L);
(d) PUSH (STACK,’P);
(e) POP (STACK, ITEM);
(f) PUSH (STACK, R)
(g) PUSH (STACK, S);
(h) POP (STACK, ITEM);
Answer:
The stack contents will be as follows after the operations of stack:
(a) STACK: A, C, D, F
{K is deleted}
(b) STACK: A, C, D
{F is deleted}
(c) STACK: A, C, D, L
{L is inserted}
(d) STACK: A, C, D, L, P
{P is inserted
(e) STACK: A, C, D, L
{P is deleted}
(f) STACK: A, C, D, L, R
{R is inserted}
(g) STACK: A, C, D, L, R, S
{S is inserted}
(h) STACK: A, C, D, L, R
{S is deleted}
Long Answer Type Questions [4 Marks]
Question 26:
Write a complete program in C++ to implement a dynamically allocated stack containing names of countries. Delhi 2010
Answer:
The program is:
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#includekconio.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 *Jemp = new Node;
cout<<"Enter the Country Name”;
gets(Temp→Country);
Temp→Link = Top;
Top = Temp;
}
void Stack :: Pop()
{
if(Top != NULL)
{
Node *Temp = Top;
cout<<"Country Name"<<Temp→Country <<" is deleted\n;
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(); break;
case 'Q':exit(0); break;
default:
cout<<"Wrong Input";
}
}while(ch!= 'Q');
getch();
}
Output
Choose any one P/O/D/Q P
Enter the Country Name India
Choose any one P/O/D/Q P
Enter the Country Name PAK
Choose any one P/O/D/Q O
Country Name PAK is deleted
Choose any one P/O/D/Q Q
Question 27:
Write a function PUSH BOO K() 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;
};
Answer:
void PUSHBOOK()
{
NODE *NEW = new NODE;
cout<<"Enter the Book Number: ";
cin>>NEW->Book_No;
cout<<"Enter the Book Title: ";
gets(NEW→ Book_Title);
NEW→ Next=top;
top = NEW;
}
Question 28:
Write a function in C++ to perform push operation on a dynamically allocated stack containing real numbers.
Answer:
struct Node
{
float data;
Node *next;
};
Node *Top=NULL;
void Push(float num)
{
Node *nptr = new Node;
nptr->data = num;
nptr->next = NULL;
if(Top == NULL)
Top = nptr;
else
{
nptr → next = Top;
Top = nptr;
}
cout<<"\nItem Inserted";
}
Question 29:
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;
};
Answer:
void POPBOOK()
{
cout<<"Deleting the top
element from stack\n";
cout<<"Book No:"<<top→Bno;
cout<<"Book Title: "<<top→ Title<<endl;
NODE *temp = top;
top = top→Link;
delete(temp);
}
Question 30:
Write a function in C++ to perform push operation on a dynamically allocated stack considering the following:
struct Node
{
int X , Y;
Node *Link;
};
class STACK
{
Node *Top;
public:
STACK()(Top=NULL;}
void PUSH!); void POP();
~ STACK();
};
Answer:
void STACK :: PUSH()
{
Node *ptr=new Node;
cout<<"Enter X and Y for new node:";
cin>>p11—>X>>ptr->Y;
ptr—>Link = Top;
Top = ptr;
}
Question 31:
Define functions stackpush() to insert nodes and stackpopf) to delete nodes, for a linked list implemented stack having following structure for each node:
struct node
{
char name[20];
int age;
node *link;
};
class stack
{
node *top;
public:
stack()
{
top = NULL;
}
void stackpush();
void stackpop();
};
Answer:
void stack :: stackpush()
{
node-*nptr = new node;
nptr—>link = NULL;
cout<<"Enter name for new node:”;
gets(nptr—>name);
cout<<"Enter age for new node";
cin>>npti—>age;
nptr—>link = top;
top = nptr;
}
void stack :; stackpop()
{
cout<<"Underflow”;
else
{
cout<<"Element being popped is \n";
cout<<top—>name<<": "<<top->age<<endl;
node *ptr;
ptr = top;
top = top—>link;
delete ptr;
}
}
Question 32:
Each node of a STACK contains the following information, in addition to pointer field:
(i) Pin code of city
(ii) Name of city.
Give the structure of node for the linked STACK in question. TOP is a pointer that points to the topmost node of the STACK. Write the following functions:
(a) PUSH() – To push a node into the STACK, which is allocated dynamically.
(b) POP() – To remove a node from the STACK and release the memory.
Answer:
The structure and the function of PUSH() and POP() operations are as:
struct node
{
int pin_code;
char name[20];
node *link;
};
node *T0P=NULL;
void PUSH()
{
node *nptr=new node;
nptr—>link=NULL;
cout<<"Enter pin code:”;
cin>>nptr—>pin_code;
cout<<"Enter city”;
gets(nptr—>name);
nptr—>link=TOP;
TOP=nptr;
}
void POP()
{
if(T 0 P==NULL)
cout<<"Underflow”;
else
{
cout<<"Element being popped is\n";
cout<<TOP—>pin_code<<":”<<T0P—>name;
cout<<endl ;
node *ptr;
ptr=T0P;
T0P=T0P—>link;
delete ptr;
}
}
Question 33:
Given the following class: HOTS
char *msg[] = {"overflow", "underflow"};
class Stack
int top; //the stack pointer
int stk[5];
//the elements
void err_rep(int e_num)
{
cout<<msg[e_num];
}
//report error message
public:
void init() I{ top = 0; }
//initialise the stack pointer
void push(int);
//put new value in stack
void pop();
//get the top value
}:
Define pop outside the stack. In your definition take care of underflow condition. Function pop should invoke error_rep to report underflow.
Answer:
The function is:
void Stack :: pop( )
{
if(top == 0)
err_rep(1):
else
cout<<stk[top--]<<" deleted”<<endl;
}
Question 34:
Declare a stack using array that contains int type numbers and define pop and push functions using C++ syntax.
Or
Write the static implementation of a stack containing int type numbers and define pop and push functions using C++ syntax. HOTS
Answer:
//define MAX 100
//Shows maximum array length
int stack[MAX];
//Declares array global variable
int top;
//Declares integer top
//Function body for add stack with array void push(int stack[],int val.int &top)
{
if(top == MAX-1)
cout<<" Stack Full";
else
{
top = top + 1;
stack[top] = val;
}
} //Function body for delete stack
//with array
int pop(int stack[],int Stop)
{
int value;
if(top<0)
{
cout<<" Stack Empty
value = - 1:
}
else
{
value = stack[top];
top = top - 1:
}
return(value);
}
Question 35:
Write a function in C++ to perform push operation in a dynamically allocated stack containing admission numbers of students. Also, declare the relevant class/structure and pointers.
Answer:
struct node
{
int admno;
node *link:
};
node *push(node *top, int val)
{
node *temp=new node;
temp—>admno=val ;
temp—>link=NULL;
if(t o p=NULL)
top=temp;
else
{
temp—>link=top;
top=temp;
}
return(top);
}
Computer ScienceChapterwise Question Bank for Computer ScienceNCERT Solutions