IUP Computer Science
CO 310 Fall 1984
Assignment #6
(Due 12 December 1984)
1. Write a Pascal procedure which inserts a new node T as the
left child of node S in a threaded binary tree. This is the
complement of procedure INSERTRIGHT in the book.
Write down 10 names in random order (whatever order you
think of them). The names must consist of 3 to 10 uppercase
letters with no spaces. This list of names, in the order you
wrote them) will serve as the data for problems 2, 3, and 4.
Please don't try to arrange the names to achieve some effect;
just write down a list and stick with it.
2. Take the names in the order listed and insert them into a
binary search tree. Draw a picture of the completed search tree.
State what the average search length is for the finished search
tree.
3. Take the names in the order listed and insert them into a
hash table that uses linear probing to handle collisions. Each
bucket in the hash table can hold one name. The hash table
consists of 13 buckets, numbered 0 - 12. The hashing function is
based on the third letter of each name. Let X represent this
letter and B represent the bucket number; then the hashing
function is
B := ord(X) mod 13
Draw a picture of the hash table after all names have been
inserted. State what the average search length is for the
finished hash table.
4. Take the names in the order listed and insert them into a
hash table that uses chaining to handle collisions. Each bucket
in the hash table is a node that can hold one name. The hash
table consists of an array of 6 pointers, numbered 0 - 5, and
chains of buckets. The hashing function is based on the first
letter of each name. Let X represent this letter and T represent
the hash table array entry; then the hashing function is
T := ord(X) mod 6
Draw a picture of the hash table after all names have been
inserted. State what the average search length is for the
finished hash table.