Data Structure(Engineering > Computer Science And Engineering ) Questions and Answers
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
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
Explanation:-
Answer: Option D. -> I,III,V,VI,X,XI,XII
Question 5.
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
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
Explanation:-
Answer: Option A. -> 5*lg(N)
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]);}
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]);}