Question

DEPTH counting starts at 1 at the root.

How many total nodes does a 7-ary tree have if its depth is 8?

Hash the given file (6,22,9,14,13,1,8) and use linear probing and the table size of 11. How many total collisions occurred? What is the loading density of the table?

Answer 1

1. A 7-ary tree is a tree in which nodes can have at most 7 children.

We assume the tree is a complete tree with all nodes have 7 children till depth 8.

so the calculation goes like this

node at depth 1 (root node) - 1 node = 7⁰

nodes at depth 2 = 7¹ = 7 nodes

nodes at depth 3 = 7² = 49 nodes

.......................................

.................

nodes at depth 8 = 7^{7 =} 823543 nodeshash

so total nodes = 7⁰ + 7¹ + 7² + ...................+ 7⁷ = 960800 nodes

2.

The file contains 7 numbers and table size is 11

elements = (6,22,9,14,13,1,8)

In linear probing hash key = data % size

key1 = 6%11 = 6

key2 = 22%11 = 0

key3 = 9%11 = 9

key4 = 14%11 = 3

key5 = 13%11 = 2

key6 = 1%11 = 1

key7 = 8%11 = 8

our hash table =

index	value
0	22
1	1
2	13
3	14
4
5
6	6
7
8	8
9	9
10

^{We can see there is 0 collisions}

^{load factor = number of keys to be inserted in the table / number of slot in the hash table}

^{here it is 7/11}