DS GRAPH NOTES
GRAPH NOTES

ANY COACHING CLASS FIND BELOW LINK IN BANGALORE

http://matruchaya-training-centre.blogspot.com

DATA STRUCTURES LAB FOR LAB FINAL LAB EXAM

Part A

1. Use a recursive function to find GCD of two numbers.
2. Use a recursive function to find the Fibonacci series.
3. Use pointers to find the length of a string
4. Use pointers to concatenate two strings.
5. Use pointers to copy a string
6. Use pointers to extract a substring from a given a string.
7. Use a recursive function for the towers of Hanoi with three discs.
8. Insert an integer into a given position in an array.
9. Deleting an integer from an array.

Part B
10. Write a program to create a linked list and to display it.
11. Write a program to sort N numbers using insertion sort.
10. Write a program to sort N numbers using selection sort.
11. Array implementation of stacks.
12. Array implementation of queues.
13. Creating a binary tree and display in inorder.
14. Sort N numbers using merge sort.

DS QUESTION BANK

MODULE-1Introduction To DS

1) Define D.S
2) How do you classify D.S?
3) What are primitive D.S?give example
4) What are non-primitive D.S?give example
5) What are linear D.S?give example
6) What are non-linear D.S?give example
7) What are the common operations on non-primitive D.S?
8) What is the time complexity of an algorithm?
9) What is the space complexity of an algorithm?
10) List out the primitive operations performed on the strings.
11) What are operations on string?

MODULE-2 Dynamic Memory Allocation

1)Give the meaning of each of the following statements
a)int a;
b)int *p;
c)p=&a;
d)printf(“%d”,*p);

2)What is the purpose of the following two statements

a)int x;
int *px=&x;

b)int x=100,y;
int *p;
p=&x;
y=*p;

3)Define static memory allocation.
4)Define dynamic memory allocation.
5)What is the purpose of using malloc(),calloc(),realloc(),free()?write the syntax of all
6)What are the advantages of pointers.
7)Difference between static and dynamic memory allocation.

MODULE-3 Recursion
1)Define Recursion.
2)Write the advantages of recursion.
3)Write a program for finding GCD of numbers using recursion.
4) Write a program for generates Fibonacci of n using recursion.

Module 4: SEARCHING

1. Differentiate between linear search and binary search.
2. What are the advantages and disadvantages of linear and binary search?
3. What are the advantages and disadvantages of binary search?
4. Write a program on linear search.
5. Write an algorithm for binary search function.
6. Write a program for binary search using recursive methods.

MODULE-5 SORTING

1) What is sorting? List any five sorting methods.
2) Apply bubble sort technique to the following list of number and explain each step 10,4,1,15,0,9.
3) Write an algorithm and program to sort n elements using merge sort method.
4) Write a program to sort n elements using insertion sort method.
5) Write a program to sort n elements using selection sort method.

10-MARKS

1)Write a program for the following.
a)Bubble sort
b)Selection sort
c)Insertion sort
d)Quick sort
e)Merge sort

MODULE-6 STACK

1) Define STACK
2) Array representation of STACK
3) List and explain briefly the basic operations on STACK
4) Applications of STACK
5) Consider the infix expression a+b*c. convert this into prefix and postfix.
6) Translate the below expression to prefix
a. (A+B)((D-E)*F+G)
b. (A+B)*(A-B)
7) Write a program on STACK to perform PUSH, POP and DISPLAY function
8) Write an algorithm for on STACK to perform PUSH, POP and DISPLAY function
9) Diagrammatically represent various an empty stack, overflow, push, pop and underflow of the stack.
10) Write a C program to illustrate stack program.
11) Diagrammatically represent and explain 1) Empty stack, 2) Stack Overflow, 3) Stack Underflow.
12) i)Define STACK ii) Array representation of STACK iii) Operations on STACK


MODULE-7 QUEUE

1) Define Queue.
2) List different types of queue.
3) What are the operations that can be performed on queue?
4) Define De-queue. List its types explain along with representation
5) What is circular queue?
6) Define degree and depth of the node.

7) What is priority queue? List its types and explain along with its representation
8) Write applications of queue.
9) Illustrate the circular Queue with neat diagram then trace it for n=4 inert 13,89,12,78 then remove 13, then insert 33, 45
10) Write a program to demonstrate insert, delete and display operation on simple Queue
11) With an example demonstrate how a queue can be represented using array.

MODULE-8 Linked List

1. Define linked list.
2. Which are the two components of linked list?
3. List different types of linked list and explain any two
4. Show with the diagram of Singly Linked List with three nodes.
5. Write applications of linked list.
6. Show with a neat diagram a linked list of 3 nodes.
7. What are different operations possible on linked list?
8. List advantages and disadvantages of linked list.
9. Write a program to create node and display linked list
10. Write an algorithm on functions to create, delete and display node in the linked list
11. WAP to create a linked list and display.
12. Write program to the following.
a)to delete a node at the beginning of list.
b)to delete a last node of the list.

MODULE-9 TREEs AND GRAPHs

1) What are the terminologies of tree, explain with tree structure
2) Write an algorithm for a creation of a binary tree.
3) Draw array representation of tree
2) What is preorder traversal of the given tree.
4) What is in order traversal, write inorder traversal for the given tree.
5) What is post order traversal. Write post order traversal for the given tree.
6) What is heap tree?
7) What is binary search tree?
8) What are the properties of binary tree?
9) What is Graph? Applications of graph
10) Types of traversal in Graphs
11) Explain the concept of depth first search with reference to graph.

ಪಾರ್ಟ್-ಬ ಪರಗ್ ೨

//PART -B PRG 2DELETE NODE IN SINGLY LINKED LIST AT DIFFERENT POSITION
#include
#include
#include
#include
struct node
{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *head;
/*Fucntion to create a linked lsit*/
NODE *GetNode()
{
NODE *NewNode;
NewNode=(NODE*)(malloc(sizeof(NODE)));
if(NewNode==NULL)
{
printf("\n\nEMPTY LIST");
exit(1);
}
return NewNode;
}
void create_link_list(NODE *CurrPtr)
{
NODE *NewNode;
int ans;
while(1)
{
printf("\n\nENTER INFO :");
scanf("%d",&CurrPtr->info);
printf("\n\nDO U WISH TO ENTER ONE MORE NODE PRESS 1 :");
scanf("%d",&ans);
if(ans==1)
{
NewNode=(NODE*)(malloc(sizeof(NODE)));
CurrPtr->link=NewNode;
CurrPtr=NewNode;
}
else
{
CurrPtr->link=NULL;
break;
}
}
}
void display(NODE *CurrPtr)
{

CurrPtr=head;
while(CurrPtr!=NULL)
{
printf("\n\n\t%d ",CurrPtr->info);
CurrPtr=CurrPtr->link;
}

}
int Delete_Beg()
{
NODE *CurrPtr;
int item;
if(head==NULL)
{
printf("\n\n DELETION NOT POSSIBLE");
exit(0);
}
CurrPtr=head;
item=CurrPtr->info;
head=CurrPtr->link;
free(CurrPtr);
return(item);
}
int Delete_Middle(int pos)
{
NODE *CurrPtr,*PrevPtr;
int item,i;
if(head==NULL)
{
printf("\n\nDELETION NOT POSSIBLE");
exit(0);
}
CurrPtr=head;
for(i=1;i {
PrevPtr=CurrPtr;
CurrPtr=CurrPtr->link;
}
if(CurrPtr==NULL)
{
printf("\n\n Position out of range");
exit(0);
}
item=CurrPtr->info;
PrevPtr->link=CurrPtr->link;
free(CurrPtr);
return(item);
}

void Delete_End()
{
NODE *CurrPtr,*PrevPtr;
int item;

CurrPtr=head;
while(CurrPtr->link!=NULL)
{
PrevPtr=CurrPtr;
CurrPtr=CurrPtr->link;
}
PrevPtr->link=NULL;
free(CurrPtr);

}

void main()
{
int item,ch,pos;
NODE *CurrPtr,*PrevPtr,*loc;
clrscr();
head=(NODE*)malloc(sizeof(NODE));
create_link_list(head);
while(1)
{
printf("\n 1,DISPALY");
printf("\n 2. DELET FROM BEGIINING OF THE LINKED LIST \n");
printf("\n 3. DELETE MIDDLE/AT GIVEN POSITION OF THE LINKED LIST \n");
printf("\n 4. DELETE AT THE END OF THE LINKED LIST \n");
printf("\n 5. EXIT FORM MENU");
printf("\n\nENTER CHOICE : ");
scanf("%d",&ch);
switch(ch)
{
case 1: if(head==NULL)
printf("\n\nUNDERFLOW !!!!");
else
{
printf("\n \nLINKED LIST ELEMENTS ARE :");
display(head);
}
break;
case 2: item=Delete_Beg();
printf("\n\n%d DELETED FROM THE LINKED LIST: ");
break;
case 3: printf("\n\nENTER POSITION TO BE INSERT : ");
scanf("%d",&pos);
item=Delete_Middle(pos);
printf("%d IS DELTED ITEM AT END :",item);
break;
case 4: Delete_End();
printf("IS DELTED ITEM AT END :");


break;
case 5: exit(0);
break;
default : printf("\n\nINVALID CHOICE !!!!!!!!");
break;
}
}
getch();
}

//PART-B PRG 1. INSERT NODE TO SINGLY LINKED LIST AT DIFFERENT POSITION
#include
#include
#include
#include
struct node
{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *head;
/*Fucntion to create a linked lsit*/
NODE *GetNode()
{
NODE *NewNode;
NewNode=(NODE*)(malloc(sizeof(NODE)));
if(NewNode==NULL)
{
printf("\n\nEMPTY LIST");
exit(1);
}
return NewNode;
}
void create_link_list(NODE *CurrPtr)
{
NODE *NewNode;
int ans;
while(1)
{
printf("\n\nEnter info :");
scanf("%d",&CurrPtr->info);
printf("\n\nDo u wish to enter one more node press 1 :");
scanf("%d",&ans);
if(ans==1)
{
NewNode=(NODE*)(malloc(sizeof(NODE)));
CurrPtr->link=NewNode;
CurrPtr=NewNode;
}
else
{
CurrPtr->link=NULL;
break;
}
}
}
void display(NODE *CurrPtr)
{
CurrPtr=head;
while(CurrPtr!=NULL)
{
printf("\n\n%d : %d",CurrPtr->info,&CurrPtr->info);
CurrPtr=CurrPtr->link;
}
}
NODE *Insert_Beg(NODE *HeadPtr,int item)
{
NODE *NewNode;
NewNode=GetNode();
NewNode->info=item;
NewNode->link=HeadPtr;
return NewNode;
}
void Insert_Middle(int item,int pos)
{
NODE *NewNode,*CurrPtr;
int i;
NewNode=(NODE*)malloc(sizeof(NODE));
NewNode->info=item;
CurrPtr=head;
for(i=0;ilink;i++)
CurrPtr=CurrPtr->link;
if(CurrPtr==NULL)
{
printf("\n\nPOSITION OUT OF RANGE");
exit(0);
}
NewNode->link=CurrPtr->link;
CurrPtr->link=NewNode;
}
void Insert_End(NODE *CurrPtr,int item)
{
NODE *NewNode;
NewNode=GetNode();
NewNode->info=item;
NewNode->link=NULL;
while(CurrPtr->link!=NULL)
{
CurrPtr=CurrPtr->link;
}
CurrPtr->link=NewNode;
NewNode->link=NULL;

}
void main()
{
int item,ch,pos;
clrscr();
head=(NODE*)malloc(sizeof(NODE));
while(1)
{
printf("\n 1. CREATE OR INSERT NODE \n");
printf("\n 2. DISPALY NODE\n ");
printf("\n 3. INSERT BEGINING OF THE LINKED LIST \n");
printf("\n 4. INSERT MIDDLE/AT GIVEN POSITION OF THE LINKED LIST \n");
printf("\n 5. INSERT AT THE END OF THE LINKED LIST \n");
printf("\n 6.EXIT FORM MENU");

printf("\n\nENTER CHOICE : ");
scanf("%d",&ch);
switch(ch)
{
case 1: create_link_list(head);
break;
case 2: printf("\n \nLINKED LIST ELEMENTS ARE :");
display(head);
break;
case 3: printf("\n\n ENTER ITEM TO BE INSERT :");
scanf("%d",&item);
head=Insert_Beg(head,item);
printf("\n\nLINKED LIST ELEMENTS ARE : ");
break;
case 4: printf("\n\nENTER ITEM TO BE INSERT : ");
scanf("%d",&item);
printf("\n\nENTER POSITION TO BE INSERT : ");
scanf("%d",&pos);
Insert_Middle(item,pos);
break;
case 5: printf("ENTER ITEM TO BE INSERT AT END :");
scanf("%d",&item);
Insert_End(head,item);
break;
case 6: exit(0);
break;
default : printf("\n\nINVALID CHOICE !!!!!!!!");
break;
}
}
getch();
}

ಪ್ರೊಗ್ರಾಮ್ ಆನ್ ಸಿನ್ಗ್ಲ್ಯ್ ಲಿನ್ಕೆದ್ ಲಿಸ್ಟ್ (ಕ್ರೆತೆ ,ದಿಸ್ಪ್ಳಿ ಅಂಡ್ ಸರ್ಚ್)

#include
#include
#include
#include
struct node
{
int info;
struct node *link;
};
typedef struct node NODE;
NODE *head;
/*Fucntion to create a linked lsit*/
void create_link_list(NODE *CurrPtr)
{
NODE *NewNode;
int ans;
while(1)
{
printf("\nEnter info :");
scanf("%d",&CurrPtr->info);
printf("\nDo u wish to enter one more node press 1 :");
scanf("%d",&ans);
if(ans==1)
{
NewNode=(NODE*)(malloc(sizeof(NODE)));
CurrPtr->link=NewNode;
CurrPtr=NewNode;
}
else
{
CurrPtr->link=NULL;
break;
}
}
}
void display(NODE *CurrPtr)
{
CurrPtr=head;
while(CurrPtr!=NULL)
{
printf("\n%d",CurrPtr->info);
CurrPtr=CurrPtr->link;
}
}
NODE *linsearch(NODE *CurrPtr,int item)
{
while(CurrPtr!=NULL)
{
if(item==CurrPtr->info)
return(CurrPtr);
CurrPtr=CurrPtr->link;
}
return NULL;
}
void main()
{
int item;
clrscr();
head=(NODE*)malloc(sizeof(NODE));

create_link_list(head);
printf("\n LINKED LIST ELEMENTS ARE :");
display(head);
printf("\n Enter an item to be search");
scanf("%d",&item);
if(linsearch(head,item)==NULL)
printf("\n %d does not exist");
else
printf("\n %d is exist");
}

ಬ್ಲುಪ್ರಿಂತ್ ಆಫ್ ದಸ್

STACK PROGRAM USING STATIC ARRAY

/* Program of stack using array*/
#include
#include

#define MAX 5

int top = -1;
int stack_arr[MAX];
int item;
void push()
{
int pushed_item;
if(top == (MAX-1))
{
printf("\n\t--------------------\n");
printf("\tStack Overflow\n");
printf("\n\t--------------------\n");
}
else
{
printf("\n\t----------------------\n");
printf("\tEnter the item to be pushed in stack : ");
scanf("%d",&pushed_item);
top=top+1;
stack_arr[top] = pushed_item;
}
}/*End of push()*/

void pop()
{
if(top == -1)
{
printf("\n--------------------\n");
printf("\tStack Underflow\n");
printf("\n\t--------------------\n");
}
else
{
item=stack_arr[top];
printf("\n\t--------------------\n");
printf("\tPopped element is : %d\n",item);
printf("\n\t--------------------\n");
top=top-1;
}
}/*End of pop()*/

void display()
{
int i;
if(top == -1)
{
printf("\n\t--------------------\n");
printf("\tStack is empty\n");
printf("\n\t--------------------\n");
}
else
{
printf("\n\t--------------------\n");
printf("\n\tStack elements : ");
printf("\n\t--------------------\n");
for(i = top; i >=0; i--)
printf("\t%d\n", stack_arr[i] );
printf("\n\t--------------------\n");
}
}/*End of display()*/

main()
{
int choice;
clrscr();
while(1)
{
printf("\n\t--------------------\n");
printf("\t STACK OPERATIONS \n");
printf("\n\t--------------------\n");
printf("\t1.Push\n");
printf("\t2.Pop\n");
printf("\t3.Display\n");
printf("\t4.Quit\n");
printf("\n\t--------------------\n");
printf("\tEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("\n\tWrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

FIND BELOW LINKS FOR ANIMTED SORTED TECHNIQUES

INSERTIONSORT:

http://www.cs.ust.hk/faculty/tcpong/cs102/summer96/aids/insert.html

MERGSORT:

http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/mergeSort/mergeSort.html

QUICK SORT:

http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/quickSort/quickSort.html


ANIMATION FOR ALL SORTING TECHNIQUE

http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html