Data Structures and Algorithms 2019

Group B

Attempt any SIX questions.[6x5 = 30]

2. What is Data Structure? Show the status of stack converting following infix expression to prost fix P + Q – (R*S/T+U)-V*W [1+4]

3. Write binary search. Consider a hash table of size 10; insert the keys 62, 37, 36, 44, 67, 91 and 107 using linear probing. [2+3]

4. What are deterministic and non-deterministic algorithms? Explain greedy algorithm. [3+2]

5. Draw a BST from the string DATASTRUCTURE and traverse the tree in post order and preorder. [3+2]

6. Define circular queue? How does circular queue overcome the limitation of linear queue? Explain. [2+3]

7. What is singly linked list? Write an algorithm to add a node at the beginning and end of singly linked list. [1+4]

8. Define AVL tree. Construct AVL tree from given data set: 4, 6, 12, 9, 5, 2, 13, 8, 3, 7, 11. [2+3]

Group C

Attempt any TWO questions. [2x10 = 20]

9. What is stack? List the applications of stack. Write an algorithm or procedure to perform PUSH and POP operation in stack. [1+2+7]

10. What is heap? Explain quick sort algorithm with Big-oh notation in best case, average case and worst case and trace it to sort the data: 8, 10, 5, 12, 14, 5, 7, 13. [2+2+6]

11. Define graph and tree data structure. Explain breadth first traversal and depth first traversal with example.