Data Structures and ALgorithms

Download the questionnaire and submit a completed PDFvia canvas.

You may NOT handwrite the assignment.

Assignment has to be typed , diagrams must be digital (use https://app.diagrams.net/inks to an external site. to make your diagrams, if you are not familiar with Visio or Omnigraffle)

CS210 Data Structures and ALgorithms
Fall 2023
Assignment 2
Points : 40
BINARY SEARCH TREES (10 Points)
Assume this tree is a Binary Search Tree even though you cannot see what
the keys and values are at the nodes (the letters we write below are just
“names” for the nodes for the purpose of answering the questions).
a. The value of H is greater than the value of I (True/False)
b. This Binary Search Tree is complete (True/False)
c. What is the height of the tree?
d. What is the maximum number of nodes that could be added to the tree
without increasing its height?
e. Which of the nodes have a value less than C ?
HEAPS (10 Points)
Suppose there is a Binary Min-Heap with exactly 4 nodes, containing
items with priorities 3, 9, 11, and 15.
a. Show every possible binary min-heap that could match this description.
For each,
draw the appropriate tree and the array representation. (You can show
just the
priorities, not the corresponding items.)
b. For one of your answers to part (a), show what happens with 4
deleteMin operations. Clearly indicate which heap you are starting with
and show the heap after each deleteMin. You can just draw the tree (not
the array) after each step.
HASHING (10 Points)
The properties of the hashtable for this question are as follows:
Size = 12
Collison Resolution Method: Open Addressing
Hash functions:
H(k) = 3 – (k mod 12)
The following keys have to be inserted into the Hash Table in sequence:
33, 10, 9, 13, 12, 45, 26, 17
Fill the values in the Hash Table below, also showcase the working of how
you find the index for each value inserted.
Do you think the above Hash Function is effective? What could make it
better? What in your opinion is a “good” hash function?
AVL TREES (10 Points)
Show the AVL tree that results from inserting the values 21, 32, 64, 75,
and 15 into an initially empty AVL tree. Show the tree after each insertion.