#### Data Structure

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,

A. I,III,V,VI,IX,XII,XIII
B. I,III,IV,VI,XII,XIII
C. III,V,VI,IX,XII,XIII
D. I,III,V,VI,X,XI,XII

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

A. pre order
B. post order
C. in order
D. any order

3
Maximum worst case complexity of heap construction:

A. O(n^2)
B. O(n)
C. O(n log n)
D. O(log n)

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

A. Selection
B. Bubble
C. Insertion
D. Quick

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



A. 5*lg(N)
B. lg(N)
C. N
D. 5*N