Scribd
Upload
8 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 on a graph, inserting elements into a hash table with linear probing, explaining AVL trees and their rotations, applying quadratic probing for hash functions, defining tree-related terms, and converting an arithmetic expression into an expression tree. Each task requires specific algorithms and methods to be applied. The document serves as an exercise set for understanding fundamental concepts in data structures.

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 PDF, TXT or read online on Scribd
8 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 on a graph, inserting elements into a hash table with linear probing, explaining AVL trees and their rotations, applying quadratic probing for hash functions, defining tree-related terms, and converting an arithmetic expression into an expression tree. Each task requires specific algorithms and methods to be applied. The document serves as an exercise set for understanding fundamental concepts in data structures.

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 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