### Data Structures and Applications – 17CS33 Question Bank 3

### Module 4 & 5 Trees, Graphs, Hashing & Files and Their Organization

1. Define the following: i) Binary tree (BT) ii) Complete BT iii) Almost Complete BT iv) Binary Search Tree v) Depth of a tree vi) Sibling

2. In brief, describe any five applications of a tree.

3. What are the different ways of representing a tree? Explain with example.

4. What are the different ways of representing a Binary tree? Explain with example.

5. Write a function to sort the elements in a BST.

6. Explain the different methods in which a binary tree can be represented? Give the advantages and disadvantages of each?

7. Write C functions for the following tree traversals: i) In order ii) Preorder iii) Postorder

8. Construct a binary tree from the given preorder and inorder sequence:

Preorder: A B D G C E H I F

In order: D G B A H E I C F

9. Construct an Expression tree for the expression A / B + C * D + E. Give an algorithm for TTT and apply the same to the above expression.

10. Prove that max no of nodes in a BT of depth K is 2 k – 1.

11. Max no of nodes on level i of a BT is 2 i-1, given that i>=1 (or)2i given that i>=0

12. Prove that no of leaf nodes = no of nodes of degree-2 (or) for any nonempty Binary Tree T, if N0 is the no of leaf nodes and N2 no of nodes of degree 2 then N0 = N2 +1.

13. What is Threaded Binary Tree? Explain its advantage over Binary Tree. Explain threaded binary tree construction with a suitable example.

14. Construct BST for the following: 22, 28, 20, 25, 22, 15, 18, 10, 14.

15. Write recursive functions for the following operations on BST:

Insert_key() ii)Delete_key() iii) Search_key()

16. Write C functions to perform the following operations on BST

Count the number of nodes.

Find the largest and smallest element.

Count and display the leaf nodes.

Count and display the non-leaf nodes.

17. What is the level order traversal of a tree? Write a C function for the level order traversal of the above graph.

18. Construct a binary tree for the following data: 23, 67, 100, 2, 11, and 56, 90, 34, 99. Perform all traversals of the constructed binary tree.

19. Write an algorithm for the following and trace for the following example 30, 10, 20, 50, 18, 40, 80

a) insertion sort b) Radix sort c) Address calculation sort d) Bubble Sort

21. What is hashing? What are the different types of hash functions? Explain with an example.

22. What is a collision? Explain different collision resolution techniques.

23. What are the pros and cons of linear probing, quadratic probing, and double hashing?

24. What are the methods used for traversing the graph? Explain each with an example.

25. What is graph traversal? What are the graph traversal algorithms? Explain with example.

26. Explain briefly different types of elementary graph operations with examples.

27. Explain Static hashing and dynamic hashing.

28. Write short notes on a) Directory hashing b) Directory less hashing.

29. Explain basic operations that can be performed on a file.

30. Explain the indexed file organization. What are its advantages?

31. Differentiate sequential and relative file organizations. Explain with examples.

32. Write short notes and explain the features, advantages and disadvantages of each of the following: Sequential Organization ii) Relative File Organization iii) Indexed Sequential File Organization.

33. What is indexing? Explain Ordered indices, Dense & Sparse indices, Cylinder Surface Indexing, Multi-level indices, Inverted indices, B-Trees indices & Hashed indices.

34. What are the biconnected components? How can a traversal algorithm be used to find biconnected components of a graph?

35. What is Spanning tree of a graph? Explain with an example how a spanning tree is constructed using DFS traversal.

36. What are the different file attributes? Explain.

37. Explain the different type of indices used in the indexed file organization.

38. Explain the data hierarchy in a file organization.

39. What is hashing? Explain the need for hashing. How does it improve the access time of data?

40. What are the key components of hashing? Explain with an example.

41. What are the requirements that a good hashing function should satisfy? Explain.

42. Explain the following terminologies with respect to a graph?

The degree of a node

Weighted graph

Adjacency matrix

Connected graph

Complete graph

*For regular updates please like the facebook page*