Question

CAN YOU PLEASE ANSWER ALL THESE QUSTIONS

1.In Merge sort, how many additional recursive partitioning levels are required for a list of 64 elements compared to a list of 8 elements?

	a.	3
	b.	9
	c.	8
	d.	6

2. Which function best represents the number of operations in the worst-case for the following code fragment?

for (i = 0; i < N; ++i) {

   if (numbers[i] % 2 == 1)

      factor = 2.5

}

	a.	f(N) = 6N2
	b.	f(N) = 5N + 2
	c.	f(N) = 2N
	d.	f(N) = 8N2 + 4

3. The list 76, 56, 93, 24, 45, 88, 13, 7, 37 is sorted using bucket sort with 4 buckets. Which bucket will contain 45?

	a.	1
	b.	0
	c.	3
	d.	2

4. When sorting with bubble sort, how many swaps are needed for 98 to reach its sorted position in the list 98, 12, 34, 78, 35, 78, 45?

	a.	4
	b.	6
	c.	5
	d.	7

Answer 1

Solution

1)the partition levels can be calculated by the following formula

So for 8 elements

Partition levels =3

For 64 elements

Partition levels =6

So we need 3 extra Recursive partition levels

2)the worst case is f(N) =8N2+4

3)the element 45 will be in second bucket (since the distribution of elements will be as M/n, where M is total number of elements and n is total number of buckets)

4) we need 6 swaps to put 97 in its sorted position