Data Structure : End Semester Examination ( 3rd Sem )

 Data Structure

End Semester Examination, 2021-22
B. Tech - Semester : 03
Time : 3 hrs. - Max. Marks : 100

Instructions:

1. All questions are Compulsory
2. Assume missing data suitably, if any.

Section : A ( 10 x 4 = 40 Marks )

All questions are compulsory

1. List advantage of linked list over arrays.
2. Evaluate time complexity of insertion sort.
3. List different ways of implement polynomial ADT.
4. Define in-degree and out-degree of a graph.
5. Discuss deque with examples.
6. What are the properties of Minimum Cost Spanning (MST) Tree ?
7. Discuss rotation of AVL tree.
8. What are the disadvantages of circular linked list.
9. Evaluate the best case, average case and worst case time complexity of Bubble sort.
10. Explain the properties of Sparse matrix.

Section : B ( 3 x 6 = 18 Marks )

All questions are compulsory

1. Write an algorithm to delete an element anywhere from doubly linked list.
   
   OR
   Write applications of single linked list to represent polynomial expressions.
2. Write an algorithm of insertion in queue using linked list.
   
   OR
   Explain polynomial addition using linked list.
3. Write an algorithm to push and pop an element using array.
   
   OR
   Write an algorithm to push and pop an element from linked list.

Section : C ( 3 x 10 = 30 Marks )

All questions are compulsory

1. Write a pseudo code for converting infix expression into postfix.
   
   OR
   Explain time complexity and space complexity of an algorithm with example.
2. Convert following expression X+(Y*Z)-((N*M+O)/P) into post form.
   
   OR
   Rearrange following numbers using selection sort : 10, 6, 3, 7, 17, 26, 56, 32, 72 and discuss its time complexity.
   
3. What is a Binary tree ? Construct a binary tree given the pre-order traversal and in-order traversal as follows:
   Pre-Order Traversal : G B Q A C K F P D E R H
   In-Order Traversal : Q B K C F A G P E D H R
   
   OR
   Construct AVL tree for the following : 1, 2, 3, 4, 5, 6, 7

Section : D ( 1 x 12 = 12 Marks )

All questions are compulsory

1. Explain Prim's algorithm and apply the same on the following graph.
   
   
   
   
   OR
   
2. Write an algorithm for minimum cost spanning tree using Kruskal's algorithm and apply same on the following graph.
   
   
   

*******************