Question 1.
Which of the following sorting algorithms are stable?
(I).Bubble Sort,
(II).Selection Sort,
(III).Insertion Sort,
(IV).Shell Sort,
(V).Binary tree sort,
(VI).Merge Sort,
(VII).In-place merge sort,
(VIII).Heap Sort,
(IX).Quick Sort,
(X).Bucket Sort,
(XI).Counting Sort,
(XII).LSD Radix Sort,
(XIII).MSD Radix Sort

Question 2.
To copy a binary tree we have to copy the tree in :

Question 3.
Maximum worst case complexity of heap construction:

Question 4.
Algorithm used to sort the subarrays of a merge sort:

Question 5.

The following code reverses an N-bit quantity in parallel. How many operations does it take?
unsigned int v; // 32 bit word to reverse bit order

v = ((v& >> 1)& 0x55555555) | ((v & 0x55555555)<<1); // swap odd and even
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333)<<2); // swapconsecutivepair
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F)<<4); // swap nibbles
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF)<<8); // swap bytes
v = ( v >> 16 ) | ( v <<16); // swap 2-byte long pairs

Question 6.
Number of distinct binary trees with 7 nodes:

Question 7.
Maximum worst case complexity of cycle deletion in a directed graph:

Question 8.
Which of the following sorting methods has least worst case complexity

Question 9.
Find the ordering in running times of following programs
(i)main(){
int i,j,l;
char str[]="Hello";
l=strlen(str);
for(i=0;i<l;i++) printf("%c",str[i]);}
(ii)main(){
int i,j,l;
char str[]="Hello";
for(i=0;i<strlen(str);i++) printf("%c",str[i]);}
(iii)main(){
int i,j,l;
char str[]="Hello";
l=strlen(str);
for(i=l-1;i>0;i--) printf("%c",str[l-i-1]);}

Question 10.
In the linked representation of binary tree, complexity of post order traversal is :