DSA Theory Assignment - 2

Trees and Graphs

1) Explain Threaded binary trees with suitable examples. [4 marks]
2) Draw a Binary expression tree for the following and perform preorder traversal:
   a * ( b + c ) + ( d * e ) / f + g * h [4 marks]
3) Given Inorder and Preorder traversal, find Postorder traversal.
   Inorder: Y B K C F A G X E D H Z
   Preorder:G B Y A C K F X D E Z H  [4 marks]
4) Comparison between B trees and to B+ trees [3 marks]
5) Discuss different representations of a graph. [4 marks]
6) Differentiate : DFS vs BFS [4 marks]

Sorting and Searching

1) Sort the following numbers in ascending order by applying quick sort.
   29 15 11 82 22 17 53 57 4 8  [5 marks]
2) Write an algorithm for insertion sort [4 marks]
3) Sort the following numbers in ascending order by applying radix sort.
   29 15 11 82 22 17 53 57 4 8  [5 marks]
4) Write the algorithm for binary search. [4 marks]
5) Consider a hash table of size 10. Using linear probing, insert the keys 
72, 27, 36, 24, 63, 81, 92, and 101 into the table.  [3 marks]
6) Explain insert and delete operations in AVL trees with suitable examples. [5 marks]