Sunday, 7 January 2018

Question Bank of Data Structure: Set 3

Q.1 Given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to output the three traversal orders. 
Q.2 Make a Binary Search Tree for the following sequence of numbers 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48. Traverse the tree in Pre-order, In-order and Post-order.
Q.3 Two Binary Trees are similar if they are both empty or if they are both nonempty and left and right sub trees are similar. Explain.
Q.4 The degree of a node is the number of children it has. Show that in any binary tree, the number of leaves are one more than the number of nodes of degree 2.
Q.5 Taking a suitable example explains how a general tree can be represented as a Binary Tree.
Q.6 What is the maximum total number of nodes in a tree that has N levels? 
Q.7 Write the non-recursive algorithm to traverse a tree in preorder.
Q.8 Write a Binary Search program.
Q.9 What are expression trees? Represent the following expression using a tree. 
Q.10 How do you rotate a Binary Tree? Explain right and left rotations with the help of an example.
Q.11 Taking a suitable example explains how a general tree can be represented as a Binary Tree.
Q.12 How many different binary trees and binary search trees can be made from three nodes that contain the key values 1, 2 & 3? 
Q.13 How will in-order, pre-order and post-order traversals print the elements of a tree?
Q.14 Which one is faster? A binary search of an ordered set of elements in an array or a sequential search of the elements.
Q.15 Write a non recursive algorithm to traverse a binary tree in in-order.
Q16 Construct a binary tree whose nodes in in-order and pre-order are given as follows:  In-order : 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50, Pre-order: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50
Q.17 Given the following in-order and pre-order traversal reconstruct a binary tree, In-order sequence D, G, B, H, E, A, F, I, C, Pre-order sequence A, B, D, G, E, H, C, F, I
Q.18 Make a Binary Search Tree for the following sequence of numbers. 45,32,90,34,68,72,15,24,30,66,11,50,10 Traverse the Binary Search Tree created in Pre-order, In-order and Post-order.                     
Q.19  What is a Binary Tree? What is the maximum number of nodes possible in a Binary Tree of depth d. 
Q.20 Construct a complete binary tree with depth 3 for this tree which is maintained in memory using linked representation. 
Q.21 Prove the hypothesis that “A tree having ‘m’ nodes has exactly (m–1) edges or branches”.
Q.22 Construct the binary tree for the following sequence of nodes in pre-order and  in-order respectively. Pre-order : G, B, Q, A, C, K, F, P, D, E, R, H, In-order: Q, B, K, C, F, A, G, P, E, D, H, R
Q.23  What is a height balanced tree? Explain how the height is balanced after addition/deletion of nodes in it?
Q.24  Let a binary tree ‘T’ be in memory. Write a procedure to delete all terminal nodes of the tree.
Q.25  Consider the following eight numbers 50, 33, 44, 22, 77, 35, 60 and 40. Display the construction of the binary by inserting the above numbers in the given order.
Q. 26 Explain the following terms with respect to Binary trees (i) Strictly Binary Tree (ii) Complete Binary Tree (iii) Almost Complete Binary Tree.


Thanks
Mukesh Rajput

Thursday, 28 December 2017

Write a C++ program to create a class called OCTAL which has the characteristics of an octal number. Implement the following operations by writing an appropriate constructor and an overloaded operator +.
(i) OCTAL h = x; where x is an integer.
(ii) int y = h + k; where h is an OCTAL object and k is an integer
Display the OCTAL result by overloading the operator <<. Also, display the values of h and y.

Implementation of the above problem:
#include <iostream.h>
#include <conio.h>
#include <math.h>
class octal
{
private:
int o;
public:
octal();
octal(int);
~octal();
int dectooct(int x);
int octtodec(int x);
friend ostream &operator<<(ostream &print,octal);
int operator +(int);
};
octal::octal()
{
}
octal::octal(int x)
{
o=dectooct(x);
}
octal::~octal()
{
}
int octal::dectooct(int x)
{
int i=0,sum=0,rem;
while(x!=0)
{
rem=x%8;
sum=sum+rem*pow(10,i);
i++;
x=x/8;
}
return sum;
}
int octal::octtodec(int x)
{
int i=0,sum=0,rem;
while(x!=0)
{
rem=x%10;
sum=sum+rem*pow(8,i);
i++;
x=x/10;
}
return sum;
}
ostream &operator<<(ostream &print,octal x)
{
print<<x.o;
return print;
}
int octal::operator+(int x)
{
return octtodec(o)+x;
}
main()
{
clrscr();
int x,y,k;
cout<<endl<<"Enter the value of x in decimal notation:";
cin>>x;
octal h(x);
cout<<endl<<"Corresponding value of x in octal notation,h="<<h;
cout<<endl<<"Enter the value of k in decimal notation:";
cin>>k;
cout<<"The value of k="<<k;
y=h+k;
cout<<endl<<"The value of h+k in decimal notation,y="<<y;
getch();
return 0;
}


Thanks
Mukesh Rajput
Design, develop and execute a program in C++ to create a class called LIST (linked list) with member functions to insert an element at the front of the list as well as to delete an element from the front of the list. Demonstrate all the functions of creating a list object.


Implementation of the above problem:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class node
public: int info;
class node*link; 
};
class list
node *head;
public: list() 
{
head=NULL;
}
void insert();
void del();
void display();
~list() {delete head;}
};
void list::insert()
{
node *temp;
temp=new node;
cout<<"\n Enter the element to be inserted:";
cin>>temp->info;
temp->link=head;
head=temp;
}
void list::del()
{
node *temp;
if(head==NULL)
cout<<"\n The list is empty";
else
{
temp=head;
cout<<"\n The deleted element = "<<temp->info;
head=head->link;
temp->link=NULL;
delete(temp);
}
}
void list::display()
{
node *temp;
if(head==NULL)
cout<<"\n The list is empty";
else
{
cout<<"\n The elements of the list are...\n\n";
for(temp=head;temp!=NULL;temp=temp->link)
cout<<temp->info<<"->";
cout<<"NULL";
}
}
void main()
{
int ch;
list l;
clrscr();
while(ch!=4)
{
cout<<"\n\n\n Enter the choice of operation:";
cout<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit:";
cin>>ch;
switch(ch)
{
case 1: l.insert();
break;
case 2: l.del();
break;
case 3: l.display();
break;
case 4: exit(0);
}
}
getch();
}


Thanks
Mukesh Rajput
Design, develop, and execute a program in C++ to create a class called STACK using an array of integers and to implement the following operations by overloading the operators
+ and - :
i. s1=s1 + element; where s1 is an object of the class STACK and element is an integer to be pushed on to top of the stack.
ii. s1=s1-; where s1 is an object of the class STACK and operator pops off the top element.
Handle the STACK Empty and STACK Full conditions. Also display the contents of the stack after each operation, by overloading the operator <<.

Implementation of the above problem:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
class stack
{
int a[MAX],top;
public: stack()
top=-1;
}
stack operator+(int ele);
stack operator--(int);
friend ostream& operator<<(ostream&,stack&);
};
stack stack::operator+(int ele)
{
if(top==MAX-1)
cout<<"\n STACK FULL";
else
a[++top]=ele;
return(*this);
}
stack stack::operator--(int)
{
if(top==-1)
cout<<"\n STACK EMPTY";
else
cout<<"\n The deleted element ="<<a[top--];
return(*this);
}
ostream& operator<<(ostream &c,stack &s)
{
if(s.top==-1)
c<<"\n STACK EMPTY";
else
for(int j=s.top;j>=0;j--)
{
c<<"\n\t\t|";
c.width(4);
c<<s.a[j]<<" |";
}
return c;
}
void main()
{
stack s;
int ch,ele;
clrscr();
while(ch!=4)
{
cout<<"\n Enter the choice of operation";
cout<<"\n 1. Push\n 2. Pop\n 3. Display\n 4. Exit:";
cin>>ch;
switch(ch)
{
case 1: cout<<"\n Enter the element :";
cin>>ele;
s=s+ele;
break;
case 2: s=s--;
break;
case 3: cout<<s;
break;
case 4: exit(0);
}
}
getch();
}


Thanks
Mukesh Rajput
Design, develop, and execute a program in C++ based on the following requirements: An EMPLOYEE class is to contain the following data members and member functions: Data members: Employee_Number (an integer), Employee_Name (a string of characters), Basic_Salary (an integer), All_Allowances (an integer), IT (an integer), Net_Salary (an integer). Member functions: to read the data of an employee, to calculate Net_Salary and to print the values of all the data members. (All_Allowances = 123% of Basic; Income Tax (IT) = 30% of the gross salary (= basic_Salary _ All_Allowance); Net_Salary = Basic_Salary + All_Allowances – IT).

Implementation of the above problem:
#include<iostream.h>
#include<conio.h>
class employee
{
int num;
char name[20];
float basic,da,it,netsal;
public:void readdata();
void netsalary();
void display();
int getnum();
};
void employee::readdata()
{
cout<<"\n\n Enter employee number:";
cin>>num;
cout<<"\n Enter name:";
cin>>name;
cout<<"\n Enter basic:";
cin>>basic;
}
void employee::netsalary()
{
float sal;
da=0.52*basic;
sal=da+basic;
it=0.3*sal;
netsal=sal-it;
}
void employee::display()
{
cout.precision(4);
cout.setf(ios::right);
cout<<"\n"<<num;
cout.width(15);
cout<<name;
cout.width(10);
cout<<basic;
cout.width(10);
cout<<da;
cout.width(10);
cout<<it;
cout.width(10);
cout<<netsal;
}
int employee::getnum()
{
return num;
}
void main()
{
int i,n;
clrscr();
cout<<"\n Enter the number of employees:";
cin>>n;
employee e[20];
for(i=0;i<n;i++)
{
cout<<"\n Enter the details of employee "<<i+1;
e[i].readdata();
for(int j=0;j<i;j++)
{
if(e[i].getnum()==e[j].getnum())
{
cout<<"\n Duplicate entry of employee number,re-type";
i--;
}
}
}
for(i=0;i<n;i++)
e[i].netsalary();
cout<<"\nNUMBER\t NAME\t BASIC\tDA\t IT\t NET SALARY\n";
for(i=0;i<n;i++)
e[i].display();
getch();
}


Thanks
Mukesh Rajput