MCS-021 ASSIGNMENT SOLUTION (2018-19)

If you have any queries please leave a message here
Your Message
×


In this ASSIGNMENT all the below PROGRAMMINGS are written and run in Turbo C++ 3.0

We have removed clrscr( ) and getch( ) functions from each programming because of different version of C compiler.




Question 1 :

Write an algorithm that accepts a Binary Tree as input and prints its height to standard output

Answer : -

/* Header-File declaration */
#include<stdio.h>
#include<stdlib.h>

/* Structure declaration */
struct BinaryTree
{
int number;
struct BinaryTree *leftchild;
struct BinaryTree *rightchild;
};
typedef struct BinaryTree NODE;

/* Global variable declaration */
NODE *root, *child, *p;
int num, height=0, count=0;

/* Global function declaration */
void insertNode(int n);

void main()
{
char choice;
root = NULL;
while(1)
{
printf("\n Insert Node ? (Y/N)...");
scanf("%c",&choice);
if(choice == 'N')
break;
else
if(choice == 'Y')
{
printf("\n Enter the Number...");
scanf("%d",&num);
insertNode(num);
if(count > height)
{
height = count;
}
count = 0;
}
else
printf("\n\n Press Only (Y/N)");
}
printf("\n\n Height = %d",height);
}

/* Insert operation and height count */
void insertNode(int n)
{
if(root == NULL)
{
root = (NODE *) malloc(sizeof(NODE));
root->number = n;
root->leftchild = NULL;
root->rightchild = NULL;
}
else
{
child = (NODE *) malloc(sizeof(NODE));
child->number = n;
child->leftchild = NULL;
child->rightchild = NULL;
p = root;
while(p != NULL)
{
/* If number <= root value then goto the left side */
if(n <= p->number)
{
if(p->leftchild == NULL)
{
p->leftchild = child;
count++;
break;
}
else
p = p->leftchild;
}
/* If number > root value then goto the right side */
if(n > p->number)
{
if(p->rightchild == NULL)
{
p->rightchild = child;
count++;
break;
}
else
p = p->rightchild;
}
count++;
}
}
}



Question 2 :

Write an algorithm for the implementation of a B tree.

Answer : - B-Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children. One of the main reason of using B-Tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.

Properties of B-Tree -


B-Tree Insertion

Let us understand the algorithm with an example tree of minimum degree ‘t’ as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-Tree.

Initially root is NULL. Let us first insert 10.


Let us now insert 20, 30, 40 and 50. They all will be inserted in root because maximum number of keys a node can accommodate is 2*t – 1 which is 5.


Let us now insert 60. Since root node is full, it will first split into two, then 60 will be inserted into the appropriate child.


Let us now insert 70 and 80. These new keys will be inserted into the appropriate leaf without any split.


Let us now insert 90. This insertion will cause a split. The middle key will go up to the parent.



B-Tree Deletion

Initial Tree


After delete 60 the Tree will be


After delete 20 the Tree will be


After delete 30 the Tree will be





Question 3 :

Write a note of not more than 5 pages summarizing the latest research in the area of “Searching Techniques”. Refer to various journals and other online resources. Indicate them in your assignment.

Answer : - Searching is an operation or a technique that helps finds the place of a given element or value in the list. Any search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not. Some of the standard searching technique that is being followed in the data structure is listed below :


Linear Search or Sequential Search

In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. This method can be performed on a sorted or an unsorted list (usually arrays).

Linear Search Programming

#include<stdio.h>
//Global function declaration
int LinearSearch(int list[],int value);

void main()
{
int number, retn;
int array[]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
printf("\n Enter the number you want to search...");
scanf("%d",&number);
retn=LinearSearch(array,number);
if(retn == 0)
printf("\n Number not found");
else
printf("\n Number found");
}

int LinearSearch(int list[],int value)
{
int i,len,count=0;
len=(sizeof(array)/sizeof(int));
for(i=0;i<len;i++)
{
if(list[i] == value)
count++;
}
return count;
}

Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you have narrowed down the possible locations to just one.

Process of Binary Search

  1. Start with the middle number : is it bigger or smaller than our target number? Since the array is sorted, this tells us if the target would be in the left half or the right half of our array.

  2. We have effectively divided the problem in half. We can "rule out" the whole half of the array that we know does not contain the target number.

  3. Repeat the same approach (of starting in the middle) on the new half-size problem. Then do it again and again, until we either find the number or "rule out" the whole set.

Binary Search Programming

#include<stdio.h>
//Global function declaration
int BinarySearch(int list[],int value);

void main()
{
int number, retn;
int array[]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
printf("\n Enter the number you want to search...");
scanf("%d",&number);
retn=BinarySearch(array,number);
if(retn == 0)
printf("\n Number not found");
else
printf("\n Number found");
}

int BinarySearch(int list[],int value)
{
int low=0, mid, high, count=0;
high = (sizeof(array) / sizeof(int)) - 1;
while(low <= high)
{
mid = (low + high) / 2;
if(list[mid] == value)
{
count = 1;
break;
}
else
if(list[mid] < value)
low = mid + 1;
else
if(list[mid] > value)
high = mid - 1;
}
return count;
}



Question 4 :

Write an algorithm for the implementation of a Circularly Doubly Linked List.

Answer : -

#include<stdio.h>
/* Structure declaration */
struct LinkedList
{
struct LinkedList *previous;
int number;
struct LinkedList *next;
};
typedef struct LinkedList NODE;

/* Global variable declaration */
NODE *head, *temp, *p;

/* Global functions declaration */
void insertNode(int n);
void deleteNode(int n);
void displayList();

/* main( ) function */
void main()
{
int choice, num;
while(1)
{
printf("\n Press 1 for insert number");
printf("\n Press 2 for delete number");
printf("\n Press 3 for display list");
printf("\n Press 4 for exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the number : ");
scanf("%d",&num);
insertNode(num);
break;
case 2:
if(head == NULL)
printf("\n List is blank !");
else
{
printf("\n Enter the number : ");
scanf("%d",&num);
deleteNode(num);
}
break;
case 3:
displayList();
break;
case 4:
exit(0);
default:
printf("\n\n\n Wrong Input");
}
}
}

/* Insert number into the list */
void insertNode(int n)
{
/* Check whether the list is blank or not */
/* If blank then create a memory into head variable and place the number into it */
if(head == NULL)
{
head = (NODE *) malloc(sizeof(NODE));
head->number = n;
head->previous = head;
head->next = head;
}
else
{
/* If the list is not blank then create a memory into temp variable, place the number into it and add this memory to the end of the list */
temp = (NODE *) malloc(sizeof(NODE));
temp->number = n;
p = head;
while(p->next != head)
p = p->next;
p->next = temp;
temp->previous = p;
temp->next = head;
head->previous = temp;
}
}

/* Delete a particular number from the list */
void deleteNode(int n)
{
int found = 0;
/* Check whether the list contain only one element or not */
if(head->next == head && head->previous == head)
{
if(head->number == n)
{
found = 1;
head = NULL;
}
}
else
/* Check whether the number found into the first-memory (head) of the list or not ? */
if(head->number == n)
{
temp = head;
head = head->next;
head->previous = temp->previous;
temp->previous->next = head;
found = 1;
}
else
{
p = head->next;
while(p != head)
{
if(p->number == n)
{
p->next->previous = p->previous;
p->previous->next = p->next;
found = 1;
break;
}
p = p->next;
}
}
if(found == 0)
printf("\n Element not found !");
}

/* Display list elements */
void displayList()
{
/* Check whether the list is blank or not */
if(head == NULL)
printf("\n List is blank !");
else
{
p = head;
while(p->next != head)
{
printf("\t%d",p->number);
p = p->next;
}
printf("\t%d",p->number);
}
}


ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us