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