This Test will cover basic concepts of data Structure and related algorithm.

Q. Consider a quick sort algorithm where n/6th element is selected as pivot element which can be done in O(n) time then what will be the worst case recurrence equation to sort the elements?

Q. Which of the following statements are false :

**(I)** Binary search can be applied to linked list.

**(II)** Worst case time complexity of bubble sort is O(n).

**(III)** Merge sort is in-place algorithm.

**(IV)** Heap sort is stable algorithm.

Q. What is the maximum profit which can be gained from the below jobs such that no two jobs can be done simultaneously?

Job | J1 | J2 | J3 | J4 | J5 | J6 |

Deadline | 5 | 3 | 3 | 2 | 4 | 2 |

Profit | 199 | 179 | 189 | 299 | 119 | 99 |

Q. What is the maximum number of spanning trees possible for the below non-weighted graph?

Q. What is the minimum weight possible for minimum spanning tree of below graph?

Q. Which of the following statements are true:

**(I)** Prim's and kruskal's algorithm for minimal spanning tree may give different trees for some graph.

**(II)** Any edge with minimum weight will always be present in minimal spanning trees with unique edge weight.

**(III)** There can be more than one minimal spanning tress for a given weighted connected graph.

Q. Which of the following is not a stable sorting algorithm pair in its typical implementation?

Q. What is the time complexity of optimal merge partition algorithm?

Q. What is the time complexity of the following program:

```
for (i=1; 2<=n; i++)
printf("Study tonight");
```

Q. What is the time complexity of the following recurrence relation:

T(n) = 16 T(n/4) + 2

T(n) = 16 T(n/4) + 2

Q. What is the total time required to merge 2 unsorted lists (of size n) using two way merging algorithm ?

Q. What is the total time required to apply quick sort algorithm for the elements present in the following array?

2 | 2 | 2 | 2 | 2 | 2 | 2 |

Q. What is the time complexity to insert an element into sorted array using best possible algorithm?

Q. What is the recurrence relation for the searching an element into sorted list using best possible algorithm?

Q. Which of the following Is representing 3-ary max heap correctly.