Programs for DSA 2 Semester Exam

Q. Write a program to sort 'n' randomly generated elements using heapsort method.

- #include<stdio.h>

void main()

{

int heap[10], no, i, j, c, root, temp;

printf("\n Enter no. of elements: ");\

scanf("%d",&heap[i]);

for(i=1;i<no;i++)

{

c=i;

do

{

root=(c-1)/2;

if(heap[root] < heap[c])

{

temp=heap[root];

heap[root]=heap[c];

heap[c]=temp;

}

c=root;

} while(c!=0);

}

printf("Heap array: ");

for(i=0;i<no;i++)

printf("%d\t",heap[i]);

for(j=no-1;j>=0;j--)

{

temp=heap[0];

heap[0]=heap[j];

heap[j]=temp;

root=0;

do

{

c=2*root+1;

if((heap[c]<heap[c+1])&& c<j-1) c++;

if(heap[root]<heap[c]&& c<j)

{

temp=heap[root];

heap[root]=heap[c];

heap[c]=temp;

}

root=c;

} while(c<j);

}

printf("\n The sorted array is: ");

for(i=0;i<no;i++)

printf("\t %d",heap[i]);

printf("\n Complexity : \n Best case= Avg case= Worts case= O(n logn) \n");

}

Q. Write a recursive C function to insert an element in binary tree.

- BST NODE *Insert_BST(BSTNODE *root, int n)

{

if(root==NULL)

{

root=(BSTNODE *)malloc(sizeof(BSTNODE));

root->data=n;

root->left=root->right=NULL;

}

else

if(n<root->data)

root->left=Insert_BST(root->left,n);

else

root->right=Insert_BST(root->right,n);

return(root);

}

Q. Write a Recursive ‘C’ function to count total nodes in a BST.

- int countnode(struct node *root)

{

static int count;

if (root==NULL)

return 0;

else

count=1+countnodes(root.left)+countnodes(root.riht);

return count;

}

Q. Write a ‘C’ function to compare two BST.

Q. Write a non-recursive ‘C’ function to insert an element in a Binary Search Tree.

-

BSTNODE *insert_bst(bstnode *root, int n)

{

bstnode *temp, *newnode;

newnode= (bstnode *)malloc(sizeof(bstnode));

newnode->data=n;

newnode->left=root->right=NULL;

if(root==NULL)

root=newnode;

else

{

temp=root;

while(temp)

{

if(n<temp->data)

{

if(n< temp->data)

temp->left=newnode;

break;

}

else

temp=temp->left;

else if (n>temp->data)

{

if(temp->right==NULL)

{

temp->right=newnode;

break;

}

else

temp=temp->Rchild;

}}

}

return root;

}

}

}

Q. Write a function to search an element in binary search tree.

- 

BSTNODE *research(BSTNODE *root, int key)

{

BSTNODE*temp=root;

if(temp==NULL) || (temp->data==key)

return(temp);

else

if(key<temp->data)

research(temp->left,key);

else

research(temp->right,key);

}