Scribd
Upload
12 views1 page

Data Structures: Heaps, Trees, and Graphs

The document outlines various tasks related to data structures, including creating a min heap, finding a minimum spanning tree using Kruskal’s algorithm, performing BFS and DFS, and inserting elements into a hash table with linear probing. It also covers AVL trees, including definitions and rotations, as well as the use of quadratic probing for hash functions. Additionally, it discusses tree traversal methods and provides an expression tree example for evaluation.

Uploaded by

archana
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views1 page

Data Structures: Heaps, Trees, and Graphs

The document outlines various tasks related to data structures, including creating a min heap, finding a minimum spanning tree using Kruskal’s algorithm, performing BFS and DFS, and inserting elements into a hash table with linear probing. It also covers AVL trees, including definitions and rotations, as well as the use of quadratic probing for hash functions. Additionally, it discusses tree traversal methods and provides an expression tree example for evaluation.

Uploaded by

archana
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Module Bank

Part-A

1. Create a min heap with the following elements: 61, 86, 100, 85, 42, 83, 101, 104. Update the
key element 86 to 100 and apply the proper heapify process wherever required.
2. Consider the following graph and find the minimum spanning tree using Kruskal’s algorithm.

3. Perform BFS and DFS in the following graph. Consider A as starting vertex.

4. Following elements are inserted into an empty hash table with hash function f(x) = x%13 and
linear probing 112,44,52,45,37,278,89,28,61,248.
i) Draw the hash table for each insertion?
ii) What is the load factor after last insertion?
What is the maximum no of buckets examined in an unsuccessful search?
5. What is AVL tree? Using an example, explain all the rotations in AVL tree. Construct the AVL
tree for the given data: 23,4,15,22,33,50,30,3,6.
6. Let us consider a simple hash function as "key % m" where m=10 and sequence of keys as 61,
86, 105, 85, 42, 83, 101. Apply quadratic probing method to place these elements in a hash
table of size 10.
7. (a)Define the following terms of a tree:
Root node, Path, degree, Similar Binary trees, Copies.
(b)What is an Expression tree? Convert the following arithmetic expression into Expression
tree and evaluate the final value of the expression. ((a + b) - (c * d)) % ((f ^ g) / (h - i))
8. What is meant by traversing a tree? Write an algorithm for Pre order, In order and Post order
traversals. Write the Pre order traversal for the following tree?

You might also like