TWO MARKS QUESTIONS AND ANSWERS

DATA STRUCTURES

Previous Next

61. what is insertion sort? How many passes are required for the elements to be sorted ?
one of the simplest sorting algorithms is the insertion sort. Insertion sort consist of N-1 passes . For pass P=1 through N-1 , insertion sort ensures that the elements in positions 0 through P-1 are in sorted order .It makes use of the fact that elements in position 0 through P-1 are already known to be in sorted order .

62. Write the function in C for insertion sort ?
void
insertionsort(elementtype A[ ] , int N)
{
int j, p;
elementtype tmp;
for(p=1 ; p 0 && a [ j -1 ] >tmp ;j--)
a [ j ]=a [j-1 ] ;
a [ j ] = tmp ;
}
}

63. Who invented shellsort ? define it ?
Shellsort was invented by Donald Shell . It works by comparing element that are distant . The distance between the comparisons decreases as the algorithm runs until the last phase in which adjacent elements are compared . Hence it is referred as diminishing increment sort.

64. write the function in c for shellsort?
Void
Shellsort(Elementtype A[ ],int N)
{
int i , j , increment ;
elementtype tmp ;
for(elementtype=N / 2;increment > 0;increment / = 2)
For( i= increment ; i =increment; j - =increment)
if(tmp<>

65. what is maxheap?
If we want the elements in the more typical increasing sorted order,we can change the ordering property so that the parent has a larger key than the child.it is called max heap.

66. What are the two stages for heap sort?
Stage 1 : Construction of heap
Stage 2 : Root deletion N-1 times

67. What is divide and conquer strategy ?
In divide and conquer strategy the given problem is divided into smaller Problems and solved recursively. The conquering phase consists of patching together the answers . Divide – and – conquer is a very powerful use of recursion that we will see many times.

68 . Differentiate between merge sort and quick sort ?
mergesort quicksort
1. Divide and conquer stategy Divide and conquer strategy
2. Partition by position Partition by value

69.Mention some methods for choosing the pivot element in quicksort ?
1. choosing first element
2. Generate random number
3. Median of three

70. What are the three cases that arise during the left to right scan in quicksort?
1. I and j cross each other
2. I and j do not cross each other
3. I and j points the same position

Previous Next